课 程 设 计 报 告
题目： 数据结构
课程名称： 数据结构 专业班级： 信息安全 1302 学 号： U201315140 姓 名： 冯实 指导教师： 周时阳
报告日期： 2015年5月10日
计算机科学与技术学院
目录
1课程实验概述 ................................................................................................................................ 0 2 实验一 基于顺序结构的线性表实现 ......................................................................................... 1
2.1 问题描述 ............................................................................................................................ 1 2.2系统设计 ............................................................................................................................. 1
2.2.1 背景 ......................................................................................................................... 1 2.2.2 系统要求 ................................................................................................................. 1 2.3系统实现 ............................................................................................................................. 1
2.3.1顺序表的动态分配存储结构以及部分量的定义 .................................................. 1 2.3.2 相关函数说明及部分函数基本算法思想 ............................................................. 2 2.3.3 实验预期及程序运行结果 ..................................................................................... 4 2.4效率分析 ........................................................................................................................... 11 3 实验二 基于链式结构的线性表实现 ....................................................................................... 12
3.1问题描述 ........................................................................................................................... 12 3.2系统设计 ........................................................................................................................... 12
3.2.1 背景 ....................................................................................................................... 12 3.2.2 系统要求 ............................................................................................................... 12 3.3系统实现 ........................................................................................................................... 12
3.3.1顺序表的动态分配存储结构以及部分量的定义 ................................................ 12 3.3.2 相关函数说明及部分函数基本算法思想 ........................................................... 12 3.3.3 实验预期及程序运行结果 ................................................................................... 14 3.4效率分析 ........................................................................................................................... 21 4 实验三 基于二叉链表的二叉树实现 ....................................................................................... 23
4.1问题描述 ........................................................................................................................... 23 4.2系统设计 ........................................................................................................................... 23
4.2.1 背景 ....................................................................................................................... 23 4.2.2 系统要求 ............................................................................................................... 23 4.3系统实现 ........................................................................................................................... 23
4.3.1顺序表的动态分配存储结构以及部分全程量 .................................................... 23 4.3.2相关函数说明以及基本算法思想 ........................................................................ 24 4.3.3 实验预期及程序运行结果 ................................................................................... 25 4.4效率分析 ........................................................................................................................... 33 5 实验总结与评价 ......................................................................................................................... 34 6 附录 ............................................................................................................................................ 35
6.1 实验一代码 ...................................................................................................................... 35 6.2 实验二代码 ...................................................................................................................... 42 6.3 实验三代码 ...................................................................................................................... 51
1课程实验概述
本次数据结构上机实验，是对我们平常所学的综合性知识的一次全面的考察，是课堂、自学、练习效果的集中体现。本次实验共分三个小实验，报告按照基于顺序结构的线性表实现、基于链式结构的线性表实现、基于二叉链表的二叉树实现的顺序，其中每个小实验均分为问题描述、系统设计、系统实现、效率分析四个部分。
问题描述部分对实验题目进行详细的描述，并且建立问题提出的背景；系统设计部分进行对问题的分析，阐述解决问题的原理，并设计出一个可以演示的系统；系统实现部分演示系统功能，并检验系统功能是否与预期一致，是否能够解决问题描述中的要求；效率分析部分对系统效率进行分析，并提出优化方法。
计算机学科是一门理论与实践相结合的学科，学习的过程中不能抛开实验。而数据结构上机实验能够提高学生对程序设计、编写和调试的能力，使学生掌握数据组织方法和计算机表示方法，以便选择合适的数据逻辑和存储结构，设计相应的操作运算，把现实问题转化为计算机内部的表示与处理方法，并且掌握时间、空间复杂度分析的基础技术。由此可见，数据结构上机实验是一门十分重要的基础实验课程。
2 实验一 基于顺序结构的线性表实现
2.1 问题描述
线性表（linear list）是最常用且最简单的一种数据结构。线性表是一种相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
2.2系统设计
2.2.1 背景
运行环境：windows 程序语言：C++ 开发环境：Dev C++ 2.2.2 系统要求
设计一个顺序存储结构的线性表，要求能够用一个系统演示，可以执行表的创建、表的销毁、表的置空、空表判断、计算表长、读取元素、读取前驱、读取后继、查找元素、插入元素、删除元素及遍历线性表。
2.3系统实现
2.3.1顺序表的动态分配存储结构以及部分量的定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASTABLE -1
#define OVERFLOW -2 //全局量定义 typedef int status;
typedef int ElemType; //数据元素类型定义 #define LIST_INIT_SIZE 100 //定义初始表长 #define LISTINCREMENT 10 //定义表长增量 typedef struct{ //顺序表（顺序结构）的定义
ElemType * elem;
数据结构课程实验报告(12)
