数据结构课程设计.doc

桂林航天工业学院实验报告系（部）： 计算机科学与工程系 课程名称: 数据结构 专业班级: 计算机应用技术1班 学 号: 学生姓名: 完成日期： 2016年12月22日一、 运行环境操作系统：Windows10 64位操作系统编译软件：Microsoft Visual C+ 6.0处理器：Intel（R）Core（TM）2 CPU 6320 1.86GHz 1.86GHz安装内存（RAM）：2.00GB二、 算法设计的思想和设计分析及流程图1.线性表的顺序存储1插入：算法思想：查找到元素X需要插入到线性表L的位置i，将该位置i后面的元素后移，将要元素X插入到i位置，表长加1。设计分析：先使用if(L-last=MAXSIZE1-1)提示空间满else if(iL-last+2)提示位置错误函数判断位置i在该线性表L中是否存在，若位置i正确再使用for(j=L-last;j=i-1;j-)L-dataj+1=L-dataj;使该位置i后面的数据元素后移，然后将数据元素插入到位置i，表长加1。流程图：2删除：算法思想：先判断线性表L是否存在数据元素i，然后在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,., n 的元素变为序号为 i, i+1,.,n-1，删除后新表长=原表长-1。设计分析：先使用if(iL-last+1)提示数据元素不存在判断元素i在线性表L中是否存在，若数据元素i存在再使用for(j=i;jlast;j+)L-dataj-1=L-dataj;L-last-;使数据元素i后面的数据元素前移，将数据元素i覆盖删除，然后表长减1。流程图：3查找：算法思想：调用函数查找数据元素i，如果其调用函数结果返回在线性表L中首次出现的值为i的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为的数据元素，返回某特殊值表示查找失败。设计分析：先使用while(ylast & L-datay!=x)y+;查找数据元素i在线性表L中的位置，如果查找失败则使用if(yL-last)return -1;返回特殊值，否则使用else return y+1;返回该数据元素的地址。流程图：4Main主函数：算法思想：使用Dowhile实现主函数的菜单界面，使用switchcase实现函数的调用。 设计分析：使用dowhile做出主菜单，使用scanf(%d,&k);getchar();switch(k)case 1: case 2: case 3: case 4: case 5:实现函数的调用。2. 线性表的链式存储1建表：算法思想：使用头插入法建立单链表，该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 设计分析： 使用p=(LNode2*)malloc(sizeof(LNode2);开辟一个动态空间使用p-data=c; p-next=head;进行赋值和使指针后移，再用head=p;使head与p同指向。流程图：2按序号查找：算法思想：调用函数查找数据元素i，从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点。设计分析： 使用while(p-next & jnext; j+;进行地址和指针后移，再用if (i=j) return p; else return NULL;返回查找结果。流程图：3插入：算法思想：插入运算是将值为x的新结点插入到表的第i个结点的位置上首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*q，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。设计分析： 使用p=Get_LinkList(L,i-1);if(p=NULL)printf(位置错误);return 0;判断i的是否存在，若存在，则使用q=(LNode*)malloc(sizeof(LNode);q-data=x;q-next=p-next;p-next=q;进行插入，再用return 1返回插入结果。流程图：4删除：算法思想：将表的第i个结点删去，是在单链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。设计分析： 使用p=Get_LinkList(L,i-1); if(p-next=NULL)return 0;判断i的是否存在，若存在，则使用q=p-next;p-next=q-next;free(q);进行删除和释放，再用return 1返回删除结果。流程图：5Main主函数：算法思想：使用Dowhile实现主函数的菜单界面，使用ifelse实现函数的调用。 设计分析：使用dowhile做出主菜单，使用scanf(%d,&k);getchar();if (k=1)else if (k=2)else if (k=3)实现函数的调用。3. 栈的应用1置空栈：算法思想：使链栈的头指针指向空。设计分析：使用top=NULL; 将头指针赋值为空。流程图：2链式进栈：算法思想：在栈顶插入新的元素，先使栈顶指针top加1，再给top赋值设计分析：使用p=(LinkStack3)malloc(sizeof(StackNode3);建立新结点，使用p-data =x; p-next=top; top=p;实现栈顶top的加1和赋值。 流程图：3链式入栈：算法思想：先使栈顶指针top减1，再释放删除的数据i。设计分析：使用*x=top-data ; p=top; top=top-next ; free(p);实现栈顶top的减1和释放。 流程图：4Main主函数：算法思想：使用Dowhile实现主函数的菜单界面，使用switchcase实现函数的调用。 设计分析：使用dowhile做出主菜单，使用scanf(%d,&k);getchar();switch(k)case 1: case 2: case 3: case 4: case 5:实现函数的调用。4. 队列的应用1置空队：算法思想：对头指针front和队尾指针rear指向同一个位置设计分析：使用Q-rear=Q-front=T; T-next=NULL 将头指针front和队尾指针rear指向同一个位置T，再把T的next指向NULL。流程图：2进队列：算法思想：入队时将新元素插入队尾指针rear所指的位置，然后将队尾指针rear加设计分析：使用p-data=x；新元素插入队列，再使用p-next=NULL; Q-rear-next=p; Q-rear=p; rear指针加1 流程图：3出队列：算法思想：出队时先判断元素是否存在，若存在则将队尾指针rear减，再释放元素。设计分析：使用if(queueempty(Q) 判断元素是否存在，若存在再使用p=Q-front; x=p-next-data; Q-front=p-next;free(p); 将队尾指针rear减和释放元素。流程图：4Main主函数：算法思想：使用Dowhile实现主函数的菜单界面，使用switchcase实现函数的调用。 设计分析：使用dowhile做出主菜单，使用scanf(%d,&k);getchar();switch(k)case 1: case 2: case 3: case 4: case 5:实现函数的调用。5. 二叉树的遍历和应用1建二叉树算法思想：对一般的二叉树，首先添加若干个虚结点，使其成为完全二叉树，然后依次输入结点信息，若输入结点非虚结点，则建立一个新结点；若是第一个则令其为根结点，否则将新结点链接到它的双亲结点上。如此反复直到输入结束信息为止。设计分析：使用scanf(%d,&x);if (x=0) 判断输入结点结束，再使用T=(BTree5 *)malloc(sizeof(BTree5) ;T-data=x;printf( 请输入 %d 结点的左孩子：,T-data);T-LChild=CreatBTree();printf( 请输入 %d 结点的右孩子：,T-data);T-RChild=CreatBTree();二叉树的前序遍历的递归算法建立二叉树。流程图：2前序递归遍历二叉树算法思想：访问根结点，先序遍历左子树，先序遍历右子树。设计分析：使用printf(%d ,T-data); 访问根结点 使用PreOrder(T-LChild) ; 递归遍历左子树 使用PreOrder(T-RChild) ; 递归遍历右子树流程图：3中序递归遍历二叉树算法思想：中序遍历左子数，访问根节点，中序遍历右子树设计分析：使用InOrder(T-LChild) ; 递归遍历左子树 使用printf(%d ,T-data); 访问根结点 使用InOrder(T-RChild) ; 递归遍历右子树流程图：4后序递归遍历二叉树算法思想：后序遍历左子树，访问根节点，后序遍历右子树设计分析：使用postOrder(T-LChild) ; 递归遍历左子树 使用postOrder(T-RChild) ; 访问根结点 使用printf(%d ,T-data); 递归遍历右子树流程图：5Main主函数：算法思想：使用Dowhile实现主函数的菜单界面，使用ifelse实现函数的调用。 设计分析：使用dowhile做出主菜单，使用scanf(%d,&k);getchar();if (k=1)else if (k=2)else if (k=3)实现函数的调用。三、 源代码1. 一级菜单#include 实验1.c#include 实验2.c#include 实验3.c#include 实验4.c#include 实验5.cvoid main() int k; do printf(nnnn);printf(ttt 数据结构课程设计一级菜单n);printf(tt*n);printf(tt* 1-线性表的顺序存储 *n);printf(tt* 2-线性表的链式存储*n);printf(tt* 3-栈的应用 *n);printf(tt* 4-队列的应用 *n);printf(tt* 5-二叉树的遍历和应用*n);printf(tt* 0-返回 *n);printf(tt*n);printf(tt 请选择菜单项(05)：);scanf(%d,&k);getchar();switch(k)case 1: main1(); /线性表的顺序存储break; case 2: main2(); /线性表的链式存储break;case 3: main3(); /栈的应用break;case 4: main4(); /队列的应用break;case 5: main5(); /二叉树的遍历和应用break;while(k!=0);2. 实验1-线性表的顺序存储#include stdio.h#include malloc.h#define MAXSIZE1 200 /线性表允许的最大长度#define datatype1 inttypedef struct /定义线性表的结构 datatype1 dataMAXSIZE1; /表示线性表（a1，a2，.,an） int last; /last表示线性表的实际长度 SeqList1; /* 线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表 */SeqList1 *insert_SeqList( ) SeqList1 *L; L=(SeqList1 *)malloc(sizeof(SeqList1);/L=new SeqList; L-last=-1; return L;/* 插入操作：Insert_List(L,i,x)初始条件：线性表L存在，插入位置正确 (1=ilast=MAXSIZE1-1)printf(空间满);return 0; else if(iL-last+2)printf(位置错误);return 0;for(j=L-last;j=i-1;j-)L-dataj+1=L-dataj;L-datai-1=x;L-last+;return 1;/*删除操作：Delete_List(L,i)初始条件：线性表L存在，1=i=n。操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,., n 的元素变为序号为 i, i+1,.,n-1，删除后新表长原表长。 */int Delete_SeqList(SeqList1 *L,int i) int j; if(iL-last+1)printf(元素不存在);return 0;for(j=i;jlast;j+)L-dataj-1=L-dataj;L-last-;return 1;/*按值查找：Locate_List(L,x)，是给定的一个数据元素。初始条件：线性表L存在操作结果：在表L中查找值为的数据元素，其结果返回在L中首次出现的值为的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为的数据元素，返回一特殊值表示查找失败。*/int Location_SeqList(SeqList1 *L, datatype1 x) int y=0;while(ylast & L-datay!=x)y+;if(yL-last)return -1;else return y+1;void print1(SeqList1 *L) /打印线性表 int i; for (i=0;ilast;i+) printf(%d,L-datai); printf(n);void main1() SeqList1 *L; int i,j,k; datatype1 x; do printf(nnnn); printf(ttt 线性表子系统n);printf(tt*n);printf(tt* 1-初始化表 *n);printf(tt* 2-插 入*n);printf(tt* 3-删除*n);printf(tt* 4-查找*n);printf(tt* 5-显示*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(05)：);scanf(%d,&k);getchar();switch(k) case 1: L=insert_SeqList( ); /初始化线性表 break; case 2: /在线性表第i位置处插入值为X的元素printf(n 请输入插入的位置i和数据X(输入格式：i,X):);scanf(%d,%d,&i,&x); j=Insert_SeqList(L,i,x);if (j=1) printf(插入成功!);else printf(插入失败!);break; case 3: /删除线性表中值为X的元素 printf(n 请输入要删除元素的位置i:);scanf(%d,&i); j=Delete_SeqList(L,i);if (j = 1) printf(删除成功!);else printf(删除失败!);break; case 4: /查找线性表中元素值为x的位置printf(n 请输入要查找的数值X:);scanf(%d,&x); j=Location_SeqList(L,x);if (j != -1 ) print1(L);printf(中值为X所在的位置是 %d ,j);elseprintf(线性表中无此元素!n);break; case 5: /输出线性表 printf(n线性表的顺序存储为：); print1(L); while(k!=0);3. 实验2-线性表的链式存储#include stdio.h#include malloc.h#define datatype2 inttypedef struct node datatype2 data; /链表的数据域 struct node *next; /链表的指针域 LNode2,*LinkList2;LinkList2 Creat_LinkList1( ) /头插入法建立单链表算法 datatype2 c; LinkList2 head; LNode2 *p;head=NULL;printf(请输入数据); scanf(%d,&c); while (c!=0) p=(LNode2*)malloc(sizeof(LNode2); p-data=c; p-next=head; head=p; scanf(%d,&c); return head;/*按序号查找 Get_Linklist(L,i)在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/LNode2 *Get_LinkList(LinkList2 L,int i) int j;LNode2 *p; p=L;j=0; while(p-next & jnext; j+; if (i=j) return p; else return NULL;/*插入运算 Insert_LinkList(L,i,x)在单链表L的第i个位置上插入值为x的元素*/int Insert_LinkList(LinkList2 L,int i,datatype2 x) LNode2 *p,*q; p=Get_LinkList(L,i-1);if(p=NULL)printf(位置错误);return 0;elseq=(LNode2*)malloc(sizeof(LNode2);q-data=x;q-next=p-next;p-next=q;return 1;/*删除运算：Del_LinkList(L,i)删除单链表L上的第i个数据结点*/int Del_LinkList(LinkList2 L,int i) LNode2 *p,*q; p=Get_LinkList(L,i-1); if(p-next=NULL)return 0;elseq=p-next;p-next=q-next;free(q);return 1;void print2(LinkList2 L) /输出单链表 LNode2 *p=L; while(p-next!=NULL) printf(%d-,p-data); /输出表中非最后一个元素 p=p-next; printf(%dn,p-data); /输出表中最后一个元素 void main2() LNode2 *p;LinkList2 H; int i,j,k;datatype2 x;do printf(nnnn); printf(ttt 链表子系统n);printf(tt*n);printf(tt* 1-建 表 *n);printf(tt* 2-插 入*n);printf(tt* 3-删除*n);printf(tt* 4-查找*n);printf(tt* 5-显示*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(05)：);scanf(%d,&k);getchar();if (k=1) H=Creat_LinkList1( ); /用头插入法建立单链表else if (k=2) /在线性表第i位置处插入值为X的元素printf(n 请输入插入的位置i和数据X(输入格式：i,X):);scanf(%d,%d,&i,&x);j=Insert_LinkList(H,i,x);if (j = 1) printf(插入成功!);else printf(插入失败!);else if (k=3)printf(n 请输入要删除元素的位置i:);scanf(%d,&i);j=Del_LinkList(H,i);if (j = 1) printf(删除成功!);else printf(删除失败!);else if (k=4) /查找线性表中元素值为x的位置printf(n 请输入要查找的序号i:);scanf(%d,&i);p=Get_LinkList(H,i);if (p!=NULL) print2(H);printf(中序号为i的地址是 %d ,p);elseprintf(链表中无此序号!n); else if (k=5) /输出链表 printf(n表的存储顺序为：); print2(H); while(k!=0);4. 实验3-栈的应用#include stdio.h#include malloc.htypedef int datatype3; typedef struct node3 /定义链式栈结构datatype3 data;struct node3 *next;StackNode3,*LinkStack3;/置空栈 LinkStack3 Init_LinkStack()LinkStack3 top; top=NULL; return top;/入栈 LinkStack3 Push_LinkStack(LinkStack3 top, datatype3 x) StackNode3 *p;p=Init_LinkStack(top);if(x!=0)p=(LinkStack3)malloc(sizeof(StackNode3);p-data=x;p-next=top;top=p;printf(插入成功！n);return p;/出栈LinkStack3 Pop_LinkStack (LinkStack3 top, datatype3 *x) StackNode3 *q=top; if(top=NULL) printf(栈为空); else *x=q-data; top=q-next; free(q); return top; void print3(LinkStack3 top)StackNode3 *p=top;while(p!=NULL) printf(%d-,p-data);p=p-next;/顺序栈#define MAXSIZE3 1024 typedef structdatatype3 dataMAXSIZE3;int top;SeqStack3;/顺序栈置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack3 *Init_SeqStack()SeqStack3 *s;s=(SeqStack3*)malloc(sizeof(SeqStack3);s-top= -1; return s;/顺序栈判空栈int Empty_SeqStack(SeqStack3 *s)if (s-top = -1) return 1; else return 0;/顺序栈入栈int Push_SeqStack (SeqStack3 *s, datatype3 x)if (s-top = MAXSIZE3-1) return 0; /栈满不能入栈else s-top+; s-datas-top=x; return 1;/顺序栈出栈int Pop_SeqStack(SeqStack3 *s, datatype3 *x) if (Empty_SeqStack(s) return 0; /栈空不能出栈 else *x=s-datas-top;s-top-; return 1; /栈顶元素存入*x，返回 void conversion(int N,int r)SeqStack3 *s;datatype3 x; s=Init_SeqStack();/初始化栈printf(n %d 的十进制数转换成 %d 进制为: ,N,r);while ( N ) Push_SeqStack (s,N%r); /余数入栈 N=N/r ;/商作为被除数继续 while ( !Empty_SeqStack(s) Pop_SeqStack (s,&x) ; printf( %d ,x) ; void main3() LinkStack3 top; int N,r; int k; datatype3 x;top=Init_LinkStack(); do printf(nnnn); printf(ttt 栈的应用子系统n);printf(tt*n);printf(tt* 1-链式进栈 *n);printf(tt* 2-链式出栈*n);printf(tt* 3-链栈显示*n);printf(tt* 4-进制转换*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(04)：);scanf(%d,&k);getchar();switch(k) case 1: /进栈printf(n 请输入要进栈的数据X:);scanf(%d,&x);top=Push_LinkStack(top,x);break; case 2:/出栈 top=Pop_LinkStack(top,&x); printf(n 出栈的元素是：%dn,x); printf(n 链式栈的元素有：); print3(top); break; case 3: /打印链式栈中的元素 printf(n 链式栈的元素有：);print3(top);break; case 4: /进制转换printf(n 请输入一个整数N=);scanf(%d,&N);printf(n 请输入一个要转换的进制数r=);conversion(N,r);break;while(k!=0); 5. 实验4-队列的应用#include stdio.h#include malloc.htypedef int datatype4; #define QueueSize4 50 /队列的最大容量/定义队列的结构体 typedef struct queuenode4 datatype4 data; struct queuenode4 *next; QueueNode4; typedef struct QueueNode4 *front; QueueNode4 *rear; LinkQueue4;/置空队LinkQueue4* Init_SeQueue() LinkQueue4 *Q; QueueNode4 *T; Q=malloc(sizeof(LinkQueue4); T=malloc(sizeof(QueueNode4); Q-rear=Q-front=T; T-next=NULL; return Q;/入队int enqueue(LinkQueue4 *Q, datatype4 x) QueueNode4 *p; p=malloc(sizeof(QueueNode4); p-data=x; p-next=NULL; Q-rear-next=p; Q-rear=p; return 1; /判队空int queueempty(LinkQueue4 *Q) return Q-front=Q-rear;/出队int dequeue(LinkQueue4 *Q) datatype4 x; QueueNode4 *p; if(queueempty(Q) printf(删除失败！);return 0; else p=Q-front; x=p-next-data; Q-front=p-next; free(p); return x; /显示队列void print4(LinkQueue4 *Q) /打印线性表 QueueNode4 *p;p=Q-front ; for (p-data ;Q-rear-next!=NULL;p-next ) ; printf(%d,p-data); printf(n);void main4()LinkQueue4 *Q;/LQueue *Lq;int j,k,z,y;datatype4 x;Q=Init_SeQueue(); /Lq=Init_LQueue();do printf(nnnn); printf(ttt 队列子系统n);printf(tt*n);printf(tt* 1-进 队 列 *n);printf(tt* 2-出 队 列*n);printf(tt* 3-队列空否*n);printf(tt* 4-显示队列*n);printf(tt* 0-返回*n);printf(tt*n);printf(tt 请选择菜单项(04)：);scanf(%d,&k);getchar();switch(k) case 1: /进队列printf(n 请输入要进队列的数据:);scanf(%d,&x);y=enqueue(Q,x);if(y=1)printf(入队成功); break; case 2: /出队列j=dequeue(Q);if(j!=0)printf(出队的数据是%d,j);break; case 3: /判断队列空否 z=queueempty(Q);if (z=1) printf(此队列为空!);else printf(此队列不空。);break; case 4: /显示队列p