2016-数据结构实验教程.docx

数 据 结 构 实 验 (2015级信息安全专业适用) 计算机科学与技术学院 数组结构课程组 2016年1月 目 录  TOC \o 1-3 \h \z \u  HYPERLINK \l _Toc440831634 1基于顺序存储结构的线性表实现  PAGEREF _Toc440831634 \h 1  HYPERLINK \l _Toc440831635 1.1 实验目的  PAGEREF _Toc440831635 \h 1  HYPERLINK \l _Toc440831636 1.2 线性表基本运算定义  PAGEREF _Toc440831636 \h 1  HYPERLINK \l _Toc440831637 1.3 实验任务  PAGEREF _Toc440831637 \h 2  HYPERLINK \l _Toc440831638 2基于二叉链表的二叉树实现  PAGEREF _Toc440831638 \h 3  HYPERLINK \l _Toc440831639 2.1 实验目的  PAGEREF _Toc440831639 \h 3  HYPERLINK \l _Toc440831640 2.2 二叉树基本运算定义  PAGEREF _Toc440831640 \h 3  HYPERLINK \l _Toc440831641 2.3 实验任务  PAGEREF _Toc440831641 \h 5  HYPERLINK \l _Toc440831642 参考文献  PAGEREF _Toc440831642 \h 6  HYPERLINK \l _Toc440831643 附录A 顺序表实现框架程序清单  PAGEREF _Toc440831643 \h 7  HYPERLINK \l _Toc440831644 附录B 数据元素的文件读写  PAGEREF _Toc440831644 \h 10  HYPERLINK \l _Toc440831645 附录C 线性表模板实例  PAGEREF _Toc440831645 \h 11  TOC \h \z \c 图表  PAGE \* MERGEFORMAT 14 1基于顺序存储结构的线性表实现 1.1 实验目的 通过实验达到⑴加深对线性表的概念、基本运算的理解；⑵熟练掌握线性表的逻辑结构与物理结构的关系；⑶物理结构采用顺序表,熟练掌握线性表的基本运算的实现。 1.2 线性表基本运算定义 依据最小完备性和常用性相结合的原则，以函数形式定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等12种基本运算，具体运算功能定义如下。 ⑴初始化表：函数名称是InitaList(L)；初始条件是线性表L不存在已存在；操作结果是构造一个空的线性表。 ⑵销毁表：函数名称是DestroyList(L)；初始条件是线性表L已存在；操作结果是销毁线性表L。 ⑶清空表：函数名称是ClearList(L)；初始条件是线性表L已存在；操作结果是将L重置为空表。 ⑷判定空表：函数名称是ListEmpty(L)；初始条件是线性表L已存在；操作结果是若L为空表则返回TRUE,否则返回FALSE。 ⑸求表长：函数名称是ListLength(L)；初始条件是线性表已存在；操作结果是返回L中数据元素的个数。 ⑹获得元素：函数名称是GetElem(L,i,e)；初始条件是线性表已存在，1≤i≤ListLength(L)；操作结果是用e返回L中第i个数据元素的值。 ⑺查找元素：函数名称是LocateElem(L,e,compare())；初始条件是线性表已存在；操作结果是返回L中第1个与e满足关系compare（）关系的数据元素的位序，若这样的数据元素不存在，则返回值为0。 ⑻获得前驱：函数名称是PriorElem(L,cur_e,pre_e)；初始条件是线性表L已存在；操作结果是若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。 ⑼获得后继：函数名称是NextElem(L,cur_e,next_e)；初始条件是线性表L已存在；操作结果是若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。 ⑽插入元素：函数名称是ListInsert(L,i,e)；初始条件是线性表L已存在且非空，1≤i≤ListLength(L)+1；操作结果是在L的第i个位置之前插入新的数据元素e。 ⑾删除元素：函数名称是ListDel