数据结构实践.doc

精品文档目录第一章 课程设计性质与目的.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或ifprintf(需先按顺序输入二叉树各节点的值：); 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(输入