数据结构实践

1、目录第一章课程设计性质与目的4第二章设计内容及基本要求5第三章详细设计说明113.1 项目一73.2 项目二163.3 项目三26第四章实训总结37附录（参考文献、核心代码）第一章课程设计性质与目的数据结构实训是信息管理与信息系统专业集中实践性环节之一，其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。链表和顺序表操作的设计目的：1.掌握线性表的在顺序结构和链式结构实现。2.掌握线性表在顺序结构和链式结构上的基本操作。二叉树操作的设计目的：1.掌握二叉树的概念和性。2,掌握任意二叉树存

2、储结构。3.掌握任意二叉树的基本操作。第二章设计内容及基本要求一、实验实训的基本要求是：本实训面向应用，以解决实际问题为主。题目以选用学生相对比较熟悉的为宜，要求通过本实训I,理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算法实现，理解数据类型的逻辑结构及物理存储结构，通过自己设计，编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化，树立并培养系统规范开发的理念。实训中学生要将相关课程中学到的知识、思想和理念尽量应用在实训中。结束后要按规定提交代码和各种文档。实训基本步骤：1 .选题设计的课题尽量结合教学、科研的实际课题，规模、大小适当，具有一定复杂度。应根据题目大

3、小、难度确定是否分组，组内成员人数。2 .数据结构及算法设计根据需求分析，选择合理的数据结构及设计相应的算法。3 .编码根据已设计的数据结构和算法，编写代码。4 .测试按照系统测试的原则、方法和步骤，对系统进行测试。测试中应形成测试报告。5 .编写实训报告实训说明书，内容及要求如下：6 1)封面7 2)成绩评定8 3)目录(4)说明书正文，主要内容包括：一、设计题目二、运行环境(软、硬件环境)三、数据结构及算法设计的思想四、数据结构及算法设计五、源代码六、运行结果分析七、实习总结(收获及体会)参考资料：附录(核心代码)。二、设计内容项目一：顺序表操作1、设计目的(1)掌握线性表的在顺序结构上的

4、实现。(2)掌握线性表在顺序结构上的基本操作2、设计内容和要求利用顺序表的插入运算建立顺序表，然后实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数)，并能在屏幕上输出操作前后的结果。项目二：链表操作1、设计目的(1)掌握线性表的在链式结构上的实现。(2)掌握线性表在链式结构上的基本操作2、设计内容和要求利用链表的插入运算建立链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数)，并能在屏幕上输出操作前后的结果。项目三：二叉树的基本操作1、设计目的(

5、1)掌握二叉树的概念和性质(2)掌握任意二叉树存储结构。(3)掌握任意二叉树的基本操作。2、设计内容和要求(1)对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构，并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。(2)求二叉树高度、结点数、度为1的结点数和叶子结点数。第三章详细设计说明项目一：顺序表操作:考查知识点：(1)利用顺序表的插入运算建立顺序表；(2)实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数)；(3)能够在屏幕上输出操作前后的结

6、果。一、算法1.创建：#defineLIST_INIT_SIZE100#defineLISTINCREMENT20typedfstructElemType*elem;intlength;intlistsize;SqList;StatusInitList.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;returnOk;/InitList_Sq2.插入:StatusListIn

7、sert_Sq(SqList&L,inti,ElemTypee)/插入if(i<1|i>L.length+1)returnERROR;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.len

8、gth-1);p>=q;-p)*(p+1)=*p;*q=e+L.length;returnOK;/ListInsert_Sq3.删除：StatusListDelete_Sq(SqList&L,nti,ElemType&e)if(i<1|(i>L.length)returnERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;/表尾元素的位置for(+p;p<=q;+p)=*p;-L.length;/表长减1returnOK;/ListDelete_Sq4.查找：IntLocateElem_Sq(SqListL

9、,ElemTypee,/查找Statuscompare)(ElemType,ElemType)i=1；p=L.elem;while(i<=L.length&&!(*compare)(*p+,e)+i;if(i<=L.length)returni;elsereturn0;/LocateElem_Sq二、源代码一#include<stdio.h>#include<stdlib.h>#include<iostream.h># defineTRUE1# defineFALSE0# defineOK1# defineERROR0# defi

10、neINFEASIBLE-1# defineOVERFLOW-2typedefintStatus;typedefintElemType;# defineLIST_INIT_SIZE100# defineLISTINCREMENT20typedefstructElemType*list;intlength;intlistsize;SqList;intInitList_Sq(SqList&L)L.list=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.list)exit(OVERFLOW);/存储分配失败inti,y;L.l

11、ength=0;L.listsize=LIST_INIT_SIZE;printf("请输入元素个数:");scanf("%d",&y);printf("请输入元素:n");for(i=0;i<y;i+,L.length+)scanf("%d”,&L.listi);for(i=0;i<L.length;i+)printf("%d",L.listi);printf("n");returnOK;/InitList_Sq/*输出函数*voidoutput_Sq(Sq

12、List&L)printf("输出顺序表n");for(inti=0;i<L.length;i+)printf("%d",L.listi);printf("n");/*插入*StatusListInsert_Sq(SqList&L)ElemType*q,*p,*newbase;inti,e;printf("请输入插入位置i:");scanf("%d",&i);if(i<1|i>L.length+1)returnERROR;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",&

14、amp;e);*q=e;+L.length;printf("输出插入之后的顺序表:");for(i=0;i<L.length;i+)printf("%d",L.listi);printf("n");returnOK;/ListInsert_Sq/*删除*intListDelete_Sq(SqList&L)ElemType*p,*q;inti,e;printf("请输入你要删除的元素位序：");scanf("%d",&i);if(i<1)|(i>L.length)

15、returnERROR;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;i<L.length;i+)printf("%d",L.listi);printf("n");returnOK;/ListDelete_SqH*查找*StatusLocateElem_Sq(SqListL)inte,i;printf("请输入你要查找元素的

16、数值:");scanf("%d",&e);printf("你要查找元素的位序为：");for(i=0;i<L.length;i+)if(e=L.listi)printf("%d",i+1);printf("n");return0;/*排序(由小到大)*voidPrint_Sq(SqList&L)intt;for(intj=0;j<L.length-1;j+)for(inti=0;i<L.length-1-j;i+)if(L.listi>L.listi+1)t=L.l

17、isti;L.listi=L.listi+1;L.listi+1=t;printf("输出排序(由小到大)表n");for(inti=0;i<L.length;i+)printf("%d",L.listi);printf("n");/*计数*voidListLength_Sq(SqListL)printf("输出表中元素个数n");printf("%dn",L.length);/*逆置*voidinverse_Sq(SqList&L)intt,i;for(i=0;i<=L.l

18、ength/2-1;i+)t=L.listi;L.listi=L.listL.length-i-1;L.listL.length-i-1=t;printf("输出逆置顺序表n");for(i=0;i<L.length;i+)printf("%d",L.listi);printf("n");/*退出*intQuit_Sq(SqListL)(exit(0);return0;)*主函数*voidmain()(SqListL;inti;printf("1.构造n");printf("2.插入n")

19、;printf("3.删除n");printf("4.排序n");printf("5.计数n");printf("6.查找n");printf("7.逆置n");printf("8.输出n");printf("9.退出n");for(;)(printf("Pleasechoose1to9:n");scanf("%d",&i);switch(i)(case1:InitList_Sq(L);break;case2

20、:ListInsert_Sq(L);break;case3:ListDelete_Sq(L);break;case4:Print_Sq(L);break;case5:ListLength_Sq(L);break;case6:LocateElem_Sq(L);break;case7:inverse_Sq(L);break;case8:output_Sq(L);break;case9:Quit_Sq(L);break;default:printf("输入有误");三、操作结果1=1|回八停出出查曲/"C:Windowssystem32Debugqwe.exe"

21、;choose的数值为:1:1to95431easecLoose1谕出顺序表15431Pleasechoose15843easechoose1to5?choose1to9出排序（由小到大）表34SBcasechoose1to?醺人作I旭里0元素位序4C:Window5sy5tem32Debugqwe.exe1choose1to项目二：链表操作考查知识点：(1)利用链表的插入运算建立链表；(2)实现链表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数)；(3)能够在屏幕上输出操作前后的结果。一、算法1 .创建：voidCreateLi

22、st_L(LinkList&L)/逆序输入n个元素的值，建立带头结点的单链线性表L。L=(LinkList)malloc(sizeof(LNode);/生成新的结点L->next=NULL;/先建立一个带头结点的单链表for(i=n;i>0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p->data);p->next=L->next;L->next=p;/插入至U表头/CreateListL2 .插入：插入StatusListInsert_L(LinkList&L,inti,ElemTypee

23、)/p=L;j=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i)returnERROR；s=(LinkList)malloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;returnOK;3 .删除：StatusListDelete_L(LinkList&L,int&e)/删除j=0;p=L;while(p->next&&j<i-1)/寻找第i个结点，并令p指向其前驱p=p->next;+j;if(!

24、(p->next)|j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;/ListDelete_L4 .查找：StatusGetElem_L(LinkListL,inti,ElemType&e)/查找.p=L->next;j=1;while(p&&j<i)/按序号查找p=p->next;j+;if(!p|j>1)retunERRORe=p->data;retunOK;/GetElem.L二、源代码#include&l

25、t;stdio.h>#include<stdlib.h>#defineOK1#defineERROR0typedefstructLNodeintdata;structLNode*next;LNode,*LinkList;/逆序输入n个元素的值，建立带头结点的单链线性表L。voidCreateList_L(LinkList&L)inti,x;LNode*p=NULL;L=(LinkList)malloc(sizeof(LNode);生成新的结点L->next=NULL;/先建立一个带头结点的单链表printf("请输入结点个数:");scanf

26、("%d",&x);printf("请输入各结点元素的值为:");for(i=x;i>0;-i)/逆序输入x个元素的值p=(LinkList)malloc(sizeof(LNode);scanf("%d”,&p->data);p->next=L->next;L->next=p;/插入至U表头p=L->next;/将p指向头结点/输出已创建的链表printf("逆序输出链表为:n");while(p)(printf("%d",p->data);p=p

27、->next;/*插入*intListInsert_L(LinkList&L)LNode*p,*s;intj=0,e,i;p=L;printf("请输入所要插入的位置:");scanf("%d",&i);printf("请输入所要插入的数:");scanf("%d",&e);while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)printf("输入数据有误，请输入数值在1-x+1之间输入");s=(Link

28、List)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");returnOK;/*删除*intListDelete_L(LinkList&L,int&e)LNode*p,*q;inti,j=0;p=L;printf("请输入要删除的第几个结点：")；scanf("%d",&

29、amp;i);while(p->next&&j<i-1)/寻找第i个结点，并令p指向其前驱(p=p->next;+j;if(!(p->next)|j>i-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("