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

实验报告课程：数据结构（c语言） 实验名称：栈和队列 系别：数字媒体技术 实验日期： 11月15号 专业班级： 组别：姓名： 学号：实验报告内容验证性实验一、 预习准备：实验目的：1. 掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；2. 掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况；实验环境：Widows操作系统、VC6.0实验原理：1. 定义：栈：只允许在一端插入和删除的线性表，允许插入和删除的一端称 为栈顶 (top)， 另一端称为栈底(bottom)。 队列: 是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。2. 特点：栈：后进先出 (LIFO)队列：先进先出(FIFO, First In First Out)3. 表示：栈：（1）栈的数组表示 顺序栈（2）栈的链接表示 链式栈 队列：（1）队列的顺序存储结构表示循环队列 （2）队列的链式表示 链队列实验内容和要求：分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准，两边字符完全相同。如：“ABCDEDCBA”。字符串长度小于等于80，用于判断回文的字符串不包括字符串的结束标记符。 基本要求：（1）字符序列可由用户从键盘随意输入；（2）可以连续测试多个字符序列，由用户决定退出测试程序； 算法思想： 判断回文的算法思想是：把字符串中的字符逐个分别存入队列和堆栈中，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文。 基本操作： 回文判断操作主要包括入栈和入队列、退栈和出队列操作。在对堆栈以及队列进行操作之前，必须对队列以及堆栈进行初始化。若使用链式堆栈和链式队列，操作结束后必须销毁链表。二、 实验过程： 程序流程图：队列实验中的关键语句： (1) 构造空顺序栈算法Status InitStack ( SqStack &S ) S.base = ( SElemType * ) malloc ( STACK_INIT_SIZE * sizeof ( SElemType ) );if ( ! S.base ) exit ( OVERFLOW );S.stacksize = STACK_INIT_SIZE; return OK; / InitStack(2) 顺序栈出栈算法Status Pop ( SqStack &S, SElemType &e ) if ( S.top = = S.base ) return ERROR;e = *-S.top; return OK; / Pop(3) (4) 将元素压入顺序栈算法Status Push ( SqStack &S, SElemType e ) 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 OK; / Push(4)在顺序队列尾插入新元素算法Status EnQueue ( SqQueue &Q; QElemType e ) if ( ( Q.rear + 1 ) % MAXQSIZE = = Q.front )return ERRORQ.base Q.rear = e; Q.rear = ( Q.rear + 1 ) % MAXQSIZE; return OK; / EnQueue(5)在顺序队列头删除旧元素算法Status DeQueue ( SqQueue &Q, QElemType &e ) if ( Q.front = = Q.rear ) return ERROR; e = Q.base Q.front ; Q.front = ( Q.front + 1 ) % MAXQSIZE; return OK; / DeQueue(6)在链式队列尾插入新元素算法Status EnQueue ( LinkQueue &Q; QElemType e ) p = ( QueuePtr ) malloc ( sizeof ( QNode ) );if ( ! p ) exit ( OVERFLOW ); p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; / EnQueue(7)在链式队列头删除旧元素算法 Status DeQueue ( LinkQueue &Q, QElemType &e ) if ( Q.front = = Q.rear ) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if ( Q.rear = = p ) Q.rear = Q.front; free ( p ); return OK; / DeQueue编写及调试程序中遇到的问题及解决方法:（1）没有注意到可以验证多次问题。解决：用循环队列（2）程序没错但不能运行。解决：开始时需要初始化栈和队列三、 实验总结： 1. 实验结果及分析：可以看到，程序运用栈和队列不同的结构特点去判断一个字符串是否是回文。先写栈，再写队列，最后调用主函数判断是否回文并输出，运行结果显示可以实现实验要求。2. 实验总结：在此次实验中更深刻的理解了栈和队列在实际应用层面的例子，对程序怎么应用在现实生活中有了初步理解，程序与我而言不再是冰冷的字母了，有了自己的意义。我相信多试验对我们以后的专业学习和工作都有帮助。3. 思考题：栈和队列都是线性表，都是限制了插入删除点的线性表（或者说