栈和队列的基本运算.doc

实验三 栈和队列的基本运算一、实验目的（1） 掌握栈和队列的各种存储结构及基本运算的实现。（2） 掌握堆栈后进先出运算原则在解决实际问题中的应用。（3） 掌握队列先进先出运算原则在解决实际问题中的应用。（4） 掌握递归程序设计的特点和编程方法。二、实验要求：（1） 熟练掌握栈和队列的基本运行及其操作。（2）理解实训案例的算法，掌握线栈和队列在实际中的运用。（3）将上机程序全部调试通过。（4）独立完成一个至两个实训项目，保存程序运行结果，并结合程序进行分析。三、实验内容：（1）任意输入一个字符串，按反序输出。要求字符串从键盘随机输入，字符长度不做具体限制。实现时，以链栈为手段。（2） 设计一个算法，判定一个字符串是否是对称字符串。若是，则返回1，否则返回0。（3） 括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其符号是否匹配。若匹配，则返回1；否则返回0。（4） 编写递归和非递归程序，计算下列表达式的值 1 n=0 2x n=1 n1 （5） 舞伴问题。假设在周末舞会上，男士和女士各自组成一排，跳舞开始的时候，依次从男队和女队上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未匹配对者等待下一轮舞曲。现要求写一篇算法模拟上述舞伴配对的问题。4、 程序代码： 1#include#includetypedef char ElemType;typedef struct snodeElemType data; struct snode *next;LinkSTACK;void InitStack(LinkSTACK *top) *top=(LinkSTACK *)malloc(sizeof(LinkSTACK);(*top)-next=NULL;int push(LinkSTACK *top,ElemType x) LinkSTACK *s;s=(LinkSTACK *)malloc(sizeof(LinkSTACK);s-data=x;s-next=(*top)-next;(*top)-next=s;return 1;int Empty(LinkSTACK *top)return (*top)-next=NULL?1:0);int Pop(LinkSTACK *top,ElemType *x)LinkSTACK *s;if(Empty(top)printf(Stack is free!n);return 0;s=(*top)-next;*x=s-data;(*top)-next=s-next;return 1;void main()char ch;LinkSTACK *top;InitStack(&top);printf(请输入一字串);while(ch=getchar()!=n) push(&top,ch);printf(n);while(!Empty(&top)Pop(&top,&ch);printf(%c,ch); 2#include #include #define MAXSIZE 40typedef char ElemType;typedef struct ElemType dataMAXSIZE;int top;STACK;void InitStack(STACK *S) S-top=-1;int Push(STACK *S,ElemType x) if(S-top=MAXSIZE-1) printf(Stack is fulln); return 0; S-top+; S-dataS-top=x; return 1; int Empty(STACK *S) return (S-top=-1?1:0); int Pop(STACK *S,ElemType *x) if(Empty(S) printf(Stack is free!n); return 0; *x=S-dataS-top; S-top-; return 1; main() STACK st; char str100,ch; int i,len,same=1;InitStack(&st);printf(请输入一字串:);gets(str);len=strlen(str);for(i=0;ilen/2;i+) Push(&st,stri);if(len%2=0) i=len/2;else i=(len+1)/2;while(!Empty(&st) Pop(&st,&ch); if(ch!=stri) same=0;break; i+;if(same) printf(%s是对称字串!,str);else printf(%s不是对称字串!,str); 3#include#include#define MAXSIZE 40typedef char ElemType;typedef struct ElemType dataMAXSIZE; int top;STACK;void InitStack(STACK *S) s-top=-1;int Push(STACK *S,ElemType x) if(s-top=MAXSIZE-1) printf(Stack is full!n); return 0; s-top+; s-datas-top=x; return 1;int Empty(STACT *S) retutrn (s-top=-1?1:0);int pop(STACK *S,ElemType *x) if(Empty(s) printf(n stack is free!); return 0; *x=s-datas-top; s-top-; return 1;int match(char *exps) STACK st;int pos=0,int yesmatch=1;while(expsi & yesmatch) switch(expspos) case (: case : case : Push(&st,epspos);break; case ): case : case :pop(&st,&ch); if(ch!=expspos) yesmatch=0;break; pos+;return (yesmatch & Empty(&st)?1:0;main() char str100; int yesmatch; printf(请输入一字串：); gets(str); yesmatch=match(str); if(yesmatch) printf(是匹配是字串！); else printf(不是匹配的字串！);4#includedouble p(int n,int x)double f;if(n=0)f=1;else if(n=1)f=2*x;else f=2*x*p(n-1,x)-2*(n-1)*p(n-2,x);return f;#include#define MAXSIZE 40typedef structint n;int x;ElemType;typedef structElemType dataMAXSIZE;int top;STACK;void InitStack(STACK *S)S-top=-1;double p(int n,double x)STACK st;int i;double f1=1,double f2=2*x,InitStack(&st);for(i=n;i=2,i-)st.top+;st.datast.top.n=i;while(top=0)st.datast.,top.x=2*x*f2-2*(st.datast.top.n-1)*f1;f1=f2;f2=st.datast.top.x;st.top-;return f2;main()int n;double x;printf(请输入n与x的值：);scanf(%d%f,&n,&x);printf(n表达式值为%1f:,p(n,x); 5#includetypedef struct char name20; char sex;ElemType;typedef struct qnode Elemtype data; struct qnode *next; QTYPE;typedef struct qptr QTYPE *front,*rear; int count; SQUEUE;void InitQueue(SQUEUE *LQ)QTYPE *p;p=(QTYPE *)malloc(sizeof(QTYPE);p-next=NULL;LQ-front=LQ-rear=p;LQ-count=0;int EnQueue(SQUEUE *LQ,ELemType x) QTYPE *s;s=(QTYPE *)malloc(sizeof(QTYPE);s-data=x;s-next=LQ-rear-next;LQ-rear-next=s;LQ-count+;return 1;int Empty(SQUEUE *LQ)return(LQ-front=LQ-rear?1:0);int OutQueue(SQUEUE *LQ,ElemType *x)QTYPE *p;if(Empty(LQ) printf(nQueue is free!);return 0;p=LQ-front -next;*x=p-data;LQ-front-next=p-next;LQ-count-;if(LQ-front-next=NULL) LQ-rear=Lq-front;free(p);return 1;int GetHead(SQUEUE *LQ,ElemType *x) if(Empty(LQ)printf(n Queue is free!); return 0; *x=LQ-front-next-data; return 1;void DancePartner() FILE *fp; ElemType p; SQUEUE mdancer, fdancer; InitQueue(&mdancer);InitQueue(&fdancer); if(fp=fopen(dancer.dat,r)=NULL) printf(cant open the file!); exit(0);while(!feof(fp) p.sex=fgetc(fp); fgetc(fp); fgets(fp,10,); if(p.sex=F) EnQueue(&fdancer,p);else EnQueue(&mdancer,p);printf(舞伴是：n);while(!Empty(&fdancer) & !Empty(&mdancer)outQueue(&fdancer,&p); printf(%s,); OutQueue(&mdancer.&p); printf(%s,);if(!Empty(&fdancer) printf(n还有%d个女士等下一轮。n,fdancer.count); GetHead(&fdancer,&p); printf(%s will be the first to get a partner.n,p,name);else if(!Empty(mdancer) printf(n还有%d个男士等下一轮。n,dmancer.count); GetHead(&mdancer,&p); printf(%s将得到第一个舞伴n,);5、 实验结果：6、 通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C语言是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操