数据结构总览

2019-10-23

一、二叉树

1、二叉树的存储结构

1.1 二叉链表存储结构

typedef struct BTNode{
    char data;    
    struct BTNode *lchild;
    struct BTNode *rchild;
}

2、二叉树的遍历算法

2.1 先序遍历

void preorder(BTNode *P)
{
    if(p!==NULL)
    {
        visit(p);
        preorder(p->lchild);   //遍历左子树
        preorder(p->rchild);
    }
}

2.2 中序遍历

void inorder(BTNode *P)
{
    if(p!==NULL)
    {
        inorder(p->lchild);   //遍历左子树
        visit(p);
        inorder(p->rchild);
    }
}

2.3 应用

1、计算 A*B的表达式，该表达式存储在二叉树中

int comp(BTNode *p)
{
    if(p!=NULL)
    {
        if(p->lchild!=NULL&&P->rchild!=NULL) //运算符
        {
            A = comp(p->lchild);
            B = comp(p->rchild);
            return op(A, B, p->data);
        }
        else
        {
            return p->data - '0'    //转化为int
        }
    }
    else return 0;
}

2、求二叉树的深度，二叉链表为存储结构

int getDepth(BTNode *p)
{
    int LD,RD;
    if(p==NULL)
    {
        return 0;
    }
    else
    {
         LD = getDepth(p->lchild);
        RD = getDepth(p->rchild);
        return (LD > RD ? LD: RD) + 1;  //左右子树深度最大值+1
    }
}

3、在一颗以二叉链表为存储结构，查找data域等于key节点是否存在

void search(BTNode *p, BTNode *&q, int key)
{
    if(p!=NULL)
    {
        if(p->data == key) q=p;
        else
        {
            search(p->lchild, q, key);  //左子树查找
            if(q==NULL){    
                search(p->rchild, q, key);        //若左子树查找不到，右子树查找
            }
        }
    }
}

4、二叉树采取二叉链表存储结构，输出先序序列中第k个结点的值，k不大于总结点的个数

int n=0;    //全局变量
void trave(BTNode *p, int k){
    if(p!=NULL)
    {
        ++n;        //第一次来到一个结点时，进行计数，表示第n个结点
        if(k==n){
            print(&d, p->data);
            return;
        }
        trave(p->lchild, k);
        trave(p->rchild, k);
    }
}

2.4 层次遍历

使用循环队列，自左向右的层次遍历

void level(BTNode *p)
{
    if(p!=NULL){    //非空才需要往下运行
        BTNode *que[maxsize];     //定义一个循环队列，用来记录将要访问的结点
        BTNode *q;
        int front=0, rear=0;
        //关键代码
        rear = (rear+1) % maxsize;    //根节点入队
        que[rear] = p;
        while(front!=rear){
            front = (front+1) % maxsize;    //队头结点出队
            q = que[front];
            visit(q);
            if(q->lchild!=NULL){    //结点的左子树不空，入队
                rear = (rear+1)%maxsize;
                que[rear] = p->lchild;
            }
            if(q->rchild!=NULL){    //结点的右子树不空，入队
                rear = (rear+1) % maxsize;
                que[rear] = p->rchild;
            }
        }
    }
}

3、二叉树非递归遍历算法

3.1 先序遍历

void preorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL){
        BTNode *stack[maxsize];    //定义一个栈    
        int top = -1;
        BTNode *p;
        stack[++top] = bt;        //根结点入栈
        while(top!=-1)
        {
            p = stack[top--];    //出栈并输出栈顶点
            visit(p);
            if(p->rchild!=NULL){    //右孩子存在
                stack[++top] = p->rchild; 
            }
            if(p->lchild!=NULL){    //左孩子存在
                stack[++top] = p->lchild;
            }
        }
    }
}

3.2 中序遍历

void inorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL){
        BTNode *stack[maxsize];
        int top = -1;
        BTNode *p;
        p = bt;
        while(top!=-1 || p!=NULL)    //遍历过程中有可能出现栈空，但是没有遍历完的情况
        {
            while(p!=NULL)
            {
                stack[++top] = p;
                p = p->lchild;
            }
            if(top!=-1)        // 栈不空的情况下，出栈并且访问        
            {
                p = stack[top--];    
                visit(p);
                p = p->rchild;
            }
        }
    }
}

3.3 后序遍历

void postorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *stack1[maxisize];
        BTNode *stack2[maxisize];
        BTNode *p;
        int top1 = -1,top2 = -1;
        stack1[++top1] = bt;
        while(top1!=-1){    //逆后序 根右左 ，后序是左右根
            p = stack[top1--];  //栈顶出栈并访问
            stack2[++top2] = p;  //入栈
            if(p->lchild!=NULL){
                stack[++top1] = p->lchild;        
            }
            if(p->rchild!=NULL){
                stack[++top1] = p->rchild;
            }
        }
        while(top!=-1)
        {
            p = stack2[top--];    //出栈即为后序访问
            visit(p);   
        }
    }
}

4、树与二叉树的应用

4.1 构造哈夫曼树和求各个字符的哈夫曼编码

typedef struct{
    int weight;        //结点的权值
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;     //动态分配数组存储赫夫曼树
typedef char* *HuffmanCode  //动态分配数组存储赫夫曼编码表

//构造算法
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
    //w中存储n个字符的权值，构造哈夫曼树HT,并求出n个字符的赫夫曼树HC;
    if(n <= 1) return ;
    int m = 2*n - 1;
    int i;
    HTNode *p;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //从1开始
    for(p=HT,i=1; i<=n; ++w,++i,++p)  *p ={*w, 0, 0, 0}; //初始化叶子结点
    for(;i<=m; ++i,++p) *p = {0, 0, 0, 0};
    for(i=n+1; i<=m; ++i)  //建哈夫曼树
    {
         //在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为S1和S2
        select(HT, i-1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight
    }
    // ---从叶子到根逆向求每个字符的赫夫曼编码
    HC = (HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
    cd = (char*)malloc(n*sizeof(char));             //分配求编码的工作空间
    cd[n-1] = '\0';                                    //编码的结束符
    for(i=1; i<=n ; ++i)                            //逐个求编码
    {
        start = n-1;                                //编码的结束位置
        for(c=i,f = HT[i].parent; f!=0; c=f,f=HT[i].parent)
        {
            if(HT[f].lchild == c)
            {
                cd[--start] = '0';
            }else
            {
                cd[--start] = '1';    
            }
            HC[i] = (char*)malloc((n-start)*sizeof(char))) //为第i个字符分配空间
            strcpy(HC[i],&cd[start]);  //从cd复制到编码hc
        }
    }
    free(cd);        
}

二、图

1、图的存储结构

1.1 邻接矩阵

图的顺序存储结构

typedef struct 
{
    int no;        //顶点编号
    char info;    //顶点的其他信息，可以不写
}VertexType;    //顶点类型

typedef struct     //图的定义
{
    int edges[maxsize][maxsize];    //邻居矩阵的定义
    int n,e;                      //顶点数和边数
    VextexType vex[maxsize];        //存放的结点信息
}MGragh;                          //图的邻接矩阵类型

1.2 领接表

//结点
typedef struct ArcNode      
{
    int adjvex;            //指向结点的位置
    ArcNode *nextarc;     //指向下一条边的信息
    int info;            //可以不写
}ArcNode;
//顶点信息 
typedef struct            
{
    char data;                //顶点信息
    ArcNode *firstarc;         //指向第一条边的信息
}VNode;

typedef struct
{
    VNode adjlist[maxsize];  //邻接表
    int n,e                    //顶点数和边数
}AGragh;

2、图的遍历算法

2.1 深度优先搜索遍历

以邻接表为存储结构的图的深度优先搜索算法

int visit[maxsize]; //访问标记
void DFS(AGragh *G, int v)    //v是起点编号
{
    ArcNode *p;
    visit[v] = 1;     //设置已访问
    Visit(v);        //访问结点操作
    p = G->adjlist[v].firstarc;   //指向顶点v的第一条边
    while(p!=NULL){
        if(visit[p->adjvex]==0)        //若顶点没访问，递归访问它
        {
            DFS(G, p->adjvex);
        }
        p = p->nextarc;          //p指向顶点v的下一条边
    }
}

2.2 广度优先搜索遍历

类似树的层次遍历，需要一个队列

以邻接表为存储结构的图的广度优先搜索算法

void BFS(AGragh *G, int v, int visit[maxsize])
{
    ArcNode *p;
    int que[maxsize], front=0, rear=0;
    int j;
    Visit(v);        //访问顶点v的函数
    visit[v];        //标记已经访问过的结点
    rear = (rear+1) % maxsize;
    que[rear] = v;        //顶点v入队列
    while(front!=rear)    //栈空说明已经遍历完
    {
        front = (front+1) % maxsize;    //顶点出队
        j = que[front];
        p = G->adjlist[j].firstarc;        //p指向出队顶点j的第一条边
        while(p!=NULL){
            if(visit[p->adjvex]==0){    //若顶点没访问则访问
                Visit(p->adjvex);    
                visit[p->adjvex] = 1;
                rear = (rear+1) % maxsize;    //顶点入队
                que[rear] = p->adjvex;
            }
            p = p->nextarc;             //p指向j的下一条边
        }
    }
}

2.3 例题

1. 设计一个算法，求不带权无向连通图距离顶点最远的点

int BFS(AGragh *G, int v)
{
    ArcNode *p;
    int que[maxsize],front=0,rear=0;
    int visit[maxsize];
    int i,j;
    for(i=0; i < G.n; ++i){      //初始化
        visit[i] = 0;
    }
    rear = (rear+1) % maxsize;
    que[rear] = v;
    visit[v] = 1;
    while(front!=rear){
        front = (front+1) % maxsize;
        j = que[front];
        p = G->agjlist[j].firstarc;
        while(p!=NULL)
        {
            if(visit[p->adjvex]==0)
            {
                visit[p->adjvex] = 1;
                rear = (rear+1) % maxsize;
                que[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
    return j;  //队为空时，j保存了遍历过程中的最后一个结点
}

2. 判断一个无向图G是否是一棵树，若是树，返回1，否则返回0

分析：无向图的一棵树的条件是有n-1条边的连通图，n为图中顶点的个数

void DFS1(AGragh *G, int v, int &vn, int &en){
    ArcNode *p;
    visit[v] = 1;
    ++vn;        //顶点数增1
    p = G->adjlist[v].firstarc;
    while(p!=NULL){
        ++en;     //边数自增1
        if(visit[p->adjvex] == 0){
            DFS(G, p->adjvex, vn, en)
        }
        p = p->nextarc;
    }
}
int GisTree(AGragh *G)
{
    int vn =0, en =0;
    for(int i=0; i<G.n; ++i){
        visit[i] = 0;
    }
    DFS2(G, 1, vn, en);
    if(G->n == vn && (G->n - 1)== en/2) //顶点数等于遍历后的顶点数，边数等于顶点数减1
        return 1;
    else
        return 0;
}

3. 判断顶点i 和顶点j (i!=j)之间存在路径

分析：从顶点i开始进行深度优先遍历，遍历过程中遇到j说明i与j之间存在路径，否则没有路径。

int DFStrave(AGragh *G, int i, int j)
{
    for(int k=0; k< G.n; ++k) visit[k] = 0;
    DFS(G,i);    //BFS(G, i)
    if(visit[j]=1){        //说明遇到了j
        return 1;
    }else{
        return 0;
    }
}

3、最小生成树

3.1 普里姆算法

执行过程：

将v0到其他顶点的所有边当做候选边；
重复一下操作n-1次，使得其他n-1个顶点并入到生成树中：
1. 从候选边中挑选出权值最小的边输出，并将与该边另一端相接的顶点v并入生成树中
2. 考察所有剩余顶点vi, 如果(v, vi)的权值比lowcost[vi]小，则用(v, vi)的权值更新lowcost[vi]；

void Prim(MGragh g, int v0, int &sum)
{
    //初始化
    int lowcost[maxsize], vset[maxsize], v;
    v = v0;
    int i, j, k, min;
    for(i = 0; i< g.n; ++i)
    {
        lostcost[i] = g.edges[v][i];
         vset[i] = 0;
    }
    vset[v] = 1;    //将v0并入树中
    sum = 0;        //累计树的权值

    for(i = 0; i< g.n - 1; ++i)
    {
        min = INF        //inf比定义图中所有边的权值都大的常量
        //在候选边中选出权值最小的边
        for(j=0; j<g.n; ++j)
        {
            if(vset[j]==0 && lowcost[j] < min)
            {
                min = lowcost[j];
                k = j;
            }
        }
        v = k;
        vset[v] = 1;
        sum += min;

        //更新候选边的最小权值
        for(j=0; j<g.n; ++j)
        {
            if(vset[j]==0 && lowcost[j]> g.edges[v][j]){
                lowcost[j] = g.edges[v][j];    //更新
            }
        }
    }
}

3.2 克鲁斯卡尔算法

执行过程：

按照权值从小到大排序，然后从最小边开始扫描各边，并检测当前边是否为候选边，即是否该边的并入会构成回路，若不构成则并入。
检查是否产生回路要用到并查集

typedef struct
{
    int a, b;        //a和b为一条边所连的两个顶点
    int w;            //边的权值
}Road;
Road road[maxsize];
int v[maxsize];        //并查集数组

//判断是否在一个集合中的函数
int getRoot(int a)        //查找根结点
{
    while(a!=v[a]){
        a=v[a];
    }
    return a;
}

void Kruskal(MGragh g, int &sum , Road road[])    //road存放着各边所连接的顶点信息
{
    int i;
    int N,E,a,b;
    N = g.n;
    E = g.e;
    for(i=0; i<N; ++i) v[i]=i;
    sort(road, E);  //根据E中边的权值从小到大排序
    for(i=0; i< E; i++)
    {
        a = getRoot(road[i].a);
        b = getRoot(road[i].b);
        if (a!=b){
            v[a] = b;
            sum += road[i].w;    //可以换成其他的
        }
    }  
}

4、最短路径

4.1 迪杰斯特拉算法

某一顶点到其余顶点的最短路径

void Dijkstra(MGragh g, int v, int dist[], int path[])
{
    int set[maxsize];
    int min, i, j, u;
    //初始化
    for(i=0; i< g.n; ++i)
    {
        set[i] = 0;
        dist[i] = g.edges[v][i];
        if(g.edges[v][i]<INF){
            path[i] = v;
        }else{
            path[i] = -1;
        }
    }
    set[v] = 1;
    path[v] = -1;
    //初始化结束
    for(i = 0; i<g.n - 1; ++i){
        min = INF;
        //通往最短的顶点
        for(j=0; j<g.n, ++j){
            if(set[j]==0 && dist[j]< min){
                min = dist[j];
                u = j;
            }
        }
        set[u] = 1;    //将选出的顶点并入到最短路径中
        //这个循环以刚并入的顶点作为中间点，对所有通往剩余结点的路径进行检测
        for(j = 0; j < g.n; ++j){
            if(set[j] == 0 && dist[j]>dist[u] + g.edges[u][j]){
                dist[j] = dist[u] + g.edges[u][j];
                path[j] = u;
            }
        }
    }
}
//函数结束时，dist[]存放着v点到其余各顶点的最短路径长度，path[]存放着v点到其余各顶点的最短路径

4.2 弗洛伊德算法

任意一对顶点间的最短路径

执行过程：

设置两个矩阵A和path，初始时将邻接矩阵赋值给A, 将path设置成-1；
以顶点k为中间顶点，k取 0 ~ n-1 ,对图中所有顶点{i,j}进行检测与修改：
1. 若A[i][j]> A[i][k] + A[k][j] ,则修改值，将path路径设为k; 否则什么都不做

void Floyd(MGragh g, int Path[][maxsize])
{
    int i,j,k;
    int A[maxsize][maxsize];
    //初始化A[]和path[]
    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为中间点对{i, j} 进行遍历修改
    for(k = 0; k< g.n; ++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 = k;
                }
            }
        }
    }
}

5、拓扑排序

5.1 AOV-网

执行过程：

扫描所有顶点，并将入度为0的顶点入栈，循环执行以下操作
1. 出栈，并将栈顶点输出，执行++n，并将由此顶点指向的顶点的入度减1；
2. 将入度为 0的顶点入栈

typedef struct     
{
    char data;
    int count;    //统计结点的当前的入度
    ArcNode *firstNode;
}VNode;

//设置一个栈，用来记录当前入度为0的结点，再设置一个计数器，用来记录已经输出的顶点个数

int Topsort(AGragh *G){
    int i, j, n =0;
    int stack[maxsize], top=-1;        //定义并初始化栈
    ArcNode *p;
    //将入度为0的结点入栈
    for(i=0; i< g.n; ++i){    //图中顶点从0开始编号
        if(G->adjlist[i].count == 0){
            stack[++top] = i;
        }
    }
    //关键操作
    while(top != -1){
        i = stack[top--];    //顶点出栈
        ++n;               //计数器+1
        p = G->adjlist[i].firstArc;
        //并将由此顶点指向的顶点的入度减1
        while(p!=NULL){
            j = p->adjvex;
            --(G->adjlist[j].count);
            if(G->adjlist[j].count == 0){
                stack[++top] = j;
            }
            p = p->nextarc;
        }
    }
    //关键操作结束
    if(n == G.n){
        return 1;
    }else{
        return 0;
    }
}

三、排序

1、插入类排序

1.1 直接插入排序

平均时间复杂度O(n^2)，最好是O(n)，空间复杂度为O(1)

void insertSort(int R[], int n)        //待排序列个数为n
{
    int i,j;
    int temp;
    for(i = 1; i< n; ++i){
        temp = R[i];
        j = i - 1;
        //从待排关键字之前开始扫描，如果大于待排关键字，则后移一位
        while( j>=0 && temp < R[j]){
            R[j+1] =R[j];
            --j;
        }
        R[j+1] = temp;    //找到插入的位置，将temp插入
    }
}

1.2 折半插入排序

时间复杂度
1. 平均复杂度O(n^2)，最好是O(nlog2n)，最坏是O(n^2)
空间复杂度O(1)

1.3 希尔排序

缩小增量排序，本质是插入排序，将待排序列按某种规则分成好几个子序列。是不稳定的算法。

增量选取注意的地方：

增量序列最后一个值一定取1；
增量序列中的值尽量没有除1之外的公因子；

空间复杂度O(1)

2、交换类排序

2.1 冒泡排序

void BubbleSort(int R[], int n){
    int i, j, flag;
    int temp;
    for(i = n-1 ; i> =1; --i){
        flag = 0;        //flag用来标记本趟排序是否发生了交换
        for(j = 1; j< = i; ++j)
        {
            if(R[j-1]>R[j]){
                temp = R[j];
                R[j] = R[j-1];
                R[j-1] =  temp;
                flag = 1;        //如果没发生交换，则flag的值为0;
            }
            if (flag == 0){
                return ;
            }
        }
    }
}

时间复杂度最好是O(n), 最差是O(n^2), 平均时间复杂度是O(n^2);

空间复杂度是O(1)

2.2 快速排序

void QuickSort(int R[], int low, int high){
    int temp;
    int i = low, j = high;
    if(low<high)
    {
        temp = R[low];
        //完成一次排序，将数组中小于temp的放在左边，大于temp的放在右边
        while(i < j)
        {
            while(j > i && temp < R[j]) --j;    //从右往左扫描
            if(i < j)
            {
                R[i] = R[j];    //放在temp的左边
                ++i;            //i右移一位
            }
            while(j > i && temp > R[i]) ++i;
            if(i < j)
            {
                 R[j] = R[i];
                --j;
            }
        }
        R[i] = temp;  //将temp放在最终位置
        QuickSort(R, low, i-1);
        QuickSort(R, i+1, high);
    }
}

时间复杂度最好是O(nlog2n), 最差是O(n^2), 平均时间复杂度是O(nlog2n);

空间复杂度是O(log2n)

3、选择类排序

3.1 简单选择排序

void SelectSort(int R[], int n)
{
    int i,j, k;
    int temp;
    for(i = 0; i< n; ++i)
    {
        //选出关键字最小的
        k = i;
        for(j = i+1; j< n; ++j){
            if(R[k] > R[j]){
                k = j;
            }
        }
        //最小的关键字与无序中第一个关键字交换序列
        temp = R[k];
        R[k] = R[i];
        R[i] = temp;
    }
}

平均时间复杂度是O(n^2);

空间复杂度是O(1)

3.2 堆排序

//调整函数
void Sift(int R[], int low, int high) //关键词的存储从1开始
{
    int i= low, j = 2*i;    //R[j]是R[i]的左孩子
    int temp = R[i];
    while(j<=high)
    {
        if(j<high && R[j+1] > R[j]){    //先选出左右子树的最大值
            ++j;
        }
        if(temp < R[j]){
            R[i] = R[j];
            i = j;                //调整i的值，继续往下调整
            j = 2*i;
        }else{
            break;
        }
    }
    R[i] = temp;
}
//堆排序函数
void heapSort(int R[], int n)
{
    int i;
    int temp; 
    for(i = n/2; i>=1; --i)    //从最后一个非零叶子结点开始调整
        Sift(R, i, n);
    for(i = n; i >=2; --i){
        //根节点的关键字，放到最终的位置
        temp = R[1];
        R[1] = R[i];
        R[i] = temp;
        Sift(R, 1, i-1);     //减少了1个关键字的无序序列进行调整
    }
}

3.3 归并排序

例题：A与B是两个单链表，其中元素递增有序，设计一个算法，将A和B归并成一个按元素值非递减有序的链表C，C由A和B中的结点组成。

void merge(LNode *A, LNode *B, LNode *&c)
{
    LNode *p = A->next; //p来跟踪A的最小值的结点
    LNode *q = B->next; //q来跟踪B的最小值的结点
    LNode *r;             //指向C的终端结点
    C = A;                //C的头结点指向A的头结点
    C->next = NULL;
    free(B);             //B的头结点已经没用
    r = C;
    while(p!=null&&q!=null)
    {
        if(p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
        }else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }

    //两个if将剩余的结点链接在C的尾部；
    if(p!=NULL){
        r-> next = p;
    }
    if(q!=NULL){
        r-> next = q;
    }
}

二路归并排序：

void mergeSort(int A[], int low, int high)
{
    if(low<high)
    {
        int mid = (low + high)/2;
        mergeSort(A, low, mid);
        mergeSort(B, mid+1, high);
        merge(A, low, mid, high);     //将上面算法稍作修改
    }    
}

四、查找

折半查找

int Bsearch(int R[], int low, int high, int k)
{
    int mid ;
    while(low <= high){
        mid = (low+high)/2;
        if(R[mid] == k){
            return mid;
        }else if(R[mid] < k){
            high = mid -1;
        }else{
             low = mid+1;   
        }
    }
    return 0;
}

二叉排序树查找

BTNode* BSTSearch(BTNode* bt, int key)
{
    if(bt==NULL){
        return NULL;
    }else
    {
        if(bt->key == key)
            return bt;
        else if(key < bt->key)
            return BSTSearch(bt->lchild, key);
        else return BSTSearch(bt->rchild, key);
    }
}

|阅读量()

一、二叉树

1、二叉树的存储结构

1.1 二叉链表存储结构

2、 二叉树的遍历算法

2.1 先序遍历

2.2 中序遍历

2.3 应用

2.4 层次遍历

3、二叉树非递归遍历算法

3.1 先序遍历

3.2 中序遍历

3.3 后序遍历

4、树与二叉树的应用

4.1 构造哈夫曼树和求各个字符的哈夫曼编码

二、图

1、图的存储结构

1.1 邻接矩阵

1.2 领接表

2、图的遍历算法

2.1 深度优先搜索遍历

2.2 广度优先搜索遍历

2.3 例题

3、最小生成树

3.1 普里姆算法

3.2 克鲁斯卡尔算法

4、最短路径

4.1 迪杰斯特拉算法

4.2 弗洛伊德算法

5、拓扑排序

5.1 AOV-网

三、排序

1、插入类排序

1.1 直接插入排序

1.2 折半插入排序

1.3 希尔排序

2、交换类排序

2.1 冒泡排序

2.2 快速排序

3、选择类排序

3.1 简单选择排序

3.2 堆排序

3.3 归并排序

四、查找

折半查找

二叉排序树 查找

2、二叉树的遍历算法

二叉排序树查找