数据结构实验报告单链表.docx

Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
数据结构实验报告单链表
2016级数据结构实验报告
实验名称： 实验一线性表——题目1
学生姓名： 李文超
班 级：
班内序号： 15
学 号： 47
日 期： 2016年11月13日
实验要求
实验目的：
根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选一）：
带头结点的单链表
不带头结点的单链表
循环链表
双链表
静态链表
线性表的基本功能：
构造：使用头插法、尾插法两种方法
插入：要求建立的链表按照关键字从小到大有序
删除
查找
获取链表长度
销毁
其他：可自行定义
编写测试main()函数测试线性表的正确性。
程序分析
存储结构
单链表的存储：
　　（1）链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的，也可以是不连续的，甚至零散地分布在内存的某些位置。
　　（2）链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链。
结点结构
┌──┬──┐ data域---存放结点值的数据域
│data│next│ next域---存放结点的直接后继的地址的指针域
└──┴──┘？

单链表在内存中的存储示意
地址 内存单元
a[3]
1080H
……
a[1]
10C0H
……
a[4]
^
……
a[2]
1000H
……
1000H
头指针 1020H
1080H
10C0H
front …………
关键算法分析
1、关键算法：
（1）头插法
自然语言描述：
a:在堆中建立新结点
b:将a[i]写入到新结点的数据域
c:修改新结点的指针域
d:修改头结点的指针域。将新结点加入链表中
伪代码描述
a:Node <T> * s=new Node <T>
b:s->data=a[i]
c:s->next=front->next;
d:front->next=s
（2）尾插法
自然语言描述：
a:在堆中建立新结点：
b:将a[i]写入到新结点的数据域：
c:将新结点加入到链表中
d:修改修改尾指针
伪代码描述
a:Node <T> * s=new Node <T>
b:s->data=a[i]
c:r->next=s;
d:r=s
（3）遍历打印函数
自然语言描述：
a:判断该链表是否为空链表，如果是，报错
b:如果不是空链表，新建立一个temp指针
c:将temp指针指向头结点
d:打印temp指针的data域
e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空
伪代码描述
a: If front->next==NULL
Throw ”an empty list ”
Node<T>* temp=front->next;
b:while(temp->next)
c:cout<<temp->data<<" ";
d:temp=temp->next;
(4) 获取链表长度函数