《山东科技大学 数据结构实训报告》由会员分享，可在线阅读，更多相关《山东科技大学 数据结构实训报告（33页珍藏版）》请在金锄头文库上搜索。
1、1 课课程程实实训训说说明明书书 课程：课程： 数据结构实训数据结构实训 题目：题目： 顺序表、顺序表、链表与二叉树链表与二叉树 院 系： 信息工程系 专业班级 ： 学 号： 学生姓名： 指导教师： 2015 年年 7 月月 21 日日 2 目录目录 1.11.1 实训内容和基本要实训内容和基本要 求求 33 1.2 设计题目及其运行环设计题目及其运行环 境境3 1.3 数据结构及算法思想的设计数据结构及算法思想的设计4 一顺序表代码及其运行结果及分一顺序表代码及其运行结果及分 析析4 二链表源代码及其运行结果及结果分二链表源代码及其运行结果及结果分 析析1515 (1)(1)主函数代码及其运
2、行结果主函数代码及其运行结果 (2)(2)输入功能及结果代码输入功能及结果代码 (3)(3)插入功能代码及其运行结果插入功能代码及其运行结果 (4)(4)删除功能代码及其运行结果删除功能代码及其运行结果 (5)(5)查找函数代码及其运行结果查找函数代码及其运行结果 (6)(6)输出函数代码及其运行结果输出函数代码及其运行结果 (7)(7)计数函数代码及其运行结果计数函数代码及其运行结果 (8)(8)排序函数代码及其运行结果排序函数代码及其运行结果 (9)(9)逆置函数代码及其运行结果逆置函数代码及其运行结果 三二叉树源代码及其运行结果及结果分三二叉树源代码及其运行结果及结果分 析析2323 (
3、1)(1)主函数代码及其运行结果主函数代码及其运行结果 (2)(2)创建二叉树函数代码及其运行结果创建二叉树函数代码及其运行结果 (4)(4)求树的结点个数及其运算结果求树的结点个数及其运算结果 (5)(5)求树的结点度为一的结点个数求树的结点度为一的结点个数 (6)(6)求树的叶子个数代码及其运行结果求树的叶子个数代码及其运行结果 (7)(7)先序遍历二叉树及其运行结果先序遍历二叉树及其运行结果 (8)(8)中序遍历二叉树及其运行结果中序遍历二叉树及其运行结果 (9)(9)后序遍历二叉树及其运行结果后序遍历二叉树及其运行结果 3 四实训总四实训总 结结 3232 五参考文五参考文 献献 33
4、33 1.11.1 实训内容和基本要求实训内容和基本要求 这次的实训是以面向应用，以解决实际问题为主。老师给的题目基本都是我们 在课堂上接触过的，实训的要求是通过上机练习，理解有关数据结构的基本概 念、不同数据类型的存储和基本操作的算法实现，理解数据类型的逻辑结构及 物理存储结构， 通过自己设计，编程、调试、测试、能够基本掌握在不同存储 结构下的算法实现及算法优化，树立并培养系统规范开发的理念。实训中我们 要将课本上的理论知识运用到实际操作中，真正做到学以致用。 1.2 设计题目及其运行环境设计题目及其运行环境 课程设计题一：顺序表的基本操作课程设计题一：顺序表的基本操作 一、 设计目的 2掌
5、握线性表在顺序结构上的基本操作。 二、设计内容和要求 利用顺序表的插入运算建立线性链表，然后实现查找、插入、删除、计数、输 出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置 要单独写成函数） ，并能在屏幕上输出操作前后的结果。 课程设计题二：链表的基本操作课程设计题二：链表的基本操作 一、 设计目的 1掌握线性表的在链式结构实现。 2掌握线性表在链式结构上的基本操作。 二、设计内容和要求 利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、 输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆 置要单独写成函数） ，并能在屏幕上输出操作前后
6、的结果。 课程设计题三：二叉树的基本操作课程设计题三：二叉树的基本操作 4 一、 设计目的 1掌握二叉树的概念和性质 2. 掌握任意二叉树存储结构。 3掌握任意二叉树的基本操作。 二、设计内容和要求 1.对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈 的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的 先序、中序、后序三种遍历，输出三种遍历的结果。 2 求二叉树高度、结点数、度为 1 的结点数和叶子结点数。 运行环境运行环境 首先需要一台 PC 机，Windows XP 系统下，其次程序在 visual C+6.0 的编译 环境中进行，界面将通过屏幕的输出
7、显示功能选项。通过键盘输入完成相应操 作。程序主界面是一个文本方式的菜单，通过键盘相应选择操作指令。 1.31.3 数据结构及算法思想的设计数据结构及算法思想的设计 首先可以把需要实现的功能分别写成一个个子函数，然后在主函数里面调用这 些子函数，此外还需编写一个菜单子函数，在主函数里面最先调用菜单函数实 现在运行界面时首先显示主菜单，根据菜单提示完成你想要执行的操作。链表 的各种功能，例如创建，输出，查找，插入，删除，计数，排序； 对于二叉树的各种功能，例如创建，先序，中序，后序三种遍历，高度，结点 数，叶子结点数等.对于二叉树的遍历，是运用的非递归的思想，求高度，结点 数，叶子结点数等方法和
8、链表一样，都是先建立子函数，再进行调用。 1顺序表代码及其运行结果及结果分析顺序表代码及其运行结果及结果分析 #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int Status; 5 typedef int ElemType; /-线性表的动态分配顺序存储结构- typedef struct ElemType *elem; /数组指针 elem 指线性表的基地址 int length; /
9、当前长度 int listsize; SqList; /-顺序表的函数调用部分- Status NiZhi(SqList Status Sort(SqList Status Count(SqList Status SearchElem(SqList Status ListDelete(SqList Status InitList_Sq(SqList Status Build(SqList Status OutPut(SqList Status ListInsert_Sq(SqList /-主函数部分- int main() SqList L; int a,i; 6 printf(“-【请先建立
10、顺序表】-n“); InitList_Sq(L); Build(L); for(i=0;iLIST_INIT_SIZE) L.elem=(ElemType * )realloc(L.elem,(n+LISTINCREMENT) *sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.listsize=n+LISTINCREMENT; for(i=0;iL.length+1)return ERROR; /i 值不合法 if(L.length=L.listsize) /当前存储空间已满，增加分配 newbase=(ElemType *)realloc(L.
11、elem,(L.listsize+LISTINCREMENT) * sizeof(ElemType); if(!newbase)exit(OVERFLOW); L.elem=newbase; /新基址 L.listsize +=LISTINCREMENT; q= /q 为插入位置 for(p=p=q;-p)/插入位置及之后的元素右移 *(p+1)=*p; *q=e; +L.length; OutPut(L) ;/调用输出 return OK; /-删除- Status ListDelete(SqList 11 printf(“删除第几个元素n“); scanf(“%d“, if(iL.leng
12、th) return ERROR; /i 值不合法 p= /p 为被删除元素的位置 e=*p; q=L.elem+L.length-1; /表尾元素的位置 for(+p;pL.elemi+1) t=L.elemi;L.elemi=L.elemi+1;L.elemi+1=t; 13 printf(“升序排列为:n“); for(i=0;i #include #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; /-线性表的单链表的存储结构- typedef struct LNode ElemType data
13、; struct LNode *next; LNode,*LinkList; int n; LinkList q,p,L,s; /-链表函数的调用部分- Status NiZhi(LinkList Status Sort(LinkList Status Count(LinkList Status LocateElem(LinkList Status ListDelete_L(LinkList Status Build_L(LinkList Status OutPut(LinkList Status ListInsert_L(LinkList /-主函数部分- int main() int i,e,a; printf(“*【请先建立单链表】*n“); printf(“请输入元素个数值n“); scanf(“%d“, printf(“请输入%d 个元素n“,n); Build_L(L,n); for(i=0;inext=NULL; /先建立一个带头结点的单链表 f
