“Algorithm + Data Structures = Programs” - Niklaus Wirth

栈和队列

栈和队列都是动态集合,且在其上进行 DELETE 操作所移除的元素都是预先设定的。

  • 在栈(stack)中,被删除的是最近插入的元素;栈实现的是一种后进先出(last-in first out, LIFO)策略。
  • 在队列(queue)中,被删去的总是在集合中存在时间最长的那个元素;队列实现的是一种先进先出(First-in first out, FIFO)策略。

可以用一个数组 \(S[1..n]\) 来实现一个最多可容纳 \(n\) 个元素的栈。该数组有一个属性 S.top,指向最新插入的元素。栈中包含的元素为 \(S[1..S.top]\),其中 \(S[1]\) 是栈底元素,而 \(S[S.top]\) 是栈顶元素。

栈S的数组实现

实现

C语言实现的倒序打印:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <stdlib.h>
int stack[512];
int top = 0;
int isEmpty()
{
if (top > 0)
return 1;
else
return 0;
}
int pop()
{
if (isEmpty())
return stack[top--];
}
void push(int num)
{
stack[++top] = num;
}
int main(void){
int i;
for (i = 0; i<10; i++) {
push(i);
}
while(!isEmpty()){
printf("%d ", pop());
}
}

链表

链表(linked list)是一种这样的数据结构,其中的各对象按线性顺序排列。数组的线性顺序是由数组下标决定的,然而与数组不同的是,链表的顺序是由各个对象里的指针决定的。链表为动态集合提供了一种简单而灵活的表示方法,并且可以支持大多数动态集合的操作。

每个链表有一个头指针(head),通过头指针可以找到第一个节点,每个节点都可以通过指针域找到它的后继(next),最后一个节点的指针域为NULL,表示没有后继。数组在内存中是连续存放的,而链表在内存中的布局是不规则的,我们知道访问某个数组元素 b[n] 时可以通过 基地址+n×每个元素的字节数 得到它地址,或者说数组支持随机访问,而链表是不支持随机访问的,只能通过前一个元素的指针域得知后一个元素的地址,因此只能从头指针开始顺序访问各节点。

定义

1
2
3
4
typedef struct Node{
int data;
Node *next;
}Node, *list;

创建结点

1
2
3
4
5
6
7
Node* createNode(int data)
{
Node *p = new Node;
p->data = data;
p->next = NULL;
return p;
}

删除结点

1
2
3
4
void freeNode(Node *p)
{
delete p;
}

遍历所有结点

1
2
3
4
5
6
7
8
9
10
11
void visit(Node *p)
{
printf("%d ", p->data);
}
void traverse(Node *head, void (*visit)(Node *))
{
for (Node *p = head; p; p = p->next){
visit(p);
}
}

查找结点

查找第一个值为 key 的结点

1
2
3
4
5
6
7
Node* searchNode(Node *head, int key)
{
for(Node *p = head; p; p = p->next){
if (p->data == key) return p;
}
return NULL;
}

查找第 pos 个位置的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node* accessNode (Node *head, int pos){
if (pos < 0) {
perror("Incorrect position!");
return NULL;
}
if (pos == 0) return head;
Node *p = head;
int i;
for (i = 0; i < pos && p; i++){
p = p->next;
}
if (i == pos) return p;
else {
printf("Incorrect position!");
return NULL;
}
}

插入结点

头插入

1
2
3
4
5
6
7
8
9
10
11
Node* insertHead(Node *head, Node *nd){
nd->next = head;
head = nd;
return head;
}
Node* insertHead(Node *head, int data){
Node *nd = createNode(data);
head = insertHead(head, nd);
return head;
}

尾插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Node* insertTail(Node *head, Node *nd){
if (!head){
head = nd;
} else {
Node *p;
for (p = head; p->next; p = p->next);
p->next = nd;
p = nd;
}
return head;
}
Node* insertTail(Node *head, int data){
Node *nd = createNode(data);
head = insertTail(head, nd);
return head;
}

任意位置插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Node* insertNode(Node *head, int pos, Node *nd){
if (pos < 0) {
perror("Incorrect position!");
return head;
}
if (pos == 0 && !head){
head = nd;
return NULL;
}
Node *p = accessNode(head, pos-1);
if (p != NULL){
nd->next = p->next;
p->next = nd;
} else {
perror("Incorrect position!");
}
return head;
}
Node* insertNode(Node *head, int pos, int data){
Node *nd = createNode(data);
insertNode(head, pos, nd);
return head;
}

删除结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Node* deleteNode(Node *head, int pos)
{
if (pos < 0){
perror("Invalidate position!");
return head;
}
if (!head){
perror("Link is empty!");
return NULL;
}
Node *p;
if (pos == 0){
p = head;
head = head->next;
freeNode(p);
return head;
}
p = accessNode(head, pos-1);
if (p != NULL && p->next != NULL){
Node *item = p->next;
p->next = item->next;
freeNode(item);
} else {
perror("Invalidate position!");
}
return head;
}

用数组初始化一个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Node* init(int a[], int n)
{
Node *head = NULL;
if (n < 0){
perror("Invalidate length!");
return NULL;
}
Node *p;
for (int i = 0; i < n; ++i){
//or: insertNode(i, a[i]);
//or: insertTail(a[i]);
Node *nd = createNode(a[i]);
if (NULL == head){
head = p = nd;
continue;
}
p->next = nd;
p = nd;
}
return head;
}

清空一个链表

1
2
3
4
5
6
7
8
9
10
11
12
Node* destroy(Node *head)
{
Node *p = head;
Node *q;
while(p){
q = p;
p = p->next;
freeNode(q);
}
head = NULL;
return head;
}

求链表长

1
2
3
4
5
6
7
8
9
int length(Node *head)
{
Node *p = head;
int i;
for(i = 0; p; ++i){
p = p->next;
}
return i;
}

获取链表中间结点

用一个快指针和一个慢指针实现。慢指针移动的速度是快指针的一半,当快指针走完链表时,输出慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node* accessMid(Node *head)
{
Node *slow = head;
Node *fast = head;
int i = 0;
int j = 0;
while(fast){
if (j < i/2){
slow = slow->next;
++j;
}
fast = fast->next;
++i;
}
return slow;
}

单链表排序

最简单的可以使用选择排序实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Node* selectionSort(Node *head)
{
if (!head) return head;
Node *p, *q, *min;
int t;
for (p = head; p; p = p->next){
min = p;
for (q = p; q; q = q->next)
if (q->data < min->data) min = q;
if (min != p){
t = min->data;
min->data = p->data;
p->data = t;
}
}
return head;
}

将单链表反转

从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O(n)。参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 反转单链表
Node * reverseList(Node * pHead)
{
// 如果链表为空或只有一个结点,无需反转,直接返回原链表头指针
if(pHead == NULL || pHead->next == NULL)
return pHead;
Node *pReversedHead = NULL; // 反转后的新链表头指针,初始为NULL
Node *pCurrent = pHead;
while(pCurrent != NULL)
{
Node *pTemp = pCurrent;
pCurrent = pCurrent->next;
pTemp->next = pReversedHead; // 将当前结点摘下,插入新链表的最前端
pReversedHead = pTemp;
}
return pReversedHead;
}

逆序打印单链表

对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况。时间复杂度为O(n)。参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 从尾到头打印链表,使用递归
void reversePrint(Node *pHead)
{
if(pHead == NULL)
{
return;
}
else
{
reversePrint(pHead->next);
printf("%d\t", pHead->data);
}
}

判断是否存在环

用一个快指针和一个慢指针实现。慢指针每次移动一步,快指针就移动两步。如果两个指针能够相遇,证明存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isLoop(Node *head)
{
Node *slow = head, *fast = head;
if (NULL == head || NULL == head->next) return false;
do {
fast = fast->next->next;
slow = slow->next;
}
while (fast && fast->next && fast!=slow);
if (fast == slow){
return true;
}
else return false;
}

找出环的起点

当快指针和慢指针相遇后,慢指针返回链表头,快指针从相遇点开始,两个指针重新恢复一次一步的速度移动。如果再次相遇,则该相遇的地点即为环的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node* loopstart(Node *head)
{
if (NULL == head || NULL == head->next) return NULL;
Node *slow = head, *fast = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
if(!fast || !fast->next) return NULL;
slow = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}

判断两个单链表是否相交

如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1+len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为 O(1)。参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isIntersected(Node *pHead1, Node *pHead2)
{
if(pHead1 == NULL || pHead2 == NULL)
return false;
Node* pTail1 = pHead1;
while(pTail1->next != NULL)
pTail1 = pTail1->next;
Node* pTail2 = pHead2;
while(pTail2->next != NULL)
pTail2 = pTail2->next;
return pTail1 == pTail2;
}

求两个单链表相交的第一个节点

  1. 对第一个链表遍历,计算长度len1,同时保存最后一个节点的地址。
  2. 对第二个链表遍历,计算长度len2,同时检查最后一个节点是否和第一个链表的最后一个节点相同,若不相同,不相交,结束。

两个链表均从头节点开始,假设len1大于len2,那么将第一个链表先遍历len1-len2个节点,此时两个链表当前节点到第一个相交节点的距离就相等了,然后一起向后遍历,直到两个节点的地址相同。

时间复杂度,O(len1+len2)。参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
Node* GetFirstCommonNode(Node *pHead1, Node * pHead2)
{
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
int len1 = 1;
Node * pTail1 = pHead1;
while(pTail1->next != NULL)
{
pTail1 = pTail1->next;
len1++;
}
int len2 = 1;
Node * pTail2 = pHead2;
while(pTail2->next != NULL)
{
pTail2 = pTail2->next;
len2++;
}
if(pTail1 != pTail2) // 不相交直接返回NULL
return NULL;
Node *pNode1 = pHead1;
Node *pNode2 = pHead2;
// 先对齐两个链表的当前结点,使之到尾节点的距离相等
if(len1 > len2)
{
int k = len1 - len2;
while(k--)
pNode1 = pNode1->next;
}
else
{
int k = len2 - len1;
while(k--)
pNode2 = pNode2->next;
}
while(pNode1 != pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}

二叉树

二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序不能任意颠倒。

节点定义

1
2
3
4
5
6
struct Node
{
int data;
Node* lchild;
Node* rchild;
};

有些实现还会带上父节点:

1
2
3
4
5
6
7
struct Node
{
int data;
Node* lchild;
Node* rchild;
Node* parent;
};

求节点数

递归解法:

  1. 如果二叉树为空,节点个数为0
  2. 如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

1
2
3
4
5
int getNodeNum(Node *pRoot)
{
if(pRoot == NULL) return 0;
return getNodeNum(pRoot->lchild) + getNodeNum(pRoot->rchild) + 1;
}

求树高

递归解法:

  1. 如果二叉树为空,二叉树的树高为0
  2. 如果二叉树不为空,二叉树的树高 = max(左子树树高, 右子树树高) + 1

1
2
3
4
5
6
int getDepth(Node *pRoot){
if(pRoot == NULL) return 0;
int ld = getDepth(pRoot->lchild);
int rd = getDepth(pRoot->rchild);
return ld > rd ? (ld + 1) : (rd + 1);
}

遍历

前序遍历

递归解法:

  1. 如果二叉树为空,空操作
  2. 如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树

1
2
3
4
5
6
7
void preOrderTraverse(Node *pRoot)
{
if(pRoot == NULL) return;
visit(pRoot); // 访问根节点
preOrderTraverse(pRoot->lchild); // 前序遍历左子树
preOrderTraverse(pRoot->rchild); // 前序遍历右子树
}

中序遍历

递归解法:

  1. 如果二叉树为空,空操作
  2. 如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树

1
2
3
4
5
6
7
void inOrderTraverse(Node *pRoot)
{
if(pRoot == NULL) return;
inOrderTraverse(pRoot->lchild); // 中序遍历左子树
visit(pRoot); // 访问根节点
inOrderTraverse(pRoot->rchild); // 中序遍历右子树
}

后序遍历

递归解法:

  1. 如果二叉树为空,空操作
  2. 如果二叉树不为空,后序遍历左子树,后序遍历右子树,访问根节点

1
2
3
4
5
6
7
void postOrderTraverse(Node *pRoot)
{
if(pRoot == NULL) return;
postOrderTraverse(pRoot->lchild); // 后序遍历左子树
postOrderTraverse(pRoot->rchild); // 后序遍历右子树
visit(pRoot); // 访问根节点
}

层序遍历

相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void levelTraverse(Node *pRoot)
{
if(pRoot == NULL) return;
queue<Node*> q;
q.push(pRoot);
while(!q.empty())
{
Node *pNode = q.front();
q.pop();
visit(pNode); // 访问节点
if(pNode->lchild != NULL)
q.push(pNode->lchild);
if(pNode->rchild != NULL)
q.push(pNode->rchild);
}
return;
}

求二叉树第K层的节点个数

递归解法:

  1. 如果二叉树为空或者k<1返回0
  2. 如果二叉树不为空并且k==1,返回1
  3. 如果二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树k-1层节点个数之和

1
2
3
4
5
6
7
8
int getNodeNumKthLevel(Node *pRoot, int k)
{
if(pRoot == NULL || k < 1) return 0;
if(k == 1) return 1;
int numLeft = getNodeNumKthLevel(pRoot->lchild, k-1); // 左子树中k-1层的节点个数
int numRight = getNodeNumKthLevel(pRoot->rchild, k-1); // 右子树中k-1层的节点个数
return (numLeft + numRight);
}

求二叉树中叶子节点的个数

递归解法:

  1. 如果二叉树为空,返回0
  2. 如果二叉树不为空且左右子树为空,返回1
  3. 如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数

1
2
3
4
5
6
7
8
9
10
int getLeafNodeNum(Node * pRoot)
{
if(pRoot == NULL)
return 0;
if(pRoot->lchild == NULL && pRoot->rchild == NULL)
return 1;
int numLeft = getLeafNodeNum(pRoot->lchild); // 左子树中叶节点的个数
int numRight = getLeafNodeNum(pRoot->rchild); // 右子树中叶节点的个数
return (numLeft + numRight);
}

判断二叉树是不是平衡二叉树

递归解法:

  1. 如果二叉树为空,返回真
  2. 如果二叉树不为空,如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isAVL(Node *pRoot, int &height)
{
if(pRoot == NULL) // 空树,返回真
{
height = 0;
return true;
}
int heightLeft;
bool resultLeft = isAVL(pRoot->lchild, heightLeft);
int heightRight;
bool resultRight = isAVL(pRoot->rchild, heightRighte);
if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL,并且高度相差不大于1,返回真
{
height = max(heightLeft, heightRight) + 1;
return true;
} else {
height = max(heightLeft, heightRight) + 1;
return false;
}
}

求二叉树的镜像

递归解法:

  1. 如果二叉树为空,返回空
  2. 如果二叉树不为空,求左子树和右子树的镜像,然后交换左子树和右子树

1
2
3
4
5
6
7
8
9
10
Node* mirror(Node *pRoot)
{
if(pRoot == NULL) return NULL;
Node *pLeft = mirror(pRoot->lchild); // 求左子树镜像
Node *pRight = mirror(pRoot->rchild); // 求右子树镜像
// 交换左子树和右子树
pRoot->lchild = pRight;
pRoot->rchild = pLeft;
return pRoot;
}

由前序遍历序列和中序遍历序列重建二叉树

二叉树前序遍历序列中,第一个元素总是树的根节点的值。中序遍历序列中,左子树的节点的值位于根节点的值的左边,右子树的节点的值位于根节点的值的右边。

递归解法:

  1. 如果前序遍历为空或中序遍历为空或节点个数小于等于0,返回NULL。
  2. 创建根节点。前序遍历的第一个数据就是根节点的数据,在中序遍历中找到根节点的位置,可分别得知左子树和右子树的前序和中序遍历序列,重建左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Node* rebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
{
if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
return NULL;
Node *pRoot = new Node;
// 前序遍历的第一个数据就是根节点数据
pRoot->data = pPreOrder[0];
pRoot->lchild = NULL;
pRoot->rchild = NULL;
// 查找根节点在中序遍历中的位置,中序遍历中,根节点左边为左子树,右边为右子树
int rootPositionInOrder = -1;
for(int i = 0; i < nodeNum; i++)
if(pInOrder[i] == pRoot->data)
{
rootPositionInOrder = i;
break;
}
if(rootPositionInOrder == -1)
{
throw std::exception("Invalid input.");
}
// 重建左子树
int nodeNumLeft = rootPositionInOrder;
int * pPreOrderLeft = pPreOrder + 1;
int * pInOrderLeft = pInOrder;
pRoot->lchild = rebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
// 重建右子树
int nodeNumRight = nodeNum - nodeNumLeft - 1;
int *pPreOrderRight = pPreOrder + 1 + nodeNumLeft;
int *pInOrderRight = pInOrder + nodeNumLeft + 1;
pRoot->rchild = rebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
return pRoot;
}

同样,有中序遍历序列和后序遍历序列,类似的方法可重建二叉树,但前序遍历序列和后序遍历序列不能恢复一棵二叉树,证明略。

前序遍历序列和后序遍历序列不能恢复一棵二叉树。

判断二叉树是不是完全二叉树

若设二叉树的深度为h,除第 h 层外,其它各层(1~h-1)的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

有如下算法:按层次(从上到下,从左到右)遍历二叉树,当遇到一个节点的左子树为空时,则该节点右子树必须为空,且后面遍历的节点左右子树都必须为空,否则不是完全二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool IsCompleteBinaryTree(Node *pRoot)
{
if(pRoot == NULL)
return false;
queue<Node*> q;
q.push(pRoot);
bool mustHaveNoChild = false;
bool result = true;
while(!q.empty())
{
Node* pNode = q.front();
q.pop();
if(mustHaveNoChild) // 已经出现了有空子树的节点了,后面出现的必须为叶节点(左右子树都为空)
{
if(pNode->lchild != NULL || pNode->rchild != NULL)
{
result = false;
break;
}
}
else
{
if(pNode->lchild != NULL && pNode->rchild != NULL)
{
q.push(pNode->lchild);
q.push(pNode->rchild);
}
else if(pNode->lchild != NULL && pNode->rchild == NULL)
{
mustHaveNoChild = true;
q.push(pNode->lchild);
}
else if(pNode->lchild == NULL && pNode->rchild != NULL)
{
result = false;
break;
}
else
{
mustHaveNoChild = true;
}
}
}
return result;
}

二叉查找树

如果我们给二叉树加一个额外的条件,就可以得到一种被称作二叉查找树(binary search tree)的特殊二叉树。二叉查找树要求:每个节点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大。

插入节点

首先执行查找算法,找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意:新插入的结点总是叶子结点。

1
2
3
4
5
6
7
8
9
10
11
12
void insertNode(Node* &pRoot, int x){
if(pRoot == NULL){
pRoot = new Node;
pRoot->lchild = pRoot->rchild = NULL;
pRoot->data = x;
return;
}
if(x < pRoot->data)
insertNode(pRoot->lchild, x);
else
insertNode(pRoot->rchild, x);
}

删除节点

删除某个结点后依然要保持二叉查找树的特性。例子中的删除过程如下:

  1. 若删除点是叶子结点,则设置其双亲结点的指针为空。
  2. 若删除点只有左子树,或只有右子树,则设置其双亲结点的指针指向左子树或右子树。
  3. 若删除点的左右子树均不为空,则:
    • 查询删除点的右子树的左子树是否为空,若为空,则把删除点的左子树设为删除点的右子树的左子树。
    • 若不为空,则继续查询左子树,直到找到最底层的左子树为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void deleteNode(Node *root, int data)
{
Node p = *root, parent, s;
if (NULL == p) return;
if (p->data == data) {
// It's a leaf node
if (!p->rchild && !p->lchild) {
*root = NULL;
free(p);
}
// the right child is NULL
else if (!p->rchild) {
*root = p->lchild;
free(p);
}
else if (!p->lchild) {
*root = p->rchild;
free(p);
}
// the node has both children
else {
s = p->rchild;
if (!s->lchild)
s->lchild = p->lchild;
else {
while (s->lchild) {
parent = s;
s = s->lchild;
}
parent->lchild = s->rchild;
s->lchild = p->lchild;
s->rchild = p->rchild;
}
*root = s;
free(p);
}
}
else if (data > p->data) {
deleteNode(&(p->rchild), data);
}
else if (data < p->data) {
deleteNode(&(p->lchild), data);
}
}

查找节点

递归解法:

  1. 若当前节点为空,返回空节点;
  2. 若当前节点的值与要查找的值相同,返回当前节点;
  3. 若当前节点的值大于要查找的值,在左子树中继续查找该值;
  4. 若当前节点的值小于要查找的值,在右子树中继续查找该值。

1
2
3
4
5
6
7
8
Node* searchNode(Node* &pRoot, int x){
if (pRoot == NULL) return NULL;
if (pRoot->data == x) return pRoot;
if(x < pRoot->data)
searchNode(pRoot->lchild, x);
else
searchNode(pRoot->rchild, x);
}

哈希表

下图示意了哈希表(Hash Table)这样的数据结构。

哈希表

如上图所示,首先分配一个指针数组,数组的每个元素是一个链表的头指针,每个链表称为一个 槽(Slot) 。哪个数据应该放入哪个槽中由哈希函数决定,在这个例子中我们简单地选取哈希函数h(x) = x % 11,这样任意数据x都可以映射成0~10之间的一个数,就是槽的编号,将数据放入某个槽的操作就是链表的插入操作。

如果每个槽里至多只有一个数据,可以想像这种情况下search、insert和delete操作的时间复杂度都是O(1),但有时会有多个数据被哈希函数映射到同一个槽中,这称为碰撞(Collision),设计一个好的哈希函数可以把数据比较均匀地分布到各个槽中,尽量避免碰撞。如果能把n个数据比较均匀地分布到m个槽中,每个糟里约有n/m个数据,则search、insert和delete和操作的时间复杂度都是O(n/m),如果n和m的比是常数,则时间复杂度仍然是O(1)。一般来说,要处理的数据越多,构造哈希表时分配的槽也应该越多,所以n和m成正比这个假设是成立的。

如果用我们学过的各种数据结构来表示n个数据的集合,下表是search、insert和delete操作在平均情况下的时间复杂度比较。

数据结构 search insert delete
数组 O(n),有序数组折半查找是O(lgn) O(n) O(n)
双向链表 O(n) O(1) O(1)
排序二叉树 O(lgn) O(lgn) O(lgn)
哈希表(n与槽数m成正比) O(1) O(1) O(1)

典型应用

  1. 统计一个文本文件中每个单词的出现次数

深入阅读

  1. 轻松搞定面试中的链表题目
  2. 轻松搞定面试中的二叉树题目

Comments