1、淮海工学院计算机科学系实 验 报 告 书课 程 名 ： 数据结构 题 目： 线性数据结构实验 （栈与对立队列及其应用）班 级： 学 号： 2012122693 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 1 -线性表算法实现与应用报告要求1 目的与要求:1）掌握栈与队列的数据类型描述及特点；2）掌握栈的顺序和链式存储存表示与基本算法的实现；3）掌握队列的链式和循环存储表示与基本操作算法实现;4) 掌握栈与队列在实际问题中的应用和基本编程技巧;5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数的运行过程抓获相关屏面验证程序设计的正确
2、性；7）由于国庆节占用授课时间，所以本次实验将不做统一上机安排，要求同学们节日期间自行完成实验任务，并于第 6 周周 4 以前按时提交实验报告。2 实验内容或题目（一）必做题：1、实现顺序栈的创建（初始化） 、压入（插入） 、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等） ，并给出栈的每次操作变化状态；2、实现链栈的创建（初始化） 、压入（插入） 、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等） ，要求给出栈的操作变化过程；3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等） ，并实时给出队列的操作变化状态；4、实现链式队列的创建、进队
3、、出队等基本操作（数据元素类型自己选取，如整型、字符型等） ，并实时给出队列的操作变化状态；（二）选做题（视自己能力而定，数量不限）：任选一个或多个源程序（已经发给学委） ，并阅读、调试和运行程序，而后给出程序功能分析和实例运行演示；1、实现表达式求值算法程序；2、用递归算法实现汉诺塔问题算法程序；3、使用循环队列实现打印杨辉三角形算法程序。3 实验步骤与源程序第一题：#include #include #define TRUE 1#define FALSE 0#define Size 50typedef structint elemSize; int top; SeqStack; 数据结构
4、实验报告 - 2 -void InitStack(SeqStack *S)S-top =-1;int IsEmpty(SeqStack *S)return(S-top=-1?TRUE:FALSE);/判断栈空 为空是真 反之为假int IsFull(SeqStack *S)return(S-top=Size-1?TRUE:FALSE);/判断栈满 为满是真 反之为假int Push(SeqStack *S,int x)/压栈if(S-top=Size-1) return(FALSE); S-top+;S-elemS-top = x;return(TRUE);int Pop(SeqStack *
5、S,int *x)/弹出 if(S-top = -1) return(FALSE);else*x = S-elemS-top;S-top-; return(TRUE);void main()SeqStack S;int x,y,i,l; 数据结构 实验报告 - 3 -InitStack(if(!IsFull(printf(“输入要压入的元素个数（50 以内）:n“);scanf(“%d“,printf(“输入要压入的元素：n“);for(i=0;i#include typedef struct nodeint data;struct node *next;LinkStackNode;typed
6、ef LinkStackNode *LinkStack;int IsEmpty(LinkStack S)return NULL=S-next?TRUE:FALSE;int InitStack(LinkStack *S)*S=(node*)malloc(sizeof(node);if(NULL=*S)return FALSE;(*S)-next =NULL;return TRUE; 数据结构 实验报告 - 4 -int Push(LinkStack S, int x)LinkStackNode *temp;temp=(LinkStackNode *)malloc(sizeof(LinkStack
7、Node);if(temp=NULL) return(FALSE); temp-data=x;temp-next=S-next;S-next=temp; return(TRUE);int Pop(LinkStack S, int *x) LinkStackNode * temp;temp=S-next;if(temp=NULL) return(FALSE);S-next=temp-next;*x=temp-data;free(temp); return(TRUE);void main()LinkStackNode *s;InitStack(int x,i,l;if(IsEmpty(s)prin
8、tf(“栈空 n“);printf(“请输入压入元素个数(50 以内)：n“);scanf(“%d“,printf(“请输入压入元素：n“);for(i=0;i#include #define TRUE 1#define FALSE 0#define MAXSIZE 50 typedef struct int elementMAXSIZE; int front; int rear; SeqQueue;void InitQueue(SeqQueue *Q) Q-front=Q-rear=0;int EnterQueue(SeqQueue *Q, int x) if(Q-rear+1)%MAXSI
9、ZE=Q-front) return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; return(TRUE); int DeleteQueue(SeqQueue *Q, int *x) if(Q-front=Q-rear) return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; return(TRUE); int IsEmpty(SeqQueue *Q) if(Q-front=Q-rear) return(TRUE); 数据结构 实验报告 - 6 -elseretur
10、n(FALSE); void main()SeqQueue s;InitQueue(int x,i,l;if(IsEmpty (printf(“请输入进队元素个数n“);scanf(“%d“,printf(“请输入元素n“);for(i=0;i#include #define TRUE 1#define FALSE 0typedef struct Nodeint data;struct Node *next;LinkQueueNode;typedef structLinkQueueNode *front ;LinkQueueNode *rear;LinkQueue;int IsEmpty(Li
11、nkQueue *Q)return Q-front =Q-rear?TRUE:FALSE; 数据结构 实验报告 - 7 -int InitQueue(LinkQueue *Q)Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);if(Q-front!=NULL)Q-rear=Q-front;Q-front-next=NULL;return (TRUE);else return(FALSE);int EnterQueue(LinkQueue *Q,int x)LinkQueueNode *NewNode;NewNode=(LinkQueue
12、Node *)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL)NewNode-data=x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;return (TRUE);else return(FALSE);int DeleteQueue(LinkQueue *Q,int *x)LinkQueueNode *p;if(Q-front=Q-rear)return(FALSE);p=Q-front-next ;Q-front-next =p-next ;if(Q-rear=p)Q-rear=Q-fr
13、ont;*x=p-data;free(p);return (TRUE);void main()LinkQueue q; 数据结构 实验报告 - 8 -int x,i,l;InitQueue(if(IsEmpty(printf(“请输入进队元个数素n“);scanf(“%d“,printf(“请输入元素：n“);for(i=0;il;i+)scanf(“%d“,EnterQueue(printf(“出队：n“);for(i=0;il;i+)DeleteQueue(printf(“%dn“,x);if(IsEmpty(4 测试数据与实验结果（可以抓图粘贴） 数据结构 实验报告 - 9 -5 结果分析与实验体会
