附录A
实验报告
课程:数据结构(c语言) 实验名称:栈和队列 系别:数字媒体技术 实验日期: 11月15号 专业班级: 组别: 姓名: 学号:
实验报告内容
验证性实验
一、 预习准备:
实验目的:
1. 掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件;
2. 掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况; 实验环境:Widows操作系统、VC6.0 实验原理: 1. 定义:
栈:只允许在一端插入和删除的线性表,允许插入和删除的一端称 为栈顶 (top), 另一端称为栈底(bottom)。
队列: 是只允许在一端删除,在另一端插入的顺序表,允许删除的一端叫做队
头(front),允许插入的一端叫做队尾(rear)。 2. 特点:
栈:后进先出 (LIFO)
队列:先进先出(FIFO, First In First Out)
9
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