数据结构经典案例

1.停车场问题

停车场管理员的任务就是帮助车主把车停放在停车场中，或者是帮助车主将 车开出乘车场。然后停车场中能够停放的车辆数目很多，这就使得让莫辆车开出停车场变得复杂。比如：要开走一辆车，则管理员需要把他前面的车全部暂时清除，然后等这辆车开出后再将这些车重新放入停车场。当然了，这个时候腾出了一个空位置，此位置由后面的车占据。

任务：编程模拟这样的情况，这里假设停车场最多可停放5辆车。data.txt记录了某一时间段内，该停车场车辆的到来与离开记录，刚开始，停车场是空的。其中大写字母A--P是车辆的代号，arrives--到来，departs---离开。

程序需要从data.txt中读取这些信息，并且用这些数据来模拟停车场的车辆调度情况。

data.txt内容如下：

A arrives A departs B arrives C arrives D arrives C departs E arrives F arrives G arrives B departs H arrives D departs E departs I arrives I departs J arrives F departs K arrives L arrives M arrives H departs N arrives J departs K departs O arrives P arrives P departs

O departs L departs 实现代码如下：

模拟停车场问题.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 license;//车的通行证

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. car::~car() 36. {} 37.

38. #include 39. #include 40. int main() 41. {

42. string in_filename=\数据文件了，包含了停车场内的车辆进出记录

43. ifstream inf(in_filename.c_str());//void open(const char* filename,int

mode,int access);另外，fstream还有和open()一样的构造函数，对于上例，在定义的时侯就可以打开文件了： 44. //fstream file1(\ 45.

46. if(!inf) 47. {

48. cerr<<\文件打开失败!\ 49. return EXIT_FAILURE; 50. }

51. stack parking_lot,tempstack;//定义两个栈，一个模拟停车场，另外一个用来暂时存放从停车场哪里暂时清除的车，当然最后还是得返回给停车场 52. car* pcar;

53. string license_plate,action;//分别记录从数据文件中读取的通行证跟行为（到达？离开？） 54. //按行读取数据文件 55. while(!inf.eof()) 56. {

57. inf>>license_plate>>action; 58. if(action==\到达 59. {

60. if(parking_lot.size()<5)//栈不满的话，继续入栈 61. {

62. pcar=new car(license_plate,0);//这个就不用多罗嗦 63. parking_lot.push(pcar); 64. 65. } 66. else 67.

68. cout<<\抱歉\停车场已满!\ 69. 70. }

71. else if(action==\如果是出发 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. //delete parking_lot.top();此处还不能销毁结点，只是一个短暂的转移罢了 80. }

81. if(parking_lot.top()->getlicense()==license_plate)//如果要出发的这辆车的license_plate刚好就处在栈顶位置，则直接销毁相关结点，不需要增加移动次数 82. {

83. cout<getlicense()<<\被移动了

\次在这里!\输出被移动的次数 84.

85. delete parking_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<getlicense()<<\被移动了

\次在这里\ 106. delete parking_lot.top();//销毁栈顶 107. parking_lot.pop();//出栈 108. }

109. inf.close(); 110. return 0; 111. 112. }

2.用队列解决数据结构经典问题：杨辉三角形问题。

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

就是下面的元素是这个元素“肩膀上”的两个元素之和。

思路：首先初始化一个队列，元素为1，然后根据这个队列迭代生成任意行的二项式系数。

判断用户输入的行数，然后决定循环次数。这些循环中，程序根据杨辉三角的实际构造函数模拟构造过程。每次形成一个新的二项式系数序列，并将这个序列 保持在一个新的队列中。本次循环结束后，这个心构造的序列将作为下次循环来构造另一个二项式序列的参照序列。

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. class LinkQueue 14. {

15. LinkQueueNode* front;