数据结构经典案例文档格式.docx
- 文档编号:7250239
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:18
- 大小:21.17KB
数据结构经典案例文档格式.docx
《数据结构经典案例文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构经典案例文档格式.docx(18页珍藏版)》请在冰点文库上搜索。
//车的通行证
16.intmovedtimes;
//被移动的次数
17.};
18.#endif
19.car:
:
car(stringlicense,intmovedtimes):
license(license),movedtimes(0)
20.{
21.}
22.
23.stringcar:
getlicense()
24.{
25.returnlicense;
26.}
27.intcar:
getmovedtimes()
28.{
29.returnmovedtimes;
30.}
31.voidcar:
move()
32.{
33.movedtimes++;
34.}
35.car:
~car()
36.{}
37.
38.#include<
fstream>
39.#include<
stack>
40.intmain()
41.{
42.stringin_"
data.txt"
;
//数据文件了,包含了停车场内的车辆进出记录
43.ifstreaminf(in_());
//voidopen(constchar*mode,intaccess);
另外,fstream还有和open()一样的构造函数,对于上例,在定义的时侯就可以打开文件了:
44.//fstreamfile1("
c:
//config.sys"
);
45.
46.if(!
inf)
47.{
48.cerr<
<
"
文件打开失败!
in_<
endl;
49.returnEXIT_FAILURE;
50.}
51.stack<
car*>
parking_lot,tempstack;
//定义两个栈,一个模拟停车场,另外一个用来暂时存放从停车场哪里暂时清除的车,当然最后还是得返回给停车场
52.car*pcar;
53.stringlicense_plate,action;
//分别记录从数据文件中读取的通行证跟行为(到达?
离开?
)
54.//按行读取数据文件
55.while(!
inf.eof())
56.{
57.inf>
>
license_plate>
action;
58.if(action=="
arrives"
)//到达
59.{
60.if(parking_lot.size()<
5)//栈不满的话,继续入栈
61.{
62.pcar=newcar(license_plate,0);
//这个就不用多罗嗦
63.parking_lot.push(pcar);
64.
65.}
66.else
67.
68.cout<
抱歉"
license_plate<
停车场已满!
69.
70.}
71.elseif(action=="
departs"
)//如果是出发
72.{
73.//首先得给出判断,此时栈是否为空?
而且出发的这辆车的license_plate是否位于栈顶
74.while((!
parking_lot.empty())&
&
(parking_lot.top()->
getlicense()!
=license_plate))//while循环
75.{
76.tempstack.push(parking_lot.top());
77.parking_lot.top()->
move();
//增加移动次数
78.parking_lot.pop();
79.//deleteparking_lot.top();
此处还不能销毁结点,只是一个短暂的转移罢了
80.}
81.if(parking_lot.top()->
getlicense()==license_plate)//如果要出发的这辆车的license_plate刚好就处在栈顶位置,则直接销毁相关结点,不需要增加移动次数
82.{
83.cout<
parking_lot.top()->
getlicense()<
被移动了"
getmovedtimes()<
次在这里!
//输出被移动的次数
84.
85.deleteparking_lot.top();
86.parking_lot.pop();
87.}
88.else
89.cout<
神马情况(异常)!
90.//接下来还得进行还原,既然有移动那就得还原
91.while(!
tempstack.empty())
92.{
93.parking_lot.push(tempstack.top());
94.tempstack.pop();
95.}
96.
97.
98.}
99.
100.
101.}
102.cout<
还在车库里面的!
//最后把还在车库里面的车的license输出,同时关注移动次数
103.while(!
parking_lot.empty())//用循环依次遍历栈中的元素,也就是对应的车辆了
104.{
105.cout<
被移动了"
次在这里"
106.deleteparking_lot.top();
//销毁栈顶
107.parking_lot.pop();
//出栈
108.}
109.inf.close();
110.return0;
111.
112.}
2.用队列解决数据结构经典问题:
杨辉三角形问题。
1
11
121
1331
14641
就是下面的元素是这个元素“肩膀上”的两个元素之和。
思路:
首先初始化一个队列,元素为1,然后根据这个队列迭代生成任意行的二项式系数。
判断用户输入的行数,然后决定循环次数。
这些循环中,程序根据杨辉三角的实际构造函数模拟构造过程。
每次形成一个新的二项式系数序列,并将这个序列保持在一个新的队列中。
本次循环结束后,这个心构造的序列将作为下次循环来构造另一个二项式序列的参照序列。
cpp]viewplaincopyprint?
1.#include<
stdio.h>
2.#include<
assert.h>
4.template<
classT>
5.classLinkQueueNode//结点类定义
6.{
7.public:
8.Tdata;
9.LinkQueueNode<
T>
*link;
10.LinkQueueNode(constT&
value):
data(value),link(NULL){}//这里传递类型const
11.};
12.template<
13.classLinkQueue
14.{
15.LinkQueueNode<
*front;
16.LinkQueueNode<
*back;
17.public:
18.LinkQueue():
front(NULL),back(NULL){}
19.voidEnQueue(constT&
element);
//这里也传递const,当然也可以不修改这里,自己再去重载一个参数为const类型的入队函数跟构造函数,道理一样
20.TDelQueue();
21.T&
GetFront();
22.voidMakeEmpty();
23.boolIsEmpty();
24.};
25.//实现如下
26.template<
27.voidLinkQueue<
EnQueue(constT&
value)
29.LinkQueueNode<
*add=newLinkQueueNode<
(value);
30.if(back==NULL)//添加第一个结点,让front指向这个结点
31.{
32.front=back=add;
33.}
34.else//如果队列中人家已经有结点,则需要改变back指针
35.{
36.back->
link=add;
37.back=back->
link;
38.
39.}
40.}
41.template<
42.TLinkQueue<
DelQueue()
43.{
44.//首先得判断是否为空队列
45.assert(!
IsEmpty());
46.LinkQueueNode<
*old=front;
47.Tdata=old->
data;
//保留原对头数据
48.front=front->
//移动对头指针
49.if(back==old)
50.back=NULL;
51.deleteold;
52.returndata;
53.
54.}
55.template<
56.T&
LinkQueue<
GetFront()
57.{
58.assert(!
//断言,这东西挺好使滴
59.returnfront->
60.}
61.template<
62.voidLinkQueue<
MakeEmpty()
63.{
64.while(!
IsEmpty())
65.{
66.this->
DelQueue();
67.}
68.
69.}
70.template<
71.boolLinkQueue<
IsEmpty()
73.returnfront==NULL;
74.}
75.#include<
76.usingnamespacestd;
77.
78.template<
//用模板实现方式
79.voidevaluate(LinkQueue<
ori,LinkQueue<
target)
80.{
81.ori.MakeEmpty();
82.while(!
target.IsEmpty())
83.{
84.ori.EnQueue(target.DelQueue());
85.}
86.}
87.intmain()
88.{
请输入杨辉三角形阶数i(i>
2):
90.intnum;
91.cin>
num;
92.LinkQueue<
int>
ori;
93.ori.EnQueue
(1);
94.ori.EnQueue
(1);
95.LinkQueue<
next;
96.for(inti=0;
i<
num-2;
i++)
97.{
98.next.EnQueue
(1);
99.while(!
ori.IsEmpty())
100.{
101.intj=ori.DelQueue();
102.if(!
103.{
104.next.EnQueue(j+ori.GetFront());
105.}
106.else
107.next.EnQueue
(1);
108.
109.
110.}
111.evaluate(ori,next);
113.cout<
杨辉三角形第"
num<
行内容如下:
114.while(!
115.{
116.cout<
ori.DelQueue()<
"
117.}
118.cout<
结束!
119.returnEXIT_SUCCESS;
120.}
汉诺塔算法
HanoiTower问题其实是印度的一个古老的传说。
开天辟地的神勃拉玛(和中国的盘古差不多的神吧)在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。
计算结果非常恐怖(移v动圆片的次数)184467445,众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍:
其实算法非常简单,当盘子的个数为n时,移动的次数应等于2^n–1(有兴趣的可以自己证明试试看)。
后来一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上,根据圆盘的数量确定柱子的排放顺序:
若n为偶数,按顺时针方向依次摆放ABC;
若n为奇数,按顺时针方向依次摆放ACB。
(1)按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;
若圆盘1在柱子B,则把它移动到C;
若圆盘1在柱子C,则把它移动到A。
(2)接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘。
这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
(3)反复进行
(1)
(2)操作,最后就能按规定完成汉诺塔的移动。
所以结果非常简单,就是按照移动规则向一个方向移动金片:
如3阶汉诺塔的移动:
A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程序设计中的经典递归问题,下面我们将给出递归和非递归的不同实现源代码。
●汉诺塔算法的递归实现C++源代码
usingnamespacestd;
2.voidtower(char,char,char,int);
3.intmain()
{
intnumDisks;
cout<
Howmanydisks:
cin>
numDisks;
tower('
A'
'
C'
B'
numDisks);
return0;
}
4.voidtower(charfromTower,chartoTower,charauxTower,intn)
if(n==1)
Movedisk1fromtower"
fromTower<
totower"
toTower<
else
tower(fromTower,auxTower,toTower,n-1);
Movedisk"
n<
fromtower"
tower(auxTower,toTower,fromTower,n-1);
5.
6.●汉诺塔算法的非递归实现C++源代码
7.#include<
8.usingnamespacestd;
9.
10.//圆盘的个数最多为64
11.constintMAX=64;
12.
13.//用来表示每根柱子的信息
14.structst{
15.
ints[MAX];
//柱子上的圆盘存储情况
16.
inttop;
//栈顶,用来最上面的圆盘
17.
charname;
//柱子的名字,可以是A,B,C中的一个
18.
intTop()//取栈顶元素
19.
20.
returns[top];
21.
22.
intPop()//出栈
23.
24.
returns[top--];
25.
26.
voidPush(intx)//入栈
27.
28.
s[++top]=x;
29.
30.};
31.
32.longPow(intx,inty);
//计算x^y
33.voidCreat(stta[],intn);
//给结构数组设置初值
34.voidHannuota(stta[],longmax);
//移动汉诺塔的主要函数
35.
36.intmain(void)
37.{
38.
intn;
39.
cin>
n;
//输入圆盘的个数
40.
stta[3];
//三根柱子的信息用结构数组存储
41.
Creat(ta,n);
//给结构数组设置初值
42.
43.
longmax=Pow(2,n)-1;
//动的次数应等于2^n-1
44.
Hannuota(ta,max);
//移动汉诺塔的主要函数
46.
system("
pause"
47.
48.}
49.
50.voidCreat(stta[],intn)
51.{
52.
ta[0].name='
53.
ta[0].top=n-1;
54.
//把所有的圆盘按从大到小的顺序放在柱子A上
55.
for(inti=0;
i<
n;
i++)
56.
ta[0].s[i]=n-i;
57.
//柱子B,C上开始没有没有圆盘
58.
ta[1].top=ta[2].top=0;
59.
60.
ta[1].s[i]=ta[2].s[i]=0;
61.
//若n为偶数,按顺时针方向依次摆放ABC
62.
if(n%2==0)
63.
64.
ta[1].name='
65.
ta[2].name='
66.
67.
else
//若n为奇数,按顺时针方向依次摆放ACB
68.
69.
70.
71.
72.}
73.
74.longPow(intx,inty)
75.{
76.
longsum=1;
77.
y;
78.
sum*=x;
79.
80.
returnsum;
81.}
82.
83.voidHannuota(stta[],longmax)
84.{
85.
intk=0;
//累计移动的次数
86.
inti=0;
87.
intch;
88.
while(k<
max)
89.
90.
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
91.
ch=ta[i%3].Pop();
92.
ta[(i+1)%3].Push(ch);
93.
cout<
++k<
<
94.
ch<
from"
ta[i%3].name<
95.
to"
ta[(i+1)%3].name<
endl;
96.
i++;
97.
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
98.
if(k<
99.
{
100.
//把非空柱子上的圆盘移动到空柱子上,当两根柱子都为空时,移动较小的圆盘
101.
if(ta[(i+1)%3].Top()==0||
102.
ta[(i-1)%3].Top()>
0&
103.
ta[(i+1)%3].Top()>
ta[(i-1)%3].
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 经典 案例