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

数学与信息技术学院2016~2017（下）学年计科专业2015级《数据结构》实验报告4学号：2015201018姓名：汪继超实验名称栈的应用完成时间2017.05.03一．实验目的和要求：一．掌握栈和队列的概念及其两种数据结构的特点，懂得在什么样的问题中应用利用哪种结构。二．熟练掌握在两种存储结构上实现栈的基本运算，特别注意栈满及栈空的条件及它们的描述方法。掌握两个顺序栈共享存储空间的概念。三．熟练掌握循环队列和链队列的基本运算，特别注意队满和队空的描述方法。四．加强编辑与调试C语言程序的能力。二.实验原理栈和队列是两种特殊的线性表。栈是限定只能在表的一端进行插入和删除的线性表，它又称为“后进先出”表；队列则是限定只能在表的一端进行插入，在表的另一端进行删除的线性表，它又称为“先进先出”表。由于栈和队列都是线性表的一种特例，所以它们都可以使用顺序存储结构和链式存储结构，栈的顺序存储结构称为顺序栈，栈的链式存储结构称为链栈；而队列的顺序存储结构称为顺序队列，队列的链式存储结构称为链队。顺序存储结构可用一维数组来实现，而链式存储结构可用指针来实现。三.实验内容假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个以”@”为结束符的字符序列是否是“回文”。实验过程：/*注：此程序为栈的操作实现与应用*/#includestdio.h#includestdlib.h#includeconio.h#includemalloc.h#includewindows.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintSElemType;typedefintQElemType;/*栈的存储结构*/typedefstruct{SElemType*base;/*栈低指针*/SElemType*top;/*栈顶指针*/intstacksize;/*栈当前已分配的所有空间，不是已使用的空间长度*/}SqStack;/*start***************队列的存储结构*********************/typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;/****************队列的存储结构********************end*//*函数声明*/SElemTypeGetTop(SqStack*S);voidPush(SqStack*S,SElemTypee);boolSEmpty(SqStack*S);SElemTypePop(SqStack*S);voidmain();//括号匹配-------------------------------------------------------startvoidmatch(SqStack*S){charstr[20];inti=0,flag;fflush(stdin);printf(\nPleaseenterastring:);scanf(%s,&str);while(str[i]!='\0'&&flag!=0){switch(str[i]){case'(':Push(S,'(');break;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;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(\nsuccess!\n);}elseprintf(\nerror!\n);}//括号匹配-------------------------------------------------------end//Queue逆置-------------------------------------------------------startLinkQueue*InitQ(){LinkQueue*Q;Q=(LinkQueue*)malloc(sizeof(LinkQueue));Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));if(!Q-front)exit(1);Q-front-next=NULL;printf(SuccessfulQ!);returnQ;}voidEnQ(LinkQueue*Q,QElemTypee)//入队{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(1);p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;}intDeQ(LinkQueue*Q)//出队{inte;QueuePtrp;if(Q-front==Q-rear)return0;else{p=Q-front-next;e=p-data;Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;free(p);returne;}}voidalgo3(LinkQueue*Q,SqStack*S)//逆置{intd;while(!(Q-front==Q-rear)){d=DeQ(Q);Push(S,d);}while(SEmpty(S))EnQ(Q,Pop(S));}voidtes(LinkQueue*Q,SqStack*S)//逆置主调函数{inti,e,n;printf(\n您要输入的数据条数是：);scanf(%d,&n);printf(\n请输入需逆置数据：);for(i=0;in;i++){scanf(%d,&e);EnQ(Q,e);}algo3(Q,S);printf(\n逆置后的数据顺序：);while(!(Q-front==Q-rear)){printf(%3d,DeQ(Q));}printf(\n);free(Q);}//Queue逆置-------------------------------------------------------end//回文-------------------------------------------------------startvoidHuiwen(LinkQueue*Q,SqStack*S){charstr[20];inti=0,flag;fflush(stdin);printf(\nPleaseenterastring:);scanf(%s,&str);while(str[i]!='\0'){Push(S,str[i]);EnQ(Q,str[i]);i++;}while(SEmpty(S)&&flag!=0){if(DeQ(Q)==Pop(S))flag=1;elseflag=0;}if(flag==1){printf(\nsuccess!\n);}elseprintf(\nerror!\n);}//回文-------------------------------------------------------endSqStack*InitStack()/*1.初始化栈*/{SqStack*S;S=(SqStack*)malloc(sizeof(SqStack));S-base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S||!S-base)exit(1);S-top=S-base;S-stacksize=STACK_INIT_SIZE;returnS;}boolSEmpty(SqStack*S)/*2.判栈空*/{if(S-top==S-base)return0;elsereturn1;/*1表示栈不空*/}voidPush(SqStack*S,SElemTypee)/*3.入栈*/{if(S-top-S-base=S-stacksize){S-base=(SElemType*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S-base)exit(1);printf(\n空间不够，开辟新空间成功！\n);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;}*S-top++=e;}SElemTypePop(SqStack*S)/*4.出栈*/{if(S-top==S-base){return0;printf(\nThesequencestackisempty!);}elsereturn*(--S-top);}voiddisplay(SqStack*S)/*5.打印*/{inte;SqStack*T;T=InitStack();/*1.新构建一个栈T*/while(SEmpty(S)){e=Pop(S);Push(T,e);/*2.将出栈打印的元素入栈T*/printf(%5d,e);/*当栈不空依次打印*/}while(SEmpty(T))Push(S,Pop(T));/*3.将栈T中元素出栈并入栈到栈S中*/free(T);printf(\n);}intStackLength(SqStack*S)/*6.统计栈长度*/{printf(\n统计得栈的长度为：%d\n,(S-top-S-base));return(S-top-S-base);}voidsearch(SqStack*S,SElemTypee)/*7.查找*/{intcount=0,flag=0;SqStack*T;T=InitStack();while(SEmpty(S)){if(e==GetTop(S)){count++;flag=1;printf(\n%d已找到元素：%d\n,count,e);}Push(T,Pop(S));}while(SEmpty(T))Push(S,Pop(T));free(T);if(flag==0)printf(\n没有找到元素：%d\n,e);}voidmodify(SqStack*S,SElemTypee)/*8.修改*/{inte1,count=0,flag=0,a;SqStack*T;T=InitStack();while(SEmpty(S)){if(e==GetTop(S)){count++;flag=1;printf(\n%d已找到元素：%d\n,count,e);printf(\n1.修改2.不修改：);scanf(%d,&a);switch(a){case1:e1=Pop(S);printf(\n将元素%d修改为：,e);scanf(%d,&e1);Push(S,e1);printf(\n修改成功！\n);//除输入1之外的情况都不做任何操作}}Push(T,Pop(S));}while(SEmpty(T))Push(S,Pop(T));free(T);if(flag==0)printf(\n没有找到元素：%d\n,e);}voidClearStack(SqStack*S)/*9.清空栈*/{S-top=S-base;printf(\n