数据结构实训报告(共32页).doc

《数据结构实训报告(共32页).doc》由会员分享，可在线阅读，更多相关《数据结构实训报告(共32页).doc（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上山东科技大学泰山科技学院课程实训说明书课程： 数据结构 系部名称： 信息工程系 专业班级： 电子信息科学与技术13-2学生姓名： 徐志宏 学 号： 0 指 导 教 师： 亓静 学 校: 山东科技大学 2015年7月22日 指导教师对课程设计的评语课程设计成绩：教师评语： 指导教师（签字）： 2013年 月 日目录第一章 课程设计性质与目的.4第二章 设计内容及基本要求.5第三章 详细设计说明.113.1 项目一.73.2 项目二.163.3 项目三.26第四章 实训总结.37附录 （参考文献、核心代码）第一章 课程设计性质与目的数据结构实训是信息管理与信息系统专业集中

2、实践性环节之一，其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。链表和顺序表操作的设计目的： 1掌握线性表的在顺序结构和链式结构实现。 2掌握线性表在顺序结构和链式结构上的基本操作。二叉树操作的设计目的： 1掌握二叉树的概念和性。2. 掌握任意二叉树存储结构。 3掌握任意二叉树的基本操作。第二章 设计内容及基本要求一、实验实训的基本要求是：本实训面向应用，以解决实际问题为主。题目以选用学生相对比较熟悉的为宜，要求通过本实训，理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算

3、法实现，理解数据类型的逻辑结构及物理存储结构， 通过自己设计，编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化，树立并培养系统规范开发的理念。实训中学生要将相关课程中学到的知识、思想和理念尽量应用在实训中。结束后要按规定提交代码和各种文档。实训基本步骤：1. 选题设计的课题尽量结合教学、科研的实际课题，规模、大小适当，具有一定复杂度。应根据题目大小、难度确定是否分组，组内成员人数。2. 数据结构及算法设计根据需求分析，选择合理的数据结构及设计相应的算法。 3. 编码根据已设计的数据结构和算法，编写代码。4. 测试按照系统测试的原则、方法和步骤，对系统进行测试。测试中应形成测试

4、报告。5. 编写实训报告实训说明书，内容及要求如下：（1） 封面（2） 成绩评定（3） 目录（4） 说明书正文，主要内容包括：一、 设计题目 二、 运行环境（软、硬件环境） 三、 数据结构及算法设计的思想 四、 数据结构及算法设计五、 源代码 六、 运行结果分析 七、 实习总结（收获及体会）参考资料：附录（核心代码）。二、设计内容 项目一：顺序表操作1、设计目的 （1）掌握线性表的在顺序结构上的实现。 （2）掌握线性表在顺序结构上的基本操作2、设计内容和要求利用顺序表的插入运算建立顺序表，然后实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、

5、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。 项目二：链表操作1、设计目的 （1）掌握线性表的在链式结构上的实现。 （2）掌握线性表在链式结构上的基本操作2、设计内容和要求利用链表的插入运算建立链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。 项目三：二叉树的基本操作1、设计目的（1）掌握二叉树的概念和性质 （2）掌握任意二叉树存储结构。 （3）掌握任意二叉树的基本操作。2、设计内容和要求（1）对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本

6、运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。 （2） 求二叉树高度、结点数、度为1的结点数和叶子结点数。第三章 详细设计说明项目一：顺序表操作：考查知识点：（1）利用顺序表的插入运算建立顺序表；（2）实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；（3）能够在屏幕上输出操作前后的结果。一、算法1. 创建：#define LIST_INIT_SIZE 100#define LISTINCREMENT 20typedf structElemType *elem;i

7、nt 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.lis

8、tsize)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,Ele

9、mType&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

10、 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;SqLi

11、st;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(

12、%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 =

13、 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 =

14、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; / 表尾元素的位置pr

15、intf(删除的元素值为: %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);pri

16、ntf(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);/

17、*逆置*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 Li

18、stInsert_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-ne

19、xt;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;/逆序

20、输入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 =

21、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(

22、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=

23、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(请输入要查找的数的序号:

24、);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) /

25、升序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)

26、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

27、( 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_

28、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

29、); /按先序遍历建立二叉树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 (PreOrderTrav

30、erse(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 (

31、!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;ty