数据结构栈队列C语言实现.doc

《数据结构栈队列C语言实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学与信息技术学院2016~2017（下）学年计科专业2015级《数据结构》实验报告4学号：2015201018姓名：汪继超实验名称栈的应用完成时间2017.05.03一．实验目的和要求：一．掌握栈和队列的概念及其两种数据结构的特点，懂得在什么样的问题中应用利用哪种结构。二．熟练掌握在两种存储结构上实现栈的基本运算，特别注意栈满及栈空的条件及它们的描述方法。掌握两个顺序栈共享存储空间的概念。三．熟练掌握循环队列和链队列的基本运算，特别注意队满和队空的描述方法。四．加强编辑与调试C语言程序的能力。二.实验原

2、理栈和队列是两种特殊的线性表。栈是限定只能在表的一端进行插入和删除的线性表，它又称为“后进先出”表；队列则是限定只能在表的一端进行插入，在表的另一端进行删除的线性表，它又称为“先进先出”表。由于栈和队列都是线性表的一种特例，所以它们都可以使用顺序存储结构和链式存储结构，栈的顺序存储结构称为顺序栈，栈的链式存储结构称为链栈；而队列的顺序存储结构称为顺序队列，队列的链式存储结构称为链队。顺序存储结构可用一维数组来实现，而链式存储结构可用指针来实现。三.实验内容假设称正读和反读都相同的字符序列为“回文”，试写一

3、个算法判别读入的一个以”@”为结束符的字符序列是否是“回文”。实验过程：/*注：此程序为栈的操作实现与应用*/#include#include#include#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintSElemType;typedefintQElemType;/*栈的存储结构*/typedefstruct

4、{SElemType*base;/*栈低指针*/SElemType*top;/*栈顶指针*/intstacksize;/*栈当前已分配的所有空间，不是已使用的空间长度*/}SqStack;/*start***************队列的存储结构*********************/typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}L

5、inkQueue;/****************队列的存储结构********************end*//*函数声明*/SElemTypeGetTop(SqStack*S);voidPush(SqStack*S,SElemTypee);boolSEmpty(SqStack*S);SElemTypePop(SqStack*S);voidmain();//括号匹配-------------------------------------------------------startvoidmatc

6、h(SqStack*S){charstr[20];inti=0,flag;fflush(stdin);printf("Pleaseenterastring:");scanf("%s",&str);while(str[i]!=''&&flag!=0){switch(str[i]){case'(':Push(S,'(');break;case')':if(*(S->top-1)=='('){flag=1;Pop(S);}elseflag=0;break;case'[':Push(S,'[');brea

7、k;case']':if(*(S->top-1)=='['){flag=1;Pop(S);}elseflag=0;break;case'{':Push(S,'{');break;case'}':if(*(S->top-1)=='{'){flag=1;Pop(S);}elseflag=0;break;default:flag=0;break;}i++;}if((flag==1)&&(SEmpty(S)==0)){printf("success!");}elseprintf("error!")

8、;}//括号匹配-------------------------------------------------------end//Queue逆置-------------------------------------------------------startLinkQueue*InitQ(){LinkQueue*Q;Q=(LinkQueue*)malloc(sizeof(LinkQueue));Q->front=Q