栈和队列的基本运算

《栈和队列的基本运算》由会员分享，可在线阅读，更多相关《栈和队列的基本运算（10页珍藏版）》请在金锄头文库上搜索。

1、 实验三实验三 栈和队列的基本运算栈和队列的基本运算 一、一、实验目的实验目的（1）掌握栈和队列的各种存储结构及基本运算的实现。 （2）掌握堆栈后进先出运算原则在解决实际问题中的应用。 （3）掌握队列先进先出运算原则在解决实际问题中的应用。 （4）掌握递归程序设计的特点和编程方法。二、二、实验要求：实验要求：（1）熟练掌握栈和队列的基本运行及其操作。 （2）理解实训案例的算法，掌握线栈和队列在实际中的运用。 （3）将上机程序全部调试通过。 （4）独立完成一个至两个实训项目，保存程序运行结果，并结合程序进行分析。三、实验内容：三、实验内容：（1）任意输入一个字符串，按反序输出。要求字符串从键盘随

2、机输入，字符长 度不做具体限制。实现时，以链栈为手段。 （2）设计一个算法，判定一个字符串是否是对称字符串。若是，则返回 1，否 则返回 0。 （3）括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其 符号是否匹配。若匹配，则返回 1；否则返回 0。 （4）编写递归和非递归程序，计算下列表达式的值1 n=02x n=1 xpnn1 xpnxxpnn21122（5） 舞伴问题。假设在周末舞会上，男士和女士各自组成一排，跳舞开始的 时候，依次从男队和女队上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队 中未匹配对者等待下一轮舞曲。现要求写一篇算法模拟上述舞伴配对的问题。4、程

3、序代码：程序代码：1 #include #include typedef char ElemType; typedef struct snode ElemType data;struct snode *next; LinkSTACK; void InitStack(LinkSTACK *top) *top=(LinkSTACK *)malloc(sizeof(LinkSTACK); (*top)-next=NULL; int push(LinkSTACK *top,ElemType x)2 LinkSTACK *s; s=(LinkSTACK *)malloc(sizeof(LinkSTACK

4、); 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; LinkSTAC

5、K *top; InitStack( printf(“请输入一字串“); while(ch=getchar()!=n) push( printf(“n“); while(!Empty( printf(“%c“,ch); 2 #include #include #define MAXSIZE 40 typedef char ElemType; typedef struct ElemType dataMAXSIZE; int top;3STACK; void InitStack(STACK *S) S-top=-1; int Push(STACK *S,ElemType x) if(S-top=M

6、AXSIZE-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( printf(“请输入一字串:“

7、); gets(str); len=strlen(str); for(i=0;i4#include #define MAXSIZE 40 typedef 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 Em

8、pty(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 break;case ):case :case :pop(if(ch!=expspos) yesmatch=0;break; pos+; 5return (yesm

9、atch main() char str100;int yesmatch;printf(“请输入一字串：“);gets(str);yesmatch=match(str);if(yesmatch)printf(“是匹配是字串！“);elseprintf(“不是匹配的字串！“); 4 #include double 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 40 typedef stru

10、ct int n;int x;ElemType; typedef struct ElemType 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( for(i=n;i=2,i-) st.top+;6st.datast.top.n=i; while(top=0) st.datast.,top.x=2*x*f2-2*(st.datast.top.n-1)*f1;

11、 f1=f2; f2=st.datast.top.x; st.top-; return f2; main() int n; double x; printf(“请输入 n 与 x 的值：“); scanf(“%d%f“, printf(“n 表达式值为%1f:“,p(n,x); 5 #include typedef structchar name20;char sex; ElemType; typedef struct qnodeElemtype data;struct qnode *next;QTYPE; typedef struct qptrQTYPE *front,*rear;int c

12、ount;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;7LQ-rear-next=s; LQ-count+; return 1; int Empty(SQUEUE *LQ) retu

13、rn(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

14、 Queue is free!“);return 0; *x=LQ-front-next-data;return 1; void DancePartner() FILE *fp;ElemType p;SQUEUE mdancer, fdancer;InitQueue(InitQueue(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,p.name);8if(p.sex=F)EnQueue(

15、elseEnQueue( printf(“舞伴是：n“); while(!Empty(printf(“%s“,p.name);OutQueue(printf(“%s“,p.name); if(!Empty(GetHead(printf(“%s will be the first to get a partner.n“,p,name); else if(!Empty(mdancer)printf(“n 还有%d 个男士等下一轮。n“,dmancer.count);GetHead(printf(“%s 将得到第一个舞伴n“,p.name); 5、实验结果：9106、通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而 C 语言是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象