《栈与对立队列及其应用》由会员分享，可在线阅读，更多相关《栈与对立队列及其应用（10页珍藏版）》请在金锄头文库上搜索。
1、淮海工学院计算机科学系实验报告书课 程 名： 数据结构 题 目： 线性数据结构实验 （栈与对立队列及其应用）班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 1 -线性表算法实现与应用报告要求1 目的与要求:1）掌握栈与队列的数据类型描述及特点；2）掌握栈的顺序和链式存储存表示与基本算法的实现；3）掌握队列的链式和循环存储表示与基本操作算法实现;4) 掌握栈与队列在实际问题中的应用和基本编程技巧;5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数的运行过程抓获相关屏面验证程序设计的正确性；7）由于国庆节占用授课时间，
2、所以本次实验将不做统一上机安排，要求同学们节日期间自行完成实验任务，并于第 6 周周 4 以前按时提交实验报告。2 实验内容或题目 （一）必做题：（一）必做题： 1、实现顺序栈的创建（初始化） 、压入（插入） 、弹出（删除）操作（数据元素类型自己选取， 如整型、字符型等） ，并给出栈的每次操作变化状态； 2、实现链栈的创建（初始化） 、压入（插入） 、弹出（删除）操作（数据元素类型自己选取， 如整型、字符型等） ，要求给出栈的操作变化过程； 3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型 等） ，并实时给出队列的操作变化状态； 4、实现链式队列的创建、进队、
3、出队等基本操作（数据元素类型自己选取，如整型、字符型 等） ，并实时给出队列的操作变化状态； （二）选做题（视自己能力而定，数量不限）：任选一个或多个源程序（已经发给学委）（二）选做题（视自己能力而定，数量不限）：任选一个或多个源程序（已经发给学委） ，并，并 阅读、调试和运行程序，而后给出程序功能分析和实例运行演示；阅读、调试和运行程序，而后给出程序功能分析和实例运行演示； 1、实现表达式求值算法程序； 2、用递归算法实现汉诺塔问题算法程序； 3、使用循环队列实现打印杨辉三角形算法程序。3 实验步骤与源程序(一)、1：#include “stdio.h“ #include “stdlib.h
4、“ #include “malloc.h“ #define TURE 1 #define FALSE 0 #define Stack_Size 25 typedef int StackElementType; typedef struct StackElementType elemStack_Size; int top; 数据结构 实验报告 - 2 -SeqStack; void InitStack(SeqStack *S) S-top=-1; int Push(SeqStack *S,StackElementType x) if(S-top=Stack_Size-1)return(FALSE
5、); S-top+; S-elemS-top=x; return(TURE); int Pop(SeqStack *S,StackElementType x) if(S-top=-1) return(FALSE); else x=S-elemS-top; S-top-; return(TURE); void main() SeqStack *S; int r,t; int i; S=(SeqStack*)malloc(sizeof(SeqStack); printf(“请输入栈的长度：“);scanf(“%d“, S-top=r-1; printf(“n 请输入栈中的个元素值：n“);for(
6、i=0;itop;i+) scanf(“ %d“, printf(“n 请输入要插入的元素值：“);scanf(“ %d“, Push(S,t);printf(“n 插入后的栈：n“);for(i=0;itop;i+) printf(“ %d“,S-elemi); Pop(S,t); printf(“n 删除后的栈：n“);for(i=0;itop;i+) printf(“ %d“,S-elemi); printf(“n“); 数据结构 实验报告 - 3 - （一） 、2：#include“stdio.h“ #include“stdlib.h“ #include“malloc.h“ #defi
7、ne TRUE 1 #define FALSE 0 typedef int StackElementType; typedef struct node StackElementType data; struct node *next; LinkStackNode; typedef LinkStackNode *LinkStack; void init_list(LinkStackNode *l) /*栈初始化*/ l=(LinkStackNode*)malloc(sizeof(node);l-next=NULL; int Push(LinkStack top,StackElementType
8、x) /*进栈*/ LinkStackNode *temp; temp=(LinkStackNode*)malloc(sizeof(LinkStackNode); if(temp=NULL) printf(“申请空间失败！“);return(FALSE); else temp-data=x; temp-next=top-next; top-next=temp; return(TRUE); int Pop(LinkStack top,StackElementType *x) /*出栈*/ LinkStackNode *temp;temp=top-next; if(temp=NULL) print
9、f(“栈为空！“);return(FALSE); else 数据结构 实验报告 - 4 - top-next=temp-next; *x=temp-data; free(temp); return(TRUE); int GetTop(LinkStack top,StackElementType *x)/*获取栈顶元素*/ if(top-next=NULL) printf(“栈为空！“);return(FALSE); else *x=top-next-data; return(TRUE); void main() LinkStackNode *top; LinkStackNode l; int
10、*k; int i,p,r; top=(LinkStackNode*)malloc(sizeof(LinkStackNode); k=(int*)malloc(sizeof(int);init_list( printf(“请输入要进栈的元素的个数：“);scanf(“%d“, printf(“请输入要进栈的元素的值:“);for(i=0;i #include #include #define TRUE 1 #define FALSE 0 typedef int QueueElementType; #define MAXSIZE 25 typedef struct QueueElementTyp
11、e elementMAXSIZE; int front; int rear; SeqQueue; void InitQueue(SeqQueue *Q) Q-front=Q-rear=0; int EnterQueue(SeqQueue *Q,QueueElementType x) if(Q-rear+1)%MAXSIZE=Q-front) return(FALSE); Q-elementQ-rear+1=x; Q-rear=(Q-rear+1)%MAXSIZE; return(TRUE); int DeleteQueue(SeqQueue *Q) int x; x=Q-elementQ-fr
12、ont; Q-front=(Q-front+1)%MAXSIZE; printf(“删除：%dn“,x);return(TRUE); void main() SeqQueue *Q; int i,r,t; Q=(SeqQueue*)malloc(sizeof(SeqQueue); InitQueue(Q); printf(“请输入队列的长度：“);scanf(“ %d“, Q-rear=r-1; printf(“n 请输入队列中各元素的值：n“);for(i=0;irear;i+) scanf(“ %d“, 数据结构 实验报告 - 6 -printf(“n 请输入要插入的元素值：n“);sca
13、nf(“%d“, EnterQueue(Q,t); printf(“n 插入后的队列：n“);for(i=0;irear;i+) printf(“ %d“,Q-elementi);printf(“n 请输入要删除的元素个数:“);scanf(“ %d“, for(i=0;ifront=Q-rear=0; int EnterQueue(SeqQueue *Q, int x) if(Q-rear+1)%MAXSIZE=Q-front) return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; return(TRUE); int Del
14、eteQueue(SeqQueue *Q, QueueElementType *x) if(Q-front=Q-rear) return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; 数据结构 实验报告 - 7 -return(TRUE); int GetHead(SeqQueue *Q, int *x) if(Q-front=Q-rear) return(FALSE); *x=Q-elementQ-front; return(TRUE); void main() SeqQueue s;InitQueue( int i,n; printf(“请输入元素值：n“);for(i=0;i%cn“,*count,a,c); fprintf(*fp,“%6d:%c%cn“,*count,a,c); hanoi(int n, char a, char b, char c, FILE *fp, int *count) if(n=1) move(a,c,fp,count); else hanoi(n-1,a,c,b,fp,count); move(a,c,fp,count); 数据结构 实验报告 - 8 -hanoi(n-1,b,a,c,fp,count);
