数据结构与算法基础

快期中考试了，对数据结构的一些定义和问题理解还不太清晰，遂决定在复习的同时在这篇文章里写下一些自己的理解和思考

数据结构的内容涉及以下几个方面

  • 算法分析
  • 表，栈和队列
  • 树（二叉树，完全二叉树）
  • 优先队列（堆）
  • 不相交集
  • …(期中考试暂时不考，后面再补档)

算法分析

算法分析主要分为时间复杂度和空间复杂度两方面的分析，复杂度的上界表示为O,复杂度的下界表示为Ω，复杂度的等价表示为Θ

复杂度的层次分为常数阶（$O(1)$），对数阶($O(logn)$) ，线性阶($O(n)$)，对数乘线性阶($O(nlogn)$)，幂指数阶($O(n^k)$)，指数阶($O(k^n)$)，阶乘阶($O(n!)$)

表，栈和队列

表

表指的是链表，是一个递归定义的抽象数据结构，含有数据域和指针域两部分,定义如下，还有循环链表（尾节点指向头节点），双链表（每个节点），实现方法类似

1
2
3
4
struct Node{
	datatype data;
	struct Node* Next;
};

事实上，栈，队列都可以用链表表示，同时链表也是树的一种特殊情况（每个节点都只有一个孩子节点），树又是不相交集和堆的基础和图的一种特殊情况，可以说链表的递归定义的思想贯穿整个数据结构

此外，值得一提的是，链表的实现，个人认为添加一个dummy node比较好，这样在删除链表结点时就更加方便，不用担心头节点被删除时不小心导致的链表丢失

除了递归定义的到链表外，链表还可以通过游标实现，核心思想是以数组的下标作为地址来进行元素间的索引

链表的实际运用例子

多项式的加减乘运算

用链表表示次数相差很大的多项式时比数组有很大的优势

基数排序

在了解基数排序之前，我们要先了解他的来源—桶式排序

桶式排序

我们有$N$个整数，范围是从$1$到$M$,我们设置一个名为$count$的数组，大小为$M$，并初始化为$0$，$count$的每一个元素都表示一个桶，开始时都是空的，当$A_i$被读入时，$count[A_i]++$,读入所有的输入后，扫描$count$,输出排好序的表

基数排序

基数排序是这种排序的推广，我们用实际的例子来解释这种排序方法，假设我们有$10$个数字，范围在$0$到$999$之间，我们将其排序，一般来说这是$0$到$N^p-1$之间的$N$个数字（这十个数字的范围就满足在$0$到$10^3-1$之间），我们的策略是使用多趟桶式排序，我们采用最低位优先的策略进行排序。

第一次比较最低位，对最低位的数字进行桶式排序。第二次比较次低位，对次低位的数字进行桶式排序，以此类推直到最高位。每一次桶式排序的过程中，每个桶得到的都是一张按特定位数排好序的表，比如第二次桶式排序完成时，桶$1$内都是十位为$1$,并且按个位的大小排好序的表。

栈（LIFO）

后进先出是栈的数据结构特点，可以用数组和链表分别对栈进行实现,pop和push是栈的两种基本操作

1
2
3
4
5
#define Maxsize 10000
struct Stack{
    int stack_array[Maxsize];
    int TopOfStacl;
};
1
2
3
4
5
6
7
8
struct Node{
    int element;
    struct Node* Next;
};
struct Stack{
    int MaxSize;
	struct Node* TopOfStack;//使用头插法在链表实现的栈中进行pop和push
}

对于数组实现的栈来说，可以用一个数组同时实现两个栈，即分别用数组的$0$号位置和$N-1$号位置作为栈底，从两端向中间靠拢，栈满的标志就是$TopofStack1 + 1 == TopOfStack2 $.

栈的应用实例

平衡符号

后缀表达式的计算

中缀表达式转后缀表达式

队列（FIFO）

二叉查找树

一棵树是$N$个节点和$N-1$条边的集合（每条边将一个节点与他的父节点相连，而除了根节点，每一个节点都有一个父节点）

没有子节点的节点称为叶子节点（leaf）

具有相同节点的节点称为兄弟节点（sibling）

在一棵树中从根节点到每一个节点都只存在一条唯一路径，节点的深度就是这条路径的长度。

后裔：descendant 祖先：ancestor 真后裔：proper descendant 真祖先：proper ancestor

树的一般实现

由于每个节点的儿子数目是未知的，所以树的一般实现是通过将父节点与他的所有孩子节点放在一个链表中，递归实现：

1
2
3
4
5
6
typedef struct TreeNode* PtrNode;
struct TreeNode{
    ElementType Element;
    PtrNode Firstchidren;
    PtrNode NextSibling;
}

每个节点储存的信息的作用是访问该节点的下一层其他节点和访问该节点的这一层其他节点。

二叉树

平均二叉树的平均深度为$N^{1/2}$,二叉查找树的平均深度是$log N$,最坏情况下是$N-1$(退化成链表)。

表达式树（expression tree）

表达式树的树叶是操作数（常量或变量）（operand），其他节点是操作符（operator),一般来说对于所有操作都是二元的情况，表达式树正好是一棵二叉树。

我们通过中序遍历（inorder traversal）实现对表达式树的求值，首先递归产生带括号的左表达式树，然后打印根处的运算符，最后递归打印带括号的右表达式树，这样就得到一个中缀表达式（infix expression）。

还可以通过后序遍历得到后缀表达式，或者前序遍历得到前缀表达式 。

由后缀表达式构建表达式树

设输入为$ab+cde+**$

  1. 前两个数是操作数，因此我们构建两个单节点树，并把他们的指针压入栈中
  2. 紧接着读入$+$，因此，弹出栈内的这两个指针，并将$+$指向这两个指针，形成一棵树。并将这棵树的指针压入栈中。
  3. 压入$cde$三个单节点树的指针。
  4. 读入$+$，弹出$de$的指针，并使$+$指向这两个指针，构建一颗树，并将这棵树压入栈内。
  5. 读入$$,弹出$c$和上一步压入的树指针，$$指向这两个指针，形成一颗新树，并压入栈中
  6. 最后读入$$,弹出栈中存在的两棵树，$$指向这两棵树，形成最后的树。
查找树ADT—二叉查找树

二叉查找树是满足树内每一个节点的左节点都小于该节点且右节点都大于该节点的二叉树。

建立空树

1
2
3
4
5
6
7
8
BinaryTree MakeEmpty(BinaryTree T){
    if(T != NULL){
        MakeEmpty(T->left);
        MakeEmpry(T->right);
        free(T);
    }
    return NULL;
}

查找元素

1
2
3
4
5
6
7
8
9
10
11
12
BinaryTree Find(BinaryTree T,ElementType target){
    if(T == NULL){
        return NULL
    }//Don't forget this Line!
	if(target > T->element){
        Find(T->right,target);
    }
    else if(target < T->element){
        Find(T->left,target);
    }
    else return T;
}

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BinaryTree Insert(BinaryTree T,Elementtype X){
    if(T == NULL){
        T = (BinaryTree)malloc(sizeof(TreeNode));
        if(T == NULL){
            printf("Out of Space");
        }
        else{
            T->elemrnt = X;
            T->ledt = T->right = NULL;
        }
    }
    else{
        if(X > T->element){
            T->right = Insert(T->right,X)
        }
        else if(X < T->element){
            T->left = Insert(T->left,X);
        }
    }
    return T;
}

删除元素

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
BinaryTree Delete(BinaryTree T,Elementtype X){
    if(T == NULL){
        printf("Not Found the Node");
    }
    else{
        if(X > T->element){
            Delete(T->right,X);
        }
        else if(X < T->element){
            Delete(T->left,X);
        }
        else{
            if(T->left&&T->right){
                TreeNode TempCell = FindMin(T->right);
                T->element = TempCell->element;
                Delete(T->right,T->element);
            }
            else{
                TreeNode TempCell = T;
                if(T->left == NULL)
                    T = T->right;
                else if(T->right == NULL)
                    T = T->left;
                free(TempCell);
            }
        }
    }
    return T;
}
AVL树（不考）

Adelson-Velskii和Landis树 是带有平衡条件的二叉查找树。

一颗AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度定义为-1），每个节点都储存着高度信息。当进行插入操作时，我们需要更新通向根节点路径上的节点的平衡信息，而这可能会破坏AVL树的特性，我们可以通过对树进行简单的修正来避免这种情况发生，这个操作我们称之为旋转。

优先队列（堆）

模型

优先队列是允许至少能实现插入和删除最小元素的操作的数据结构。

二叉堆（binary heap）

和二叉树一样，堆也具有两个性质，结构性和堆序性。

结构性

堆是一颗被完全填满的二叉树（完全二叉树）（complete binary tree）,高为$h$的完全二叉树有$2^h$到$2^{h+1}-1$个节点的树，完全二叉树的结构性质使得它可以被一个数组实现而不需要指针，对于任意下标为 i上的元素，其左儿子在下标 2i+1上，其父节点在$\lfloor （i-1）/2 \rfloor$上。

堆序性

以一个最小堆为例，在一个堆中，对于每一个节点$X$，$X$的父节点的值应该小于或者等于$X$节点的值，根结点除外。

堆的基本操作

堆的数据结构声明

1
2
3
4
5
6
7
struct heap{
    int Capacity;
    int size;
    ElementType* Elements;
};
typedef struct heap heap;
typedef heap* Heap;

我们将索引值封装成函数，方便后续使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 获取左子节点的索引 */
int left(Heap heap, int i) {
    return 2 * i + 1;
}

/* 获取右子节点的索引 */
int right(Heap heap, int i) {
    return 2 * i + 2;
}

/* 获取父节点的索引 */
int parent(Heap heap, int i) {
    return (i - 1) / 2; // 向下取整
}

插入（percolate up）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void push(Heap heap,ElementType val){
    //不考虑堆满的情况
    heap->Elements[heap->size++] = val;
    ShiftUp(heap,heap->size);
}
void ShiftUp(Heap heap,int index){
    while(true){
        int p = parent(heap,index);
        if(p>0||heap->Elements[p]>heap->Elements[index])
            break;
        swap(heap,p,index);//swap函数是交换两个节点的元素值，实现略去
        index = p;
    }
}

删除最小元（pop）

堆删除顶点是通过将堆尾元素代替堆顶元素，然后进行percolate down实现的。

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
int pop(Heap heap){
    //不考虑堆为空的情况
    int val = heap->Elements[0];
    heap->Elements[0] = heap->Elements[heap->size--];
    Shiftdown(heap,0);
    return val;
}
void Shiftdown(Heap heap,int i){
    while(true){
        //判断节点中最小的值，记作min
        int L = left(heap,index);
        int R = right(heap,index);
        int min = i;
        if(L < heap->size&&heap->Elements[L]<heap->Elements[min]){
            min = L;
        }
        if(R < heap->size&&heap->Elements[R]<heap->Elements[min]){
            min = R;
        }
        if(max == i){//如果max＝i那么说明，要么L和R越界了，要么i所在的元素已经比他的子节点都小了，这两种情况下都不需要再进行交换了。
            break;
        }
        swap(heap,i,min);
        i = min;
    }
}

建堆

建堆可以通过两种方法实现，一种是不断将元素入堆，时间复杂度为$O(n\log n)$,另一种是对已有的数组进行从底至上遍历堆化，时间复杂度为$O(n)$。

我们对第二种遍历堆化进行分析，由于每个叶子节点没有子节点，天然地是一个合法的堆，所以我们自底向上的堆化是从最后一个节点的父节点开始的。

1
2
3
4
5
6
7
8
9
Heap BuidHeap(int* nums,int size){
    Heap minheap = (Heap)malloc(sizeof(heap));
    minheap->size = size;
    memcpy(minheap->Elements,nums,size*sizeof(int));
    for(int i = parent(minheap,size-1);i>=0;--i){
        Shiftdown(minheap,i);
    }
    return minheap;  
}

图

基础概念

连通：若两个顶点之间存在路径，那么这两个顶点就是连通的

路径：指的是两个顶点之间一系列顶点的集合，路径的长度是边长度的总和，如果两个顶点之间的路径的所有顶点都不同，则称为简单路径

回路：起点等于终点的路径

连通图：任意两点均连通的图

连通分量：无向图的极大连通子图（极大值和最大值的区别，极大连通子图不止一个）

强连通：有向图中两个顶点存在双向路径，则称这两个顶点是强连通的

强连通图：任意两个顶点都是强连通的有向图

强连通分量：有向图的极大强连通子图

图的拓扑排序（TopSort）

拓扑排序是对有向无圈图顶点的一种排序，它使得如果存在一条从$v_i$到$v_j$的路径，那么在排序中$v_j$出现在$v_i$后面。如果图是有圈的，那么拓扑排序无法实现，因为在圈中的顶点既是圈内其他顶点的前驱，也是圈内其他顶点的后继，使得拓扑排序结果不唯一。

简单的拓扑排序伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void TopSort(Gragh G){
    int counter;
    Vertex V,W;
    for(couter = 0;counter < NumOfVertex; ++Couter){
 		V = FindNewVertexOfZeroIndegree();
        if(V == NotVertex){
            Error("Gragh has a cycle");
            break;
        }
        TopNum[V] = couter;
        for each W adjacent to V
            Indegree[W]--;
    }
}

FindNewVertexOfZeroIndegree()是一个对含有所有顶点的集合进行遍历，返回其中入度为0的顶点的函数，如果没有入度为0的函数，那么就返回NotVertex。这个算法存在对顶点的多次重复扫描，我们可以通过队列，将所有入度为0的顶点全部都放入这个队列当中，减少扫描次数。

队列实现的拓扑排序伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void TopSort(){
    Queue Q;
    int couter = 0;
    Vertex V,W;
    Q = createQueue();
    Q = makeempty();
    for each Vertex
        if Indegree[Vertex] == 0
            Enqueue(Vertex,Q);
    while(!Isempty(Q)){
        V = Dequeue(Q);
        TopNUm[V] = ++couter;
        for each W adjacent to V
            if(--Indegree[W]==0)
                Enqueue(W,Q);
    }
    if(couter != NumOfvertex)
        Error("Gragh has a cycle");
    DisposeQueue(Q);
}

最短路径算法

单源最短路径问题（introduction）

给定一个赋权图$G=(V,E)$和一个特定顶点$s$作为输入，找到从$s$到$G$中每一个其他的顶点的最短赋权路径。

无权最短路径

广度优先算法（breadth-first search）

按照递增的顺序找出各个顶点的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Unweighted(Tabel T)/*Assume T is initialized*/
{
    int CurrDist;
    Vertex V,W;
    for(currDist = 0;CurrDist<numVertex;CurrDist++){
        for each Vertex V
            if(!T[V].known && T[V].Dist == CurDist){
                T[V].known = True;
                for each W adjacent to V
                    if(T[W].Dist == Infinity){
                        T[W].Dist = CurrDist + 1;
                        T[W].path = V;
                    }
            }
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。