没有合适的资源?快使用搜索试试~ 我知道了~
U201610504_刘逸帆_数据结构实验报告1
需积分: 0 0 下载量 122 浏览量
2022-08-08
18:32:06
上传
评论
收藏 3.33MB DOCX 举报
温馨提示
试读
264页
1.1.1 线性表抽象数据类型依据最小完备性和常用性相结合的原则,设计了线性表的数据对象和数据关系,并定义了线性表的初始化、销毁、置空、求长度、获取数据元素等1
资源详情
资源评论
资源推荐
课 程 实 验 报 告
课程名称: 数据结构实验
专业班级: 校际交流 1601 班
学 号: U201610504
姓 名: 刘逸帆
指导教师: 魏巍
报告日期: 2018 年 1 月 11 日
计算机科学与技术学院
华中科技大学计算机学院数据结构实验报告
2
目 录
1 基于顺序存储结构的线性表实现......................................1
1.1 问题描述......................................................1
1.2 系统设计......................................................3
1.3 系统实现.....................................................15
1.4 实验小结.....................................................33
2 基于链式存储结构的线性表实现.....................................36
2.1 问题描述.....................................................36
2.2 系统设计 .....................................................38
2.3 系统实现 .....................................................50
2.4 实验小结 .....................................................68
3 基于链式存储结构的二叉树实现.....................................70
3.1 问题描述 .....................................................70
3.2 系统设计 .....................................................73
3.3 系统实现 .....................................................93
3.4 实验小结 ....................................................121
4 基于邻接表存储结构的图(无向网)实现 ..............................124
4.1 问题描述 ....................................................124
4.2 系统设计 ....................................................126
4.3 系统实现 ....................................................144
4.4 实验小结 ....................................................173
参考文献 .........................................................177
附录 A 基于顺序存储结构的线性表实现的源程序 .......................179
附录 B 基于链式存储结构的线性表实现的源程序 .......................191
附录 C 基于链式存储结构的二叉树实现的源程序 .......................206
附录 D 基于邻接表存储结构的图实现的源程序 .........................232
华中科技大学计算机学院数据结构实验报告
1
1 基于顺序存储结构的线性表实现
1.1 问题描述
为实现基于顺序存储结构的线性表及以此为基础的多表管理、文件读写功
能,按如下形式设计数据的逻辑结构及基本运算。
1.1.1 线性表抽象数据类型
依据最小完备性和常用性相结合的原则,设计了线性表的数据对象和数据
关系,并定义了线性表的初始化、销毁、置空、求长度、获取数据元素等 12 种
基本运算,具体数据和运算功能定义如下。
1. 数据结构
数据对象:D = { a
i
|a
i
∈ Elem }
数据关系:R = { <a
i-1
,a
i
>|a
i-1
, a
i
∈D }
2. 基本运算
初始化表:函数名称是 InitaList(*L);初始条件是线性表 L 不存在;操
作结果是构造一个空的线性表。
销毁表:函数名称是 DestroyList(*L);初始条件是线性表 L 已存在;操
作结果是销毁线性表 L。
清空表:函数名称是 ClearList(*L);初始条件是线性表 L 已存在;操作
结果是将 L 重置为空表。
判定空表:函数名称是 ListEmpty(L);初始条件是线性表 L 已存在;操作
结果是若 L 为空表则返回 OK,否则返回 ERROR。
求表长:函数名称是 ListLength(*L);初始条件是线性表已存在;操作结
果是返回 L 中数据元素的个数。
获得元素:函数名称是 GetElem(L,i,*e);初始条件是线性表已存在,1≤
i≤ListLength(L);操作结果是用 e 返回 L 中第 i 个数据元素的值。
查找元素:函数名称是 LocateElem(L,e,*i);初始条件是线性表已存在;
操作结果是用 i 返回 L 中第 1 个数据元素 e 的位序,若这样的数据元素不存
在,则返回值为 0。
华中科技大学计算机学院数据结构实验报告
2
获得前驱:函数名称是 PriorElem(L,cur,*pre_e);初始条件是线性表 L
已存在;操作结果是若 cur 是 L 的数据元素,且不是第一个,则用 pre_e 返回
它的前驱,否则操作失败,pre_e 无定义。
获得后继:函数名称是 NextElem(L,cur,*next_e);初始条件是线性表 L
已存在;操作结果是若 cur 是 L 的数据元素,且不是最后一个,则用 next_e 返
回它的后继,否则操作失败,next_e 无定义。
插入元素:函数名称是 ListInsert(*L,i,e);初始条件是线性表 L 已存
在,1≤i≤ListLength(L)+1;操作结果是在 L 的第 i 个位置之前插入新的数据
元素 e。
删除元素:函数名称是 ListDelete(*L,i,*e);初始条件是线性表 L 已存
在且非空,1≤i≤ListLength(L);操作结果:删除 L 的第 i 个数据元素,用 e
返回其值。
遍历表:函数名称是 ListTraverse(L),初始条件是线性表 L 已存在;操
作结果是依次输出展示 L 的每个数据元素。
1.1.2 多线性表抽象数据类型
基于 1.1.1 中已经实现的线性表数据类型与基本运算功能,设计多线性表
的数据对象、数据关系。具体数据和多表间切换功能定义如下。
1. 数据结构
数据对象:D = { e
i
|e
i
∈ SqList }
数据关系:R = { <e
i-1
,e
i
>|e
i-1
,e
i
∈D }
2. 基本运算
定义 Sqlist 类型静态数组 MulList[MAX],其中 MAX 即多顺序表个数;定
义 Sqlist 类型指针*L,通过其指向数组的不同元素实现对多顺序表的基本操
作。
1.1.3 演示系统与数据文件
构造一个具有文本菜单的功能演示系统,用于演示对顺序表以及多表进行
的各项操作。其中,在主函数中完成子函数调用所需的参数输入、结果显示以
及对应的文字操作提示。
华中科技大学计算机学院数据结构实验报告
3
在设计了相应数据存储格式后,演示系统可进行线性表数据的文件保存或
读取,增加系统合理性。
演示系统还可以根据需要实现多线性表的管理操作。
1.2 系统设计
对数据类型与基本操作进行相应分析后,从物理结构,具体算法等方面合
理设计系统,具体设计分析如下。
1.2.1 数据物理结构
1. 线性表数据的存储结构
typedef struct{ //顺序表(线性表/顺序结构)的定义
ElemType *elem; //指向线性表数据的线性存储区
int length; //表中元素个数(长度)
int listsize; //存储容量
}SqList;
2. 多线性表数据的存储结构
SqList MulList[MAX] //通过数组形式构建多表结构
多线性表数据的物理存储结构如图 1-1 所示。
图 1-1 多线性表数据的物理存储结构
1.2.2 演示系统
演示系统使用基于标准输入输出库(stdio.h)实现的文本界面,由功能菜
单界面和用户操作(交互)界面组成。
剩余263页未读,继续阅读
宏馨
- 粉丝: 20
- 资源: 293
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0