1. 1. 图
    1. 1.1. 1.图的基本概念
      1. 1.1.1. 1.1.图的定义
      2. 1.1.2. 1.2.图的基本术语
    2. 1.2. 2.图的存储结构
      1. 1.2.1. 2.1.图的连接矩阵
      2. 1.2.2. 2.2.图的连接表
    3. 1.3. 3.图的遍历
      1. 1.3.1. 3.1.广度优先搜索
      2. 1.3.2. 3.2.深度优先搜索
    4. 1.4. 4.有向图连接矩阵
      1. 1.4.1. 4.1.图的定义
      2. 1.4.2. 4.2.创建图
      3. 1.4.3. 4.3.列出图
      4. 1.4.4. 4.4.main
    5. 1.5. 5.有向图连接链表
      1. 1.5.1. 5.1.图的定义
      2. 1.5.2. 5.2.创建图
      3. 1.5.3. 5.3.列出图
      4. 1.5.4. 5.4.main
    6. 1.6. 6.图的基本运算(By-Go)
    7. 1.7. 7.图的遍历
      1. 1.7.1. 7.1.广度优先遍历
      2. 1.7.2. 7.2.深度优先遍历
    8. 1.8. 8.最小生成树
      1. 1.8.1. 8.1.普利姆算法
      2. 1.8.2. 8.2.克鲁斯卡尔算法
    9. 1.9. 9.最短路径
      1. 1.9.1. 9.1.狄克斯特拉算法
      2. 1.9.2. 9.2.弗洛伊德算法
    10. 1.10. 10.拓扑排序算法
  2. 2. 查找
    1. 2.1. 1.查找的基本概念
      1. 2.1.1. 1.1.查找的定义
      2. 2.1.2. 1.2.查找算法分类
    2. 2.2. 2.顺序查找
    3. 2.3. 3.二分法查找
    4. 2.4. 4.分块查找
    5. 2.5. 5.二叉排序树查找
    6. 2.6. 6.哈希表查找
      1. 2.6.1. 6.1.By C++
      2. 2.6.2. 6.2.By Golang
    7. 2.7. 7.哈希查找
  3. 3. 排序
    1. 3.1. 1.排序的定义
      1. 3.1.1. 1.1.排序方法比较
    2. 3.2. 2.插入排序
      1. 3.2.1. 2.1.直接插入排序
      2. 3.2.2. 2.2.希尔排序
    3. 3.3. 3.选择排序
      1. 3.3.1. 3.1.直接选择排序
        1. 3.3.1.1. 3.1.1.基本思想
        2. 3.3.1.2. 3.1.2.步骤
        3. 3.3.1.3. 3.1.3.By C++
        4. 3.3.1.4. 3.1.4.By Golang
        5. 3.3.1.5. 3.1.5.排序过程
      2. 3.3.2. 3.2.堆排序
        1. 3.3.2.1. 3.2.1.By C++
    4. 3.4. 4.交换排序
      1. 3.4.1. 4.1.冒泡排序
        1. 3.4.1.1. 4.1.1.基本思想
        2. 3.4.1.2. 4.1.2.步骤
        3. 3.4.1.3. 4.1.3.By C++
        4. 3.4.1.4. 4.1.4.By Golang
        5. 3.4.1.5. 4.1.5.排序过程
      2. 3.4.2. 4.2.快速排序
        1. 3.4.2.1. 4.2.1.基本思想
        2. 3.4.2.2. 4.2.2.步骤
        3. 3.4.2.3. 4.2.3.By C++
        4. 3.4.2.4. 4.2.4.By Golang
        5. 3.4.2.5. 4.2.5.排序过程
    5. 3.5. 5.归并排序
    6. 3.6. 6.基数排序

数据结构笔记归档3

图

1.图的基本概念

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

1.1.图的定义

图(Graph)是一种非线性结构，其中的元素是多对多的关系。

图(Graph)是由非空的顶点的集合和描述顶点关系即边的集合组成。

1.2.图的基本术语

  • 有向图：边是有方向的图
  • 无向图：边是无方向的图

2.图的存储结构

2.1.图的连接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAXVEX  100

typedef char VertexType[3];        /*定义VertexType为char数组类型*/

typedef struct vertex
{    
    int adjvex;                 /*顶点编号*/
    VertexType data;             /*顶点的信息*/
} VType;                        /*顶点类型*/

typedef struct graph
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VType vexs[MAXVEX];            /*顶点集合*/
    int edges[MAXVEX][MAXVEX];    /*边的集合*/
} AdjMatix;                        /*图的邻接矩阵类型*/

2.2.图的连接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MAXVEX 100

typedef char VertexType[3];

typedef struct edgenode
{    
    int adjvex;                  /*邻接点序号*/
    int value;                  /*边的权值*/
    struct edgenode *next;        /*下一条边的顶点*/
} ArcNode;                        /*每个顶点建立的单链表中结点的类型*/

typedef struct vexnode
{
    VertexType data;               /*结点信息*/
    ArcNode *firstarc;             /*指向第一条边结点*/
} VHeadNode;                    /*单链表的头结点类型*/

typedef struct 
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
} AdjList;                         /*图的邻接表类型*/

3.图的遍历

3.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
32
33
34
/* 邻接矩阵存储的图 - BFS */
 
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}
 
/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;
 
    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */
     
    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}

3.2.深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 邻接表存储的图 - DFS */
 
void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}
 
/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;
     
    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */
 
    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

4.有向图连接矩阵

4.1.图的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#define MAXVEX  100

typedef char VertexType[3];        /*定义VertexType为char数组类型*/

typedef struct vertex
{    
    int adjvex;                 /*顶点编号*/
    VertexType data;             /*顶点的信息*/
} VType;                        /*顶点类型*/

typedef struct graph
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VType vexs[MAXVEX];            /*顶点集合*/
    int edges[MAXVEX][MAXVEX];    /*边的集合*/
} AdjMatix;                        /*图的邻接矩阵类型*/

4.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
int CreateMatix(AdjMatix &g)
{
    int i,j,k,b,t;
    int w;
    printf("顶点数(n)和边数(e):");
    scanf("%d%d",&g.n,&g.e);
    for (i=0;i<g.n;i++)
    {    
        printf("   序号为%d的顶点信息:",i);
        scanf("%s",g.vexs[i].data);
        g.vexs[i].adjvex=i;        /*顶点编号为i*/
    }
    for (i=0;i<g.n;i++)
        for (j=0;j<g.n;j++)
            g.edges[i][j]=0;
    for (k=0;k<g.e;k++)
    {
        printf("   序号为%d的边=>",k);
        printf("  起点号 终点号 权值:");
        scanf("%d%d%d",&b,&t,&w);
        if (b<g.n && t<g.n && w>0)
            g.edges[b][t]=w;
        else
        {
            printf("输入错误!\n");
            return(0);        
        }
    }
    return(1);
}

4.3.列出图

1
2
3
4
5
6
7
8
9
10
11
void DispMatix(AdjMatix g)
{
    int i,j;
    printf("\n图的邻接矩阵:\n");
    for (i=0;i<g.n;i++)
    {
        for (j=0;j<g.n;j++)
            printf("%3d",g.edges[i][j]);
        printf("\n");
    }
}

4.4.main

1
2
3
4
5
6
void main()
{
    AdjMatix g;
    CreateMatix(g);
    DispMatix(g);
}

5.有向图连接链表

5.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
#include <stdio.h>
#include <malloc.h>
#define MAXVEX 100

typedef char VertexType[3];

typedef struct edgenode
{    
    int adjvex;                  /*邻接点序号*/
    int value;                  /*边的权值*/
    struct edgenode *next;        /*下一条边的顶点*/
} ArcNode;                        /*每个顶点建立的单链表中结点的类型*/

typedef struct vexnode
{
    VertexType data;               /*结点信息*/
    ArcNode *firstarc;             /*指向第一条边结点*/
} VHeadNode;                    /*单链表的头结点类型*/

typedef struct 
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
} AdjList;                         /*图的邻接表类型*/

5.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
int CreateAdjList(AdjList *&G)    /*建立有向图的邻接表*/
{
    int i,b,t,w;
    ArcNode *p;
    G=(AdjList *)malloc(sizeof(AdjList));
    printf("顶点数(n),边数(e):");
    scanf("%d%d",&G->n,&G->e);
    for (i=0;i<G->n;i++)
    {    
        printf("   序号为%d的顶点信息:", i);
        scanf("%s",G->adjlist[i].data);
        G->adjlist[i].firstarc=NULL;
    }
    for (i=0;i<G->e;i++)
    {
        printf("   序号为边=>",i);
        printf(" 起点号 终点号 权值:");
        scanf("%d%d%d",&b,&t,&w);
        if (b<G->n && t<G->n && w>0)
        {
            p=(ArcNode *)malloc(sizeof(ArcNode));    /*建立*p结点*/
            p->value=w;p->adjvex=t;
            p->next=G->adjlist[b].firstarc;     /**p插入到adjlist[b]的单链表之首*/
            G->adjlist[b].firstarc=p;
        }
        else
        {
            printf("输入错误!\n");
            return(0);        
        }
    }
    return(1);
}

5.3.列出图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DispAdjList(AdjList *G)
{
    int i;
    ArcNode *p;
    printf("图的邻接表表示如下:\n");
    for (i=0;i<G->n;i++)
    {    
        printf("  [%d,%3s]=>",i,G->adjlist[i].data);
        p=G->adjlist[i].firstarc;
        while (p!=NULL)
        {    
            printf("(%d,%d)->",p->adjvex,p->value);
            p=p->next;
        }
        printf("∧\n");
    }
}

5.4.main

1
2
3
4
5
6
void main()
{
    AdjList *G;
    CreateAdjList(G);
    DispAdjList(G);
}

6.图的基本运算(By-Go)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// Package graph creates a ItemGraph data structure for the Item type
package graph

import (
    "fmt"
    "sync"
)

// Item the type of the binary search tree
type Item interface{}

// Node a single node that composes the tree
type Node struct {
    value Item
}

func (n *Node) String() string {
    return fmt.Sprintf("%v", n.value)
}

// ItemGraph the Items graph
type ItemGraph struct {
    nodes []*Node
    edges map[Node][]*Node
    lock  sync.RWMutex
}

// AddNode adds a node to the graph
func (g *ItemGraph) AddNode(n *Node) {
    g.lock.Lock()
    g.nodes = append(g.nodes, n)
    g.lock.Unlock()
}

// AddEdge adds an edge to the graph
func (g *ItemGraph) AddEdge(n1, n2 *Node) {
    g.lock.Lock()
    if g.edges == nil {
        g.edges = make(map[Node][]*Node)
    }
    g.edges[*n1] = append(g.edges[*n1], n2)
    g.edges[*n2] = append(g.edges[*n2], n1)
    g.lock.Unlock()
}

// AddEdge adds an edge to the graph
func (g *ItemGraph) String() {
    g.lock.RLock()
    s := ""
    for i := 0; i < len(g.nodes); i++ {
        s += g.nodes[i].String() + " -> "
        near := g.edges[*g.nodes[i]]
        for j := 0; j < len(near); j++ {
            s += near[j].String() + " "
        }
        s += "\n"
    }
    fmt.Println(s)
    g.lock.RUnlock()
}

// Traverse implements the BFS traversing algorithm
func (g *ItemGraph) Traverse(f func(*Node)) {
    g.lock.RLock()
    q := NodeQueue{}
    q.New()
    n := g.nodes[0]
    q.Enqueue(*n)
    visited := make(map[*Node]bool)
    for {
        if q.IsEmpty() {
            break
        }
        node := q.Dequeue()
        visited[node] = true
        near := g.edges[*node]

        for i := 0; i < len(near); i++ {
            j := near[i]
            if !visited[j] {
                q.Enqueue(*j)
                visited[j] = true
            }
        }
        if f != nil {
            f(node)
        }
    }
    g.lock.RUnlock()
}

7.图的遍历

给定一个图G=(V,E)和V(G)中的任一顶点v，从v出发，顺着G的边访问G中的所有顶点，且每个顶点仅被访问一次，这一过程称为遍历图。

一般设置一个辅助数组visited[]，用来标记顶点是否被访问过，初始状态为0，访问过则设置为1。

7.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define MAXVEX 100

typedef char VertexType[3];        /*定义VertexType为char数组类型*/

typedef struct vertex
{    
    int adjvex;                     /*顶点编号*/
    VertexType data;             /*顶点的信息*/
} VType;                        /*顶点类型*/

typedef struct graph
{    
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VType vexs[MAXVEX];            /*顶点集合*/
    int edges[MAXVEX][MAXVEX];    /*边的集合*/
} AdjMatix;                        /*图的邻接矩阵类型*/

typedef struct edgenode
{    
    int adjvex;                  /*邻接点序号*/
    int value;                  /*边的权值*/
    struct edgenode *next;        /*下一条边的顶点*/
} ArcNode;                        /*每个顶点建立的单链表中结点的类型*/

typedef struct vexnode
{
    VertexType data;               /*结点信息*/
    ArcNode *firstarc;             /*指向第一条边结点*/
} VHeadNode;                    /*单链表的头结点类型*/

typedef struct 
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
} AdjList;                         /*图的邻接表类型*/

void DispAdjList(AdjList *G)
{
    int i;
    ArcNode *p;
    printf("图的邻接表表示如下:\n");
    for (i=0;i<G->n;i++)
    {    
        printf("  [%d,%3s]=>",i,G->adjlist[i].data);
        p=G->adjlist[i].firstarc;
        while (p!=NULL)
        {    
            printf("(%d,%d)->",p->adjvex,p->value);
            p=p->next;
        }
        printf("∧\n");
    }
}

void MatToList(AdjMatix g,AdjList *&G)  /*例6.3算法:将邻接矩阵g转换成邻接表G*/
{
    int i,j;
    ArcNode *p;
    G=(AdjList *)malloc(sizeof(AdjList));
    for (i=0;i<g.n;i++)                    /*给邻接表中所有头结点的指针域置初值*/
    {    
        G->adjlist[i].firstarc=NULL;
        strcpy(G->adjlist[i].data,g.vexs[i].data);
    }
    for (i=0;i<g.n;i++)                    /*检查邻接矩阵中每个元素*/
        for (j=g.n-1;j>=0;j--)
            if (g.edges[i][j]!=0)        /*邻接矩阵的当前元素不为0*/
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
                p->value=g.edges[i][j];p->adjvex=j;
                p->next=G->adjlist[i].firstarc;          /*将*p链到链表后*/
                G->adjlist[i].firstarc=p;
            }
    G->n=g.n;G->e=g.e;
}

void BFS(AdjList *G,int vi)        /*对邻接表g从顶点vi开始进行广宽优先遍历*/
{
    int i,v,visited[MAXVEX];
    int Qu[MAXVEX],front=0,rear=0;        /*循环队列*/
    ArcNode *p;
    for (i=0;i<G->n;i++)                /*给visited数组置初值0*/
        visited[i]=0;
    printf("%d ",vi);                    /*访问初始顶点*/
    visited[vi]=1;                        /*置已访问标识*/
    rear=(rear=1)%MAXVEX;                /*循环移动队尾指针*/
    Qu[rear]=vi;                        /*初始顶点进队*/
    while (front!=rear)                    /*队列不为空时循环*/
    {    
        front=(front+1) % MAXVEX;
        v=Qu[front];                    /*顶点v出队*/
        p=G->adjlist[v].firstarc;        /*找v的第一个邻接点*/
        while (p!=NULL)                    /*找v的所有邻接点*/
        {    
            if (visited[p->adjvex]==0)    /*未访问过则访问之*/
            {
                visited[p->adjvex]=1;    /*置已访问标识*/
                printf("%d ",p->adjvex);/*访问该点并使之入队列*/
                rear=(rear+1) % MAXVEX;    /*循环移动队尾指针*/
                Qu[rear]=p->adjvex;        /*顶点p->adjvex进队*/
            }
            p=p->next;                    /*找v的下一个邻接点*/
        }
    }
}

void main()
{
    int i,j;
    AdjMatix g;
    AdjList *G;
    int a[5][5]={ {0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0} };
    char *vname[MAXVEX]={"a","b","c","d","e"};
    g.n=5;g.e=12;    /*建立图6.1(a)的无向图,每1条无向边算为2条有向边*/
    for (i=0;i<g.n;i++)
        strcpy(g.vexs[i].data,vname[i]);
    for (i=0;i<g.n;i++)
        for (j=0;j<g.n;j++)
            g.edges[i][j]=a[i][j];
    MatToList(g,G);        /*生成邻接表*/
    DispAdjList(G);        /*输出邻接表*/
    printf("从顶点0的广度优先遍历序列:\n");
    printf("\t");BFS(G,0);printf("\n");
}

7.2.深度优先遍历

  • 从图G中某个顶点vi出发，访问vi，然后选择一个与vi相邻且没有被访问过的顶点v访问，再从v出发选择一个与v相邻且未被访问的顶点vj访问，依次访问。
  • 如果当前已被访问的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点w，从w出发按相同的方法继续遍历，直到所有的顶点都被访问到。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define MAXVEX 100

typedef char VertexType[3];        /*定义VertexType为char数组类型*/

typedef struct vertex
{    
    int adjvex;                     /*顶点编号*/
    VertexType data;             /*顶点的信息*/
} VType;                        /*顶点类型*/

typedef struct graph
{    
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VType vexs[MAXVEX];            /*顶点集合*/
    int edges[MAXVEX][MAXVEX];    /*边的集合*/
} AdjMatix;                        /*图的邻接矩阵类型*/

typedef struct edgenode
{    
    int adjvex;                  /*邻接点序号*/
    int value;                  /*边的权值*/
    struct edgenode *next;        /*下一条边的顶点*/
} ArcNode;                        /*每个顶点建立的单链表中结点的类型*/

typedef struct vexnode
{
    VertexType data;               /*结点信息*/
    ArcNode *firstarc;             /*指向第一条边结点*/
} VHeadNode;                    /*单链表的头结点类型*/

typedef struct 
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
} AdjList;                         /*图的邻接表类型*/

void DispAdjList(AdjList *G)
{
    int i;
    ArcNode *p;
    printf("图的邻接表表示如下:\n");
    for (i=0;i<G->n;i++)
    {    
        printf("  [%d,%3s]=>",i,G->adjlist[i].data);
        p=G->adjlist[i].firstarc;
        while (p!=NULL)
        {    
            printf("(%d,%d)->",p->adjvex,p->value);
            p=p->next;
        }
        printf("∧\n");
    }
}

void MatToList(AdjMatix g,AdjList *&G)  /*例6.3算法:将邻接矩阵g转换成邻接表G*/
{
    int i,j;
    ArcNode *p;
    G=(AdjList *)malloc(sizeof(AdjList));
    for (i=0;i<g.n;i++)                    /*给邻接表中所有头结点的指针域置初值*/
    {    
        G->adjlist[i].firstarc=NULL;
        strcpy(G->adjlist[i].data,g.vexs[i].data);
    }
    for (i=0;i<g.n;i++)                    /*检查邻接矩阵中每个元素*/
        for (j=g.n-1;j>=0;j--)
            if (g.edges[i][j]!=0)        /*邻接矩阵的当前元素不为0*/
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
                p->value=g.edges[i][j];p->adjvex=j;
                p->next=G->adjlist[i].firstarc;          /*将*p链到链表后*/
                G->adjlist[i].firstarc=p;
            }
    G->n=g.n;G->e=g.e;
}

int visited[MAXVEX];
void DFS(AdjList *g,int vi)        /*对邻接表G从顶点vi开始进行深度优先遍历*/
{
    ArcNode *p;
    printf("%d ",vi);            /*访问vi顶点*/
    visited[vi]=1;                /*置已访问标识*/
    p=g->adjlist[vi].firstarc;    /*找vi的第一个邻接点*/
    while (p!=NULL)                /*找vi的所有邻接点*/
    {
        if (visited[p->adjvex]==0) 
            DFS(g,p->adjvex);    /*从vi未访问过的邻接点出发深度优先搜索*/
        p=p->next;                /*找vi的下一个邻接点*/
    }
}

void DFS1(AdjList *G,int vi)        /*非递归深度优先遍历算法*/
{
    ArcNode *p;
    ArcNode *St[MAXVEX];
    int top=-1,v;
    printf("%d ",vi);                    /*访问vi顶点*/
    visited[vi]=1;                        /*置已访问标识*/
    top++;                                /*将初始顶点vi的firstarc指针进栈*/
    St[top]=G->adjlist[vi].firstarc;
    while (top>-1)                        /*栈不空循环*/
    {
        p=St[top];top--;                /*出栈一个顶点为当前顶点*/
        while (p!=NULL)                    /*循环搜索其相邻顶点*/
        {
            v=p->adjvex;                /*取相邻顶点的编号*/
            if (visited[v]==0)            /*若该顶点未访问过*/
            {                            
                printf("%d ",v);        /*访问v顶点*/
                visited[v]=1;            /*置访问标识*/
                top++;                    /*将该顶点的第1个相邻顶点进栈*/
                St[top]=G->adjlist[v].firstarc;
                break;                    /*退出当前顶点的搜索*/
            }        
            p=p->next;                    /*找下一个相邻顶点*/
        }
    }
}

void main()
{
    int i,j;
    AdjMatix g;
    AdjList *G;
    int a[5][5]={ {0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0} };
    char *vname[MAXVEX]={"a","b","c","d","e"};
    g.n=5;g.e=12;    /*建立图6.1(a)的无向图,每1条无向边算为2条有向边*/
    for (i=0;i<g.n;i++)
        strcpy(g.vexs[i].data,vname[i]);
    for (i=0;i<g.n;i++)
        for (j=0;j<g.n;j++)
            g.edges[i][j]=a[i][j];
    MatToList(g,G);        /*生成邻接表*/
    DispAdjList(G);        /*输出邻接表*/
    for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
    printf("从顶点0的深度优先遍历序列:\n");
    printf("  递归算法:");DFS(G,0);printf("\n");
    for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
    printf("  非递归算法:");DFS1(G,0);printf("\n");
}

8.最小生成树

8.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#define MAXVEX 100
#define INF 32767       /*INF表示∞*/

void Prim(int cost[][MAXVEX],int n,int v)
/*输出最小生成树的每条边*/
{
    int lowcost[MAXVEX],min;
    int closest[MAXVEX],i,j,k;
    for (i=0;i<n;i++)              /*给lowcost[]和closest[]置初值*/
    {    
        lowcost[i]=cost[v][i];
            closest[i]=v;
    }
    for (i=1;i<n;i++)              /*找出n-1个顶点*/
    {   
        min=INF;
        for (j=0;j<n;j++)       /*在(V-U)中找出离U最近的顶点k*/
            if (lowcost[j]!=0 && lowcost[j]<min) 
            {    
                min=lowcost[j];
                k=j;  
            }
        printf("  边(%d,%d)权为:%d\n",closest[k],k,min);
        lowcost[k]=0;             /*标记k已经加入U*/
        for (j=0;j<n;j++)       /*修改数组lowcost和closest*/
            if (cost[k][j]!=0 && cost[k][j]<lowcost[j]) 
            {    
                lowcost[j]=cost[k][j];
                closest[j]=k; 
            }
    }
}

void main()
{
    int n=7;
    int cost[7][MAXVEX]={
        {0,50,60,INF,INF,INF,INF},
        {50,0,INF,65,40,INF,INF},
        {60,INF,0,52,INF,INF,45},
        {INF,65,52,0,50,30,42},
        {INF,40,INF,50,0,70,INF},
        {INF,INF,INF,30,70,0,INF},
        {INF,INF,45,42,INF,INF,0}};
    printf("最小生成树:\n");Prim(cost,n,0);
}

8.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
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#define MAXVEX 100

typedef struct 
{    
    int u;     /*边的起始顶点*/
    int v;     /*边的终止顶点*/
    int w;     /*边的权值*/
} Edge;

void Kruskal(Edge E[],int n,int e)
{
    int i,j,m1,m2,sn1,sn2,k;
    int vset[MAXVEX];
    for (i=0;i<n;i++) vset[i]=i;    /*初始化辅助数组*/
    k=1;                             /*k表示构造最小生成树的第几条边,初值为1*/
    j=0;                             /*E中边的下标,初值为0*/
    while (k<n)                       /*生成的边数小于n时循环*/
    {
        m1=E[j].u;m2=E[j].v;        /*取一条边的头尾顶点*/
        sn1=vset[m1];sn2=vset[m2];     /*分别得到两个顶点所属的集合编号*/
        if (sn1!=sn2)                   /*两顶点属不同的集合,该边是最小生成树的边*/
        {
            printf("  边(%d,%d)权为:%d\n",m1,m2,E[j].w);
            k++;                    /*生成边数增1*/
            for (i=0;i<n;i++)          /*两个集合统一编号*/
                if (vset[i]==sn2)      /*集合编号为sn2的改为sn1*/
                    vset[i]=sn1;
        }
        j++;                           /*扫描下一条边*/
    }
}

void main()
{
    int n=7,e=10;
    Edge E[]={
        {3,5,30},{1,4,40},{3,6,42},
        {2,6,45},{0,1,50},{3,4,50},
        {2,3,52},{0,2,60},{1,3,65},
        {4,5,70}};
    printf("最小生成树:\n");Kruskal(E,n,e);
}

9.最短路径

9.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#define MAXVEX 100
#define INF 32767

void Dijkstra(int cost[][MAXVEX],int n,int v)
{
    int dist[MAXVEX],path[MAXVEX];
    int s[MAXVEX];
    int mindis,i,j,u,pre;
    for (i=0;i<n;i++) 
    {    
        dist[i]=cost[v][i];           /*距离初始化*/
        s[i]=0;                        /*s[]置空*/
        if (cost[v][i]<INF)            /*路径初始化*/
            path[i]=v;
        else
            path[i]=-1;
    }
    s[v]=1;path[v]=0;                /*源点编号v放入s中*/
    for (i=0;i<n;i++)                 /*循环直到所有顶点的最短路径都求出*/
    {    
        mindis=INF;
        u=-1;
        for (j=0;j<n;j++)             /*选取不在s中且具有最小距离的顶点u*/
            if (s[j]==0 && dist[j]<mindis) 
            {     
                u=j;
                mindis=dist[j];    
            }
        if (u!=-1)                        /*找到最小距离的顶点u*/
        {    s[u]=1;                     /*顶点u加入s中*/
            for (j=0;j<n;j++)              /*修改不在s中的顶点的距离*/
                if (s[j]==0) 
                    if (cost[u][j]<INF && dist[u]+cost[u][j]<dist[j]) 
                    {    
                        dist[j]=dist[u]+cost[u][j];
                        path[j]=u;
                    } 
        }
    }
    printf("\n Dijkstra算法求解如下:\n"); 
    for (i=0;i<n;i++)                /*输出最短路径长度,路径逆序输出*/
    {
        if (i!=v)
        {    
            printf("  %d->%d:",v,i);
            if (s[i]==1)  
            {    
                printf("路径长度为%2d ",dist[i]);
                pre=i;
                printf("路径逆序为");
                while (pre!=v)        /*一直求解到初始顶点*/
                {    
                    printf("%d,",pre);
                    pre=path[pre];
                }
                printf("%d\n",pre);
            }
            else
                printf("不存在路径\n");
        }
    }
}

void main()
{
    int cost[6][MAXVEX]={        /*图6.9的代价矩阵*/
        {0,50,10,INF,INF,INF},
        {INF,0,15,50,10,INF},
        {20,INF,0,15,INF,INF},
        {INF,20,INF,0,35,INF},
        {INF,INF,INF,30,0,INF},
        {INF,INF,INF,3,INF,0}};
    Dijkstra(cost,6,1);
    printf("\n");
}

9.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#define MAXVEX 100
#define INF 32767

void Floyed(int cost[][MAXVEX],int n)
{
    int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
    int i,j,k,pre;
    for (i=0;i<n;i++)        /*置初值*/
        for (j=0;j<n;j++) 
        {    
            A[i][j]=cost[i][j];
            path[i][j]=-1;
        }
    for (k=0;k<n;k++)
    {    
        for (i=0;i<n;i++)
            for (j=0;j<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;
                }
    }
    printf("\n Floyed算法求解如下:\n"); 
    for (i=0;i<n;i++)        /*输出最短路径*/
        for (j=0;j<n;j++) 
            if (i!=j)
            {    
                printf("   %d->%d:",i,j);
                if (A[i][j]==INF)
                {    
                    if (i!=j) 
                        printf("不存在路径\n");
                }
                else 
                {    
                    printf("路径长度为:%3d ",A[i][j]);
                    printf("路径为%d ",i);
                    pre=path[i][j];
                    while (pre!=-1)
                    {    
                        printf("%d ",pre);
                        pre=path[pre][j];
                    }
                    printf("%d\n",j);
                }
            }
}

void main()
{
    int cost[6][MAXVEX]={        /*图6.9的代价矩阵*/
        {0,50,10,INF,INF,INF},
        {INF,0,15,50,10,INF},
        {20,INF,0,15,INF,INF},
        {INF,20,INF,0,35,INF},
        {INF,INF,INF,30,0,INF},
        {INF,INF,INF,3,INF,0}};
    Floyed(cost,6);
    printf("\n");
}

10.拓扑排序算法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXVEX 100

typedef char VertexType[3];        /*定义VertexType为char数组类型*/

typedef struct vertex
{
    int adjvex;
    VertexType data;
} VType;

typedef struct graph
{    
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VType vexs[MAXVEX];            /*顶点集合*/
    int edges[MAXVEX][MAXVEX];    /*边的集合*/
} AdjMatix;                        /*图的邻接矩阵类型*/

typedef struct edgenode
{    
    int adjvex;                  /*邻接点序号*/
    int value;                  /*边的权值*/
    struct edgenode *next;        /*下一条边的顶点*/
} ArcNode;                        /*每个顶点建立的单链表中结点的类型*/

typedef struct vexnode
{
    VertexType data;               /*结点信息*/
    int count;                     /*存放顶点入度,新增用于拓扑排序*/
    ArcNode *firstarc;             /*指向第一条边结点*/
} VHeadNode;                    /*单链表的头结点类型*/

typedef struct 
{
    int n,e;                    /*n为实际顶点数,e为实际边数*/
    VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
} AdjList;                         /*图的邻接表类型*/

void DispAdjList(AdjList *G)    /*显示邻接表(含顶点入度)*/
{
    int i;
    ArcNode *p;
    printf("图的邻接表表示如下:\n");
    for (i=0;i<G->n;i++)
    {    
        printf("  [%d,%3s:]=>",i,G->adjlist[i].data,G->adjlist[i].count);
        p=G->adjlist[i].firstarc;
        while (p!=NULL)
        {    
            printf("(%d,%d)->",p->adjvex,p->value);
            p=p->next;
        }
        printf("∧\n");
    }
}

void MatToList(AdjMatix g,AdjList *&G)  /*例6.3算法:将邻接矩阵g转换成邻接表G*/
{
    int i,j;
    ArcNode *p;
    G=(AdjList *)malloc(sizeof(AdjList));
    for (i=0;i<g.n;i++)                    /*给邻接表中所有头结点的指针域置初值*/
    {    
        G->adjlist[i].firstarc=NULL;
        strcpy(G->adjlist[i].data,g.vexs[i].data);
    }
    for (i=0;i<g.n;i++)                    /*检查邻接矩阵中每个元素*/
        for (j=g.n-1;j>=0;j--)
            if (g.edges[i][j]!=0)        /*邻接矩阵的当前元素不为0*/
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
                p->value=g.edges[i][j];p->adjvex=j;
                p->next=G->adjlist[i].firstarc;          /*将*p链到链表后*/
                G->adjlist[i].firstarc=p;
            }
    G->n=g.n;G->e=g.e;
}

void TopSort(AdjList *G)
{
    int i,j;
    int St[MAXV],top=-1;              /*栈St的指针为top*/
    ArcNode *p;
    for (i=0;i<n;i++)
        if (adj[i].count==0)           /*入度为0的顶点入栈*/
        {
            top++; 
            St[top]=i;  
        }
        while (top>-1)                 /*栈不为空时循环*/
        {
            i=St[top];top--;          /*出栈*/
            printf("%d ",i);          /*输出顶点*/
            p=adj[i].firstarc;         /*找第一个相邻顶点*/
            while (p!=NULL) 
            {
                j=p->adjvex;
                adj[j].count--; 
                if (adj[j].count==0)/*入度为0的相邻顶点入栈*/
                {
                    top++;
                    St[top]=j;
                }
                p=p->nextarc;        /*找下一个相邻顶点*/
            }
        }
}

void main()
{
    int i,j;
    AdjMatix g;
    AdjList *G;
    int a[6][6]={ {0,1,0,10},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0} };
    char *vname[MAXVEX]={"a","b","c","d","e"};
    g.n=5;g.e=12;    /*建立图6.1(a)的无向图,每1条无向边算为2条有向边*/
    for (i=0;i<g.n;i++)
        strcpy(g.vexs[i].data,vname[i]);
    for (i=0;i<g.n;i++)
        for (j=0;j<g.n;j++)
            g.edges[i][j]=a[i][j];
    MatToList(g,G);        /*生成邻接表*/
    DispAdjList(G);        /*输出邻接表*/
    for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
    printf("从顶点0的深度优先遍历序列:\n");
    printf("  递归算法:");DFS(G,0);printf("\n");
    for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
    printf("  非递归算法:");DFS1(G,0);printf("\n");
}

查找

1.查找的基本概念

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。

1.1.查找的定义

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

1.2.查找算法分类

  1. 静态查找和动态查找

注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

  1. 无序查找和有序查找

    • 无序查找：被查找数列有序无序均可。
    • 有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

  • Pi：查找表中第i个数据元素的概率。
  • Ci：找到第i个数据元素时已经比较过的次数。

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
34
35
36
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;

typedef char ElemType[10];

typedef struct
{    
    KeyType key;       /*存放关键字,KeyType为关键字类型*/
    ElemType data;    /*其他数据, ElemType为其他数据的类型*/
} LineList;

int SeqSearch(LineList R[],int n,KeyType k)
{
    int i=0;
    while (i<n && R[i].key!=k) i++;
    if (i>=n) 
        return(-1);
    else
        return(i);
}

void main()
{
    KeyType a[]={3,9,1,5,8,10,6,7,2,4},k=6;
    LineList R[MaxSize];
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    i=SeqSearch(R,n,k);
    if (i>=0)
        printf("R[%d].key=%d\n",i,k);
    else
        printf("%d不在a中\n",k);
}

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
47
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;

typedef char ElemType[10];

typedef struct
{    
    KeyType key;       /*存放关键字,KeyType为关键字类型*/
    ElemType data;    /*其他数据, ElemType为其他数据的类型*/
} LineList;

int BinSearch(LineList R[],int n,KeyType k)
{
    int i,low=0,high=n-1,mid;
    int find=0;                /*find=0表示未找到;find=1表示已找到*/
       while (low<=high && !find)
     {    mid=(low+high)/2;   /*整除取中间值*/
        if (k<R[mid].key) 
            high=mid-1;
        else if (k>R[mid].key) 
            low=mid+1;
           else 
        {    i=mid;
            find=1;
        }
}
     if (find==0) 
        return(-1);
else
        return(i);
}

void main()
{
    KeyType a[]={2,4,7,9,10,14,18,26,32,40},k=7;
    LineList R[MaxSize];
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    i=BinSearch(R,n,k);
    if (i>=0)
        printf("R[%d].key=%d\n",i,k);
    else
        printf("%d不在a中\n",k);
}

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#define MaxSize 100
#define MaxBlk 20

typedef int KeyType;

typedef char ElemType[10];

typedef struct
{    
    KeyType key;       /*存放关键字,KeyType为关键字类型*/
    ElemType data;    /*其他数据, ElemType为其他数据的类型*/
} LineList;

typedef struct
{    
    KeyType key;
    int low,high;
} IDXType;            /*索引表的类型*/

int BlkSearch(LineList R[],IDXType idx[],int m,KeyType k)
{
    int low=0,high=m-1,mid,i,j,find=0;
    while (low<=high && !find)    /*二分查找索引表*/
    {
        mid=(low+high)/2;
        if (k<idx[mid].key) 
            high=mid-1;
        else if (k>idx[mid].key) 
            low=mid+1;
        else 
        {
            high=mid-1;
            find=1;
        }
    }
    if (low<m)                     /*k小于索引表内最大值*/
    {
        i=idx[low].low;            /*在索引表中定块起始地址*/
        j=idx[low].high;        /*在索引表中定块终止地址*/
       }
    while (i<j && R[i].key!=k) /*在指定的块内采用顺序方法进行查找*/
        i++;
     if (i>=j)
         return(-1);
    else
        return(i);
}

void main()
{
    KeyType a[]={9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82},k=48;
    LineList R[MaxSize];
    IDXType I[MaxBlk];
    int n=16,m=4,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    I[0].key=22;I[0].low=0;I[0].high=3;
    I[1].key=44;I[1].low=4;I[1].high=7;
    I[2].key=60;I[2].low=8;I[2].high=11;
    I[3].key=82;I[3].low=12;I[3].high=15;
    i=BlkSearch(R,I,m,k);
    if (i>=0)
        printf("R[%d].key=%d\n",i,k);
    else
        printf("%d不在a中\n",k);
}

5.二叉排序树查找

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <malloc.h>

typedef int KeyType;

typedef char ElemType[10];

typedef struct tnode
{    
    KeyType key;
    ElemType data;
    struct tnode *lchild,*rchild;
} BSTNode;

BSTNode *BSTSearch(BSTNode *bt,KeyType k)
{
    BSTNode *p=bt;
    while (p!=NULL && p->key!=k)
    {
        if (k<p->key)
            p=p->lchild;  /*沿左子树查找*/
        else
            p=p->rchild;  /*沿右子树查找*/
    }
    return(p);
}

int BSTInsert(BSTNode *&bt,KeyType k)
{
    BSTNode *f,*p=bt;
    while (p!=NULL)
    {
        if (p->key==k)
            return(0);
        f=p;                        /*f指向*p结点的双亲结点*/
        if (p->key>k)
            p=p->lchild;            /*在左子树中查找*/
        else
            p=p->rchild;            /*在右子树中查找*/
    }
    p=(BSTNode *)malloc(sizeof(BSTNode));    /*建立新结点*/
    p->key=k;
    p->lchild=p->rchild=NULL;
    if (bt==NULL)                    /*原树为空时,*p作为根结点插入*/
        bt=p;
    else if (k<f->key)
        f->lchild=p;                /*插入*p作为*f的左孩子*/
    else
        f->rchild=p;                /*插入*p作为*f的右孩子*/
    return(1);
}

void CreateBST(BSTNode *&bt,KeyType str[],int n)
{
    bt=NULL;                       /*初始时bt为空树*/
    int i=0;
    while (i<n) 
    {      
        BSTInsert(bt,str[i]); /*将关键字str[i]插入二叉排序树bt中*/
        i++;
    }
}

void DispBST(BSTNode *bt)
{
    if (bt!=NULL)
    {    printf("%d",bt->key);
        if (bt->lchild!=NULL || bt->rchild!=NULL)
        {    printf("(");
            DispBST(bt->lchild);                /*递归处理左子树*/
            if (bt->rchild!=NULL) printf(",");
            DispBST(bt->rchild);                /*递归处理右子树*/
            printf(")");
        }
    }
}

int BSTDelete(BSTNode *&bt,KeyType k)
{
    BSTNode *p=bt,*f,*r,*f1;
    f=NULL;                        /*p指向待比较的结点,f指向*p的双亲结点*/
    while (p!=NULL && p->key!=k)/*查找值域为x的结点*/
    {    f=p;
            if (p->key>k) 
            p=p->lchild;        /*在左子树中查找*/
            else
            p=p->rchild;        /*在右子树中查找*/
    }
    if (p==NULL)                /*未找到key域为k的结点*/
        return(0);
    else if (p->lchild==NULL)  /**p为被删结点,若它无左子树*/
    {
        if (f==NULL)            /**p是根结点,则用右孩子替换它*/
            bt=p->rchild;
        else if (f->lchild==p)    /**p是双亲结点的左孩子,则用其右孩子替换它*/
        {    f->lchild=p->rchild;
            free(p);
        }
        else if(f->rchild==p)    /**p是双亲结点的右孩子,则用其右孩子替换它*/
        {    f->rchild=p->rchild;
            free(p);
        }
    }
    else if (p->rchild==NULL)    /**p为被删结点,若它无右子树*/
    {
        if (f==NULL)            /**p是根结点,则用左孩子替换它*/
            bt=p->lchild;
        if (f->lchild==p)        /**p是双亲结点的左孩子,则用其左孩子替换它*/
        {    f->lchild=p->lchild;
            free(p);
        }
        else if(f->rchild==p)    /**p是双亲结点的右孩子,则用其左孩子替换它*/
        {    f->rchild=p->lchild;
            free(p);
        }
    }
    else                        /**p为被删结点,若它有左子树和右子树*/
    {
        f1=p;r=p->lchild;        /*查找*p的左子树中的最右下结点*r*/
        while (r->rchild!=NULL)    /**r一定是无右子树的结点,*f1作为r的双亲*/
        {    f1=r;
            r=r->rchild;
        }
        if (f1->lchild==r)        /**r是*f1的左孩子,删除*r*/
            f1->lchild=r->rchild;
        else if (f1->rchild==r)    /**r是*f1的右孩子,删除*r*/
            f1->rchild=r->lchild;
        r->lchild=p->lchild;    /*以下语句是用*r替代*p*/
        r->rchild=p->rchild;    
        if (f==NULL)            /**f为根结点*/
            bt=r;                /*被删结点是根结点*/
        else if (f->lchild==p)    /**p是*f的左孩子*/
            f->lchild=r;
        else                    /**p是*f的右孩子*/
            f->rchild=r;
        free(p);
    }
    return(1);
}

void main()
{
    BSTNode *bt=NULL,*p;
    KeyType a[]={10,6,12,8,3,20,9,25,15},k;
    int n=9;
    CreateBST(bt,a,n);
    printf("BST:");DispBST(bt);printf("\n");
    k=9;
    printf("查找关键字为%d的结点\n",k);
    p=BSTSearch(bt,k);
    if (p!=NULL)
        printf("存在关键字为%d结点\n",k);
    else
        printf("不存在关键字为%d结点\n",k);
    k=7;
    printf("插入关键字为%d的结点\n",k);
    BSTInsert(bt,k);
    printf("BST:");DispBST(bt);printf("\n");
    k=10;
    printf("删除关键字为%d的结点\n",k);
    BSTDelete(bt,k);
    printf("BST:");DispBST(bt);printf("\n");
}

6.哈希表查找

6.1.By 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#define MaxSize 100        /*哈希表最大长度*/

typedef int KeyType;

typedef struct
{
    KeyType key;    /*关键字值*/
    int si;            /*探查次数*/
} HashTable;

void CreateHT(HashTable ht[],KeyType a[],int n,int m,int p)    /*构造哈希表*/
{
    int i,d,cnt;
    for (i=0;i<m;i++)  /*置初值*/
    {
        ht[i].key=0;
        ht[i].si=0;
    }
    for (i=0;i<n;i++)
    {
        cnt=1;            /*累计探查次数*/
        d=a[i]%p;
        if (ht[d].key==0)
        {
            ht[d].key=a[i];
            ht[d].si=cnt;
        }
        else
        {
            do            /*处理冲突*/
            {
                d=(d+1)%m;
                cnt++;
            } while (ht[d].key!=0);
            ht[d].key=a[i];
            ht[d].si=cnt;
        }
    }
}

void DispHT(HashTable ht[],int n,int m)    /*输出哈希表*/
{
    int i;
    double avg;
    printf("i:  ");
    for (i=0;i<m;i++) 
        printf("%-3d",i);
    printf("\n");
    printf("key:");
    for (i=0;i<m;i++) 
        printf("%-3d",ht[i].key);
    printf("\n");
    printf("si: ");
    for (i=0;i<m;i++) 
        printf("%-3d",ht[i].si);
    printf("\n");
    avg=0;
    for (i=0;i<m;i++) 
        avg+=ht[i].si;
    avg=avg/n;
    printf("平均查找长度:ASL(%d)=%g\n",n,avg);
}

void main()
{
    HashTable ht[MaxSize];
    KeyType a[]={19,1,23,14,55,20,84,27,68,11,10,77};
    int n=12,m=19,p=13;
    CreateHT(ht,a,n,m,p);
    DispHT(ht,n,m);
}

6.2.By Golang

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Package hashtable creates a ValueHashtable data structure for the Item type
package hashtable

import (
    "fmt"
    "sync"
)

// Key the key of the dictionary
type Key interface{}

// Value the content of the dictionary
type Value interface{}

// ValueHashtable the set of Items
type ValueHashtable struct {
    items map[int]Value
    lock  sync.RWMutex
}

// the hash() private function uses the famous Horner's method
// to generate a hash of a string with O(n) complexity
func hash(k Key) int {
    key := fmt.Sprintf("%s", k)
    h := 0
    for i := 0; i < len(key); i++ {
        h = 31*h + int(key[i])
    }
    return h
}

// Put item with value v and key k into the hashtable
func (ht *ValueHashtable) Put(k Key, v Value) {
    ht.lock.Lock()
    defer ht.lock.Unlock()
    i := hash(k)
    if ht.items == nil {
        ht.items = make(map[int]Value)
    }
    ht.items[i] = v
}

// Remove item with key k from hashtable
func (ht *ValueHashtable) Remove(k Key) {
    ht.lock.Lock()
    defer ht.lock.Unlock()
    i := hash(k)
    delete(ht.items, i)
}

// Get item with key k from the hashtable
func (ht *ValueHashtable) Get(k Key) Value {
    ht.lock.RLock()
    defer ht.lock.RUnlock()
    i := hash(k)
    return ht.items[i]
}

// Size returns the number of the hashtable elements
func (ht *ValueHashtable) Size() int {
    ht.lock.RLock()
    defer ht.lock.RUnlock()
    return len(ht.items)
}

7.哈希查找

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100        /*哈希表最大长度*/

typedef int KeyType;

typedef struct node
{
    KeyType key;    /*关键字值*/
    int si;            /*探查次数*/    
    struct node *next;
} Node;        /*数据结点类型*/

typedef struct
{
    Node *link;
} HNode;    /*头结点类型*/

void CreateHT(HNode *ht[],KeyType a[],int n,int p)    /*构造哈希表*/
{
    int i,d,cnt;
    Node *s,*q;
    for (i=0;i<p;i++)    /*所有头结点的link域置空*/
    {
        ht[i]=(HNode *)malloc(sizeof(HNode));
        ht[i]->link=NULL;
    }
    for (i=0;i<n;i++)
    {
        cnt=1;
        s=(Node *)malloc(sizeof(Node));    /*构造一个数据结点*/
        s->key=a[i];s->next=NULL;
        d=a[i]%p;                        /*求其哈希地址*/
        if (ht[d]->link==NULL)            
        {
            ht[d]->link=s;
            s->si=cnt;
        }
        else
        {
            q=ht[d]->link;
            while (q->next!=NULL)
            {
                q=q->next;cnt++;
            }
            cnt++;
            s->si=cnt;q->next=s;
        }
    }
}

void DispHT(HNode *ht[],int n,int p)    /*输出哈希表*/
{
    int i,sum=0;
    Node *q;
    printf("哈希表:\n");
    for (i=0;i<p;i++)
    {
        q=ht[i]->link;
        printf("%d:link->",i);
        while (q!=NULL)
        {
            sum+=q->si;
            printf("[%d,%d]->",q->key,q->si);
            q=q->next;
        }
        printf("∧\n");
    }
    printf("\n平均查找长度:ASL=%g\n",1.0*sum/n);
}

void main()
{
    HNode *ht[MaxSize];
    KeyType a[]={87,25,310,8,27,132,68,95,187,123,70,63,47};
    int n=13,p=13;
    CreateHT(ht,a,n,p);
    DispHT(ht,n,p);
}

排序

1.排序的定义

对一序列对象根据某个关键字进行排序。

1.1.排序方法比较

排序方法 时间复杂度 空间 复杂度 稳定性 复杂性
最坏情况 平均情况 最好情况
直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
希尔排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 较复杂
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂

2.插入排序

2.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void InsertSort(LineList R[],int n)
{
    int i,j;
    LineList tmp;
    for (i=1;i<n;i++)
    {    
        tmp=R[i];
        j=i-1;
        while (j>=0 && tmp.key<R[j].key)/*元素后移,以便腾出一个位置插入tmp*/
        {    
            R[j+1]=R[j];
            j--;
        }
        R[j+1]=tmp;        /*在j+1位置处插入tmp*/
    }
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    InsertSort(R,n);
    printf("排序后:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}

2.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void ShellSort(LineList R[],int n)
{
    int i,j,gap;
    LineList tmp;
    gap=n/2;                    /*增量置初值*/
    while (gap>0)
    {    
        for (i=gap;i<n;i++)      /*对所有相隔gap位置的所有元素组进行排序*/
        {
            tmp=R[i];
            j=i-gap;
            while (j>=0 && tmp.key<R[j].key)/*对相隔gap位置的元素组进行排序*/
            {
                R[j+gap]=R[j];
                j=j-gap;                    /*移到本组中的前一个元素*/
            }
            R[j+gap]=tmp;
            j=j-gap;
        }
        gap=gap/2;    /*减小增量*/
    }
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    ShellSort(R,n);
    printf("排序后:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}

3.选择排序

3.1.直接选择排序

3.1.1.基本思想
  • 每次从未排序的序列中选择最小的数放置在该未排序序列的第一个
  • 不断循环，直到排序完成
3.1.2.步骤
  • 第一层循环：i=0; i < len(list)-1; i++
  • 第二层循环：j := i + 1; j < len(list); j++
  • 寻找未排序序列中最小的数: if list[j] < list[minIndex] { minIndex = j }
  • 将最小的数与放置到当前未排序序列的第一个: list[i], list[minIndex] = list[minIndex], list[i]
3.1.3.By 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
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void SelectSort(LineList R[],int n)
{
    int i,j,k;
    LineList tmp;
    for (i=0;i<n-1;i++)
    {    
        k=i;
        for (j=i+1;j<n;j++)
            if (R[j].key<R[k].key) 
                k=j;        /*用k指出每趟在无序区段的最小元素*/
        tmp=R[i];            /*将R[k]与R[i]交换*/
        R[i]=R[k];
        R[k]=tmp;
    }
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    SelectSort(R,n);
    printf("排序后:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}
3.1.4.By Golang
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
package main

import (
    "fmt"
)

// 选择排序
func selectSort(list []int) []int {
    var minIndex int
    for i := 0; i < len(list)-1; i++ {
        minIndex = i
        for j := i + 1; j < len(list); j++ {
            if list[j] < list[minIndex] { // 寻找未排序序列中最小的数
                minIndex = j
            }
        }
        list[i], list[minIndex] = list[minIndex], list[i] // 将当前数与最小的数交换位置
        fmt.Println("第", i+1, "趟：", list)                 // 打印每趟的序列
    }
    return list
}

func main() {
    list := []int{75, 87, 68, 92, 88, 61, 77, 96, 80, 72}
    fmt.Println("初始序列:", list)
    result := selectSort(list)
    fmt.Println("最终结果:", result)
}
3.1.5.排序过程
1
2
3
4
5
6
7
8
9
10
11
12
13
初始序列: [75 87 68 92 88 61 77 96 80 72]

第 1 趟： [61 87 68 92 88 75 77 96 80 72]
第 2 趟： [61 68 87 92 88 75 77 96 80 72]
第 3 趟： [61 68 72 92 88 75 77 96 80 87]
第 4 趟： [61 68 72 75 88 92 77 96 80 87]
第 5 趟： [61 68 72 75 77 92 88 96 80 87]
第 6 趟： [61 68 72 75 77 80 88 96 92 87]
第 7 趟： [61 68 72 75 77 80 87 96 92 88]
第 8 趟： [61 68 72 75 77 80 87 88 92 96]
第 9 趟： [61 68 72 75 77 80 87 88 92 96]

最终结果: [61 68 72 75 77 80 87 88 92 96]

3.2.堆排序

3.2.1.By 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void Sift(LineList R[],int low,int high)
{
    int i=low,j=2*i;             /*R[j]是R[i]的左孩子*/
    LineList tmp=R[i];
    while (j<=high) 
    {    if (j<high && R[j].key<R[j+1].key)     /*若右孩子较大,把j指向右孩子*/
            j++;                    /*j变为2i+1,指向右孩子结点*/
        if (tmp.key<R[j].key) 
        {    R[i]=R[j];           /*将R[j]调整到双亲结点位置上*/
            i=j;                  /*修改i和j值,以便继续向下筛选*/
            j=2*i;
        }
        else break;              /*筛选结束*/
    }
    R[i]=tmp;                     /*被筛选结点的值放入最终位置*/
}

void HeapSort(LineList R[],int n)
{
    int i;
    LineList tmp;
    for (i=n/2;i>=1;i--)      /*循环建立初始堆*/
        Sift(R,i,n); 
    for (i=n;i>=2;i--)       /*进行n-1次循环,完成堆排序*/
    {      tmp=R[1];            /*将第一个元素同当前区间内R[1]对换*/
        R[1]=R[i];
        R[i]=tmp;
        Sift(R,1,i-1);         /*筛选R[1]结点,得到i-1个结点的堆*/
    }
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={0,75,87,68,92,88,61,77,96,80,72};    /*有效数据从a[1]开始*/
    int n=10,i;
    for (i=0;i<=n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=1;i<=n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    HeapSort(R,n);
    printf("排序后:");
    for (i=1;i<=n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}

4.交换排序

4.1.冒泡排序

4.1.1.基本思想
  • 比较相邻两个元素，如果第一个比第二个大，就交换两者的顺序
  • 对每一对相邻的元素做同样的操作，从最后一对到第一对，每一趟结束最小的元素会排在第一个（即冒泡）
  • 从未排序的元素开始循环做以上操作，直到排序完成
4.1.2.步骤
  1. 第一层循环: i=0; i<(len-1); i++
  2. 第二层循环: j=len-1; j>i; j–
  3. 比较相邻两个元素: list[j-1]和list[j]
  4. 如果前者比后者大，就交换顺序: list[j-1], list[j] = list[j], list[j-1]
4.1.3.By 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void BubbleSort(LineList R[],int n)
{
    int i,j,exchange;
    LineList tmp;
    for (i=0;i<n-1;i++) 
    {    exchange=0;
        for (j=n-1;j>i;j--)    /*比较,找出最小关键字的记录*/
            if (R[j].key<R[j-1].key)       
            {    tmp=R[j];  /*R[j]与R[j-1]进行交换,将最小关键字记录前移*/
                R[j]=R[j-1];
                R[j-1]=tmp;
                exchange=1;
            }
        if (exchange==0)     /*本趟未发生交换时结束算法*/
            return;
    }
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    BubbleSort(R,n);
    printf("排序后:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}
4.1.4.By Golang
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
package main

import (
    "fmt"
)

// 冒泡排序，从小到大
func bubbleSort(list []int) []int {
    for i := 0; i < len(list)-1; i++ {  
        for j := len(list) - 1; j > i; j-- {  // 从最后两个元素开始比较
            if list[j-1] > list[j] { // 相邻元素对比
                list[j-1], list[j] = list[j], list[j-1] // 如果后者比前者小，就交互位置
            }
        }
        fmt.Println("第", i+1, "趟：", list)
    }
    return list
}

func main() {
    list := []int{75, 87, 68, 92, 88, 61, 77, 96, 80, 72}
    fmt.Println("初始序列:", list)
    result := bubbleSort(list)
    fmt.Println("最终结果:", result)
}
4.1.5.排序过程
1
2
3
4
5
6
7
8
9
10
11
12
13
初始序列: [75 87 68 92 88 61 77 96 80 72]

第 1 趟： [61 75 87 68 92 88 72 77 96 80]
第 2 趟： [61 68 75 87 72 92 88 77 80 96]
第 3 趟： [61 68 72 75 87 77 92 88 80 96]
第 4 趟： [61 68 72 75 77 87 80 92 88 96]
第 5 趟： [61 68 72 75 77 80 87 88 92 96]
第 6 趟： [61 68 72 75 77 80 87 88 92 96]
第 7 趟： [61 68 72 75 77 80 87 88 92 96]
第 8 趟： [61 68 72 75 77 80 87 88 92 96]
第 9 趟： [61 68 72 75 77 80 87 88 92 96]

最终结果: [61 68 72 75 77 80 87 88 92 96]

4.2.快速排序

4.2.1.基本思想
  • 分治：在未排序序列中选择一个基准数（一般为第一个），将小于基准数的放在其左边，大于基准数的放在其右边，即分成两个区间
  • 递归：将上述两个区间，每个区间内执行上述操作，以此类推，直到排序完成
4.2.2.步骤
  • 选择一个基准数，一般为第一个: pivot := list[left]
  • 将小于基准数的放在其左边
  • 将大于基准数的放在其右边
  • 对每个分区执行递归操作：quickSort(list, left, i-1)；quickSort(list, i+1, right)
4.2.3.By 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void QuickSort(LineList R[],int s,int t) /*对R[s]至R[t]的元素进行快速排序*/
{
    int i=s,j=t;
    LineList tmp;
    if (s<t)                 /*区间内至少存在一个元素的情况*/
    {    tmp=R[s];             /*用区间的第1个记录作为基准*/
        while (i!=j)          /*从区间两端交替向中间扫描,直至i=j为止*/
        {    while (j>i && R[j].key>tmp.key) 
                j--;          /*从右向左扫描,找第1个关键字小于tmp.key的R[j]*/ 
            R[i]=R[j];        /*找到这样的R[j],则R[i]和R[j]交换*/
            while (i<j && R[i].key<tmp.key) 
                i++;        /*从左向右扫描,找第1个关键字大于tmp.key的R[i]*/
            R[j]=R[i];        /*找到这样的R[i],则R[i]和R[j]交换*/
        }
        R[i]=tmp;
        QuickSort(R,s,i-1);    /*对左区间递归排序*/
        QuickSort(R,i+1,t);    /*对右区间递归排序*/
    }
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    QuickSort(R,0,n-1);
    printf("排序后:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}
4.2.4.By Golang
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
package main

import (
    "fmt"
)

func quickSort(list []int, left, right int) []int {
    if left < right {
        i, j := left, right
        pivot := list[left] // 以左边第一个数作为基准数，将第一个数暂存在pivot变量中

        // 分治
        for i < j {
            // 从右向左找出第一个小于基准数的，将list[j]赋值给list[i] 
            for j > i && list[j] > pivot {
                j--
            }
            list[i] = list[j]

            // 从左向右找出第一个大于基准数的，将list[i]赋值给list[j] 
            for i < j && list[i] < pivot {
                i++
            }
            list[j] = list[i]
        }
        list[i] = pivot
        fmt.Println(list) // 打印该趟的序列

        // 递归
        quickSort(list, left, i-1)
        quickSort(list, i+1, right)
    }
    return list
}

func main() {
    list := []int{75, 87, 68, 92, 88, 61, 77, 96, 80, 72}
    fmt.Println("初始序列:", list)
    result := quickSort(list, 0, len(list)-1)
    fmt.Println("最终结果:", result)
}
4.2.5.排序过程
1
2
3
4
5
6
7
8
9
10
11
初始序列: [75 87 68 92 88 61 77 96 80 72]

第 1 趟：[72 61 68 75 88 92 77 96 80 87]
第 2 趟：[68 61 72 75 88 92 77 96 80 87]
第 3 趟：[61 68 72 75 88 92 77 96 80 87]
第 4 趟：[61 68 72 75 87 80 77 88 96 92]
第 5 趟：[61 68 72 75 77 80 87 88 96 92]
第 6 趟：[61 68 72 75 77 80 87 88 96 92]
第 7 趟：[61 68 72 75 77 80 87 88 92 96]

最终结果: [61 68 72 75 77 80 87 88 92 96]

5.归并排序

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100

typedef int KeyType;        /*关键字类型*/

typedef char ElemType[10];    /*其他数据项类型*/

typedef struct 
{    
    KeyType key;               /*关键字域*/
    ElemType data;             /*其他数据域*/
} LineList;                    /*线性表元素类型*/

void Merge(LineList R[],int low,int mid,int high) 
{
    LineList *R1;
    int i=low,j=mid+1,k=0; /*k是R1的下标,i、j分别为第1、2段的下标*/
    R1=(LineList *)malloc((high-low+1)*sizeof(LineList));  /*动态分配空间*/
    while (i<=mid && j<=high)    /*在第1段和第2段均未扫描完时循环*/
        if (R[i].key<=R[j].key)  /*将第1段中的记录放入R1中*/
        {    R1[k]=R[i];
            i++;k++; 
        }
        else                           /*将第2段中的记录放入R1中*/
        {    R1[k]=R[j];
            j++;k++; 
        }
        while (i<=mid)               /*将第1段余下部分复制到R1*/
        {  
            R1[k]=R[i];
            i++;k++; 
        }
        while (j<=high)           /*将第2段余下部分复制到R1*/
        {    R1[k]=R[j];
            j++;k++;  
        }
        for (k=0,i=low;i<=high;k++,i++) /*将R1复制回R中*/
            R[i]=R1[k];
} 

void MergePass(LineList R[],int length,int n)
{
    int i;
    for (i=0;i+2*length-1<n;i=i+2*length)     /*归并length长的两相邻子表*/
        Merge(R,i,i+length-1,i+2*length-1);
    if (i+length-1<n)                    /*余下两个子表,后者长度小于length*/
        Merge(R,i,i+length-1,n-1);     /*归并这两个子表*/
}

void MergeSort(LineList R[],int n)    /*二路归并算法*/
{
    int length;
    for (length=1;length<n;length=2*length)
        MergePass(R,length,n);
}

void main()
{
    LineList R[MaxSize];
    KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    int n=10,i;
    for (i=0;i<n;i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
    MergeSort(R,n);
    printf("排序后:");
    for (i=0;i<n;i++)
        printf("%3d",R[i].key);
    printf("\n");
}

6.基数排序

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXE 20            /*线性表中最多元素个数*/
#define MAXR 10            /*基数的最大取值*/
#define MAXD 8            /*关键字位数的最大取值*/

typedef struct node
{    
    char data[MAXD];    /*记录的关键字定义的字符串*/
       struct node *next;
} RecType;

void RadixSort(RecType *&p,int r,int d) 
/*p为待排序序列链表指针,r为基数,d为关键字位数*/
{
    RecType *head[MAXR],*tail[MAXR],*t;/*定义各链队的首尾指针*/
    int i,j,k;
    for (i=d-1;i>=0;i--)                   /*从低位到高位做d趟排序*/
    {    for (j=0;j<r;j++)                 /*初始化各链队首、尾指针*/
            head[j]=tail[j]=NULL;
        while (p!=NULL)                  /*对于原链表中每个结点循环*/
        {    k=p->data[i]-'0';           /*找第k个链队*/
            if (head[k]==NULL)           /*进行分配,即采用尾插法建立单链表*/
            {    
                head[k]=p;
                tail[k]=p;
            }
              else
            {      
                tail[k]->next=p;
                tail[k]=p;
            }
            p=p->next;                     /*取下一个待排序的元素*/
        }
        p=NULL;
           for (j=0;j<r;j++)                /*对于每一个链队循环*/
            if (head[j]!=NULL)             /*进行收集*/
            {    if (p==NULL)
                {    p=head[j];
                    t=tail[j];
                }
                else
                {    t->next=head[j];
                    t=tail[j];
                }
            }
        t->next=NULL;                    /*最后一个结点的next域置NULL*/
    }
}

void main()
{
    RecType *h=NULL,*p,*t;
    char *A[]={"75","87","68","92","88","61","77","96","80","72"};
    int i,n=10;
    for (i=0;i<n;i++)        /*构造不带头结点的单链表h*/
    {    
        p=(RecType *)malloc(sizeof(RecType));
        strcpy(p->data,A[i]);
        if (h==NULL)
        {    
            h=p;
            t=h;
        }
        else
        {    
            t->next=p;
            t=p;
        }
    }
    t->next=NULL;
    printf("排序前:");
    for (i=0;i<n;i++)
        printf("%3s",A[i]);
    printf("\n");
    RadixSort(h,10,2);
    printf("排序后:");
    p=h;
    while (p!=NULL)
    {    
        printf("%3s",p->data);
        p=p->next;
    }
    printf("\n");
}