1 2016 级数据结构实验报告实验名称：实验一线性表——题目1 学生姓名：李文超班级： 2015661131 班内序号： 15 学号： 2015522147 日期： 2016 年 11 月 13 日1
2 实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能
线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的基本功能：1、 构造：使用头插法、尾插法两种方法2、 插入：要求建立的链表按照关键字从小到大有序3、 删除4、 查找5、 获取链表长度6、 销毁7、 其他：可自行定义编写测试 main() 函数测试线性表的正确性
1 存储结构单链表的存储：（1）链表用一组任意的存储单元来存放线性表的结点
这组存储单元既可以是连续的，也可以是不连续的，甚至零散地分布在内存的某些位置
（2）链表中结点的逻辑次序和物理次序不一定相同
为了能正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链
结点结构┌──┬──┐ data域--- 存放结点值的数据域│data │ next │ next域--- 存放结点的直接后继的地址的指针域└──┴──┘单链表在内存中的存储示意地址内存单元a[3] 1080H ⋯⋯a[1] 10C0H ⋯⋯
3 1000H 头指针 1020H 1080H 10C0H front ⋯⋯⋯⋯2
2 关键算法分析1、关键算法：（1）头插法自然语言描述： a:在堆中建立新结点 b:将 a[i]写入到新结点的数据域c: 修改新结点的指针域d: 修改头结点的指针域
将新结点加入链表中伪代码描述 a:Node * s=new Node b:s->data=a[i] c:s-
