2021年整理版链表.ppt

1、单链表
链表的引入
为了解决数组的定长结构的局限性，用“链表”的结构实现一个顺序表。应该说明的是所谓的“链表”结构不仅能表示线性群体，也可以表示非线性群体，如树、图等等。
单链表及其变形是实现线性群体的形式。
单链表是一种最简单的链表，也叫线性链表。每个数据元素占用一个“结点”，每个结点至少要有2个信息：一个该数据元素，另一个反映出它与下一个结点的关联关系，即所谓“指针”，它给出下一个结点的开始存储地址。如下：
空表的标志：head = null
结点(头)
结点
结点
结点(尾)
data
next
→
data
next
→
data
next
→
data
next
→
↑
↑
↑
≡
head
currPtr(当前结点)
rear
null
整理版链 表
2021/1/15
1
单链表(结点定义)
ADT Node is
Data
data // 保存信息
next // 指向下一个结点的指针
Operations
Constructor
NextNode // 返回下一个结点的地址
InsertAfter // 在当前结点后插入一个新结点，并把
// 新结点作为当前结点
DeleteAfter // 删除当前结点后的直接后继
end ADT Node
整理版链 表
2021/1/15
2
单链表(结点封装的方法)
InsertAfter
操作次序
P->next = next;
next = p;
DeleteAfter
操作次序
tempPtr = next;
next = tempPtr->next;
data
next
data
next
↑
↑
↑
↑
currPtr
q
currPtr
q
新结点p
data
next
currPtr
q
tempPtr
data
next
currPtr
q
整理版链 表
2021/1/15
3
单链表(链表的实现)
结点的声明
Template <class T>
class Node
{
private:
Node <T> *next;
public:
T data;
Node(const T& item, Node<T> *next = Null);
void InsertAfter(Node<T> *p);
Node<T> *DeleteAfter(void);
};
例 Node<int> t(10)
Node<char> *p, *q;
q = new Node<char> (‘B’)’;
p = new Node<char> (‘A’, q);
整理版链 表
2021/1/15
4
单链表(构造链表)
生成结点函数GetNode（初始数据值，指针值），返回新结点的指针。
插入头结点函数INSERTFRONT
void InsertFront(Node<T> *&head, T item)
{
head = GetNode(item, head);
};
head head