《栈和队列的基本操作实现及其应用》由会员分享，可在线阅读，更多相关《栈和队列的基本操作实现及其应用（13页珍藏版）》请在金锄头文库上搜索。
1、实验 二 栈和队列的基本操作实现及其应用 一_一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实 现。一_二、实验内容 题目一、试写一个算法，判断依次读入的一个以为结束符的字符序列， 是否为回文。 所谓“回文“是指正向读和反向读都 一样的一字符串 , 如“321123”或“ ableelba ”。相关常量及结构定义：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef struct SqStack SElemType *base;SElemType *top;int sta
2、cksize;SqStack; 设计相关函数声明： 判断函数： int IsReverse() 栈：int InitStack(SqStack &S ) int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s) 一_三、数据结构与核心算法的设计描述1、初始化栈/* 函数功能：对栈进行初始化 。参数：栈 (SqStack S) 。 成功初始化返回 0,否则返回 -1 */int InitStack(SqStack &S)=(SElemType *)malloc(10*sizeof(S
3、ElemType);if(! / 判断有无申请到空间return -1; / 没有申请到内存 , 参数失败返回 -1一 J=STACK_INIT_SIZE;=new SElemType; return 0;2、判断栈是否是空/*函数功能：判断栈是否为空。参数；栈(SqStack S)。栈为空时返回-1,不为空返回0*/int StackEmpty(SqStack S)if= return -1；else return 0；3、入栈/*函数功能：向栈中插入元素。参数;栈(SqStack S),元素(SEIemtype e)。成功插入返回0, 否则返回 -1 */int Push(SqStack
4、&S,SEIemType e)if =(SEIemType *)reaIIoc,+1) * sizeof(SEIemType);/重新分配空间if(! return -1;=+;+=STACKINCREMENT;*+=e;/插入操作return 0;4、出栈/*函数功能：在栈中删除元素。参数；栈(SqStack S),元素(SElemtype e)。成功删除返回0, 否则返回 -1 */int Pop(SqStack &S,SElemType &e)if= return -1;e=*; / 删除操作 return 0;5、判断是否为回文1, 否则/*函数功能：判断栈中的字符串是否为回文。参数;
5、栈(SqStack S)。是回文时返回返回 0*/ int IsReverse(SqStack &S)int i;char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) return 0;return 1;一_四、函数的调用主函数主要设计：int lpp;char ch;SqStack p;InitStack(p);cout 请输入字符： ; while(ch=()&ch!=) Push(p,ch);bj=ch;j+;if (StackEmpty(p)=-1)cout 此为空栈 endl; return 0;lpp=IsReverse(p);if(lpp=0) cout
6、此字符串不是回文。 endl;else cout 此字符串是回文。 endl;知道自己容一_五、实验总结 通过这次试验我熟悉了对栈的基本操作， 对基本的栈操作有了很好的掌握， 易在什么地方出错，。一_六、程序清单#include using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10char bSTACK_INIT_SIZE+STACKINCREMENT;int j=0;typedef char SElemType;typedef struct SqStack SElemType *base;SElemT
7、ype *top;int stacksize;SqStack;int InitStack(SqStack &S) =(SElemType *)malloc(10*sizeof(SElemType); if(! return -1;一 J=STACK_INIT_SIZE;=new SElemType; return 0;int StackEmpty(SqStack S)if= return -1;else return 0;int Push(SqStack &S,SElemType e)if =(SElemType *)realloc,+1) * sizeof(SElemType);if(! r
8、eturn -1;=+;+=STACKINCREMENT;*+=e;return 0;int Pop(SqStack &S,SElemType &e)if= return -1;e=*;return 0;int IsReverse(SqStack &S) int i; char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) return 0;return 1;int main()int lpp;char ch;SqStack p;InitStack(p);cout 请输入字符： ; while(ch=()&ch!=)Push(p,ch);bj=ch;j+;if (Sta
9、ckEmpty(p)=-1)cout 此为空栈 endl;return 0; lpp=IsReverse(p); if(lpp=0) cout 此字符串不是回文。 endl; else cout 此字符串是回文。 next=NULL; return 0;2、入队列int EnQueue(LinkQueue &Q,QElemType e) QueuePtr lpp; lpp=(QueuePtr)malloc(sizeof(QNode); if(!lpp) return -1;lpp-data=e; lpp-next=NULL; if=NULL) next=lpp; =lpp; else next
10、=lpp; =lpp; return 0;3、出队列int DeQueue(LinkQueue &Q,QElemType &e) QueuePtr lpp; if= return -1; lpp=next; e=lpp-data;next=lpp-next;if=lpp) =;delete lpp;return 0;4、统计队列的长度int QueueLength(LinkQueue Q)QueuePtr lpp=;int i=0;while(lpp!=i+; lpp=lpp-next; return i;5、查找队列的某个元素int QueueFind(LinkQueue Q,QElemTy
11、pe e) QueuePtr p;p=next;while(p) if(p-data=e) return 1;p=p-next; return 0;6、遍历队列int QueueTraverse(LinkQueue Q)QueuePtr p;p=next;while(p)coutdatanext; coutendl; return 0;7、主界面函数 void zhujiemian() coutendl;coutcout【tt数据结构实验二】endl;【 tt】endl;cout【tt 1队列初始化】endl;cout【tt 2出队列】endl;cout【tt 3入队列】endl;cout【tt 4队列长度】endl;cout【tt 5在队列中查找元素】endl;cout【tt 6遍历队列】endl;cout【tt其他键退出】endl;cout【 tt】endl;couta;while(a!=1
