数据结构经典案例

1、.1.停车场问题停车场管理员的任务就是帮助车主把车停放在停车场中，或者是帮助车主将 车开出乘车场。然后停车场中能够停放的车辆数目很多，这就使得让莫辆车开出停车场变得复杂。比如：要开走一辆车，则管理员需要把他前面的车全部暂时清除，然后等这辆车开出后再将这些车重新放入停车场。当然了，这个时候腾出了一个空位置，此位置由后面的车占据。任务：编程模拟这样的情况，这里假设停车场最多可停放5辆车。data.txt记录了某一时间段内，该停车场车辆的到来与离开记录，刚开始，停车场是空的。其中大写字母A-P是车辆的代号，arrives-到来，departs-离开。程序需要从data.txt中读取这些信息，并且用这

2、些数据来模拟停车场的车辆调度情况。 data.txt内容如下：A arrivesA departsB arrivesC arrivesD arrivesC departsE arrivesF arrivesG arrivesB departsH arrivesD departsE departsI arrivesI departsJ arrivesF departsK arrivesL arrivesM arrivesH departsN arrivesJ departsK departsO arrivesP arrivesP departsO departsL departs实现代码如下：模

3、拟停车场问题.cpp（没有再继续分.h文件，混为一体了，主要.h文件过于简单）cpp view plaincopyprint?1. #ifndef CAR_H 2. #define CAR_H 3. #include 4. #include 5. using namespace std; 6. class car 7. 8. public: 9. car(string,int); 10. string getlicense(); 11. int getmovedtimes(); 12. car(); 13. void move(); 14. private: 15. string licens

4、e;/车的通行证 16. int movedtimes;/被移动的次数 17. ; 18. #endif 19. car:car(string license,int movedtimes):license(license),movedtimes(0) 20. 21. 22.23. string car:getlicense() 24. 25. return license; 26. 27. int car:getmovedtimes() 28. 29. return movedtimes; 30. 31. void car:move() 32. 33. movedtimes+; 34. 35

5、. car:car() 36. 37.38. #include 39. #include 40. int main() 41. 42. string in_data.txt;/数据文件了，包含了停车场内的车辆进出记录 43. ifstream inf(in_();/void open(const char* mode,int access);另外，fstream还有和open()一样的构造函数，对于上例，在定义的时侯就可以打开文件了： 44. /fstream file1(c:/config.sys); 45.46. if(!inf) 47. 48. cerr文件打开失败!in_endl; 4

6、9. return EXIT_FAILURE; 50. 51. stack parking_lot,tempstack;/定义两个栈，一个模拟停车场，另外一个用来暂时存放从停车场哪里暂时清除的车，当然最后还是得返回给停车场 52. car* pcar; 53. string license_plate,action;/分别记录从数据文件中读取的通行证跟行为（到达？离开？） 54. /按行读取数据文件 55. while(!inf.eof() 56. 57. inflicense_plateaction; 58. if(action=arrives)/到达 59. 60. if(parking_

7、lot.size()5)/栈不满的话，继续入栈 61. 62. pcar=new car(license_plate,0);/这个就不用多罗嗦 63. parking_lot.push(pcar); 64.65. 66. else 67.68. cout抱歉license_plate,停车场已满!getlicense()!=license_plate)/while循环 75. 76. tempstack.push(parking_lot.top(); 77. parking_lot.top()-move();/增加移动次数 78. parking_lot.pop(); 79. /delete

8、parking_lot.top();此处还不能销毁结点，只是一个短暂的转移罢了 80. 81. if(parking_lot.top()-getlicense()=license_plate)/如果要出发的这辆车的license_plate刚好就处在栈顶位置，则直接销毁相关结点，不需要增加移动次数 82. 83. coutgetlicense()被移动了getmovedtimes() 次在这里!endl;/输出被移动的次数 84.85. delete parking_lot.top(); 86. parking_lot.pop(); 87. 88. else 89. cout神马情况（异常）!

9、endl; 90. /接下来还得进行还原，既然有移动那就得还原 91. while(!tempstack.empty() 92. 93. parking_lot.push(tempstack.top(); 94. tempstack.pop(); 95. 96.97.98. 99.100.101. 102. cout还在车库里面的!endl;/最后把还在车库里面的车的license输出，同时关注移动次数 103. while(!parking_lot.empty()/用循环依次遍历栈中的元素，也就是对应的车辆了 104. 105. coutgetlicense() 被移动了getmovedti

10、mes()次在这里endl; 106. delete parking_lot.top();/销毁栈顶 107. parking_lot.pop();/出栈 108. 109. inf.close(); 110. return 0; 111.112. 2.用队列解决数据结构经典问题：杨辉三角形问题。11 11 2 11 3 3 11 4 6 4 1就是下面的元素是这个元素“肩膀上”的两个元素之和。思路：首先初始化一个队列，元素为1，然后根据这个队列迭代生成任意行的二项式系数。判断用户输入的行数，然后决定循环次数。这些循环中，程序根据杨辉三角的实际构造函数模拟构造过程。每次形成一个新的二项式系数序

11、列，并将这个序列 保持在一个新的队列中。本次循环结束后，这个心构造的序列将作为下次循环来构造另一个二项式序列的参照序列。cpp view plaincopyprint?1. #include 2. #include 3. #include 4. template 5. class LinkQueueNode/结点类定义 6. 7. public: 8. T data; 9. LinkQueueNode* link; 10. LinkQueueNode(const T& value):data(value),link(NULL)/这里传递类型const 11. ; 12. template 13

12、. class LinkQueue 14. 15. LinkQueueNode* front; 16. LinkQueueNode* back; 17. public: 18. LinkQueue():front(NULL),back(NULL) 19. void EnQueue(const T& element);/这里也传递const，当然也可以不修改这里，自己再去重载一个参数为const类型的入队函数跟构造函数，道理一样 20. T DelQueue(); 21. T& GetFront(); 22. void MakeEmpty(); 23. bool IsEmpty(); 24. ;

13、 25. /实现如下 26. template 27. void LinkQueue:EnQueue(const T& value) 28. 29. LinkQueueNode* add=new LinkQueueNode(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. T LinkQu

14、eue:DelQueue() 43. 44. /首先得判断是否为空队列 45. assert(!IsEmpty(); 46. LinkQueueNode* old=front; 47. T data=old-data;/保留原对头数据 48. front=front-link;/移动对头指针 49. if(back=old) 50. back=NULL; 51. delete old; 52. return data; 53.54. 55. template 56. T& LinkQueue:GetFront() 57. 58. assert(!IsEmpty();/断言，这东西挺好使滴 59

15、. return front-data; 60. 61. template 62. void LinkQueue:MakeEmpty() 63. 64. while(!IsEmpty() 65. 66. this-DelQueue(); 67. 68.69. 70. template 71. bool LinkQueue:IsEmpty() 72. 73. return front=NULL; 74. 75. #include 76. using namespace std; 77.78. template/用模板实现方式 79. void evaluate(LinkQueue& ori,Li

16、nkQueue& target) 80. 81. ori.MakeEmpty(); 82. while(!target.IsEmpty() 83. 84. ori.EnQueue(target.DelQueue(); 85. 86. 87. int main() 88. 89. cout2):; 90. int num; 91. cinnum; 92. LinkQueue ori; 93. ori.EnQueue(1); 94. ori.EnQueue(1); 95. LinkQueue next; 96. for(int i=0;inum-2;i+) 97. 98. next.EnQueue

17、(1); 99. while(!ori.IsEmpty() 100. 101. int j=ori.DelQueue(); 102. if(!ori.IsEmpty() 103. 104. next.EnQueue(j+ori.GetFront(); 105. 106. else 107. next.EnQueue(1); 108.109.110. 111. evaluate(ori,next); 112. 113. cout杨辉三角形第num行内容如下:endl; 114. while(!ori.IsEmpty() 115. 116. coutori.DelQueue() ; 117. 11

18、8. cout结束!endl; 119. return EXIT_SUCCESS; 120. 汉诺塔算法 Hanoi Tower问题其实是印度的一个古老的传说。开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移v动圆片的次数)184467445，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。算法介绍：其实算法非常简单，当盘子的个数为n时，

19、移动的次数应等于2n 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，

20、当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。 汉诺塔算法的递归实现C+源代码1. #includeusing namespace std;2. void tower(char,char,char,int);3. int main()int numDisks

21、;coutnumDisks;tower(A,C,B,numDisks);return 0;4. void tower(char fromTower,char toTower,char auxTower,int n)if(n=1)coutMove disk 1 from tower fromTower to tower toTowerendl;elsetower(fromTower,auxTower,toTower,n-1);coutMove disk n from tower fromTower to tower toTowerendl;tower(auxTower,toTower,fromT

22、ower,n-1);5. 6. 汉诺塔算法的非递归实现C+源代码7. #include 8. using namespace std; 9.10. /圆盘的个数最多为64 11. const int MAX = 64; 12.13. /用来表示每根柱子的信息14. struct st15. int sMAX; /柱子上的圆盘存储情况16. int top; /栈顶，用来最上面的圆盘17. char name; /柱子的名字，可以是A，B，C中的一个18. int Top()/取栈顶元素19. 20. return stop;21. 22. int Pop()/出栈23. 24. return

23、stop-;25. 26. void Push(int x)/入栈27. 28. s+top = x;29. 30. ; 31.32. long Pow(int x, int y); /计算xy33. void Creat(st ta, int n); /给结构数组设置初值34. void Hannuota(st ta, long max); /移动汉诺塔的主要函数 35.36. int main(void)37. 38. int n;39. cin n; /输入圆盘的个数40. st ta3; /三根柱子的信息用结构数组存储41. Creat(ta, n); /给结构数组设置初值 42.43

24、. long max = Pow(2, n) - 1;/动的次数应等于2n - 144. Hannuota(ta, max);/移动汉诺塔的主要函数 45.46. system(pause);47. return 0;48. 49.50. void Creat(st ta, int n)51. 52. = A;53. ta0.top = n-1;54. /把所有的圆盘按从大到小的顺序放在柱子A上55. for (int i=0; in; i+)56. ta0.si = n - i;57. /柱子B，C上开始没有没有圆盘58. ta1.top = ta2.top = 0;59. for (int i=0; in; i+)60. ta1.si = ta2.si = 0;61. /若n为偶数，按顺时针方向依次摆放 A B C62. if (n%2 = 0)63. 64. = B;65. = C;66. 67. else/若n为奇数，按