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

2021年数据结构实验报告单链表
2021年数据结构实验报告单链表
1 / 22
2021年数据结构实验报告单链表
级数据结构试验汇报
试验名称: 试验一线性表——题目1
学生姓名: 李文超
班 级: 661131
班内序号: 15
学 号: 522147
日 期: 11月13日
2021年数据结构实验报告单链表
2021年数据结构实验报告单链表
2 / 22
2021年数据结构实验报告单链表
试验要求
试验目:
依据线性表抽象数据类型定义, 选择下面任一个链式结构实现线性表, 并完成线性表基础功效。
线性表存放结构（五选一）:
带头结点单链表
不带头结点单链表
循环链表
双链表
静态链表
线性表基础功效:
结构: 使用头插法、 尾插法两种方法
插入: 要求建立链表根据关键字从小到大有序
删除
查找
获取链表长度
2021年数据结构实验报告单链表
2021年数据结构实验报告单链表
3 / 22
2021年数据结构实验报告单链表
销毁
其她: 可自行定义
编写测试main()函数测试线性表正确性。
程序分析
存放结构
单链表存放:
　　（1）链表用一组任意存放单元来存放线性表结点。这组存放单元既能够是连续, 也能够是不连续, 甚至零碎地分布在内存一些位置。
　　（2）链表中结点逻辑次序和物理次序不一定相同。为了能正确表示结点间逻辑关系, 在存放每个元素值同时, 还要存放该元素直接后继元素位置信息, 这个信息称为指针或链。
结点结构
  ┌──┬──┐ data域---存放结点值数据域
  │data│next│ next域---存放结点直接后继地址指针域
  └──┴──┘ 
     
单链表在内存中存放示意
地址 内存单元
a[3]
1080H
……
2021年数据结构实验报告单链表
2021年数据结构实验报告单链表
4 / 22
2021年数据结构实验报告单链表
a[1]
10C0H
……
a[4]
^
……
a[2]
1000H
……
1000H
头指针 1020H
1080H
10C0H


front …………
关键算法分析
1、 关键算法:
（1）头插法
自然语言描述:
2021年数据结构实验报告单链表
2021年数据结构实验报告单链表
5 / 22
2021年数据结构实验报告单链表
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;
2021年数据结构实验报告单链表
2021年数据结构实验报告单链表
6 / 22
2021年数据结构实验报告单链表
d:r=s
（3）遍历打印函数
自然语言描述:
a:判定该链表是否为空链表, 假如是,