1、淮海工学院数据结构第二次实验淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 线性数据结构实验 （栈与队列及其应用）班 级： 软嵌151 学 号： 2015123352 姓 名： 韩吉 线性表算法实现与应用报告要求1目的与要求:1）掌握栈与队列的数据类型描述及特点；2）掌握栈的顺序和链式存储存表示与基本算法的实现；3）掌握队列的链式和循环存储表示与基本操作算法实现;4) 掌握栈与队列在实际问题中的应用和基本编程技巧;5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例的运行过程抓获相关屏面验证程序设计的正确性；7）希望大家过一个丰富多彩的国庆节，抽出一定时间圆满
2、完成实验，并于第6周周二以前按时提交实验报告，逾期按照旷交处理。2 实验内容或题目（一）必做题：1、实现顺序栈的创建（初始化）、压入（插入）操作（数据、弹出（删除）元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并给出栈的每次操作变化状态；2、实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），要求给出栈的操作变化过程；3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并实时给出队列的操作变化状态；4、实现链式队列的创建、进队、出队等基
3、本操作（数据元素类型自己选取，如整型、字符型等，或参照书上算法选取数据类型），并实时给出队列的操作变化状态；（注意：必做题需用一个主程序实现所有功能）（二）选做题（视自己能力而定，数量不限）：任选下列一个或多个栈或队列应用源程序（已经发给学委），并阅读、调试和运行程序，而后给出程序功能分析和实例运行演示；1、实现表达式求值算法程序；2、用递归算法实现汉诺塔问题算法程序；3、使用循环队列实现打印杨辉三角形算法程序。3 实验步骤与源程序#include#include#include #define TRUE 1#define FALSE 0#define Stack_Size 50#define
4、 MAXSIZE 5 void mainmenu();/*/*顺序栈*/typedef struct int elemStack_Size; int top;SeqStack;/*链栈*/typedef struct node int data; struct node *next;LinkStackNode;/*循环队列*/typedef struct int elementMAXSIZE; int front; int rear;SeqQueue;/*链式队列*/typedef struct Node int data; struct Node *next;LinkQueueNode;ty
5、pedef struct LinkQueueNode *front; LinkQueueNode *rear;LinkQueue;/*/*顺序栈*/*构造一个空栈S*/void InitStack(SeqStack *S) S-top = -1;/*进栈*/int Push(SeqStack *S,int x) if(S-top=(Stack_Size-1) return(FALSE); /*栈已满*/ S-top+; S-elemS-top=x; return(TRUE);/*出栈*/int Pop(SeqStack *S,int *x) /* 将栈S的栈顶元素弹出，放到x所指的存储空间中
6、*/ if(S-top=-1) /*栈为空*/ return(FALSE); else *x=S-elemS-top; S-top-; /* 修改栈顶指针 */ return(TRUE); /*取栈顶元素*/int GetTop(SeqStack *S, int *x) /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */ if(S-top=-1) /*栈为空*/ return(FALSE); else *x = S-elemS-top; return(TRUE); /*/*链栈*/*初始化*/void InitStack1(LinkStackNode *top) /构
7、造一个空栈 top = (LinkStackNode *)malloc(sizeof(LinkStackNode); if(!top) printf(OVERFLOWn); top = NULL; /*进栈操作。*/int Push1(LinkStackNode *top, int x)/* 将数据元素x压入栈top中 */ LinkStackNode *temp; temp=(LinkStackNode *)malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE); /* 申请空间失败 */ temp-data=x; temp-nex
8、t=top-next; top-next=temp; /* 修改当前栈顶指针 */ return(TRUE);/*出栈操作。*/int Pop1(LinkStackNode *top, int *x) /* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */ LinkStackNode * temp; temp=top-next; if(temp=NULL) /*栈为空*/ return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 释放存储空间 */ return(TRUE);/*/*循环队列*/void InitQue
9、ue(SeqQueue *Q) /* 将*Q初始化为一个空的循环队列 */ Q-front=Q-rear=0;int EnterQueue(SeqQueue *Q,int x) /*将元素x入队*/ if(Q-rear+1)%MAXSIZE=Q-front) /*队列已经满了*/ return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return(TRUE); /*操作成功*/int DeleteQueue(SeqQueue *Q,int *x) /*删除队列的队头元素，用x返回其值*/ if(Q
10、-front=Q-rear) /*队列为空*/ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/ return(TRUE); /*操作成功*/*/*链式队列*/int InitQueue1(LinkQueue *O) /* 将Q初始化为一个空的链队列 */ O-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(O-front!=NULL) O-rear=O-front; O-front-next=NULL; return(TRU
11、E); else return(FALSE); /* 溢出！*/int EnterQueue1(LinkQueue *O,int x) /* 将数据元素x插入到队列Q中 */ LinkQueueNode *NewNode; NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(NewNode!=NULL) NewNode-data=x; NewNode-next=NULL; O-rear-next=NewNode; O-rear=NewNode; return(TRUE); else return(FALSE); /* 溢出！*/i
12、nt DeleteQueue1(LinkQueue *O, int *x) /* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */ LinkQueueNode *p; if(O-front=O-rear) return(FALSE); p=O-front-next; O-front-next=p-next; /* 队头元素p出队 */ if(O-rear=p) /* 如果队中只有一个元素p，则p出队后成为空队 */ O-rear=O-front; *x=p-data; free(p); /* 释放存储空间 */ return(TRUE); /*/void mainmenu1() int
13、 chioce; int m; int x1, x2; SeqStack s; while(chioce) printf( * 请输入你的选择 *n); printf( * 1:初始化操作 *n); printf( * 2:进栈操作 *n); printf( * 3:出栈操作 *n); printf( * 4:取栈顶元素 *n); printf( * 5:返回主菜单 *n); printf(请输入你的选择:); scanf(%d, &chioce); switch(chioce) case 1: InitStack(&s); printf(初始化完成!n); break; case 2: pr
14、intf(输入进栈元素:); scanf(%d, &m); if(Push(&s,m) printf(进栈成功!n); else printf(栈已满!n); break; case 3: if(Pop(&s,&x1) printf(出栈元素:%dn, x1); else printf(栈为空!n); break; case 4: if(GetTop(&s,&x2) printf(栈顶元素:%dn, x2); else printf(栈为空!n); break; case 5: printf(nnnn); system(cls); mainmenu(); break; default: pri
15、ntf(输入有误!n); for(int i = 2; i 0; i-) printf(请等待%d秒后重新输入!n,i); Sleep(1000); system(cls); mainmenu1(); break; void mainmenu2() int chioce2; int x; int x1; LinkStackNode top; while(chioce2) printf( * 请输入你的选择 *n); printf( * 1:初始化操作 *n); printf( * 2:进栈操作 *n); printf( * 3:出栈操作 *n); printf( * 4:返回主菜单 *n);
16、printf(请输入你的选择:); scanf(%d, &chioce2); switch(chioce2) case 1: InitStack1(&top); printf(初始化完成!n); break; case 2: printf(输入进栈元素:); scanf(%d, &x); if(Push1(&top,x) printf(进栈成功!n); else printf(栈已满!n); break; case 3: if(Pop1(&top,&x1) printf(出栈元素:%dn, x1); else printf(栈为空!n); break; case 4: printf(nnnn)
17、; system(cls); mainmenu(); break; default: printf(输入有误!n); for(int i = 2; i 0; i-) printf(请等待%d秒后重新输入!n,i); Sleep(1000); system(cls); mainmenu2(); break; void mainmenu3() int chioce3; int x; int x1; SeqQueue Q; while(chioce3) printf( * 请输入你的选择 *n); printf( * 1:初始化操作 *n); printf( * 2:进栈操作 *n); printf
18、( * 3:出栈操作 *n); printf( * 4:返回主菜单 *n); printf(请输入你的选择:); scanf(%d, &chioce3); switch(chioce3) case 1: InitQueue(&Q); printf(初始化完成!n); break; case 2: printf(输入进栈元素:); scanf(%d, &x); if(EnterQueue(&Q,x) printf(进栈成功!n); else printf(栈已满!n); break; case 3: if(DeleteQueue(&Q,&x1) printf(出栈元素:%dn, x1); els
19、e printf(栈为空!n); break; case 4: printf(nnnn); system(cls); mainmenu(); break; default: printf(输入有误!n); for(int i = 2; i 0; i-) printf(请等待%d秒后重新输入!n,i); Sleep(1000); system(cls); mainmenu3(); break; void mainmenu4() int chioce4; int x; int x1; LinkQueue O; while(chioce4) printf( * 请输入你的选择*n); printf(
20、 * 1:初始化操作 *n); printf( * 2:进栈操作 *n); printf( * 3:出栈操作 *n); printf( * 4:返回主菜单 *n); printf(请输入你的选择:); scanf(%d, &chioce4); switch(chioce4) case 1: InitQueue1(&O); printf(初始化完成!n); break; case 2: printf(输入进栈元素:); scanf(%d, &x); if(EnterQueue1(&O,x) printf(进栈成功!n); else printf(栈已满!n); break; case 3: if
21、(DeleteQueue1(&O,&x1) printf(出栈元素:%dn, x1); else printf(栈为空!n); break; case 4: printf(nnnn); system(cls); mainmenu(); break; default: printf(输入有误!n); for(int i = 2; i 0; i-) printf(请等待%d秒后重新输入!n,i); Sleep(1000); system(cls); mainmenu4(); break; void mainmenu() int chioce1; printf(* 主菜单 * n); printf(
22、 * 1:顺序栈操作 * n); printf( * 2:链栈操作 * n); printf( * 3:循环队列 * n); printf( * 4:链式队列 * n); printf( * 0:退出操作 * n); printf(请输入你的选择:); scanf(%d, &chioce1); switch(chioce1) case 1: mainmenu1(); break; case 2: mainmenu2(); break; case 3: mainmenu3(); break; case 4: mainmenu4(); system(cls); break; case 0: exit(0); break; default: printf(输入有误!n); for(int i = 3; i 0; i-) printf(请等待%d秒后重新输入!n,i); Sleep(1000); system(cls); mainmenu(); break; void main() system(color 0); system(color bc); mainmenu();杨辉三角:#include seq
