Hexo
0%

数据结构(按大纲整理)

Posted on In
数据结构

倒计时

考纲

概述

线性表

数组

一维数组与二维数组的存储

数组一般情况下采用顺序存储结构

一维数组

若一维数组的每个元素占k个存储单元,并且从地址1开始存储数组的第1个元素,则数组第ⅰ个元素的存储位置LOC(ai)可由下式确定
LOC(ai) = LOC(ai) + (i - 1)*k = l0 + (i - 1) * k

二维数组

若已知元素a1的存储地址为LOC(a1),并且每个元素占用k个存储单元,则数组第i行第j列的元素a的存储位置为
LOC(aij) = LOC(a11) + (i - 1) * n * k + (j - 1) * k
= LOC(a11) + [(i - 1) * n + (j - 1)] * k

矩阵压缩

栈与队列

树与二叉树

基本概念

术语

  • 结点的度:结点拥有的子树个数或者分支的个数。例如,A结点有3棵子树,所以A结点的度为3
  • 树的度:树中各结点度的最大值。如例子中结点度最大为3(A、D结点),最小为0(F、G、1、J K、L、M结点),所以树的度为3。
  • 祖先:从根到某结点的路径上的所有结点,都是这个结点的祖先。如K的祖先是AB、E,因为从A到K的路径为A-B-E一K。
  • 层次:从根开始,根为第一层,根的孩子为第二层,根的孩子的孩子为第三层,以此类推。
  • 树的高度(或者深度):树中结点的最大层次。如例子中的材共有4层,所以高度为4。
  • 结点的深度和高度:
    • 结点的深度是从根结到该结点路径上的结点个数
    • 从某结点往下走可能到达多个叶子结点,对应予多条通往这些叶子结点的路径,其中最长的那条路径的长度即为该结点在树中的高度,如结点D的高度为3、就是从D到M的路径长度。
    • 根结点的高度为树的高度,如结点A,其高度为4。是从A到K(L、M)这条路径的长度,也是整棵树的高度。
  • 有序树:树中结点的子树从左到右是有次序的,不能交换,这样的树叫作有序树。
  • 无序树:树中结点的子树没有顺序,可以任意交换,这样的树叫作无序树
  • 丰满树:丰满树即理想华衡树、要求除最底层外,其他层都是满的

二叉树的存储结构

顺序存储结构

顺序存储结构即用一个数组来存储一棵二又树,这种存储方式最适合于完全二叉树，用于存储一般ニ叉树会浪费大量的存储空间。将完全二又树中的结点值按编号依次存入ー个一维数组中,即完成了叉树的顺序存储。
如果知道一个节点i如果2i不大于n，则i的左孩子就是BTree[2*i]。而如果i，j满足log2i = log2j则，i，j在同一层

链式存储结构

链式存储结构如下

1
2
3
4
5
6
typedef struct BTNode
{
  char data;             // 数据域
  struct BTNode *lchild; // 左孩子
  struct BTNode *rchild; // 右孩子
} BTNode;

二叉树的遍历

中序遍历（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void mid(BTREE T)
{
  BTREE stack[maxSize], p = T;
  int top = -1;
  if (p != NULL)
  {
    while (p != NULL && top != -1)
    {
      // 此循环将p及p的左孩子依次入栈
      while (p != NULL)
      {
        stack[++top] = p; // 将p所指节点入栈
        p = p->lchild;    // 将p指向其左孩子
      }
      p = stack[top--]; // 将p出栈
      visit(p);         // 访问p节点
      p = p->rchild;
    }
  }
}

后序遍历（非递归）

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
// 声明两个堆栈一个存储节点，一个存贮标志位，每个节点入栈2次，第一次取左子树，第二次取右子树
void back(BTREE T)
{
  BTREE stack1[maxSize], p = T;
  int stack2[maxSize], flag, top = -1;

  if (p != NULL)
  {
    // 当p不为NULL，或者堆栈不空时循环
    while (p != NULL && top != -1)
    {
      // 将左子树存入堆栈
      while (p != NULL)
      {
        stack1[++top] = p;
        stack2[++top] = 0;
        p = p->lchild;
      }
      // 将节点取出标记，并将右孩子赋给p以将其以及其左子树放入堆栈
      p = stack1[top];
      flag = stack1[top--];
      if (flag == 0)
      {
        stack1[++top] = p;
        stack2[++top] = 1;
        p = p->rchild;
      }
      else
      {
        // 如果节点已经取出过一次，代表其右子树已经访问过，可以访问这个节点
        visit(p);
        p = NULL; //本节点左右子树均已访问完毕，这步可以让下次访问从堆栈中取出下一个节点
      }
    }
  }
}

层级遍历

图6-10所示为二叉树的层次遍历,即按照箭头所指方向,按照1、2、3、4的层次顺序,对二叉树中各个结点进行访问(此图反映的是自左至右的层次遍历,自右至左的方式类似)。
要进行层次遍历,需要建立一个循环队列。先将二叉树头结点入队列,然后出队列,访问该结点,如果它有左子树,则将左子树的根结点入队:如果它有右子树,则将右子树的根结点入队。然后出队列,对出队结点访问,如此反复,直到队列为空为止，由此得到的对应算法如下:

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
// 层次遍历
// 要点：靠队列辅助，依次将一层入队列然后出队列即可
void level(BTNode *p)
{
  BTNode *que[maxSize]; // 建立队列
  BTNode *q;
  int rear = 0;
  int front = 0;
  if (p)
  {
    rear = (rear + 1) % maxSize; // 将根节点放入队列
    que[rear] = q;
    while (rear != front) // 队列不为空就一直循环
    {
      front = (front + 1) % maxSize; //从队列出节点读取
      visit(que[front]);
      if (q->lchild) // 如果有左孩子就入队列
      {
        rear = (rear + 1) % maxSize;
        que[rear] = p->lchild;
      }
      if (q->rchild) // 如果有右孩子就入队列
      {
        rear = (rear + 1) % maxSize;
        que[rear] = p->rchild;
      }
    }
  }
}

图

基本概念

  1. 图
    由结点的有穷集合V和边的集合E组成。为了与树形结构进行区别,在图结构中常常将结点称为边是顶点的有序偶对。若两个顶点之间存在一条边,则表示这两个顶点具有相邻关系
  2. 有向图和无向图
    每条边都有方向是有向图，每条边都没有方向是无向图
  3. 弧
    在有向图中,通常将边称为弧,含箭头的一端称为弧头,另一端称为弧尾,记作<Vi,Vj>,它表示从顶点v到顶点v有一条边。
  4. 有向完全图和无向完全图
    若有向图中有n个顶点,则最多有n(n-1)条边(图中任意两个顶点都有两条边相连),将具有n(n-1) 条边的有向图称为有向完全图。若无向图中有n个顶点,则最多有n(n-1)/2条边(任意两个顶点之间都有一条边),将具有n(n-1)/2条边的无向图称为无向完全图。
  5. 路径和路径长度
    在一个图中,路径为相邻顶点序偶所构成的序列。路径长度是指路径上边的数目。例如,在图7-1a 中,<C,B>、<B,A>是一条路径,长度为2:在图7-1b中,(D,C)、(C,B)、(B,A)是一条路径, 长度为3
  6. 简单路径
    序列中顶点不重复出现的路径称为简单路径。
  7. 回路
    若一条路径中第一个顶点和最后一个顶点相同,则这条路径是一条回路。
  8. 连通、连通图和连通分量
    在无向图中,如果从顶点v到顶点y有路径,则称v和y连通。如果图中任意两个顶点之间都连通,则称该图为连通图:否则,图中的极大连通子图称为连通分量。如在图7-2中,图7-2c是一个非连通图它由图7-2a和图7-2b组成,图7-2a和图7-2b都是连通图。对于图7-2c、图7-2a和图7-2b就是它的两个连通分量。
  9. 强连通图和强连通分量
    在有向图中,若从Vi到Vj有路径,则称从Vi到Vj是连通的。如果对于每一对顶点Vi和Vj,从Vi到Vj和Vj到Vi都有路径,则称该图为强连通图;否则,将其中的极大强连通子图称为强连通分量。
  10. 权和网
    图中每条边都可以附有一个对应的数,这种与边相关的数称为权。权可以表示从一个顶点到另一个顶点的距离或者花费的代价。边士错有权的图称为带权图,也称为网。

邻接矩阵和邻接表

邻接矩阵

概念

邻接矩阵是图的顺序存储结构，对于无向图，邻接矩阵是对称的，矩阵中“1”的个数是图中总边数的2倍，矩阵中第i行或第i列的元素之和即为顶点i的度。
对于有向图，矩阵中“1”的各处为图的边数，矩阵中第i行的元素之和为顶点i的出度，第j列为顶点i的入度。

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 图节点定义
typedef struct
{
  int no;
  char info;
}VertexType;

// 图的定义
typedef struct
{
  int edges[maxSize][maxSize]; // 邻接矩阵定义，如果是有权图，将int改为float
  int n, e;                    // 存放定点数和边数
  VertexType vex[maxSize];
} MGraph;

有时给出压缩矩阵写法，三元组表示，只需要知道三元组原理即可

邻接表

概念

邻接表是图的一种链式存储结构。所邻接表就是对图中的每个顶点i建立一个单链表,每个单链表的第一个结点存放有关顶点的信把这点看作链表的表头,其余结点存放有关边的信息,因此邻接表由单链表的表头形成的顶点表利单链表其余结点形成的边表两部分组成。一般顶点表存放顶点信息和指向第一个边结点指针,边表结点存放与当前顶点相邻接顶点的序号和指向下一个边结点的指针。

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 定义边结构
  typedef struct ArcNode
  {
    int adjvex;              // 该边指向结点的位置
    struct ArcNode *nextarc; // 指向下一条边信息
    int info;                // 该边的相关信息，如权值，这一句用的不多
  } ArcNode;
  // 定义顶点结构
  typedef struct
  {
    char data;
    ArcNode *firstarc; // 指向第一条边的指针
  } VNode;
  typedef struct
  {
    VNode adjlist[maxSize]; //邻接表
    int n, e;               // 顶点数和边数
  } AGraph

逆邻接表

逆邻接表与邻接表相似，只是邻接表存储的是每个节点的出度，而逆邻接表存储的是入度。

图的深度优先搜索和广度优先搜索

DFS

图的深度优先搜素遍历(DFS)类似于二叉树的先序遍历。它的基本思想是:首先访问出发点v并将其标记为已访问过;然后选取与v邻接的未被访问的任意一个顶点w,并访问它;再选取与w邻接的未被访间的任一顶点并访问,以此重复进行。当一个顶点所有的邻接顶点都被访问过时,则依次退回到最近被访问过的顶点,若该顶点还有其他邻接顶点未被访问,则从这些未被访问的顶点中取一个并重复上述访问过程,直至图中所有顶点都被访问过为止。图7-8所示即为一个图的深度优先搜索遍历过程。
深度优先搜索与拓扑排序也可以用来判断图有没有回路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 深度优先遍历
int visited[maxSize];
void DFS(AGraph G, int n)
{

  visited[n] = 1;
  visit(G.adjlist[n]);
  ArcNode *p;
  p = G.adjlist[n].firstarc;
  while (p)
  {
    if (!visited[p->adjvex])
      DFS(G, visited[p->adjvex]);
    p = p->nextarc;
  }
}

BFS

图的广度优先搜索遍历(BFS)类似于树的层次追历。它的基本思想是:首先访问起始顶点v,然后选取与v邻接的全部顶点w1,…,wn进行访间,再依次访间与w1,…,wn邻接的全部顶点(已经访间过的除外),以此类推,直到所有顶点都被访问过为止。
广度优先搜索遍历图的候,需要用到一个队列(二叉树的层次遍历也要用到队列),算法执行过程可简单概括如下:

  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
    // 广度优先遍历
    int visited[maxSize];
    void BFS(AGraph G, int n)
    {
      // 初始化队列
      int que[maxSize];
      int front = 0, rear = 0;
      int j;
      ArcNode p;
      // 访问第一个结点并将第一个结点入队列
      visited[n] = 1;
      visit(G.adjlist[n]);
      rear = (rear + 1) % maxSize;
      que[rear] = 0;
      while (rear != front)// 当队列空时结束循环
      {
        // 从队列取出节点
        front = (front + 1) % maxSize;
        j = que[front];
        p = G.adjlist[j].fistarc;
        // 如果有邻接节点则依次访问
        while(p) {
          // 如果没访问过则访问该节点，并将该节点放入队列中
          if (!visited[p->adjvex]) {
            visited[p->adjvex] = 1;
            visit(G.adjlist[p->adjvex]);
            rear = (rear + 1) % maxSize;
            que[rear] = G.adjlist[j->adjvex];
          }
          p = p->nextarc;
        }
      }
    }

    上面两个方法都是针对连通图的，如果是非连通图只需要将遍历函数放入一个循环中即可，依次对所有顶点执行遍历操作

最小（代价）生成树、最短路径、AOV网与拓扑排序的基本概念

最小（代价）生成树

概念

  • 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
  • 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

普利姆算法

思想

从图中任意取出一个顶点,把它当成一棵树,然后从与这棵树相接的边中选取一条最短(权值最小) 的边,并将这条边及其所连接的顶点也并入这棵树中,此时得到了一棵有两个顶点的树。然后从与这棵树相接的边中选取一条最短的边,并将这条边及其所连顶点并入当前树中,得到一棵有3个顶点的树。以此类推,直到图中所有顶点都被并入树中为止,此时得到的生成树就是最小生成树。
例如,图7-10a所示的带权无向图采用普里姆算法求解最小生成树的过程如图7-10b~图7-10e所示, 以顶点0为起点,生成树生成过程如下:

  1. 如图710a所示,此时候选边的边长分别为5、1和2,最小边长为1
  2. 如图7-10所示,选择边长为1的边,此时候选边的边长分别为5、3、2、6和2,其中最小边长为2
  3. 如图7-10c所示,选择边长为2的边,此时候选边的边长分别为5、3、2和3,其中最小边长为2:
  4. 如图710d所示,选择边长为2的边,此时候选边的边长分别为3、4和5,其中最小边长为3:
  5. 如图7-10e所示,选择边长为3的边,此时所有顶点都已并入生成树中,生成树求解过程完毕。
执行过程

从树中某一个顶点v开始,构造生成树的算法执行过程如下:

  1. 将V0到其他顶点的所有边当作候选边
  2. 重复以下步骤n-1次,使得其他n-1个顶点被并入到生成树中。
    1. 从候选边中挑选出权值最小的边输出,并将与该边另一端相接的顶点V并入生成树中
    2. 考查所有剩余顶点Vi,如果(V,Vi)的权值比 lowcost[Vi]小,则用(V,Vi)的权值更新lowcost[Vi]
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 建立两个数组veset[i]=1标识顶点i已经在生成树中，lowcost[]表示当前生成树到各顶点最小权值
void prime (MGraph G, int v0) {
  int veset[maxSize], lowcost[maxSize], i, j, k;
  for(i = 0; i < G.n; i++) {
    lowcost = G.edgess[v0][i];
    veset[i] = 0;
  }
  veset[v0] = 1;
  for (i = 0; i < G.n - 1; i ++) {
    int min = INF; 
    for (j = 0; j < G.n; j++) {
      if (veset[j] != 0 && lowcost[j] < min) {
        min = lowcost[j];
      }
    }
    veset[k] = 1;
    for (j = 0; j < .n; j++) {
      if (veset[j] != 0 && lowcost[j] > edges[k][j])
        lowcost[j] = edges[k][j];
    }
  }
}
时间复杂度

时间复杂度为O(n^2),时间复杂度与边数没有关系，只与定点数有关系，所以普里姆算法适用于稠密图.

克鲁斯卡尔算法

思想

每次找出候选边中权值最小的边,就将该边并入生成树中。重复此过程直到所有边都被检测完为止。
说明:克鲁斯卡尔算法思想较为简单,因此在考研中需要手工构造生成树时,一般多用此方法。图7-12所示为用克鲁斯卡尔方法求图的最小生威树的过程

执行过程

将图中边按照权值从小到大排序,然后从最小边开始扫描各边,并检测当前边是否为候选边,即是否该边的并入会构成回路,如不构成回路,则将该边并入当前生成树中,直到所有边都被检测完为止判断是否产生回路要用到并査集,关于并查集只介绍它在本算法中的应用。并査集中保存了一棵或者几棵树,这些树有这样的特点:通过树中一个结点,可以找到其双亲结点,进而找到根结点(其实就是之前讲过的树的双亲存储结构)。这种特性有两个好处:一是可以快速地将两个含有很多元素的集合并为一个。两个集合就是并査集中的两棵树,只需找到其中一棵树的根,然后将其作为另一棵树中任何一个结点的孩子结点即可。二是可以方便地判断两个元素是否属于同一个集合。通过这两个元素所在的结点找到它们的根结点,如果它们有相同的根,则说明它们属于同一个集合,否则属于不同集合、并查集可以用一维数组来简单地表示。图7-13所示即为并查集在数组中的表示及合并过程。

代码
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
typedef struct {
  int a, b; //一条边连接的两个顶点
  int w; 边的权值
} Road;
Road road[maxSize];
int v[maxSize];// 并查集数组
int getRoot(int a) {
  while(a != v[a]) a=v[a];
  return a;
}
// 假设road数组数据已有，排序算法已有
void Kruskal(MGraph G) {
  int n = G.n;
  int e = G.e;
  Road edge;
  int i;
  sort(road, e);
  // 初始化并查集
  for (i = 0;i < n; i ++) 
    v[i] = i;
  // 遍历左右边
  for (i = 0;i < e; i++) {
    edge = road[i];
    // 查看加入边是否构成回路，如果不构成回路就将其加入并查集
    if (getRoot(edge.a) != getRoot(edge.b))
      v[edge.a] = v[edge.b];
      // 此处也可以进行其他操作
  }
}
时间复杂度

算法时间复杂度集中在排序算法上，所以处理规模由e决定，所以克鲁斯卡尔适用于稀疏图.

最短路径

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

迪杰斯特拉算法

设有两个顶点集合S和T,集合S中存放图中已找到最短路径的顶点,集合T存放图中剩余顶点。初始状态时,集合S中只包含源点V0,然后不断从集合T中选取到顶点V0路径长度最短的顶点Vu并入到集合S中。集合S每并入一个新的顶点Vu。,都要修改顶点V0到集合T中顶点的最短路径长度值。不f程断重复此过直到集合T的顶点全部并入到S中为止。
在理解“集合S每并入一个新的顶点V。,都要修改顶点V0到集合T中顶点的最短路径长度值”的时候需要注意,在Vu被选入S中后,Vu被确定为最短路径上的顶点,此时Vu就像V0到达T中顶点的中转站,多了一个中转站,就会多一些到达T中项点的新的路径,而这些新的路径有可能比之前V0到T中项点的路径要短,因此需要修改原有V0到T中其他顶点的路径长度。此时对于T中的一个顶点v,有两种情况:一种是V0不经过Vu到达Vk的路径长度为a(旧的路径长度),另一种是V0经过Vu到达Vk的路径长度为b(新的路径长度)。如果a≤b,则什么也不做:如果a>b,则用b来代替a。用同样的方法处理T中其他顶点。当T中所有顶点都被处理完之后,会出现一组新的V0到T中各顶点的路径,这些路径中有一条最短的,对应了T中一个顶点,就是新的Vu,将其并入S。重复上述过程,最后T中所有的顶点都会被并入S中,此时就可以得到V0到图中所有顶点的最短路径。
时间复杂度为O(n^2).

代码思路

引入三个辅助数组dist[], path[]和set[]。
dist[Vi]表示当前已找到的从V0到每个终点Vi的最短路径的长度。它的初态为:若从v0到Vi有边, 则 disti[i]为边上的权值,否则置dist[i]为∞。
path[Vi]中保存从V0到Vi最短路径上Vi的前一个顶点,假设最短路径上的顶点序列为V0,V1,…,Vi,则 path[i]=Vi-1。path[]的初态为:如果v0到Vi有边,则path[Vi]=V0,否则 path[Vi]=-1.
set[]为标记数组, set[Vi]=0表示Vi在T中,即没有被并入最短路径;set[Vi]=1表示Vi在S中,即已经被并入最短路径。set[]初态为: set[V0]=1,其余元素全为0。

弗洛伊德算法

代码思路

建立两个矩阵A[][],path[][]，A用来记录从到j的最小权值，path用来记录最小路径，A的初始值为临界矩阵，path的初始值均为-1。将k点作为中间点遍历所有边如果满足A[i][j]>A[i][k] + A[k][j]则将A[i][j]替换为A[i][k] + A[k][j]，同时将path[i][j]替换为k。
如果查找从i到j最小权值则取A[i][j]，其路径为path[i][j]若值为k则继续查找path[k][j]直到path[Kn][j] = -1，所经过的路径即为最小路径。

代码
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
void Floyd(MGraph G)
{
  int A[maxSize][maxSize], path[maxSize][maxSize];
  int i, j, k;
  // 初始化两个矩阵
  for (i = 0; i < G.n; i++)
  {
    for (j = 0; j < G.n; j++)
    {
      A[i][j] = G.edges[i][j];
      path[i][j] = -1;
    }
  }
  // 算法主体
  // 以k为中间点
  for (k = 0; k < G.n; k++)
  {
    // 查看从i到j是否需要经过k
    for (i = 0; i < G.n; i++)
    {
      for (j = 0; j < G.n; j++)
      {
        if (A[i][j] > A[i][k] + A[k][j])
        {
          A[i][j] = A[i][k] + A[k][j];
          path[i][j] = k;
        }
      }
    }
  }
}

时间复杂度为O(n^3)

AOV网

考试中,只要知道AOV网是一种以顶点表示活动、以边表示活动的先后次序且没有回路的有向图即可。因为AOV网有实际意义,所以出现回路就代表一项活动以自己为前提,这显然违背实际。

拓扑排序

对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点i和j,若存在由i到j的路径,则在拓扑排序序列中一定是i出现在j的前边.
在一个有向图中找到一个拓扑排序序列的过程如下:

  1. 从有向图中选择一个没有前驱(入度为0)的顶点输出;
  2. 除1)中的顶点,并且删除从该顶点发出的全部边;
  3. 重复上述两步,直到利余的图中不存在没有前驱的顶点为止

    思路

    假设图的邻接表已经生成,并且各个顶点的入度都已经记录在count中,在本算法中要设置一个栈, 用来记泉当前图中入度为0的顶点,还要设置一个计数器n,用来记录已经输出的顶点个数.
    算法始时置n为0,扫描所有顶点,将入度为0的顶点入栈。然后在栈不空的时候循环执行:出栈,将出栈顶点输出,执行++n,并且将由此顶点引出的边所指向的顶点的入度都减1,并且将入度变为0的顶点入栈:出,…,空时循环退出,排序结束。循环退出后判断n是否等于图中的顶点个数如果相等则返回1,拓扑排序成功;否则返回0,拓扑排序失败。

    代码

    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
    // 拓扑排序
    int topSort(AGraph G)
    {
      int i, j, n;
      // 初始化栈
      int stack[maxSize], top = -1;
      VNode v;
      ArcNode A;
      // 将入度为0的端点入栈
      for (i = 0; i < G.n; i++)
      {
        if (!adjlist[i].firstarc)
        {
          top += 1;
          stack[top] = i;
        }
      }
      // 如果栈不空就一直循环
      while (top != -1)
      {
        // 从栈中去除顶点，并去除其出度
        A = G.adjlist[stack[top]].firstarc;
        top--;
        n++;
        while (A)
        {
          A.count--;
          // 如果去除出度后有顶点入度为0则将其入栈
          if (A.count == 0)
            stack[++top] = A.adjvex;
          A = A->nextarc;
        }
      }
      if (n == G.n)
      {
        return 1;
      }
      else
      {
        return 0;
      }
    }

文件及查找

概念

ASL

ASL = P1C1 + … + PnCn
n为存储对象总数；Pi为查找第一个记录的概率；Ci为查找第i个记录是所进行过的关键字值的比较次数，它取决于被查找记录在文件中的位置。

折半查找

判定树

折半査找的过程可以用二叉树来表示。把当前査找区间中的中间位置上的记录作为树根,左子表和右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树称为描述折半查找的判定树。例如, 对于序列{1,2,3,4,5,6,7,8,9,10,11}可以做出一棵判定树,如图9-1所示,图中叶子结点(方框所示)代表查找不成功的位置。由图9-1可知,折半査找的比较次数即为从根结点到待查找元素所经过的结点数,其比较次数最多的情况即为一直走到叶子结点的情况。因此,算法的时间复杂度可以用树的高度来表示。推广到一般情况,对于有n个记录的查找表,进行折半査找的时间复杂度为log2n。折查找的平均查找长度近似为log2(n+l)-1,严版课本中有推导过程,了解但可不作重点。

内排序

插入排序

这种排序方法的基本思想可以简单描述为:第i趟排序将序列中的第i+1个元素插入到一个已经按值有序的子序列的合适位置,得到一个长度为i+1且仍然保持按值有序的子序列。

插入排序方法的核心动作是插入,而寻找被插入元素的合适位置是主要工作。

时间复杂度

最坏事件复杂度为O(n^2)，最好时间复杂度简单插入排序为O(n^2),折半插入算法为O(nlog2n)

选择排序

选择排序法的核心思想是:第i趟排序从序列的后n-i+1(i=1,2,…n-1)个元素中选择一个值最小的元素与该n-i+1个元素的最前面那个元素交换位置,即与整个序列的第i个位置上的元素交换位置。如此下去,直到i=n-1,排序结束。

时间复杂度

O(n^2)

起泡排序

起泡排序又称冒泡排序。它是通过一系列的“交換”动作完成的。首先第一个关键字和第二个关健字比较,如果第一个大,则二者交换,否则不交換;然后第二个关键字和第三个关键字比较,如果第个大,则二者交换,否则不交换…一直按这种方式进行下去,最终最大的那个关键字被交換到了最后, 越起泡排序完成。经过多越这样的排序,最终使整个序列有序,这个过程中,大的关健字像石头一样沉底”,小的关键字像气泡一样逐渐向上“浮动”,起泡排序的名字由此而来。

执行过程

从第一个元素开始将元素一次两两比较，如果前面那个大则交换次序，然后后移一位比较，一趟结束后缩小可将序列缩小一位，如果在一趟排序中没有发生交换次序的行为则说明序列有序，结束排序

时间复杂度

最好情况O(n)，序列有序，一趟后发现没有交换动作结束算法，最坏情况O(n^2)，待排序列逆序。

谢尔排序

谢尔排序的核心思想是:首先确定一个元素间隔数gap(也称增量),然后将参加排序的序列按此间隔数从第1个元素开始依次分成若干个子序列,即分别将所有位置相隔为gap的元素视为一个子序列,在各个子序列中采用某种排序方法进行排序(例如,可用泡排序方法,也可利用其他排序方法,这里,不妨采用泡排序方法);然后减小间隔数,并重新将整个序列按新的间隔数分成若干个子序列,再分别对各个子序列进行排序,如此下去,直到间隔数gap=1

快速排序

快速排序也是“交换”类的排序,它通过多次划分操作实现排序。以升序为例,其执行流程可以概括为:每一趟选择当前所有子序列中的一个关键字(通常是第一个)作为枢轴,将子序列中比枢轴小的移到枢轴前边,比枢轴大的移到枢轴后边;当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列,它们成为下一趣划分的初始序列集。

执行过程

  1. 反复执行i+1送i的动作,直到满足条件ks≤ki,或者i=t;然后反复执行j一1送j的动作,直到满足条件ks≥kj或者j=s。

  2. 若ij,则将k与k交换位置,然后重复步骤1与步骤2或者步骤3。

  3. 若i≥j,则将ks,与kj交换位置,然后分别递归地对(ks…,kj-1)和(kj+1,…,kt)中长度大于1的子序列执行上述过程,直到整个序列排序结束。

时间复杂度

最好时间复杂度为O(nlog2n)，待排序越接近无序效率越高，最坏情况为O(n^2)，待排序列越接近有序，算法效率越低，因为会产生元素为0和n-1的分区，并且每趟时间复杂度为O(n)，所以为O(n^2)。

堆排序

堆是一种数据结构,可以把堆看成一棵完全二叉树,这棵完全二叉树满足:任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小,则这样的堆叫作大顶堆:若父亲小孩子大,则这样的堆叫作小顶堆。

根据堆的定义知道,代表堆的这棵完全二又树的根结点的值是最大(或最小)的,因此将一个无序序列调整为一个堆,就可以找出这个序列的最大(或最小)值,然后将找出的这个值交换到序列的最后(或最前)这样,有序序列关键字增加1个,无序序列中关键字减少1个,对新的无序序列重复这样的操作,就实现了排序。这就是堆排序的思想。

堆排序最关键的操作是将序列调整为堆。整个排序的过程就是通过不断调整,使得不符合堆定义的完全二叉树变为符合堆定义的完全二又树。

堆二叉树和二叉排序树的区别：堆二叉树（大顶堆）要求孩子节点都小于父母节点，而二叉排序树要求左孩子小于父母节点右孩子大于父母节点