文档介绍：第2章数据结构基础
线性表
将集合中的n 个元素一字排列:
a1,a2,…,ai-1,ai,ai+1,…,an
↑↑
表首表尾
有且仅有一个元素a1没有前驱,该元素称为表首;有且仅有一个元素an没有后继,称为表尾;此外的所有1 < i < n的元素ai均有一个前驱ai-1,且有一个后继ai+1。以这样的方式组织起来的数据结构称为一个线性表。
在计算机中,用一个连续存储的数组来表示一个线性表是很自然的,因为数组的下标自然地表示出了线性表中元素的前后关系。
线性表的链表表示
链表常用来表示可变长线性表。链表中为每一个元素单独分配一个称为结点的存储空间,元素间的前后顺序是由指向每个结点的指针确定的。
带有哨兵结点的环形链表
在一个链表中,若表首的prev域指向表尾,而表尾的next域指向表首,称为环形表。此时表可视为一个由元素构成的环。这样,链表中任何一个结点都有唯一前驱和后继。
我们为链表L添加一个哨兵结点nil[L]:它不表示任何数据元素,但它是头结点的前驱,尾结点的后继。添加了哨兵后,形成了一个环形链表,其中的每个结点都有各自的前驱和后继。
对链表的扫描
LIST-DISPLAY(L)
1 xnext[nil[L]]x指向头结点
2 while xnil[L]x指向链表中的正常结点
3 do print key[x]
4 xnext[x]
运行时间T(n)=(n),n为L的结点数。
在链表中查找
LIST-SEARCH (L, k)
1 x ←next[nil[L]] 从表首结点开始
2 while x ≠nil[L] and key[x] ≠ k
3 do x ← next[x]
4 return x
运行时间T(n)=O(n),n为L的结点数。
将元素插入到链表中
LIST-INSERT(L, a, x) 在L的结点a之前插入新的结点x
1 if x=nil[L]
2 then return
3 b prev[a]
4 prev[x] b
5 next[x]  a
6 next[b]  prev[a] x
运行时间T(n)=(1)。
从链表中删除元素
LIST-DELETE(L, x)
1 if x=NIL 空结点
2 then return
3 a←next[x]
4 b←prev[x]
5 next[b] ←a
6 prev[a] ←b
运行时间T(n)=(1)。
栈
栈是用线性表表示的动态集合,INSERT操作DELETE操作均被限制在表首。在栈中,从集合中删除的元素是最近才插入其中的:栈实现的是后进先出或LIFO的策略。
可以用一个链表来实现一个栈S。S有两个属性:一个是链表L[S],另一个属性是栈顶top[S],它指向最近才插入的元素(表头head)。
栈的基本操作
STACK-EMPTY(S)
1 if top[S] = nil[L[S]]
2 then return TRUE
3 else return FALSE
运行时间T(n)=(1)。
PUSH(S, x)
1 创建一个以x为关键值的结点x1
2 LIST-INSERT(L[S], next[nil[L[S]]], x1)
3 top[S]  x1
运行时间T(n)=(1)。
POP(S)
1 if STACK-EMPTY(S)
2 then error "underflow"
3 else xtop[S]
4 top[S] next[x]
5 LIST-DELETE(L[S],x)
6 return x
运行时间T(n)=(1)。