华中科技大学数据结构实验答案.doc

课 程 实 验 报 告 课程名称： 数 据 结 构 专业班级：华中科技大学材控1402班 学 号： U201411219 姓 名： 张煌 指导教师： 袁凌 报告日期： 2016年5月20日 计算机科学与技术学院 目录 实验报告要求说明 1 1基于顺序存储结构实现线性表的基本运算 1 1.1 问题描述 1 1.2 顺序表演示系统设计 1 1.2.1 系统总体设计 1 1.2.2 有关常量和类型定义 1 1.2.3 算法设计 1 1.3 顺序表演示系统实现与测试 1 1.3.1 系统实现 1 1.3.2 系统测试 1 1.4 实验小结 2 2基于链式存储结构实现线性表的基本运算 3 2.1 问题描述 3 2.2 单链表演示系统设计 3 2.2.1 系统总体设计 3 2.2.2 有关常量和类型定义 3 2.2.3 算法设计 3 2.3 单链表演示系统实现与测试 3 2.3.1 系统实现 3 2.3.2 系统测试 3 2.4 实验小结 3 参考文献 5 1课程实验概述 本次课程实验旨在加强学生课堂理论学习之后增强上机能力，熟练掌握并应用数据结构中的两种逻辑结构的典型代表——线性表和树。线性表的顺序存储具有随机存取的功能，而链式存储能有效的利用动态存储空间，学会合理的选择这两种存储方式，看似简单，但在实际应用具有很大的用处。而树（二叉树）是非线性逻辑结构的代表，树模型的建立可以说完全建立在递归思想之上，树的几乎所有操作都涉及到递归调用，当然我们也可以用栈来实现非递归调用，但是其思想也是相近的。因此树的实验旨在帮助我们递归思想的建立和成熟。 2实验一 基于顺序结构的线性表实现 2.1实验内容与要求 实验内容：基于顺序存储结构，实现线性表ADT，具有10种基本运算。 具体要求：1.提供一个实现功能的演示系统。 2.具体物理结构和数据元素类型自定。 3.线性表数据可以使用磁盘文件永久保存。 2.2程序概要设计 1.明确基本功能 程序需要实现的12个基本功能分别是：IntiaList（初始化），DestroyList（摧毁线性表），ClearList（清空线性表），ListEmpty（判断表空），ListLength（求表长），GetElem（取表中元素），LocatElem（获得元素地址），PriorElem（取前继），NextElem（取后继）。ListInsert（插入）， ListDelete（删除），ListTrabverse（遍历显示），此外还有辅助功能：Load（载入），Save（保存） 确定各功能实现的函数参数 status IntiaList(SqList * L); status DestroyList(SqList * L); status ClearList(SqList L); status ListEmpty(SqList L); int ListLength(SqList L); status GetElem(SqList L,int i,Elemtype *e); int LocatElem(SqList L,Elemtype *e); status PriorElem(SqList *L,Elemtype cur,Elemtype * pre_e); status NextElem(SqList L,Elemtype cur,Elemtype * next_e); status ListInsert(SqList *L, Elemtype e,int i); status ListDelete(SqList * L,Elemtype * e,int i); status ListTrabverse(SqList L,void (* visit)(Elemtype e)); void Save(SqList L); status Load(SqList*L); 2.3数据结构与算法设计 为了满足概述中的功能，结合线性表结构，给出以下结构的定义： typedef int status; typedef struct{ int item1; }Elemtype; typedef struct{ Elemtype * elem; int length; int listsize; }SqList,*L; 算法设计： 1.IntiaList： 初始化线性表，传入的是头结点地址。申请一个大小为LIST_INT_SIZE、类型为销毁头结点中首结点址针指向的线性