实验 二 栈和队列的基本操作实现及其应用.docx

软件114班 李大宝 201100834416数据结构实验报告（二）姓名: 李 大 宝学院：计算机学院班级：软件114班 实验 二 栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。2、会用栈和队列解决简单的实际问题。二、实验内容题目一试写一个算法，判断依次读入的一个以为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。一、相关常量及结构定义：# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define OK 1# define ERROR 0typedef char SElemType; /把char类型定义为SElemType/栈类型定义typedef struct SqStack SElemType *base; /栈底SElemType *top; /栈顶int stacksize; /最大容量SqStack;/队列类型定义typedef struct QNodeSElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; /队首QueuePtr rear; /队尾LinkQueue;二、设计相关函数声明：判断函数：int IsReverse()栈：int InitStack(SqStack &S )int Push(SqStack &S, SElemType e )int Pop(SqStack &S,SElemType &e)int StackEmpty(s)队列；int initqueue(LinkQueue &Q)int EnQueue(LinkQueue &Q,SElemType e)int DeQueue(LinkQueue &Q,SElemType &e)三、函数说明：1、栈初始化/*函数功能：对栈进行初始化 参数：栈(SqStack &S)成功初始化返回1,否则返回0 */int InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); /对栈申请空间。if(!S.base)exit(0); /未申请空间退出。S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;2、弹出栈顶元素，并返回/*函数功能：对栈删除栈顶元素参数：栈SqStack &S, 元素SElemType &e用e返回栈顶元素 */int Pop(SqStack &S,SElemType &e)if(S.top=S.base) /栈为空时返回错误。return ERROR;e=*-S.top; /成功返回栈顶元素return OK;3、向栈中压入元素/*函数功能：向栈中压入元素参数：栈SqStack &S, 元素SElemType e成功压入返回1，否则返回0 */int Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize) /栈的大小过小时，从新申请内存S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ = e; /成功压入元素。return OK;4、栈是否为空/*函数功能：判断栈是否为空参数：栈SqStack S为空返回1，否则返回0 */int StackEmpty(SqStack S)if(S.top=S.base) /为空条件S.top=S.basereturn OK;elsereturn ERROR; /不空返回05、队列初始化/*函数功能：对队列进行初始化 参数：队列(LinkQueue &Q)成功初始化返回1,否则返回0 */int initqueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(ERROR);Q.front-next=NULL;return OK;6、入队/*函数功能：对队列进行入队 参数：队列LinkQueue &Q，元素SElemType e成功入栈返回1 */int EnQueue(LinkQueue &Q,SElemType e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);/对p申请内存if(!p)exit(ERROR); /未申请到内存退出p-data=e;p-next=NULL;if(Q.rear=NULL) /队列为空时Q.front-next=p;Q.rear=p;Else /队列不为空时Q.rear-next=p;Q.rear=p; /在队尾入栈return OK;7、出队/*函数功能：对队列进行出队 参数：队列LinkQueue &Q，元素SElemType &e用元素e将队首元素进行返回成功出栈返回1 */int DeQueue(LinkQueue &Q,SElemType &e)if(Q.front=Q.rear)return ERROR; /队空QueuePtr p;p=Q.front-next;e=p-data; /队首元素Q.front-next=p-next;if(Q.rear=p) /p为最后一个元素时Q.rear=Q.front;free(p); /释放p节点return OK;8、判断函数： /*函数功能：判断字符串是否是回文字符串 参数：栈SqStack S,队列LinkQueue &Q如果是回文字符串返回1，否则返回0 */int IsReverse(SqStack S,LinkQueue Q)SElemType a,b;while(!StackEmpty(S) /栈不为空时Pop(S,a);DeQueue(Q,b);if(a!=b) /栈顶元素与队首元素进行比较，不相等返回0return 0;return 1; /栈与队列相同返回1，即字符串为回文字符串。三、主函数设计int main()char YES; /用来存放字符doSElemType e;SqStack S;LinkQueue Q;InitStack(S); /初始化栈initqueue(Q); /初始化队列cout请输入字符串以结尾！endl;while(e=getchar()!=) /输入以结束。Push(S,e); /入栈EnQueue(Q,e); /入队if(IsReverse(S,Q)=1) /判断返回是否为1，为1就是回文字符串cout此字符串是回文字符串endl;elsecout此字符串不是回文字符串endl;cout是否继续，继续（y/Y），其他键退出YES;getchar(); / getchar()接收缓冲区本来保存的东西while(YES=y|YES=Y);return 0;四、程序调试及运行结果分析程序完美运行。特别注意：cinYES;getchar();这里很容易出错getchar()是用来做缓冲。用getchar()接收缓冲区本来保存的东西程序运行结果如下：五、实验总结通过这次试验我熟悉了对栈和队列的基本操作，对基本的栈和队列操作有了很好的掌握，知道自己容易在什么地方出错。六、程序清单#include #include #include using namespace std;# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define OK 1# define ERROR 0typedef char SElemType;typedef struct SqStackSElemType *base; SElemType *top; int stacksize;SqStack;typedef struct QNodeSElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;int InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;int Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ = e;return OK;int StackEmpty(SqStack S)if(S.top=S.base)return OK;elsereturn ERROR;int initqueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(ERROR);Q.front-next=NULL;return OK;int EnQueue(LinkQueue &Q,SElemType e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(ERROR);p-data=e;p-next=NULL;if(Q.rear=NULL)Q.front-next=p;Q.rear=p;elseQ.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,SElemType &e)if(Q.front=Q.rear)return ERROR;QueuePtr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;int IsReverse(SqStack S,LinkQueue Q)SElemType a,b;while(!StackEmpty(S) Pop(S,a);DeQueue(Q,b);if(a!=b)return 0;return 1;int main()char YES;doSElemType e;SqStack S;LinkQueue Q;InitStack(S);initqueue(Q);cout请输入字符串以结尾！endl;while(e=getchar()!=)Push(S,e);EnQueue(Q,e);if(IsReverse(S,Q)=1)cout此字符串是回文字符串endl;elsecout此字符串不是回文字符串endl;cout是否继续，继续（y/Y），其他键退出YES;getchar(); /表示缓冲字符YES；while(YES=y|YES=Y);return 0;STL标准模板库程序：#includeusing namespace std;#include#includestack s;queue q;int IsReverse() while(!s.empty() if(s.top()!=q.front() return 0; s.pop(); q.pop(); return 1;int main() char YES; do cout请输入字符串以结尾！endl; char e; while(e=getchar()!=) s.push(e); q.push(e); getchar(); if(IsReverse()=1) cout此字符串是回文字符串endl; else cout此字符串不是回文字符串endl; while(!s.empty() s.pop(); while(!q.empty() q.pop(); cout是否继续，继续（y/Y），其他键退出YES; getchar(); while(YES=y|YES=Y);题目二编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。实现提示：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。一、 相关结构定义#define elemtype int /定义int为elemtype类型typedef struct STDelemtype data;struct STD *next;Qnode,*Queueptr;typedef structQueueptr front; /队首Queueptr rear; /队尾int count;linkqueue;二、 函数说明：1、初始化队列/*函数功能：对队列进行初始化 参数：队列(linkqueue &Q)成功初始化返回1,否则返回0 */int init(linkqueue &Q)Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode); /对队列申请空间。if(!Q.front) exit(0); /未申请空间退出。Q.front-next=NULL;Q.count=0;return 1;2.出队/*函数功能：对队列进行出队 参数：队列linkqueue &Q，元素elemType &e成功出栈返回1 */int dequeue(linkqueue &Q)Queueptr p;if(Q.front=Q.rear) /队空return 0;p=Q.front-next;Q.front-next=p-next;if(Q.rear=p) /p为最后一个元素时Q.rear=Q.front;free(p); /释放p节点Q.count-; /队长度减1return 1;3.入队/*函数功能：对队列进行入队 参数：队列linkqueue &Q，元素elemType e成功入栈返回1 */int enqueue(linkqueue &Q,elemtype e)Queueptr p;p=(Queueptr)malloc(sizeof(Qnode); /对p申请内存if(!p)exit(0); /未申请到内存退出p-data=e;p-next=NULL;if(Q.front=NULL) /队列为空时Q.front-next=p;Q.rear=p;Else /队列不为空时Q.rear-next=p;Q.rear=p; /在队尾入栈Q.count+; /长度加1。return 1;4.长度/*函数功能：返回队列的长度 参数：队列linkqueue Q返回Q.count */int length(linkqueue Q)return Q.count; /队列的长度5.查找/*函数功能：在队列中查找元素 参数：队列linkqueue Q，元素elemtype e找到返回1，否则返回0 */int find(linkqueue Q,elemtype e)Queueptr p;p=Q.front-next;while(p)if(p-data=e) /找到元素e返回1return 1;p=p-next;return 0; /找不到元素e返回06.显示/*函数功能：显示队列中所有元素 参数：队列linkqueue Q无返回值 */void show(linkqueue Q)Queueptr p;p=Q.front-next;while(p) /队列元素不为空时coutdatanext;coutendl;7.主界面/*函数功能：操作主界面 参数：无无返回值 */void zhujiemian()coutendlendl;couttttt数据结构实验二endl;couttt-endlendl;couttt 1 队列初始化endl;couttt 2 出队列endl;couttt 3 入队列endl;couttt 4 队列长度endl;couttt 5 在队列中查找元素endl;couttt 6 遍历队列endl;couttt其他键退出endl;couttt-endlendlendl;couta;while(a!=1) /第一步一定要对队列初始化couta;coutendl;doswitch(a)case 1:if(init(Q)=1)cout初始化成功！endl;elsecout初始化失败！endl;break;case 2:if(length(Q)=0)cout队列为空无法出队！endl;break;if(dequeue(Q)=1)cout删除成功！endl;elsecout删除失败！endl;break;case 3:cout输入你要入队元素c;if(enqueue(Q,c) =1)cout入队成功！endl;elsecout入队失败！endl;break;case 4:b=length(Q);cout队列的长度为：bendl;break;case 5:coutb;if(find(Q,b)=1)cout恭喜您，队列中有您要找的元素bendl;elsecout不好意思，队列中没有您要找的元素bendl;break;case 6:if(length(Q)=0)cout队列为空！a;cout0&a=6); /判断输入的a是否在1-6之间。return 0;四、程序调试及运行结果分析运行主界面：操作界面清晰，方便操作。入队：出队：当队列为空时不会出现错误。查找：五、实验总结通过这个实验我明白了队列的基本操作，和熟练掌握了队列的基本实现。通过这次实验我懂得了关于队列该如何操作。六、程序清单#include #include #include #include #include using namespace std;#define elemtype inttypedef struct STDelemtype data;struct STD *next;Qnode,*Queueptr;typedef structQueueptr front;Queueptr rear;int count;linkqueue;int init(linkqueue &Q)Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode);if(!Q.front)exit(0);Q.front-next=NULL;Q.count=0;return 1;int dequeue(linkqueue &Q)Queueptr p;if(Q.front=Q.rear)return 0;p=Q.front-next;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);Q.count-;return 1;int enqueue(linkqueue &Q,elemtype e)Queueptr p;p=(Queueptr)malloc(sizeof(Qnode);if(!p)exit(0);p-data=e;p-next=NULL;if(Q.front=NULL)Q.front-next=p;Q.rear=p;elseQ.rear-next=p;Q.rear=p;Q.count+;return 1;int length(linkqueue Q)return Q.count;int find(linkqueue Q,elemtype e)Queueptr p;p=Q.front-next;while(p)if(p-data=e)return 1;p=p-next;return 0;void show(linkqueue Q)Queueptr p;p=Q.front-next;while(p)coutdatanext;coutendl;void zhujiemian()coutendlendl;couttttt数据结构实验二endl;couttt-endlendl;couttt 1 队列初始化endl;couttt 2 出队列endl;couttt 3 入队列endl;couttt 4 队列长度endl;couttt 5 在队列中查找元素endl;couttt 6 遍历队列endl;couttt其他键退出endl;couttt-endlendlendl;couta;while(a!=1)couta;coutendl;doswitch(a)case 1:if(init(Q)=1)cout初始化成功！endl;elsecout初始化失败！endl;break;case 2:if(length(Q)=0)cout队列为空无法出队！endl;break;if(dequeue(Q)=1)cout删除成功！endl;elsecout删除失败！endl;break;case 3:cout输入你要入队元素c;if(enqueue(Q,c) =1)cout入队成功！endl;elsecout入队失败！endl;break;case 4:b=length(Q);cout队列的长度为：bendl;break;case 5:coutb;if(find(Q,b)=1)cout恭喜您，队列中有您要找的元素bendl;elsecout不好意思，队列中没有您要找的元素bendl;break;case 6:if(length(Q)=0)cout队列为空！a;cout0&a=6);return 0;题目三、 RailsDescriptionThere is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N = 1000 coaches numbered in increasing order 1, 2, ., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station. InputThe input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ., N. The last line of the block contains just 0. The last block consists of just one line containing 0. OutputThe output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last null block of the input. Sample Input51 2 3 4 55 4 1 2 3066 5 4 3 2 100Sample OutputYesNoYes程序清单：（STL标准模板库）一、#include#include#includeusing namespace std;int a1001,n,i,j;int fan()stacks; /火车是按（1-n）的顺序进栈 int i,j; for(i=0,j=1;in&j=n+1;) if(s.empty()|s.top()!=ai)/栈空或栈顶元素不与ai相同时进站 if(j=(n+1) /不能正常出站条件 return 0; /不能正常出站返回0 s.push(j+); /将j压入栈中 else /栈顶元素与ai相同时进站 s.pop(); /弹出栈顶元素 i+; /i+，a的下个元素继续进行 return 1;/*fan()解释：1-n和an的每个元素进行比较。用j=1，j+表示1n的每个元素用ai（0=in）表示ai的每个元素。如果栈为空时让j进栈，然后j+。如果栈顶元素与ai不相同，让j进栈，然后j+。如果栈顶元素与ai相同，弹出栈顶元素，然后i+。结束条件：1、j=(n+1)时表示不