《数据结构第三章实验报告》由会员分享，可在线阅读，更多相关《数据结构第三章实验报告（23页珍藏版）》请在金锄头文库上搜索。
1、1.问题描述（1）顺序栈 顺序栈的 C 语言描述 基本运算的算法置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满（2）链栈 链栈的 C 语言描述 基本运算的算法置空栈、判栈空、进栈、出栈、读栈顶（3）循环队列 循环队列的 C 语言描述 基本运算的算法置空队、判队空、进队、出队、读队头元素、输出循环队列（4）链队列 链队列的 C 语言描述 基本运算的算法置空队、判队空、进队、出队、读队头元素2.数据结构设计（1）顺序栈要实现顺序栈操作，我们需要一个栈顶指针一个栈底指针，以及说明当前已经分配的存储空间（即当前可使用的最大容量） ，因此结构中需要定义这三个部分typedef structchar
2、*base;char *top;int stacksize;Sq;（2）链栈对于链栈，每一个人节点需要有 data 域和 next 域，分别储存数据以及指向下一个节点，下一个节点也应该是拥有这两个域，所以用到嵌套定义来定义节点的数据结构typedef struct node char data;struct node *next;node;（3）循环队列对于循环队列，需要有头尾指针指向队列头元素和尾元素的下一个位置，所以我们定义 front，rear 指针，为了说明动态分配的存储空间，我们定义了base，这就是循环队列的存储结构typedef struct int *base;int fron
3、t;int rear;SqQueue;（4）链队列根据要求可知，我们运用单链队列即可实现所需要的功能，对于单链队列，我们需要两个指针作为队头队尾指针从而实现队列的操作，所以定义front，rear。对于每一个节点都有 data 和 next 域来存储数据和指向下一个节点，所以进行这种节点定义。typedef struct QNode int data;QNode *next;QNode,*QPtr;typedef struct QlinkQPtr front;QPtr rear;Qlink;3.算法设计(1)顺序栈系统规定的功能设计的算法有：置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满1
4、】初始化和建立顺序栈1）定义数据结构类型typedef structchar *base;char *top;int stacksize;Sq;2）初始化顺序栈 int InitSq(Sq&S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(Sq);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; 3）创建顺序栈Sq create(Sq &S)InitSq(S);printf(请输入你的栈:n);char str100;gets(str);int
5、n=strlen(str);for(int i=0;i=S.stacksize)S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit (OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;int GetTop(Sq S,char &e)if(S.top=S.base) return ERROR;e=*(S.top-1);return e;int Pop(Sq&S
6、,char e)if(S.top=S.base)return ERROR;e=*-S.top;return e;int Clear(Sq&S)while(S.top!=S.base)char e;Pop(S,e);return OK;int Empty(Sq S)if(S.top=S.base)return OK;else return ERROR;int Print(Sq S)char *p,*q;p=S.top;q=S.base;if(p=q) return ERROR;while(p!=q)printf(%cn,*(p-1);p-;return OK;int T(Sq S) if(S.t
7、op-S.base=S.stacksize)return OK;elsereturn ERROR;(2)链栈系统规定的功能设计的算法有置空栈、判栈空、进栈、出栈、读栈顶。1】定义节点、初始化链栈、创建链栈1）定义节点typedef struct node char data;struct node *next;node;2）初始化链栈int Init(node* &h) h-next=NULL;return OK;3）创建链栈int Set(node* &h) int i;printf(请输入你的栈:n);char str100;gets(str);int n=strlen(str);for(
8、i=0;inext=NULL) return OK;else return FALSE;int Push(node* &h,char x) node *s;s=(node*)malloc(sizeof(node);s-data=x;s-next=h;h=s;return OK;int Pop(node* &h) char x;x=h-data;node *p;p=(node*)malloc(sizeof(node);p=h;h=h-next;free(p);return OK;int Gethead(node* &h,char a) if(h-next=NULL)return FALSE ;a
9、=h-data;printf(栈顶元素是:%cn,a);return OK;int Clear(node* &h) h-next=NULL;return OK;(3)循环队列系统规定的功能设计的算法有置空队、判队空、进队、出队、读队头元素、输出循环队列。1】初始化和建立队列1）定义结构体typedef struct int *base;int front;int rear;SqQueue;2）初始化队列int Init(SqQueue &Q)Q.base=(int *)malloc(MAXQSIZE*sizeof(int);if(!Q.base)return (OVERFLOW);Q.fron
10、t=Q.rear=0;return OK;3）建立队列int Set(SqQueue &Q) int i;Init(Q);char str100;printf(请输入队列:n);gets(str);int n=strlen(str);for(i=0;inext=NULL;return OK;3）建立空队列Qlink Setqueue(Qlink &Q)int i; Initqueue(Q);QPtr p;printf(请输入你的队列n);char str100;gets(str);int n=strlen(str);for(i=0;idata=stri;p-next=NULL;Q.rear-n
11、ext=p;Q.rear=p;return Q;2】以下操作依次是置空队、判队空、进队、出队、读队头元素。int Clear(Qlink &Q) Q.front=Q.rear;return OK;int Empty(Qlink &Q)if(Q.front=Q.rear)return TRUE;elsereturn FALSE;int En(Qlink &Q,char e) QPtr p;p=(QPtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW); p-data=e;p-next=NULL;Q.rear-next=p;p-next=Q.rear-next-
12、next;Q.rear=p;return OK;int De(Qlink &Q,char &e)if(Q.front=Q.rear)printf(队列为空n);return FALSE; QPtr p;p=(QPtr)malloc(sizeof(QNode);p=Q.front-next;Q.front=Q.front-next;e=p-data;printf(出队的元素是:%cn,e);return OK;int Gethead(Qlink Q,char &n)if(Q.front=Q.rear)return FALSE;n=Q.front-next-data;return OK;4、界面设
13、计顺序栈、链栈、循环队列、链队列的界面设计依次为5、运行与测试1）顺序栈2）链栈3）循环队列4）链队列6、实验收获与思考本次实验难度较大，所以我选择的验证性实验。通过验证性实验，我对一些基本操作更加熟悉了，本次收获虽然不太大，但是也锻炼了动手能力。7、源代码1）顺序栈#include #include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -1#define N 100typedef structchar *base;cha
14、r *top;int stacksize;Sq;int InitSq(Sq&S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(Sq);if(!S.base)exit(OVERFLOW); S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int Push(Sq&S,char e)if(S.top-S.base=S.stacksize)S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) e
15、xit (OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Sq create(Sq &S)InitSq(S);printf(请输入你的栈:n);char str100;gets(str);int n=strlen(str);for(int i=0;i=S.stacksize)return OK;elsereturn ERROR;int main() Sq S;create(S);int m;char a,x;printf(选择你想要的功能n);printf(1 置空栈n2 判断栈空n3 进栈n4 出栈n5 读栈顶n6 输出栈n7判栈满n);while(1)printf(选择你想要的功能n);scanf(%d,getchar();switch(m)case 1:Clear(S);printf(Emptyn);break;case 2:if(Empty(S) printf(Emptyn);else printf(NotEmptyn);break;case 3:printf(进栈元素是:);scan
