数据结构实践Word版

如果您需要使用本文档，请点击下载按钮下载!目录第一章 课程设计性质与目的.4第二章 设计内容及基本要求.5第三章 详细设计说明.113.1 项目一.73.2 项目二.163.3 项目三.26第四章 实训总结.37附录 （参考文献、核心代码）第一章 课程设计性质与目的数据结构实训是信息管理与信息系统专业集中实践性环节之一，其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。如果您需要使用本文档，请点击下载按钮下载!链表和顺序表操作的设计目的： 1掌握线性表的在顺序结构和链式结构实现。 2掌握线性表在顺序结构和链式结构上的基本操作。二叉树操作的设计目的： 1掌握二叉树的概念和性。2. 掌握任意二叉树存储结构。 3掌握任意二叉树的基本操作。第二章 设计内容及基本要求一、实验实训的基本要求是：本实训面向应用，以解决实际问题为主。题目以选用学生相对比较熟悉的为宜，要求通过本实训，理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算法实现，理解数据类型的逻辑结构及物理存储结构， 通过自己设计，编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化如果您需要使用本文档，请点击下载按钮下载!，树立并培养系统规范开发的理念。实训中学生要将相关课程中学到的知识、思想和理念尽量应用在实训中。结束后要按规定提交代码和各种文档。实训基本步骤：1. 选题设计的课题尽量结合教学、科研的实际课题，规模、大小适当，具有一定复杂度。应根据题目大小、难度确定是否分组，组内成员人数。2. 数据结构及算法设计根据需求分析，选择合理的数据结构及设计相应的算法。 3. 编码根据已设计的数据结构和算法，编写代码。4. 测试按照系统测试的原则、方法和步骤，对系统进行测试。测试中应形成测试报告。5. 编写实训报告实训说明书，内容及要求如下：（1） 封面（2） 成绩评定（3） 目录（4） 说明书正文，主要内容包括：一、 设计题目 二、 运行环境（软、硬件环境） 三、 数据结构及算法设计的思想 四、 数据结构及算法设计五、 源代码 六、 运行结果分析 七、 实习总结（收获及体会）参考资料：附录（核心代码）。二、设计内容 项目一：顺序表操作如果您需要使用本文档，请点击下载按钮下载!1、设计目的 （1）掌握线性表的在顺序结构上的实现。 （2）掌握线性表在顺序结构上的基本操作2、设计内容和要求利用顺序表的插入运算建立顺序表，然后实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。 项目二：链表操作1、设计目的 （1）掌握线性表的在链式结构上的实现。 （2）掌握线性表在链式结构上的基本操作2、设计内容和要求利用链表的插入运算建立链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。 项目三：二叉树的基本操作1、设计目的（1）掌握二叉树的概念和性质 （2）掌握任意二叉树存储结构。 （3）掌握任意二叉树的基本操作。2、设计内容和要求（1）对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。 （2） 求二叉树高度、结点数、度为1的结点数和叶子结点数。第三章 详细设计说明项目一：顺序表操作：如果您需要使用本文档，请点击下载按钮下载!考查知识点：（1）利用顺序表的插入运算建立顺序表；（2）实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；（3）能够在屏幕上输出操作前后的结果。一、算法1. 创建：#define LIST_INIT_SIZE 100#define LISTINCREMENT 20typedf structElemType *elem;int length;int listsize;SqList;Status InitList.Sq(SqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW); L.lengh=0;L.listsize=LIST_INIT_SIZE;return Ok;/InitList_Sq2.插入:Status ListInsert_Sq(SqList&L,int i,ElemType e)/插入if(iL.length+1)return ERROR;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);/q指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e+L.length；return OK;/ListInsert_Sq3.删除：Status ListDelete_Sq(SqList &L，nt i,ElemType&e)if(iL.length)return ERROR;p=&(L.elemi-1);如果您需要使用本文档，请点击下载按钮下载!e=*p;q=L.elem+L.length-1;/表尾元素的位置for(+p;p=q;+p)=*p;-L.length;/表长减1return OK;/ListDelete_Sq4.查找：Int LocateElem_Sq(SqList L，ElemType e， /查找Status（*compare）（ElemType，ElemType）i=1；p=L.elem;while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length) return i;else return 0;/LocateElem_Sq二、源代码#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 20typedef struct ElemType *list;int length;int listsize;SqList;int InitList_Sq(SqList &L) 如果您需要使用本文档，请点击下载按钮下载! L.list = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType); if (!L.list) exit (OVERFLOW); / 存储分配失败int i,y; L.length = 0; L.listsize = LIST_INIT_SIZE; printf(请输入元素个数:);scanf(%d,&y);printf(请输入元素:n);for(i=0;iy;i+,L.length+)scanf(%d,&L.listi);for(i=0;iL.length;i+)printf(%d ,L.listi);printf(n); return OK; / InitList_Sq/*输出函数*void output_Sq(SqList &L) printf(输出顺序表n);for(int i=0;iL.length;i+) printf(%d ,L.listi);printf(n); /*插入*Status ListInsert_Sq(SqList &L) ElemType *q,*p,*newbase;int i,e;printf(请输入插入位置i:); scanf( %d,&i);如果您需要使用本文档，请点击下载按钮下载!if(i L.length + 1) return ERROR;if(L.length = L.listsize)newbase = (ElemType *)realloc(L.list,(L.listsize + LISTINCREMENT) * sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.list = newbase;L.listsize += LISTINCREMENT;q = &(L.listi-1); / q指示插入位置for (p = & (L.listL.length-1); p = q; -p)*(p+1) = *p; / 插入位置及之后的元素右移printf(输入插入数值e: );scanf(%d,&e);*q = e; +L.length; printf(输出插入之后的顺序表:);for( i=0;iL.length;i+) printf(%d ,L.listi);printf(n);return OK; / ListInsert_Sq/*删除*int ListDelete_Sq(SqList &L) ElemType *p,*q;int i,e;printf(请输入你要删除的元素位序：);scanf(%d,&i);if (i L.length) return ERROR; p = & (L.listi-1); 如果您需要使用本文档，请点击下载按钮下载!e = *p; q = L.list + L.length - 1; / 表尾元素的位置printf(删除的元素值为: %dn,e);for (+p; p = q; +p) *(p-1) = *p; -L.length; for( i=0;iL.length;i+) printf(%d ,L.listi);printf(n);return OK; / ListDelete_Sq /*查找* Status LocateElem_Sq(SqList L) int e,i;printf(请输入你要查找元素的数值: );scanf(%d,&e);printf(你要查找元素的位序为: );for(i=0;iL.length;i+)if(e=L.listi)printf(%d ,i+1);printf(n);return 0; /*排序（由小到大）*void Print_Sq(SqList &L) int t;for(int j=0;jL.length-1;j+)如果您需要使用本文档，请点击下载按钮下载!for(int i=0;iL.listi+1)t=L.listi;L.listi=L.listi+1;L.listi+1=t;printf(输出排序（由小到大）表n);for(int i=0;iL.length;i+) printf(%d ,L.listi);printf(n);/*计数*void ListLength_Sq(SqList L) printf(输出表中元素个数n);printf(%dn,L.length);/*逆置*void inverse_Sq(SqList &L) int t,i;for(i=0;i=L.length/2-1;i+)t=L.listi;L.listi=L.listL.length-i-1;L.listL.length-i-1=t;printf(输出逆置顺序表n);for( i=0;inext=NULL; /先建立一个带头结点的单链表for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);p-next = L-next;L-next = p; /插入到表头/CreateList L2. 插入：Status ListInsert_L(LinkList &L,int i ,ElemType e) /插入p=L;j=0;while(p&jnext;+j;if(!p|ji)return ERROR；s=(LinkList)malloc(sizeof(LNode);s-data=e; s-next=p-next;p-next=s;return OK;3. 删除：Status ListDelete_L(LinkList &L,int &e) /删除j=0;p=L;while(p-next & jnext;+j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;如果您需要使用本文档，请点击下载按钮下载!e=q-data;free(q);return OK;/ListDelete_L4. 查找:Status GetElem_L(LinkList L,int i , ElemType &e) /查找p=L-next;j=1;while(p & jnext;j+;if(!p|j1)retun ERRORe=p-data;retun OK;/GetElem.L二、源代码#include#include#define OK 1#define ERROR 0typedef struct LNode int data;struct LNode * next;LNode, * LinkList;/逆序输入n个元素的值，建立带头结点的单链线性表L。void CreateList_L(LinkList &L) int i,x;LNode *p=NULL;L=(LinkList)malloc(sizeof(LNode);/生成新的结点L-next=NULL; /先建立一个带头结点的单链表 printf(请输入结点个数:); scanf(%d,&x); printf(请输入各结点元素的值为:);for(i=x;i0;-i) /逆序输入x个元素的值 p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);p-next = L-next;L-next = p; /插入到表头p=L-next; /将p指向头结点如果您需要使用本文档，请点击下载按钮下载! /输出已创建的链表printf(逆序输出链表为:n); while(p)printf(%d ,p-data);p=p-next;/*插入*int ListInsert_L(LinkList &L) LNode *p,*s;int j=0,e,i;p=L;printf(请输入所要插入的位置:);scanf(%d,&i);printf(请输入所要插入的数:);scanf(%d,&e);while(p&jnext;+j;if(!p|ji-1)printf(输入数据有误,请输入数值在1 - x+1之间输入);s=(LinkList)malloc(sizeof(LNode);s-data=e; s-next=p-next;p-next=s;p=L -next;while(p)printf(%5d,p-data);p=p-next;printf(n);return OK; /*删除*int ListDelete_L(LinkList &L,int &e) LNode *p,*q;int i,j=0;p=L;printf(请输入要删除的第几个结点:);如果您需要使用本文档，请点击下载按钮下载! scanf(%d,&i);while(p-next & jnext;+j;if(!(p-next)|ji-1)printf(输入的数值错误或删除位置不合理);q=p-next;p-next=q-next;e=q-data;free(q);/释放被删除结点printf(被删除结点的数值为: %dn,e);p=L -next;while(p)printf(%5d,p-data);p=p-next;printf(n);return OK; /*计数*void CountList_L(LinkList &L) int i=0;LNode *p=L-next;while(p)i+;p=p-next;printf(结点个数为:%dn,i); /*查找*int LocateElem_L(LinkList L) LinkList p=L;int i,j=0;printf(请输入要查找的数的序号:);scanf(%d,&i);while(p & jnext;j+;如果您需要使用本文档，请点击下载按钮下载!if(j!=i|!p)printf(参数i错或单链表不存在);return(NULL);printf(你查找的第 %d 个结点的数值为 %dn,i,p-data);return OK;/*排序*void SortList_L(LinkList L) int i,j,t,k = 0;LNode *p = L-next,*q;while(p)k+;p=p-next;p=L-next; q=p-next; /初始化for(i=0;inext;for(j=0,p;jnext)q = p-next;if(p-data q-data) /升序t=p-data;p-data=q-data;q-data=t;p=L-next;printf(输出升序的链表为:n);while(p)printf(%5d,p-data);p=p-next;printf(n); /*输出*void OutputList_L(LinkList L) 如果您需要使用本文档，请点击下载按钮下载!LNode *p;p=L-next;while(p)printf(%5d,p-data);p=p-next;printf(n);/*逆置*int ReverseList_L(LinkList &L) LNode *p ,*q;p=L-next;q=p-next;L-next=NULL;while(p-next)p-next=L-next; L-next=p; p=q;q=q-next;p-next=L-next;L-next=p;printf(逆置后的链表结果为:);for(p=L-next;p;p=p-next)printf(%d ,p-data);printf(n);return 0;/*主函数*int main()LinkList L=NULL;int i,e;printf(逆序输入创建一个链表并实现下列功能n);printf( 1. 创建 n);printf( 2. 插入 n);printf( 3. 删除 n);printf( 4. 计数 n);printf( 5. 查找 n);printf( 6. 排序 n);如果您需要使用本文档，请点击下载按钮下载!printf( 7. 输出 n);printf( 8. 逆置 n);for(;)printf(请在1-8功能中选择一个: );scanf(%d,&i);/*函数调用*switch(i)case 1:CreateList_L(L); break;case 2:ListInsert_L(L); break;case 3:ListDelete_L(L,e); break;case 4:CountList_L(L); break;case 5:LocateElem_L(L); break;case 6:SortList_L(L); break;case 7:OutputList_L(L); break;case 8:ReverseList_L(L); break;default:printf(输入错误);printf(n);return 0;三、操作结果如果您需要使用本文档，请点击下载按钮下载!项目三：二叉树的操作：一、考查知识点：1.对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构； 2.利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。 3. 求二叉树高度、结点数、度为1的结点数和叶子结点数。二、算法：如果您需要使用本文档，请点击下载按钮下载!1.创建二叉树：Status Createbitree(bitree &t) /功能1：构建二叉树的二叉链表scanf(& ch); /按先序遍历建立二叉树if(ch=)T=NULL;elseif(!(T=(BiTNde)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;Createbitree(t-lchild);Createbitree(t-rchild);Return OK;/CreatBiTree2.先序遍历： Status PreOrderTraverse(Bitree T,Status（* visit）（TElemType)） /采用二叉链表存储结构，Visit是对数据元素操作的应用函数 if(T)if(Visist(T-data)if (PreOrderTraverse(p-lchild,Visit);if PreOrderTraverse(p-rchild,Visit);return OK;return ERROR;elese returnOK; / PreOrderTraverse3.中序遍历：Status InOrderTraverse(Bitree T,Status（* Visit）（TElemType)）InitStack(s);Push (S,T);While(!StackEmpty(s)While(GetTop(s,p)&p)Push(S,p-lchild);Pop(S,p);If(!StackEmpty(s)Pop(s,p);if (!Visit(p-data)retu ERROR;Push(S,p-rchild);/if/WhileRetun OK;/ InOrderTraverse二、源代码#include#include如果您需要使用本文档，请点击下载按钮下载!#include#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef void status;typedef char BTtype;typedef char Stype;typedef struct BTnode /定义二叉树存储结构 BTtype data; struct BTnode *lc,*rc;BTnode,*BTtree;typedef struct/定义栈的存储结构Stype *base;Stype *top;int stacksize; Sqstack;int max(int a,int b)return ab?a:b;char Creat(BTtree &t)/创建char ch;/printf(按顺序输入二叉树各节点的值：); scanf(%c,&ch);if(ch= ) t=NULL;else if(!(t=(BTtree )malloc(sizeof(BTnode)printf(创建失败。); exit(overflow);t-data=ch;Creat(t-lc);Creat(t-rc);return ok;如果您需要使用本文档，请点击下载按钮下载!char orderx(BTtree &t)/先序BTtree p=t;if(p)printf(%c,p-data);orderx(p-lc); orderx(p-rc);return 0;char orderz(BTtree &t)/中序BTtree p=t;if(p)orderz(p-lc);printf(%c,p-data); orderz(p-rc);return 0;char orderh(BTtree &t)/后序BTtree p=t;if(p)orderh(p-lc); orderh(p-rc);printf(%c,p-data);return 0;int Depth(BTtree t)/求深度int d,dl,dr;if(!t) d=0;else dl=Depth(t-lc); dr=Depth(t-rc);d=max(dl,dr)+1; return d;int Nodes(BTtree &t)/结点数如果您需要使用本文档，请点击下载按钮下载! int num1,num2; if(t=NULL) return 0; else num1=Nodes(t-lc); num2=Nodes(t-rc); return (num1+num2+1); void Degree(BTtree t,int &n)/度为1的结点个数/int n=0;if(t)if(t-lc & !t-rc) | (!t-lc & t-rc) n+;Degree(t-lc,n);Degree(t-rc,n);void Leaves(BTtree &t,int &yz)/叶子数/int yz=0;if(t)if(!t-lc) & (!t-rc) yz+;Leaves(t-lc,yz);Leaves(t-rc,yz);/return yz;void Quit()/退出exit(0);int main()BTtree t;int yz=0;int n=0;int x;/用于case或if如果您需要使用本文档，请点击下载按钮下载!printf(需先按顺序输入二叉树各节点的值：); if(Creat(t) printf(创建成功！n);printf(1、先序n2、中序n3、后序n4、求深度n5、求结点数n6、求度为一的结点数n7、求叶子数n8、退出n);/*for(;)printf(请选择1-9：);scanf(%d,&x);switch(x) case 1:printf(按顺序输入二叉树各节点的值：); Creat(t); printf(创建成功！n); break; case 2:printf(先序遍历二叉树：); orderx(t); printf(n);break; case 3:printf(中序遍历二叉树：); orderz(t); printf(n);break; case 4:printf(后序遍历二叉树：); orderh(t); printf(n);break;case 5:printf(二叉树的深度为：%dn,Depth(t);break;case 6:printf(二叉树的节点数为：%dn,Nodes(t);break;case 7:Leaves(t,yz); printf(叶子数为：%dn,yz);break;case 8:Degree(t,n); printf(度为1的节点个数为：%dn,n);break; case 9:Quit(); break;default:printf(输入错误);*/ for(;)printf(请选择1-8：);scanf(%d,&x);/*if(x=1) printf(按顺序输入二叉树各节点的值：); Creat(t); printf(创建成功！n); else*/ if(x=1)如果您需要使用本文档，请点击下载按钮下载! printf(先序遍历二叉树：); orderx(t); printf(n);else if(x=2) printf(中序遍历二叉树：); orderz(t); printf(n);else if(x=3) printf(后序遍历二叉树：); orderh(t); printf(n);else if(x=4) printf(二叉树的深度为：%dn,Depth(t);else if(x=5) printf(二叉树的节点数为：%dn,Nodes(t);else if(x=6) Degree(t,n); printf(度为1的节点个数为：%dn,n);else if(x=7) Leaves(t,yz); printf(叶子数为：%dn,yz);else if(x=8) Quit();else printf(输入有误。n);/*printf(按顺序输入二叉树各节点的值：); if(Creat(t) printf(创建成功！n);printf(先序遍历二叉树：);orderx(t);printf(n);printf(中序遍历二叉树：);orderz(t);printf(n);如果您需要使用本文档，请点击下载按钮下载!printf(后序遍历二叉树：);orderh(t);printf(n);printf(二叉树的深度为：%dn,Depth(t);printf(二叉树的节点数为：%dn,Nodes(t);Degree(t,n);printf(度为1的节点个数为：%dn,n);Leaves(t,yz); printf(叶子数为：%dn,yz);*/ return 0;三、操作结果如果您需要使用本文档，请点击下载按钮下载! 第四章 实训总结通过这次实训，我把在课本上所学到的理论知识，运用到了实际的编程当中，也让我受益颇深。在这个为期两周的实训中,我发觉到了自己的弱项和不足项,也经过努力去克服了它们.最深刻的总结成一个公式:学了学会了会用了，有些东西自己利用所学的地只是远远不能用算法很好的表达出来,只能借助于书本,互联网查找资料,甚至以前老师所给做的笔记才能勉强完成.有些不足还是.在开始的时候困难是很大的,于是乎我并没有急于开工,我先翻阅书本查找了有关知识点进行温习熟悉,然后翻阅有关笔记,上网查找资料.之后我才开始编写算法,实现目标这个过程中不免与同学进行交流合作.这个铺桥的工作完成了.下面的路也就好修了.附录参考文献： （1）C程序设计（第二版），谭浩强编，清华大学出版社，1999年1月。如果您需要使用本文档，请点击下载按钮下载! （2）C语言程序设计题解与上机指导，谭浩强编，清华大学出版社，2000年11月。 （3）数据结构C语言版，严蔚敏，吴伟民编著，清华大学出版社，1997年4月。 （注：可编辑下载，若有不当之处，请指正，谢谢!）