数学与信息技术学院2016~2017（下）学年 计科专业2015级《数据结构》实验报告 4
学号：2015201018 姓名：汪继超
实验名称 栈的应用 完成时间 2017.05.03 一． 掌握栈和队列的概念及其两种数据结构的特点，懂得在什么样的问题中应用利用哪种结构。 二． 熟练掌握在两种存储结构上实现栈的基本运算，特别注意栈满及一．实验目的和要求： 栈空的条件及它们的描述方法。掌握两个顺序栈共享存储空间的概念。 三． 熟练掌握循环队列和链队列的基本运算，特别注意队满和队空的描述方法。 四． 加强编辑与调试C语言程序的能力。 栈和队列是两种特殊的线性表。栈是限定只能在表的一端进行插入和删除的线性表，它又称为“后进先出”表；队列则是限定只能在表的一端进行插入，在表的另一端进行删除的线性表，它又称为“先二.实验原理 进先出”表。由于栈和队列都是线性表的一种特例，所以它们都可以使用顺序存储结构和链式存储结构，栈的顺序存储结构称为顺序栈，栈的链式存储结构称为链栈；而队列的顺序存储结构称为顺序队列，队列的链式存储结构称为链队。顺序存储结构可用一维数组来实现，而链式存储结构可用指针来实现。 三.实验内容 假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个以”@”为结束符的字符序列是否是“回文”。 实验过程： /*注：此程序为栈的操作实现与应用*/ #include #include #include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType; typedef int QElemType; /*栈的存储结构*/ typedef struct{ SElemType *base; /*栈低指针*/ SElemType *top; /*栈顶指针*/ int stacksize; /*栈当前已分配的所有空间，不是已使用的空间长度*/ }SqStack; /*start***************队列的存储结构*********************/ typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; /****************队列的存储结构********************end*/ /*函数声明*/ SElemType GetTop(SqStack *S); void Push(SqStack *S,SElemType e); bool SEmpty(SqStack *S); SElemType Pop(SqStack *S); void main(); //括号匹配-------------------------------------------------------start void match(SqStack *S) { char str[20]; int i=0,flag; fflush(stdin); printf(\ scanf(\ while(str[i]!='\\0'&&flag!=0) { switch(str[i]) { case '(': Push(S,'('); break; case ')': if(*(S->top-1)=='(') { flag=1; Pop(S); } else flag=0; break; case '[': Push(S,'['); break; case ']': if(*(S->top-1)=='[') { flag=1; Pop(S); } else flag=0; break; case '{': Push(S,'{'); break; case '}': if(*(S->top-1)=='{') { flag=1; Pop(S); } else flag=0; break; default :flag=0;break; } i++; } if((flag==1)&&(SEmpty(S)==0)) { printf(\ } else printf(\} //括号匹配-------------------------------------------------------end //Queue逆置-------------------------------------------------------start LinkQueue * InitQ() { LinkQueue *Q; Q=(LinkQueue *)malloc(sizeof(LinkQueue));