数据结构与算法
第二章 线性表(二)
1
wangzhao
内容提要
线性表的概念(逻辑结构) 线性表的顺序表示和实现(顺序表) 线性表的链式表示和实现(链表) 线性表的应用
2
wangzhao
线性表的链式表示和实现
单链表 循环链表 双向链表
3
wangzhao
单链表
线性表的链式表示 单链表的基本运算 单链表的完整程序示例 头结点的作用
4
wangzhao
线性表的链式表示
链接存储的特点:用一组任意的存储单元来存储线性表 链接存储的特点 用一组任意的存储单元来存储线性表 的各个数据元素. 结点:每个元素要存储自身的信息以及指示其后继的信 结点 每个元素要存储自身的信息以及指示其后继的信 息,这两部分信息构成一个数据元素的存储结构,称为 结点 结点. 基本思想: 用附加的指针来表示结点之间的线性关系 假设 个线性表有n个元素,则n个元素所对应的n个结 假设一个线性表有n个元素,则n个元素所对应的n个结 点就通过指针链结成一个链表.由于每个结点只有一个 指针域,故又称为单链表. a0 数据域 指针域
5
a1
...
an-1 ^
单链表
a0 a1 存储地址 1 7 13 19 25 31 37 43 ... an-1 ^ 指针域 43 13 1 NULL 37 7 19 25
6
结点: 数据域
指针域
头指针:指示单链表中 第 个结点(头结点或 第一个结点(头结点或 首元结点)的位置. 头指针H 31
数据域 Li Qian Sun Wang Wu Zhao Zheng Zhou
wangzhao
线性链表的图示
H (数据元素的逻辑顺序,不是存储位置) (数据元素的逻辑顺序 不是存储位置) Zhao Zhou Qian Wu Sun Zheng Li Wang ^
线性链表的逻辑状态(不带头结点) H
数据域可以存储任何附加信息 指针域存储指向第一个节点
a0 头结点
a1
...
an-1 ^
带头结点的线性链表
7
wangzhao

下一页