01实验报告模板(带评语).doc

第 PAGE 1 页 共 NUMPAGES 6 页 第 PAGE 1 页 共 NUMPAGES 3 页 石 家 庄 铁 道 大 学 实 验 报 告 课程名称： 数据结构与算法 任课教师： 王兴鹏 实验日期： 2010-11-15 班 级： 经0909 姓 名： 刘欣欣 学 号： 实验项目名称：栈和队列的基本操作及其应用 一、实验目的及要求 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈和队列的特点，即后进先出和先进先出的原则。 3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。 二、实验环境 1．系统软件：Windows XP 2．编程环境：Visual studio C++ 6.0 三、实验内容与步骤 1.回文判断 [问题描述] 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。 [基本要求] （1）数据从键盘读入； （2）输出要判断的字符串； （3）用顺序栈和循环队实现，先写出栈和队的基本操作；利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。 [测试数据] 由学生任意指定。 2．后缀表达式求解 [问题描述] 对于一个从键盘输入的后缀表达式，能够对其求解。 [基本要求] （1）表达式从键盘读入； （2）输出表达式的解； （3）用链栈实现，先写出栈的基本操作；利用栈的基本操作对其求解。 [测试数据] 由学生任意指定。 实验过程 #include stdio.h #include stdlib.h #include malloc.h #include string.h #define MAXQSIZE 50 //最大队列长度 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -2 #define ERROR 0 #define OK 1 typedef char SElemType; typedef char QElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; typedef struct { QElemType * base; //初始化的动态分配存储空间 int front; //头指针，若队列不空，指向队列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue; //循环队列的基本算法的算法描述 Status InitStack(SqStack S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status 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(OVERFLOW); S.top=S.base+S.stacksize; } *S.top++=e; return OK; } Status Pop(SqStack S,SElemType e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; } // Status InitQueue(SqQueue Q){ //构造一个空队列Q Q.base=(QElemType * ) malloc (MAXQSIZE *sizeof (QElemType)); if(!Q.base) exit(OVERFLOW); Q.front = Q.rear