数据结构——算法学习（三）上
前言
数据结构是计算机科学的基石，几乎所有的软件开发、算法设计都离不开对数据的组织与管理。它不仅是程序高效运行的保障，也是解决复杂问题的关键工具。学习数据结构的过程，不仅仅是掌握具体的知识点，更是培养逻辑思维能力和问题解决能力的重要途径。
在本章中，我们要讨论如何通过使用指针的简单数据结构来表示动态集合。虽然运用指针可以构造多种复杂的数据结构，但这里只介绍几种基本的结构：栈、队列、链表和有根树。
有限动态集合
概念
可以进行增大、缩小或其他变化的集合，集合中的每个元素都由一个对象表示
常见的动态集合操作
SEARCH(S,k)：返回在集合S中指向关键字k的指针，没有则返回NIL
NSERT(S,x)：将指针x指向的元素加入到集合S中
DELETE(S,x)：将指针x指向的元素从集合S中删除
MINIMUM(S)：返回指向全序集S中具有最小关键字元素的指针
MAXIMUM(S)：返回指向全序集S中具有最大关键字元素的指针
SUCCESSOR(S,x)：返回全序集S中比元素x大的下一个元素的指针，没有则返回NIL
PREDECESSOR(S,x)：返回全序集S中比元素x小的前一个元素的指针，没有则返回NIL
线性数据结构
线性数据结构是指数据元素按照线性顺序排列，每个元素仅有一个直接前驱和一个直接后继，常见形式包括数组、链表、栈和队列，广泛应用于数据存储与算法设计中，因其简单直观的特性而成为计算机科学的重要基础。
栈
栈(Stack)实现一种在进行DELETE操作时后进先出(last-in, first-out, LIFO)的策略
栈上的INSERT操作称为压入PUSH，DELETE操作称为弹出POP
对空栈的弹出操作称为栈下溢，若S.top超过了n则称为栈上溢，检查栈空的查询操作STACK_EMPTY
实现栈的空判断、push、pop的伪代码( 这三种栈操作的执行时间都为O(1) )
Function stack-empty(S):
if S.top = 0 then return true;
else return false;
end
Function push(S,x):
if S.top = S.capactity then error "overflow";
S.top <- S.top + 1;
S[S.top] <- x;
end
Function pop(S):
if stack-empty(S) then error "underflow";
else
S.top <- S.top - 1;
return S[S.top+1];
end
end
队列
队列实现一种在进行DELETE操作时先进先出的策略
队列上的INSERT操作称为入队(ENQUEUE)，DELETE操作称为出队(DEQUEUE)
队列有队头(head)和队尾(tail)
实现队列ENQUEUE、DEQUEUE操作伪代码
Function enqueue(Q,x):
if S.head = S.tail then error "overflow";
Q[Q.tail] <- x;
if Q.tail = Q.capacity then Q.tail <- 1;
else Q.tail <- Q.tail + 1;
end
Function dequeue(Q):
if S.head = S.tail then error "underflow";
x <- Q[Q.head];
if Q.head = Q.capacity then Q.head <- 1;
else Q.head <- Q.head + 1;
return x;
end
链表
链表是一种元素按线性顺序排列的数据结构，元素的顺序由元素内部的指针决定
链表的几种形式：
- 单链接链表中元素没有prev指针，双链接链表不省略
- 已排序链表中元素的线性顺序与关键字线性顺序一致，未排序链表元素可按任意顺序出现
- 循环链表中表头元素的prev指针指向表尾元素，表尾元素的next指针指向表头元素
无哨兵的链表操作实现伪代码：
Function list-search(L,k):
x <- L.head;
while x != NIL and x.key != k do x <- x.next;
return x;
end
Function list-insert(L,x):
x.next <- L.head;
if L.head !=NIL then L.head.prev <- x;
L.head <- x;
x.prev <- NIL;
end
Function list-delete(L,x):
if x.prev != NIL then x.prev.next <- x.next;
else L.head <- x.next;
if x.next != NIL then x.next.next <- x.prev;
end
带哨兵的链表操作实现伪代码：
Function list-search(L,k):
x <- L.nil.next;
while x != L.nil and x.key != k do x <- x.next;
return x;
end
Function list-insert(L,x):
x.next <- L.nil.next;
L.nil.next.prev <- x;
L.nil.next <- x;
x.prev <- L.nil;
end
Function list-delete(L,x):
x.prev.next <- x.next;
x.next.prev <- x.prev;
end
图和树
图
有向图G是一个二元组（V，E），其中V是有限集，E是V上的二元关系。集合V称为图G的顶点集，其元素称为顶点。集合E是G的边集，其元素称为边。图中可能存在自环
有向图G = (V,E),其中V = {1,2,3,4,5,6},E = {(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)}
在无向图G = (V,E)中，边集E由无序的顶点对组成，其中V = {1,2,3,4,5,6},E={(1,2),(1,5),(2,5),(3,6)}
树
概念
一、自由树
自由树是一个连通的、无环的无向图，不连通的无环无向图称为森林，对于自由树G = (V,E)，有|E| = |V|-1
二、有根树
有根树是一棵自由树，存在一个顶点作为树的根。
从有根树T中的一个结点x到根r的简单路径上的任一结点y称为x的一个祖先，x是y的后代。每个结点既是自己的祖先也是自己的后代。若y是x的祖先且y≠x，则y是x的真祖先；若y是x的后代且y≠x，则y是x的真后代
以x为根的子树是根为x由x的后代组成的有根树
如果从根r到结点x的简单路径上的最后一条边是(y,x)，则y是x的父结点，而x是y的子结点。若两个结点有相同的父结点，则它们是兄弟。一个没有子结点的结点为叶结点（或外部结点），非叶结点也称内部结点
有根树T的结点x的度等于其子结点的数目，从根r到结点x的简单路径的长度即为x在T中的深度，有根树T的高度等于树中结点的最大深度
三、有序树
有序树是每个结点的子结点都有序的有根树
四、二叉树
二叉树T是定义在有限结点集上的结构，它或者不包含任何结点，或者包含三个不相交的结点集合：一个根结点，一棵称为左子树的二叉树，一棵称为右子树的二叉树，不包含任何结点的二叉树称为空树或零树，有时用符号NIL表示
若左子树非空，则它的根结点称为整棵树的根的左孩子；类似地，非空右子树地根称为整棵树的根的右孩子，如果一棵子树是零树，则称该孩子是缺失的
二叉树不仅仅是一棵结点度数均为2的有序树，一棵满二叉树的每个结点或是叶结点或度为2
五、完美二叉树和完全二叉树
完美二叉树的所有内部结点均有2个子结点，所有叶结点深度相同，高度为k完美二叉树包含2^k-1个结点
•完全二叉树除最后一层外其余层都是满的，且最后一层要么是满的，要么在右边缺少若干连续结点，高度为k的完全二叉树最少有2(k-1)个结点，最多有2k-1个结点，一个包含n个结点的完全二叉树高度为⌊lgn ⌋+1
二叉树的表示
每个结点具有三个属性p、left和right，分别存放指向父结点、左孩子和右孩子的指针，如果x.p=NIL，则x是根结点；如果x没有左孩子，则x.left=NIL；如果x没有右孩子，则x.right=NIL，T.root指向整棵树的根结点，如果T.root=NIL则该树为空
对于每个结点至多有k个孩子的有根树，每个结点维护k个指针可能造成大量空间浪费,使用左孩子右兄弟表示法来避免空间浪费，每个结点维护三个指针：
- 指向父结点的指针x.p
- 指向最左边孩子的指针x.left_child
- 指向右侧相邻兄弟的指针x.right_sibling
如果结点x没有孩子结点，则x.left_child=NIL；如果结点x是其父结点的最右孩子，则x.right_sibling=NIL
二叉堆
二叉堆是一棵完全二叉树
二叉堆有两种形式:
- 最大堆（大根堆）
除根结点外的所有节点满足A[parent(i)]≥A[i] - 最小堆（小根堆）
除根结点外的所有节点满足A[parent(i)]≤A[i]
实现维护二叉堆的性质(假定根节点为left(i)和right(i)的二叉堆都是最大堆)
//递归
Function max-heapify（A,i)：
l <- left(i)；
r <- right(i)；
if l <= A.heapSize and A[l] > A[i] then largest <- l;
else largest <- i；
if r <= A.heapSize and A[r] > A[i] then largest <- r;
if largest != i then
exchange A[j] with A[largest];
max-heapify（A,largest)；
end
end
//非递归
Function max-heapify(A,i):
while i <- A.heapSize/2 do
l←left(i)；
r←right（i)；
if l <= A.heapSize and A[l] > A[i] then largest <- l;
else largest <- i；
if r <= A.heapSize and A[r] > A[i] then largest <- r;
if largest != i then
exchange A[i] with A[largest];
i <- largest;
end
else break;
end
end
建堆
Function build-max-heap(A):
A.heapSize <- A.length;
for i <- [A.length/2] downto 1 do
max-heapify(A,i);
end
end