华中科技大学 数据结构 实验报告.doc

精品文档 1欢迎下载 课课 程程 实实 验验 报报 告告 课程名称 课程名称 数数 据据 结结 构构 专业班级 专业班级 华中科技大学材控华中科技大学材控 14021402 班班 学学 号 号 U201411219U201411219 姓姓 名 名 张煌张煌 指导教师 指导教师 袁凌袁凌 报告日期 报告日期 20162016 年年 5 5 月月 2020 日日 计算机科学与技术学院计算机科学与技术学院 精品文档 2欢迎下载 目录目录 实验报告要求说明 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 精品文档 11欢迎下载 1 1 课程实验概述课程实验概述 本次课程实验旨在加强学生课堂理论学习之后增强上机能力 熟练掌握并 应用数据结构中的两种逻辑结构的典型代表 线性表和树 线性表的顺序存 储具有随机存取的功能 而链式存储能有效的利用动态存储空间 学会合理的 选择这两种存储方式 看似简单 但在实际应用具有很大的用处 而树 二叉 树 是非线性逻辑结构的代表 树模型的建立可以说完全建立在递归思想之上 树的几乎所有操作都涉及到递归调用 当然我们也可以用栈来实现非递归调用 但是其思想也是相近的 因此树的实验旨在帮助我们递归思想的建立和成熟 2 2 实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现 2 12 1 实验内容与要求实验内容与要求 实验内容 基于顺序存储结构 实现线性表 ADT 具有 10 种基本运算 具体要求 1 提供一个实现功能的演示系统 2 具体物理结构和数据元素类型自定 3 线性表数据可以使用磁盘文件永久保存 2 22 2 程序概要设计程序概要设计 1 明确基本功能 程序需要实现的 12 个基本功能分别是 IntiaList 初始化 DestroyList 摧毁线性表 ClearList 清空线性表 ListEmpty 判断表 空 ListLength 求表长 GetElem 取表中元素 LocatElem 获得元 素地址 PriorElem 取前继 NextElem 取后继 ListInsert 插入 ListDelete 删除 ListTrabverse 遍历显示 此外还有辅助功能 Load 载入 Save 保存 2 确定各功能实现的函数参数 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 精品文档 22欢迎下载 int LocatElem SqList L Elemtype e 精品文档 3欢迎下载3 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 32 3 数据结构与算法设计数据结构与算法设计 为了满足概述中的功能 结合线性表结构 给出以下结构的定义 typedef int status typedef struct int item1 Elemtype typedef struct Elemtype elem int length int listsize SqList L 算法设计 1 IntiaList 初始化线性表 传入的是头结点地址 申请一个大小为 LIST INT SIZE 类型为 Elemtype 的线性存储空间 并用头结点中的首结点指针指向该空间首地 址 2 DestroyList 销毁头结点中首结点址针指向的线性存储空间 传入的是头结点地址 3 ClearList 与 Destroy 类似但是又有不同 ClearList 并不销毁物理空间 而是修改 逻辑关系值 4 ListEmpty 判空功能 判断表是否为空表 传入的是头结点值 而非地址 因为不需 要对头结点进行修改 若长度为 0 表空 否则不空 5 ListLength 求表长功能 由于创建过程中已经把表长信息包含在头结点中 所以直接 精品文档 4欢迎下载4 调用并显示即可 6 GetElem 获取第 i 号元素 传入的是头结点值 元素编号 i 以及出口表结点地址 7 LocatElem 取指定元素编号 传入头结点值 存储了所需元素信息的一个临时表结点 值 equal 函数地址 采用顺序比较法从表头遍历并比较 一旦找到 返回编 号 i 8 PriorElem 求指定元素的前一个元素的内容 传入头结点值 包含指定元素信息的一 个临时表结点值 存储前一个元素的表结点地址 主要思路是先调用 LocatElem 确定指定元素的位置 如果不是首结点则可直接取到 PriorElem 的 地址 9 NextElem 与 PriorElem 功能类似 不再赘述 10 ListInset 插入一个数据元素 传入头结点地址 插入位置 i 临时表结点值 在调 用插入函数前构造一个临时表结点 用于存储数据元素信息 进入插入子函数 插入前先判断插入位置是否合理 再判断是否 满载 如果满载则重新申请 更大的存储空间 接下来正式插入数据元素 先空位置再插入 11 ListDelete 删除一个数据元素 传入头结点地址 删除位置 i 删除前先判断位置是 否合理 先删除元素 然后将所有删除元素之后的元素前移一个位置 12 ListTrabverse 传入头结点 循环访问各个元素 直至到表尾停止 2 42 4 输入输出设计输入输出设计 1 输入 在输入方面 我采用了用户自定义输入的方式 既可以采用用户自行输入 又可以载入之前保存的数据 在每次操作之后 会提示是否保存刚才的数据 以便下次再次使用 以下是用户自行输入的功能实现 void creat SqList L int a 0 printf Input the number of your datas n 精品文档 5欢迎下载5 scanf d L elem Elemtype malloc a sizeof Elemtype L length a int i printf Please input your data n for i 1 ielem i item1 L listsize LIST INIT SIZE printf You have to save your data getchar Save L 2 输出 采用遍历输出 即功能 10 的输出 2 52 5 源程序及注释源程序及注释 Linear Table On Sequence Structure include include include include define LIST INIT SIZE 10 define OK 1 define FALSE 0 define TRUE 1 define ERROR 1 define OVERFLOW 2 define LISTINCREMENT 1 typedef int status typedef struct int item1 Elemtype 精品文档 6欢迎下载6 typedef struct Elemtype elem int length int listsize SqList L int changed 0 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 status compare Elemtype e1 Elemtype e2 status equal Elemtype x Elemtype y void display Elemtype e void Save SqList L status Load SqList L void creat SqList L void menu void char file0 20 int main void SqList L L listsize LIST INIT SIZE 精品文档 7欢迎下载7 int op 0 char req do system cls menu printf Do you want to input new liear table Y N req getchar getchar if req Y req y creat else printf Do you want to load saved data Y N req getchar if req Y req y while Load else printf You still use the data use before n getchar getchar system cls menu printf Then please input your option 0 12 scanf d switch op case 0 break case 1 printf n here is IntiaList which being realized n getchar getchar if IntiaList getchar getchar printf Dou you want to save Y N 精品文档 8欢迎下载8 else printf Not realised n getchar getchar break case 2 printf n here is DestroyList which being realized n getchar getchar if DestroyList getchar getchar else printf Not realised n getchar getchar break case 3 printf n here is ClearList which being realized n getchar getchar if ClearList L printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break case 4 printf n here is ListEmpty which being realized n getchar getchar if ListEmpty L printf It is an empty list n getchar getchar else printf It is not an empty list n getchar getchar break 精品文档 9欢迎下载9 case 5 printf n here is ListLength which being realized n if printf Successfully realized The length of L is d n ListLength L getchar getchar else printf Not realised n getchar getchar break case 6 printf n here is GetElem which being realized n getchar getchar int i Elemtype e printf which elem do you want to pick i scanf d if GetElem L i printf And the dth elem data is d i e item1 getchar getchar else printf Not realised n getchar getchar break case 7 printf n here is LocatElem which being realized n getchar getchar int t i a Elemtype e 精品文档 10欢迎下载10 printf What do you want to locate item scanf d for i 1 i L length i if L elem i item1 t break if i L length 1 printf There is no such item in this list n e L elem i if a LocatElem L printf e is in the dth location n a getchar getchar else printf Not realised n getchar getchar break case 8 printf n here is PriorElem which being realized n getchar getchar Elemtype e cur int i printf To find the prio of who i scanf d cur L elem i if PriorElem printf And the prio of elem d is d n i e item1 getchar getchar else printf Not realised n getchar getchar break case 9 printf n here is NextElem which being 精品文档 11欢迎下载11 realized n getchar getchar Elemtype e cur int i printf To find the next of who i scanf d cur L elem i if NextElem L cur printf And the nextelem of elem d is d n i e item1 getchar getchar else printf Not realised n getchar getchar break case 10 printf n here is ListInsert which being realized n getchar getchar int i j Elemtype e printf choose where to insert i scanf d printf nInsert new data scanf d if ListInsert printf the list data is now n for j 1 j L length j printf d L elem j item1 getchar getchar else printf Not realised n getchar getchar break 精品文档 12欢迎下载12 case 11 printf n here is ListDelete which being realized n getchar getchar int i j Elemtype e printf choose where to delete i scanf d if ListDelete printf The deleted data is d n e item1 getchar getchar printf the list data is now n for j 1 jelem Elemtype malloc LIST INIT SIZE sizeof Elemtype if L exit OVERFLOW L length 0 L listsize LIST INIT SIZE return OK status DestroyList SqList L free L L NULL char req printf Are you sure to destroy the file Y N req getchar if req y req Y remove file0 printf The file has been destroyed n return OK status ClearList SqList L L length 0 精品文档 14欢迎下载14 return OK status ListEmpty SqList L if L length 0 return TRUE else return FALSE int ListLength SqList L return L length status GetElem SqList L int i Elemtype e if L length 0 iL length e L elem i return OK else return ERROR int LocatElem SqList L Elemtype e int i for i 1 ielem return ERROR else for i 1 ilength i if compare L elem i cur break if i 1 return FALSE else pre e L elem i 1 return OK status NextElem SqList L Elemtype cur Elemtype next e int i if L elem return ERROR else for i 1 ilength 0 L length L elem 1 e return OK if iL length return FALSE if L length L listsize 精品文档 16欢迎下载16 newbase Elemtype realloc L elem L listsize LISTINCREMENT sizeof Elemtype if newbase return OVERFLOW L elem newbase L listsize LISTINCREMENT q for p p q p p 1 p q e L length return OK status ListDelete SqList L Elemtype e int i Elemtype q p if L elem return ERROR if iL length return FALSE q for p p q p p p 1 e L elem i L length return OK status ListTrabverse SqList L void visit Elemtype e int i if L length return 0 printf n all elements of liear table n for i 1 i L length i visit L elem i return 1 status compare Elemtype e1 Elemtype e2 if e1 item1 e2 item1 return OK else return FALSE 精品文档 17欢迎下载17 void menu void printf n n printf Menu for Linear Table On Sequence Structure n printf n printf 1 IntiaList 7 LocatElem n printf 2 DestroyList 8 PriorElem n printf 3 ClearList 9 NextElem n printf 4 ListEmpty 10 ListInsert n printf 5 ListLength 11 ListDelete n printf 6 GetElem 12 ListTrabverse n printf 0 Exit n printf n status equal Elemtype x Elemtype y return x item1 y item1 void display Elemtype e printf d e item1 void Save SqList L FILE fp NULL int i char file1 20 do puts n t creating data file puts n please input the file name 精品文档 18欢迎下载18 gets file1 if fp fopen file1 wb NULL puts nfile cannot open printf press ENTER to continue getchar while fp NULL for i 1 ielem Elemtype malloc LIST INIT SIZE sizeof Elemtype if changed char req puts nYou have not saved save nowY N req getchar getchar if req Y req y Save L do puts nLoading data now puts nPlease input the file name getchar gets file1 精品文档 19欢迎下载19 if fp fopen file1 rb NULL puts nThe file cannot open printf press ENTER to continue getchar while fp NULL int i 1 L length 0 while feof fp if ilistsize fread else printf Loading overflow n getchar fclose fp return ERROR L length i L length printf Loading a d lenth List L length getchar puts nSuccessfully loaded printf press ENTER to continue getchar changed 0 strcpy file0 file1 fclose fp return OK void creat SqList L int a 0 精品文档 20欢迎下载20 printf Input the number of your datas n scanf d L elem Elemtype malloc a sizeof Elemtype L length a int i printf Please input your data n for i 1 ielem i item1 L listsize LIST INIT SIZE printf You have to save your data getchar Save L 2 62 6 程序测试与结果程序测试与结果 采用简易界面 实验测试数据之前保存在 hf0 文件中 内容为 1 2 3 4 5 图 2 1 下面选取几个重要功能展示 1 求表长 精品文档 21欢迎下载21 图 2 2 2 插入 在 3 号位置插入值为 10 的元素 图 2 3 3 遍历输出 精品文档 22欢迎下载22 图 2 4 4 取某位置的元素 图 2 5 5 删除与插入类似 在实验二中演示其链式结构 2 72 7 复杂性分析复杂性分析 空间复杂度为 O 1 时间复杂度见下表 函数时间复杂度函数时间复杂度 精品文档 23欢迎下载23 InitialListO 1 LocatElemO N DestroyListO 1 PriorElemO 1 ClearListO 1 NextElemO 1 ListEmpyO 1 ListInsertO N ListLenthO 1 ListDeleteO N GetElemO N ListTrabverseO N 表格 2 1 3 3 实验二实验二 基于链式结构的线性表实现基于链式结构的线性表实现 3 23 2 程序概要设计程序概要设计 基于链式存储结构 实现线性表 ADT 具有 8 种基本运算 并籍此建立你 在社交网站 如人人网 的联系人 好友表 提示 提供一个实现功能的演示系统 具体物理结构和数据元素类型自行选定与设计 线性表数据可以使用磁盘文件永久保存 3 23 2 程序概要设计程序概要设计 1 明确基本功能 程序需要实现的 12 个基本功能分别是 IntiaList 初始化 DestroyList 摧毁线性表 ClearList 清空线性表 ListEmpty 判断表 空 ListLength 求表长 GetElem 取表中元素 Search 查找 ListInsert 插入 ListDelete 删除 ListTrabverse 遍历显示 此外还有辅助功能 Load 载入 Save 保存 2 确定各函数参数 status IntiaList LNode L 精品文档 24欢迎下载24 status DestroyList LNode L status ClearList LNode L status ListEmpty LNode L int ListLength LNode L status Search LNode L status LinkInsert LNode L status LinkDelete LNode L status LinkMod LNode L status LinkTrabverse LNode L 3 33 3 数据结构与算法设计数据结构与算法设计 为了满足概述中的功能 结合线性表结构 给出以下结构的定义 typedef int status typedef struct char name 10 char num 20 Elemtype typedef struct LNode Elemtype data struct LNode next LNode 算法设计 1 IntiaList 初始化线性表 传入的是头结点地址的地址 释放 L 重新申请一个节点 作为表头节点 返回新的指向该表头节点的指针的指针 2 DestroyList 销毁头结点中首结点址针指向的线性存储空间 传入的是头结点地址 并 且销毁文件 3 ClearList 与 Destroy 类似但是又有不同 ClearList 并不销毁物理空间 而是修改 逻辑关系值 4 ListEmpty 判空功能 判断表是否为空表 传入头结点地址 若头节点的 next 为空指 针 则表空 否则不空 精品文档 25欢迎下载25 5 ListLength 求表长功能 传入头结点地址 每向下取一次节点 计数器自增 1 直至 为空 此时计数器值为表长 6 Search 根据用户所选取的查找关键字进行查找 查找方式为逐节点查找 一旦找 到便返回包含该关键字的数据元素的所有信息 7 ListInset 插入一个数据元素 传入头结点地址的地址 插入位置 i 临时表结点值 在调用插入函数前构造一个临时结点 用于存储数据元素信息 进入插入子函 数 插入前先判断插入位置是否合理 先断开所插位置 将临时节点插入 8 ListDelete 删除一个数据元素 传入头结点地址的地址 删除位置 i 删除前先判断 位置是否合理 先删除元素 将删除节点的前继和后继相连 释放删除节点 9 ListMod 修改一个元素的信息 调用 Search 来找到所要修改的节点 根据用户要求 自行修改 返回头结点地址 10 ListTrabverse 传入头结点地址 循环访问各个元素 直至到表尾停止 3 43 4 输入输出设计输入输出设计 同实验一相同 此处不再赘述 3 53 5 源程序及注释源程序及注释 include include include include define LIST INIT SIZE 10 define OK 1 define FALSE 0 define TRUE 1 define ERROR 1 精品文档 26欢迎下载26 define OVERFLOW 2 define LISTINCREMENT 1 typedef int status typedef struct char name 10 char num 20 Elemtype typedef struct LNode Elemtype data struct LNode next LNode int changed 0 char req LNode loc status IntiaList LNode L status DestroyList LNode L status ClearList LNode L status ListEmpty LNode L int ListLength LNode L status Search LNode L status LinkInsert LNode L status LinkDelete LNode L status LinkMod LNode L status LinkTrabverse LNode L status equal Elemtype x Elemtype y void display Elemtype e void Save LNode L status Save LNode L status Load LNode L status creat LNode L 精品文档 27欢迎下载27 void menu void char file0 20 int main void int op 0 do LNode L system cls menu printf Do you want to input new link table Y N req getchar getchar if req Y req y creat else printf Do you want to load saved data Y N req getchar if req Y req y if Load printf press ENTER to continue getchar else printf fail to load n getchar getchar else printf You still use the data use before getchar getchar system cls menu printf Then please input your option 0 12 scanf d 精品文档 28欢迎下载28 switch op case 0 break case 1 printf n here is IntiaList which being realized n getchar getchar if IntiaList getchar getchar printf Dou you want to save Y N else printf Not realised Maybe the cause is overflow n getchar getchar break case 2 printf n here is DestroyList which being realized n getchar getchar if DestroyList L printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break case 3 printf n here is ClearList which being realized n getchar getchar if ClearList L printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break case 4 printf n here is ListEmpty which being 精品文档 29欢迎下载29 realized n getchar getchar if ListEmpty L printf It is an empty list n getchar getchar else printf It is not an empty list n getchar getchar break case 5 printf n here is ListLength which being realized n printf Successfully realized The length of L is d n ListLength L getchar getchar break case 6 printf n here is Search which being realized n getchar getchar if Search L OK printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break case 7 printf n here is LinkInsert which being realized n getchar getchar if LinkInsert L OK printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break 精品文档 30欢迎下载30 case 8 printf n here is LinkDelete which being realized n getchar getchar if LinkDelete L OK printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break case 9 printf n here is LinkMod which being realized n getchar getchar if LinkMod L OK printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break case 10 printf n here LinkTrabverse which being realized n getchar getchar if LinkTrabverse L OK printf Successfully realized n getchar getchar else printf Not realised n getchar getchar break default while op 精品文档 31欢迎下载31 printf n Welcome again n getchar getchar return 1 status IntiaList LNode L free L L LNode malloc sizeof LNode if L NULL return OVERFLOW L next NULL return OK status DestroyList LNode L free L L NULL char req printf Are you sure to destroy the file Y N req getchar if req y req Y remove file0 printf The file has been destroyed n return OK status ClearList LNode L L next NULL return OK 精品文档 32欢迎下载32 status ListEmpty LNode L if L next NULL return TRUE else return FALSE int ListLength LNode L int i 0 printf n s L next data num while L NULL L L next i printf d i return i 1 status GetElem LNode L int i Elemtype e if L length 0 iL length e L elem i return OK else return ERROR status Search LNode L LNode p int i char req1 20 req2 20 p L next printf Search ifo according to which way 1 name 2 tel num scanf d if i 1 printf Please input the name n 精品文档 33欢迎下载33 getchar gets req1 while p NULL if strcmp p data name req1 0 printf name s tel num s p data name p data num loc p return OK else p p next else if i 2 printf Please input the tel num n getchar gets req2 while p NULL if strcmp p data num req2 0 printf name s name s p data name p data num loc p return OK else p p next return OK printf Can not find or choice is wrong n return ERROR status LinkInsert LNode L LNode p q r char req1 20 req2 20 do 精品文档 34欢迎下载34 printf Where to insert after whom Please input the name gets req1 printf s n req1 p L while p next NULL if strcmp req1 p next data name 0 q p break p p next p p next if p NULL printf Please input the data you want to insert scanf s s req1 req2 r LNode malloc sizeof LNode strcpy r data name req1 strcpy r data num req2 q next r r next p return OK else printf Can not find name please repeat n getchar getchar while p NULL return ERROR status LinkDelete LNode L LNode p q int i 精品文档 35欢迎下载35 char req1 20 req2 20 p L next printf Search ifo according to which way 1 name 2 tel num scanf d if i 1 printf Please input the name n getchar gets req1 while p if strcmp p next data name req1 0 q p q next p next next printf Successfully deleted n getchar getchar return OK else p p next else if i 2 printf Please input the tel num n getchar gets req2 while p NULL if strcmp p next data num req2 0 printf name s name s p data name p data num q p q next p next next printf Successfully deleted n getchar ge