实验报告(栈和队列).doc

《实验报告(栈和队列).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告课程：数据结构（c语言）实验名称：栈和队列系别：数字媒体技术实验日期：11月15号专业班级：组别：姓名：学号：实验报告内容验证性实验一、预习准备：实验目的：1.掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；2.掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况；实验环境：Widows操作系统、VC6.0实验原理：1.定义：栈：只允许在一端插入和删除的线性表，允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。队列:是只允许在一端删除，在另一

2、端插入的顺序表,允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。2.特点：栈：后进先出(LIFO)队列：先进先出(FIFO,FirstInFirstOut)3.表示：栈：（1）栈的数组表示—顺序栈（2）栈的链接表示—链式栈队列：（1）队列的顺序存储结构表示——循环队列（2）队列的链式表示—链队列实验内容和要求：分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准，两边字符完全相同。如：“ABCDEDCBA”。字符串长度小于等于80，用于判断

3、回文的字符串不包括字符串的结束标记符。基本要求：（1）字符序列可由用户从键盘随意输入；（2）可以连续测试多个字符序列，由用户决定退出测试程序；算法思想：判断回文的算法思想是：把字符串中的字符逐个分别存入队列和堆栈中，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文。基本操作：回文判断操作主要包括入栈和入队列、退栈和出队列操作。在对堆栈以及队列进行操作之前，必须对队列以及堆栈进行初始化。若使用链式堆栈和链式队列，操作结束后必须销毁链表。一、实验过程：程序流程图：队列实验

4、中的关键语句：(1)构造空顺序栈算法StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack(2)顺序栈出栈算法StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;retu

5、rnOK;}//Pop(3)(4)将元素压入顺序栈算法StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksixe+STACKINCREMENT*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return

6、OK;}//Push(4)在顺序队列尾插入新元素算法StatusEnQueue(SqQueue&Q;QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERRORQ.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}//EnQueue(5)在顺序队列头删除旧元素算法StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front

7、];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}//DeQueue(6)在链式队列尾插入新元素算法StatusEnQueue(LinkQueue&Q;QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}//EnQueue(7)在链式队列头删除旧元素算法StatusDeQueue(LinkQueue&Q,Q

8、ElemType&e){if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(