002-数据结构和算法探索

2021-03-09  本文已影响0人  千转军师

时间：2021年3月9日13:43:06
作者：along

参考1：
https://www.runoob.com/data-structures/data-structures-tutorial.html
参考2：
https://weread.qq.com/web/reader/f66323605a0426f66836979ka87322c014a87ff679a21ea

c语言的特点是面向过程，有它的应用领域，但也有局限性：在编写某些类型的大程序是，没有高级语言快捷和方便。

一、绪论

由来

现实问题,抽象为===>
数学模型（解题思路），设计===>
数据结构（算法），编码===>
数据类型（程序），运行===>
结果

1.1 概念

1.2 数据结构的分类

（1）集合结构：在集合结构中，数据元素之间的关系是“属于同一个集合”。数据元素之间除了同属一个集合外，不存在其他关系。
（2）线性结构：在该结构中，数据元素除了同属于一个集合外，数据元素之间还存在着一对一的顺序关系。
（3）树形结构：该结构的数据元素之间存在着一对多的层次关系。（4）图状结构：该结构的数据元素之间存在着多对多的任意关系，图状结构也称为网状结构。
（4）图状结构：该结构的数据元素之间存在着多对多的任意关系，图状结构也称为网状结构。

数据结构有两个要素：一是数据元素，二是数据元素之间的关系。

1.3 逻辑存储和物理存储

1.4 算法

1.4.1 特性

1.4.2 要求

1.4.3 基本操作

1.4.4 算法描述

1.4.5 算法分析

（1）时间复杂度
同一问题的不同的算法，通常的做法是：

（2）空间复杂度
空间复杂度一个程序的空间复杂度（Space Complexity）是指程序运行从开始到结束所需的存储量与问题规模的对应关系，记做：S(n)=Ο(f(n))

二、线性表

线性表（Linear List）是一种线性结构

三、栈和队列

3.1 栈

3.1.1 顺序栈

利用顺序存储方式实现的栈称为顺序栈。
（1）例子：

#define MAX_NUM 100
typedef struct stack{
  int ele[MAC_NUM];
  int top;
}stack_t;

序号为0的元素为栈底，top记录的时栈顶元素的序号。
（2）顺序栈初始化

stack_t *init_stack(void)
{
  stack_t *p;
  p = (stack_t *)malloc(sizeof(stack_t ));
  p->top = -1;
  return p;
}

3.1.2 链栈

用链式存储结构实现的栈称为链栈。
用单链表来实现。
应用：

运算符按优先级排列优先级为：（）→ ^ → *、/、%→ +、-

3.1.3 栈与递归

例子：

3.2 队列

3.2.1 顺序队

用顺序存储结构来存储数据。

typedef int data_type 
#define MAX_SIZE 10
typedef struct queue{
    data_type data[MAX_SIZE];
    int front, rear;    //队头和队尾
    int num;    //元素个数
}queue_t;

3.2.2 链队列

队列采用带头结点的链表结构

3.3 队列的应用

四、串和数组

串线性表：以字符串为数据元素的线性表
数组线性表：以数组为数据元素的线性表

4.1 串

4.1.1 顺序存储结构（定长）

#define MAX_SIZE 256
typedef struct str{
    char data[MAX_SIZE];
    int len;
}str_t;

//或者
char s[MAXP_SIZE];

子串的定位操作通常称做串的模式匹配。
基本运算：

4.1.2 对分配存储结构

typedef struct str{
    char *data_p;
    int len;
}str_t;

动态分配内存，更加灵活，解决了可能“溢出”的问题。

4.2 数组

4.2.1 存储结构

4.2.2 稀疏矩阵

稀疏矩阵（Sparse Matrix）是指矩阵中大多数元素为零元素的矩阵。

15  0   0   22  0   -15
0   11  3   0   0   0
0   0   0   6   0   0
0   0   0   0   0   0
91  0   0   0   0   0
0   0   0   0   0   0

三元组表

    | i i   v
------------------
1   | 1 1   15
2   | 1 4   22
3   | 1 6   -15
4   | 2 2   11
5   | 2 3   3
6   | 3 4   6
7   | 5 1   91

五、树与二叉树

典型的非线性结构。

5.1 树的基本概念

术语：
（1）结点：包含一个数据元素及若干指向其他结点的分支信息的数据结构。
（2）结点的度：结点所拥有的子树的个数称为该结点的度。
（3）叶子结点：度为0的结点称为叶子结点，或者称为终端结点。
（4）分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的结点都是分支结点。
（5）孩子结点、双亲结点、兄弟结点：树中一个结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点。具有同一个双亲结点的孩子结点互称为兄弟结点。
（6）路径、路径长度：设n1, n2, …, nk为一棵树的结点序列，若结点ni是ni+1的双亲结点（1≤i <k），则把n1, n2, …, nk称为一条由n1至nk的路径。这条路径的长度是k-1。
（7）祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的
（8）结点的层次：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
（9）树的深度（高度）：树中所有结点的层次的最大数称为树的深度。（10）树的度：树中所有结点的度的最大值称为该树的度。
（11）有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。
（12）森林：m（m≥0）棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林；反之，给森林增加一个统一的根结点，森林就变成了一棵树。

操作：

5.2 二叉树

每个结点只能含有0、1或2个孩子结点，而且其孩子结点有左右之分的树。

5.2.1 二叉树的五种形态
5.2.2 概念

5.2.3 二叉树的存储结构

typedef int deat_type
typedef struct node{
    deat_type data;
    struct node *l_child;
    struct node *r_child;
}node_t;

三叉链表存储：每个结点由四个域组成，具体结构为：其中，data、lchild及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。

typedef int deat_type
typedef struct node{
    deat_type data;
    struct node *l_child;   //指向左子节点
    struct node *r_child;   //指向有子节点
    struct node *parent;    //指向父节点
}node_t;

5.2.4 二叉树的基本操作

5.2.5 二叉树的遍历

5.2.6 先序遍历（DLR）及其算法

访问过程
（1）访问根结点；
（2）先序遍历根结点的左子树；
（3）先序遍历根结点的右子树
可见这个过程包含递归形式。例子：

//二叉树测试
#include <stdio.h>
#include <stdlib.h>
//二叉链表
typedef int data_type;
typedef struct node{
    data_type data;
    struct node *l_child;
    struct node *r_child;
}node_t;
//创建根节点
node_t *node_creat_root(void)
{
    node_t *ret = (node_t*)malloc(sizeof(node_t));
    ret->l_child = NULL;
    ret->r_child = NULL;
    return ret;
}
//向节点插入左节点
node_t *tree_insert_l(node_t *node_p)
{
    node_t *l = (node_t *)malloc(sizeof(node_t));
    l->l_child = NULL;
    l->r_child = NULL;
    node_p->l_child = l;
    return l;
}
//向节点插入左节点
node_t *tree_insert_r(node_t *node_p)
{
    node_t *r = (node_t *)malloc(sizeof(node_t));
    r->l_child = NULL;
    r->r_child = NULL;
    node_p->r_child = r;
    return r;
}
//先序遍历二叉树节点，打印数据（用递归方法比较合适）
void tree_scan_dlr(node_t *root)
{
    printf("%c\n", root->data);
    if(root->l_child != NULL)
    {
        tree_scan_dlr(root->l_child);
    }
    
    if(root->r_child != NULL)
    {
        tree_scan_dlr(root->r_child);
    }
}
int main()  
{     
    node_t *tree_p;
    tree_p = node_creat_root();
    tree_p->data = 'a';
    node_t *l = tree_insert_l(tree_p);
    l->data = 'b';
    node_t *r = tree_insert_r(tree_p);
    r->data = 'c';
    node_t *n1 = tree_insert_l(l);
    n1->data = 'd';
    node_t *n2 = tree_insert_r(l);
    n2->data = 'e';
    node_t *n3 = tree_insert_l(r);
    n3->data = 'f';
    node_t *n4 = tree_insert_r(r);
    n4->data = 'g';
    tree_scan_dlr(tree_p);  
    return 0;    
}

也有非递归先序遍历的方式（通过“辅助栈”的思想实现）

5.2.6 中序遍历（LDR）及其算法

中序遍历（LDR）的递归过程为：若二叉树为空，遍历结束。否则：
（1）中序遍历根结点的左子树；
（2）访问根结点；
（3）中序遍历根结点的右子树。

5.2.7 后续遍历（LRD）及其算法

后序遍历（LRD）的递归过程为：若二叉树为空，遍历结束。否则：
（1）后序遍历根结点的左子树；
（2）后序遍历根结点的右子树；
（3）访问根结点。

5.2.8 层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
算法实现：
二叉树以二叉链表存储，一维数组用以实现队列。
注意应用队列的头和尾的移动。

5.2.9 二叉树的其他操作

5.3 树与森林

5.3.1 树的表示方法

树的存储方式有顺序存储、链式存储，表示的方法也有多种：
（1）双亲表示法
树中的每个结点（除根结点外）都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息及该结点的双亲结点在数组中的序号，树的这种存储方法称为双亲表示法。
（2）孩子表示法

（3）孩子兄弟表示法

5.3.2 树、二叉树和森林的转换

将一棵树转换为二叉树的方法是：
（1）树中所有相邻兄弟之间加一条连线；
（2）对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线；
（3）以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。

【待续：森林转换为二叉树、二叉树转换为树和森林】

5.3.3 树遍历

先根遍历：
（1）访问根结点；
（2） 按照从左到右的顺序先根遍历根结点的每一棵子树。
后根遍历：
（1） 按照从左到右的顺序后根遍历根结点的每一棵子树；
（2） 访问根结点。

5.3.4 森林的遍历

前序遍历：
（1）0 访问森林中第一棵树的根结点；
（2） 前序遍历第一棵树的根结点的子树；
（3） 前序遍历去掉第一棵树后的子森林。
中序遍历：
（1）0 中序遍历第一棵树的根结点的子树；
（2）访问森林中第一棵树的根结点；
（3） 中序遍历去掉第一棵树后的子森林。

5.4 哈夫曼树（最优二叉树）

5.4.1 哈夫曼树的构造方法

（1）由给定的n个权值{w1, w2, …, wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1, T2, …, Tn}；
（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

5.4.2 哈夫曼树的构造算法

【待续】

5.4.3 哈夫曼数的编码

利用哈夫曼树来构造编码方案，就是哈夫曼树的典型应用。

六、图

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的。

6.1 图的基本概念

6.1.1 术语

（1）无向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。如图6.1所示是一个无向图G1。
（2）有向图：在一个图中，如果任意两个顶点构成的偶对<vi, vj>∈E是有序的（有序对常常用尖括号“< >”表示），即顶点之间的连线是有方向的，则称该图为有向图。
（3）顶点、边、弧、弧头、弧尾：在图中，数据元素vi称为顶点（Vertex）；(vi,vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对(vi, vj)来表示，称顶点vi和顶点vj互为邻接点，边(vi, vj)依附于顶点vi与顶点vj；弧用顶点的有序偶对<vi, vj>来表示，有序偶对的第一个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧头），在图中就是带箭头的一端。
（4）无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。
（5）有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。
（6）顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD (v)。在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。有TD (v)=ID (v)＋OD (v)。
可以证明，对于具有n个顶点、e条边的无向图，顶点vi的度TD(vi)与顶点的个数及边的数目满足关系：


图片.png

（8）路径、路径长度：顶点vp到顶点vq之间的路径（Path）是指顶点序列vp, vi1,vi2, …, vim, vq。其中，(vp, vi1), (vi1, vi2), …, (vim, vq)分别为图中的边。路径上边的数目称为路径长度。图6.1所示的无向图G1中，v1→v4→v3→v5与v1→v2→v5是从顶点v1到顶点v5的两条路径，其路径长度分别为3和2。
（9）简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。在图6.1中，前面提到的v1到v5的两条路径都为简单路径。路径中第一个顶点与最后一个顶点相同的路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图6.2中的v1→v3→v4→v1。
（10）子图：对于图G=(V, E)，G′=(V′, E′)，若存在V′是V的子集、E′是E的子集，则称图G′是G的一个子图。图6.4给出了图6.2(G2)和图6.1(G1)的两个子图G′和G″。
（11）连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。
（12）强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj(i≠j)均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。图6.2中有两个强连通分量，分别是{v1, v3, v4}和{v2}，如图6.6所示。
（13）生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。图6.4（b）中的G″给出了图6.1中G1的一棵生成树。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。
（14）生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

6.1.2 图的操作

（1）CreatGraph(G)：输入图G的顶点和边，建立图G的存储。（2）DestroyGraph(G)：释放图G占用的存储空间。
（3）GetVex(G, v)：在图G中找到顶点v，并返回顶点v的相关信息。（4）PutVex(G, v, value)：在图G中找到顶点v，并将value值赋给顶点v。
（5）InsertVex(G, v)：在图G中增添新顶点v。
（6）DeleteVex(G, v)：在图G中，删除顶点v及所有和顶点v相关联的边或弧。
（7）InsertArc(G, v, w)：在图G中增添一条从顶点v到顶点w的边或弧。
（8）DeleteArc(G, v, w)：在图G中删除一条从顶点v到顶点w的边或弧。
（9）DFSTraverse(G, v)：在图G中，从顶点v出发深度优先遍历图G。
（10）BFSTtaverse(G, v)：在图G中，从顶点v出发广度优先遍历图G。在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图还有以下的基本操作。
（11）LocateVex(G, u)：在图G中找到顶点u，返回该顶点在图中位置。（12）FirstAdjVex(G, v)：在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。（13）NextAdjVex(G, v, w)：在图G中，返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。

6.2 图的存储结构

6.2.1 邻接矩阵

特点：
（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。
（2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。
（3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。
（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

6.2.2 邻接表

邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表

在邻接表上容易找到任意顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需查找第i个或第j个链表，因此，不如邻接矩阵方便。

6.3 图的遍历

图的遍历是指从图中的任意顶点出发，对图中的所有顶点访问一次且只访问一次。

6.3.1 深度优先搜索（Depth-First Search，DFS）

类似于树的先根遍历，是树的先根遍历的推广。

6.3.2 广度优先搜索（Breadth-First Search，BFS）

类似于树的按层次遍历的过程。

6.4 图的应用

6.4.1 最小生成树

如果无向连通图是一个网，那么，它的所有生成树中必有一棵生成树的边的权值总和最小，称这样一棵生成树为最小代价生成树（Minimum Cost SpanningTree），简称最小生成树（MST）。一棵生成树的代价就是树中所有边的代价之和。

构造最小生成树的Prim算法和Kruskal算法
【待续】

6.4.2 最短路径

在网中求点A到点B的所有路径中边的权值之和最短的那一条路径，这条路径就是两点之间的最短路径
【待续】

6.4.3 拓扑排序

七、查找

（1）关键码

7.2 静态表查找

7.2.1 静态表查找结构

静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。

7.2.2 顺序查找

顺序查找又称线性查找，是最基本的查找方法之一。其查找过程为：从表的一端开始，向另一端逐个将其关键码与给定值kx进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出失败信息。

7.2.3 有序表查找

有序表是表中数据元素按关键码升序或降序排列。对于有序表，若按顺序存储结构存储，可以用折半查找来实现查找操作。

7.2.4 分块查找

分块查找又称索引顺序查找，是对顺序查找的一种改进。分块查找要求将查找表分成若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。

7.3 动态表查找

二叉排序树就是一种常见的动态查找表

7.3.1 二叉排序树定义

二叉排序树（Binary Sort Tree）或者是一棵空二叉树，或者是具有下列性质的二叉树。
（1）若左子树不空，则左子树上所有结点的关键码值均小于根结点的关键码值；若右子树不空，则右子树上所有结点的关键码值均大于根结点的关键码值。
（2）左、右子树也都是二叉排序树。
左子节点键值 < 父节点键值 < 右子节点键值

7.3.1 二叉排序树查找算法

7.3.1 二叉排序树构造和插入

7.4 哈希表

建立关键码与数据元素间的一一对应关系，通过这个关系，能很快地由关键码值得到对应的数据元素位置。而哈希方法就是试图建立这样的对应关系。

选取某个函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键码进行比较，确定查找是否成功，这就是哈希（Hash）方法（又称为散列法、杂凑法或关键字地址计算法）；哈希方法中使用的转换函数称为哈希（Hash）函数（散列函数）。

7.4.1 常用的哈希函数构造方法

【待续】

7.4.2 处理冲突的方法

【待续】

7.4.4 哈希表的查找算法

【待续】

7.4.4 哈希表的性能分析

8 排序

上一篇下一篇

猜你喜欢

热点阅读