数据结构实践

目录第一章课程设计性质与目的 (4)第二章设计内容及基本要求 (5)第三章详细设计说明 (11)3.1 项目一 (7)3.2 项目二 (16)3.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 struct{Elem Type *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(i<1||i>L.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.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.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((i<1||(i>L.length))return ERROR;p=&(L.elem[i-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 <stdio.h>#include <stdlib.h>#include <iostream.h>#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;i<y;i++,L.length++)scanf("%d",&L.list[i]);for(i=0;i<L.length;i++)printf("%d ",L.list[i]);printf("\n");return OK;} // InitList_Sq//*****************输出函数******************void output_Sq(SqList &L){printf("输出顺序表\n");for(int i=0;i<L.length;i++)printf("%d ",L.list[i]);printf("\n");}//*****************插入*********************Status ListInsert_Sq(SqList &L){ElemType *q,*p,*newbase;int i,e;printf("请输入插入位置i:");scanf(" %d",&i);if(i < 1 || 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.list[i-1]); // q指示插入位置for (p = & (L.list[L.length-1]); p >= q; --p)*(p+1) = *p; // 插入位置及之后的元素右移printf("输入插入数值e: ");scanf("%d",&e);*q = e;++L.length;printf("输出插入之后的顺序表:");for( i=0;i<L.length;i++)printf("%d ",L.list[i]);printf("\n");return OK;} // ListInsert_Sq//*****************删除*********************int ListDelete_Sq(SqList &L){ElemType *p,*q;int i,e;printf("请输入你要删除的元素位序：");scanf("%d",&i);if ((i < 1) || (i > L.length)) return ERROR;p = & (L.list[i-1]);e = *p;q = L.list + L.length - 1; // 表尾元素的位置printf("删除的元素值为: %d\n",e);for (++p; p <= q; ++p)*(p-1) = *p;--L.length;for( i=0;i<L.length;i++)printf("%d ",L.list[i]);printf("\n");return OK;} // ListDelete_Sq//******************查找********************Status LocateElem_Sq(SqList L){int e,i;printf("请输入你要查找元素的数值: ");scanf("%d",&e);printf("你要查找元素的位序为: ");for(i=0;i<L.length;i++){if(e==L.list[i])printf("%d ",i+1);}printf("\n");return 0;}//************排序（由小到大）*************void Print_Sq(SqList &L){int t;for(int j=0;j<L.length-1;j++)for(int i=0;i<L.length-1-j;i++)if(L.list[i]>L.list[i+1]){t=L.list[i];L.list[i]=L.list[i+1];L.list[i+1]=t;} printf("输出排序（由小到大）表\n");for(int i=0;i<L.length;i++)printf("%d ",L.list[i]);printf("\n");}//*****************计数********************void ListLength_Sq(SqList L){printf("输出表中元素个数\n");printf("%d\n",L.length);}//*****************逆置********************void inverse_Sq(SqList &L){int t,i;for(i=0;i<=L.length/2-1;i++){t=L.list[i];L.list[i]=L.list[L.length-i-1];L.list[L.length-i-1]=t;}printf("输出逆置顺序表\n");for( i=0;i<L.length;i++)printf("%d ",L.list[i]);printf("\n");}//*****************退出*********************int Quit_Sq(SqList L){exit (0);return 0;}//****************主函数********************void main(){SqList L;int i;printf(" 1. 构造 \n");printf(" 2. 插入 \n");printf(" 3. 删除 \n");printf(" 4. 排序 \n");printf(" 5. 计数 \n");printf(" 6. 查找 \n");printf(" 7. 逆置 \n");printf(" 8. 输出 \n");printf(" 9. 退出 \n");for(;;){printf("Please choose 1 to 9 :\n");scanf("%d",&i);switch(i){case 1:InitList_Sq(L);break;case 2:ListInsert_Sq(L); break;case 3:ListDelete_Sq(L); break;case 4:Print_Sq(L); break;case 5:ListLength_Sq(L); break;case 6:LocateElem_Sq(L);break;case 7:inverse_Sq(L);break;case 8:output_Sq(L);break;case 9: Quit_Sq(L);break;default:printf("输入有误");}}}三、操作结果项目二：链表操作考查知识点：（1）利用链表的插入运算建立链表；（2）实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；（3）能够在屏幕上输出操作前后的结果。