数据结构实验二 网络134 康阳 11.docx

实验二 栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一：回文判断（*）问题描述对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。基本要求（1）数据从键盘读入；（2）输出要判断的字符串； （3）利用栈和队列对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。回文 栈的输出与队列的输出相同；也就是每一个输出的字符都是相同的。若有一个不同，就不是回文。在一个循环中判断。有一个不同就跳出循环，不是回文。循环结束，是回文。测试数据由学生任意指定。1、 算法设计利用栈和队列对给定的字符串判断其是否是回文。是回文则栈和队列的输出结果相同。由于栈是后进先出，队列是先进先出，所以栈和队列输出的完全相同，则给定的字符串是回文。所以可以将给定的字符串先进栈，再进队，然后一个一个字符比较输出，有一个字符不相同就不是回文。2、 本程序包含模块1）主函数int main（）分别对栈和队列进行初始化；While循环分别将字符串进栈和进队；循环里有一个整形变量，整型变量作为循环的判断条件，字符变量作为数据存入栈和队列；For循环比较输出，判断是否是回文；2）栈和队列的存储结构typedef struct Stacknode /构造栈char Zdata;struct Stacknode *Znext;StackNode;typedef struct QueueNode /构造队列char Qdata;struct QueueNode *Qnext;QueueNode;typedef struct /指向队列QueueNode *front, *rear;LinkQueue;typedef struct /指向栈的指针StackNode *top;LinkStack;3）进栈和出栈函数void Push(LinkStack &s, char &x) /进栈操作int Pop(LinkStack &s, char &a) /出栈操作需判断栈是否为空4）进队和出队函数void InQueue(LinkQueue *q) /进队操作int OutQueue(LinkQueue *q, char &b) /出队操作需判断队是否为空3、 调试分析1. 在进行栈和队列的构造以进栈出栈和进队出队操作时，出栈和出队会遇到指针的指向问题。2. 再主函数中while循环往栈和队列输入数据，遇到了判断条件的决定问题。不知如何用字符当做判断条件，最终做出以整型做出修改作为判断条件，但是需要多次输入。然后在if语句中进行字符的输入和进栈进队。3. 在回文判断的核心处，初始想法是比较输出的字符，但是输出总是出现问题，最后做出的修改是定义一个计数器，比较出栈和出队函数执行结果，若为真则计数器加一。若为假则直接跳出循环，输出不是回文的结果。最后比较计数器和字符数量，若相等则是回文。4. 算法仍有欠缺，在判断条件和回文判断处应有更合理的修改4、 实验结果进入操作页进栈和进队操作，进栈数与进队数相等进栈为abcba,进队相同最后分别是栈和队的输出。aabbccbbaa由此可判断栈和队的输出相等，是回文进栈和进队操作，进栈数与进队数相等进栈为abcb,进队相同最后分别是栈和队的输出。ba，且栈和队都只输出一次，证明第一个字符就不想等，由此可判断栈和队的输出不相等，不是回文题目三：舞伴问题（*）假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。【实验提示】先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。【实验要求】 利用队列实现，存储结构采用顺序或链式均可1、算法设计构造三个队列，第一个用来储存所有人的姓名和姓名，第二个用来储存男士的姓名性别，第三个用来储存女士的姓名和性别。配舞伴的时候，用人数少的来作为判断条件进行出队，当一方出队结束，另一方剩余的人留到下一轮。将剩余人姓名输出，按顺序为下一轮的配舞伴顺序。2、 本程序包含模块1） 主函数/假设W为女性M为男性int main（）三个队列的初始化；设定总人数；所有人进入第一个队，队中储存姓名和性别；按顺序出队；判断条件W和M；若为M，进入男队，否则进入女队，进队的同时Mi为男队计数器，Wi为女队计数器；比较Mi和Wi，此处为核心算法if (Mi = WMi)cout 本轮男女分配：endl;for (int i = 1; i = Mi; +i)OutMQueue(q, a, c); cout ;OutWMQueue(p, b, c);cout endl;cout 留到下一轮的女士：;for (int i = 1; i = WMi - Mi; +i)OutWMQueue(p, b, c);cout ;elsecout 本轮男女分配：endl;for (int i = 1; i = WMi; +i)OutMQueue(q, a, c); cout ;OutWMQueue(p, b, c);cout endl;cout 留到下一轮的男士：;for (int i = 1; i = Mi - WMi; +i)OutMQueue(q, a, c);cout ;2） 进队和出队函数void InQueue(LinkQueue *q) /进队操作int OutQueue(LinkQueue *q, char &b, char &sex) /出队操作出队需判断队是否为空。男女进队出队操作同上3、 调试分析1. 初始只构造了两个队，即男队和女队，在进行输入的时候不知如何判断输入条件，所以又构造一个队列输入所有的数据，然后出队，判断出队者的性别，男士进男队，女士进女队。2. 在进行分配时，初始是以男队女队都不为空位判断条件，但是判断条件总是出错。后增加了人数的计数器，以男女人数作为判断条件进行舞伴的配对。3. 在输出滞留到下一轮的人姓名时，以队不为空为条件，出错。后用for循环，用剩余人数作为循环条件输出实验结果输入进队的总人数输入进队人的姓名和性别男女分配结果自动输出输出滞留下一轮的人三、总结此次实验应用了栈和队列实现实际操作，完成了基本操作和分配舞伴的简单操作，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了队的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。四、源程序（带注释）回文的判断#includeusing namespace std;typedef struct Stacknode /构造栈char Zdata;struct Stacknode *Znext;StackNode;typedef struct QueueNode /构造队列char Qdata;struct QueueNode *Qnext;QueueNode;typedef struct /指向队列QueueNode *front, *rear;LinkQueue;typedef struct /指向栈的指针StackNode *top;LinkStack;void Push(LinkStack &s, char &x) /进栈操作StackNode *p = new StackNode;p-Zdata = x;p-Znext = s.top;s.top = p;int Pop(LinkStack &s, char &a) /出栈操作StackNode *p;if (s.top != NULL)p = s.top;a = p-Zdata;s.top = p-Znext;delete p;return 1;elsereturn 0;void InQueue(LinkQueue *q) /进队操作char x;QueueNode *p = new QueueNode;cout endl x;getchar();p-Qdata = x;p-Qnext = NULL;if (q-front = NULL)q-front = p;elseq-rear-Qnext = p;q-rear = p;if (p)cout 进队成功front=q-rear)b = q-front-Qdata;p = q-front;free(p);return 1;p = q-front;b = p-Qdata;q-front = p-Qnext;if(q-front=p)q-rear=q-front;free(p);return 1;int main()LinkStack Stack;Stack.top = NULL;LinkQueue *q = new LinkQueue;q-front = q-rear = NULL;char x; int n = 0; char a, b; int j = 0; int z; z = 1; int mm;cout进栈操作，输入序号为0进栈停止endl;while (z) /进栈cout mm;cout endl x;Push(Stack, x);n+;else z = 0; for (int i = 1; i = n; +i) /进队InQueue(q);for(int i = 1;i=n;+i)/核心算法，回文判断Pop(Stack, a);OutQueue(q, b);cout a b;if(a = b)j+;elsebreak;if(n = j)cout是回文;elsecout不是回文;system(pause);return 0;舞伴的分配问题#includeusing namespace std;/假设W为女性M为男性typedef struct QueueNode /构造队列char data;char sex;struct QueueNode *next;QueueNode;typedef struct /指向队列QueueNode *front, *rear;LinkQueue;void InQueue(LinkQueue *q) /进队操作char x, sex;QueueNode *p = new QueueNode;cout endl 请输入进队数据;cout x;cout sex;getchar();p-data = x;p-sex = sex;p-next = NULL;if (q-front = NULL)q-front = p;elseq-rear-next = p;q-rear = p;if (p)cout 进队成功 front = q-rear)b = q-front-data;sex = q-front-sex;p = q-front;cout b;cout front;b = p-data;sex = p-sex;cout b;cout front = p-next;if (q-front = p)q-rear = q-front;free(p);return 1;typedef struct MQueueNode /构造男队列char Mdata;char sex;struct MQueueNode *Mnext;MQueueNode;typedef struct /指向男队列MQueueNode *Mfront, *Mrear;MLinkQueue;typedef struct WMQueueNode /构造女队列char WMdata;char sex;struct WMQueueNode *WMnext;WMQueueNode;typedef struct /指向女队列WMQueueNode *WMfront, *WMrear;WMLinkQueue;void InMQueue(MLinkQueue *q,char &x,char &sex) /进男队操作MQueueNode *p = new MQueueNode;p-Mdata = x;p-sex = sex;p-Mnext = NULL;if (q-Mfront = NULL)q-Mfront = p;elseq-Mrear-Mnext = p;q-Mrear = p;if (p)cout 进队成功 Mfront = q-Mrear)b = q-Mfront-Mdata;sex = q-Mfront-sex;p = q-Mfront;cout Mfront;b = p-Mdata;sex = p-sex;cout Mfront = p-Mnext;if (q-Mfront = p)q-Mrear = q-Mfront;free(p);return 1;void InWMQueue(WMLinkQueue *q,char &x, char &sex) /进女队操作WMQueueNode *p = new WMQueueNode;p-WMdata = x;p-sex = sex;p-WMnext = NULL;if (q-WMfront = NULL)q-WMfront = p;elseq-WMrear-WMnext = p;q-WMrear = p;if (p) cout 进队成功 WMfront = q-WMrear)b = q-WMfront-WMdata;sex = q-WMfront-sex;p = q-WMfront;cout WMfront;b = p-WMdata;sex = p-sex;cout WMfront = p-WMnext;if (q-WMfront = p)q-WMrear = q-WMfront;free(p);return 1;void main()MLinkQueue *q = new MLinkQueue;q-Mfront = q-Mrear = NULL;WMLinkQueue *p = new WMLinkQueue;/队的构造以及初始化p-WMfront = p-WMrear = NULL;LinkQueue *Line = new LinkQueue;Line-front = Line-rear = NULL;int