大话数据结构笔记

数据结构的详细笔记，对应课本

1 引言

1.1 基本概念和术语

数据：是描述客观事物的符号，是计算机中操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。 数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型（信息的载体；对客观事物符号化的表示；能够被计算机识别，存储和加工）

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录、结点或顶点。 例如，人。

数据项：一个数据元素可以由若干个数据项组成。例如人有眼、耳、鼻、嘴、手、脚这些数据项，也可以有姓名、年龄、性别等数据项，要视所做的系统来决定。 数据项是数据不可分割的最小单位

数据 > 数据元素 > 数据项

数据对象：是性质相同的数据元素的集合，是数据的子集。数据元素是数据的个体，数据对象是数据的子集

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。数据结构是带结构的数据元素的集合

1.2 数据结构的两个层次

1.2.1 逻辑结构

逻辑结构是指数据对象中数据元素之间的相互关系。与数据的存储无关，独立于计算机，具体分为以下四种

集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系

线性结构：线性结构中的数据元素之间是一对一的关系。例如：线性表、栈、队列、串

树形结构：树形结构中的数据元素之间存在一种一对多的层次关系

图形结构：图形结构的数据元素是多对多的关系

用示意图表示逻辑结构时应注意：

• 将每一个数据元素看做一个结点，用圆圈表示
• 元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示

1.2.2 物理结构

物理结构是指数据的逻辑结构在计算机中的存储形式，有时也称存储结构，是数据结构在计算机中的表示

顺序存储结构：是指把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。C语言用数组实现

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。C语言用指针实现

索引存储结构：在存储结点信息的同时，还建立附加的索引表

散列存储结构：根据结点的关键字直接计算出该结点的存储地址。散列表

两者关系：
物理结构是逻辑关系的映像和元素本身的映像；逻辑结构是数据结构的抽象，物理结构是数据结构的实现

1.3 抽象数据类型

1.3.1 数据类型

是指性质相同的值的集合及定义在此集合上的一些操作的总称。它是按照值的不同进行划分的

• 原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等
• 结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据构成的

1.3.2 抽象数据类型

是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部表示和实现无关，而链式存储关系并不能反映其逻辑关系，因此需要一个指针存放数据元素的地址，通过地址找到相关联数据元素的位置

抽象是指抽取出事物具有的普遍性的本质，其意义在于数据类型的数学抽象特性。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来

1.4 算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

1.4.1 算法的描述

• 自然语言：英语，中文
• 流程图：传统流程图、NS流程图
• 伪代码：类C语言
• 程序代码：…

1.4.2 算法的特性

• 算法具有零个或多个输入，至少一个或多个输出
• 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
• 确定性：算法的每一步骤都具有确定的含义，不会出现二义性
• 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成

1.4.3 算法设计的要求

• 正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
• 可读性：算法设计的另一目的是为了便于阅读、理解和交流
• 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名奇妙的结果
• 时间效率高，存储量低

1.4.4 算法效率的度量方法

（1）事后统计法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。缺陷多，一般不使用

（2）事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。一个程序的运行时间，依赖于算法的好坏和问题的输入规模

1.4.5 函数的渐近增长

关注主项的阶数

1.4.6 算法时间复杂度

1 定义

算法时间复杂度： 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数

2 推导大O阶步骤

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不是1，则去除这个项相乘的常数，结果就是大O阶

3 具体阶数

• 常数阶
  顺序结构，分支结构

• 线性阶
  循环结构

• 对数阶

  int count = 1;
  while (count <= n){
      count = count * 2;
  }

  时间复杂度为O($log_2n$))

• 平方阶
  时间复杂度为O($n^2$)

  for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
          a++;
      }
  }
  for(int i = 0; i < n; i++) {
      b++;
  }
  while(n) {
      n = n / 2;
  }

• nlogn阶
  2n+3nlog2(n)+19对应O(nlogn)

• 立方阶

• 指数阶

  $2^n$对应O($2^n$)

常用的时间复杂度所耗费的时间从小到大依次是：O(1) < O(logn) < O(n) < O(nlogn) < O($n^2$) < O($n^3$) < O($2^n$) < O(n!) < O($n^n$)

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。除非特别指定，我们提到的运行时间都是最坏时间复杂度。平均运行时间是所有情况中最有意义的，因为它是期望的运行时间

1.4.7 算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，包括指令空间、数据空间、动态申请的内存空间等，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数

算法要占据的时间包括：算法本身要占据的空间，输入/输出，指令，常数，变量等；算法要使用的辅助空间

（1）S(n) = n + $n^2$ ，则空间复杂度为O($n^2$)

int *a = new int[n];
int **b = new int*[n];
for(int i = 0; i < n; i++) {
    b[i] = new int[n];
}

（2）S(n) = O(1)

for(i = 0; i < n / 2; i++) {
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
}

（3）S(n) = O(n)

for(i = 0; i < n; i++) {
    b[i] = a[n - i - 1];
    for(i = 0; i < n; i++) {
        a[i] = b[i];
    }
}

2 线性表

2.1 线性表的定义

线性表：零个或多个元素的有限序列

2.2 线性表的抽象数据类型

线性表的数据对象集合为{$a_1$,$a_2$,……,$a_n$}，每个元素的类型均为DataType。其中，除第一个元素$a_1$外，每一个元素有且只有一个直接前趋元素，除了最后一个元素$a_n$外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系

InitList(*L);   //初始化操作，建立一个空的线性表L
ListEmpty(L);   //若线性表为空，返回true，否则返回false
ClearList(*L);   //将线性表清空
GetElem(L,i,*e);  //将线性表L中的第i个位置元素值返回给e
LocateElem(L,e);  //若线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功；否则，返回0表示失败
ListInsert(*L,i,e);  //在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e);  //删除线性表L中第i个位置元素，并用e返回其值
ListLength(L);    //返回线性表L的元素个数

求A = A并B，假设La表示集合A，Lb表示集合B，则实现代码如下：

void union(List* La,List Lb){
    int La_len,Lb_len,i;
    ElemType e;//声明与La和Lb相同的数据元素e
    La_len = ListLength(La);//求线性表的长度
    Lb_len = ListLength(Lb);
    for(i = 1; i <= Lb_len; i++ ){
        GetElem(Lb, i, e);//取Lb中第i个数据元素赋给e
        if(!LocateElem(La, e, equal))//La中不存在和e相同数据元素
            ListInsert(La, ++La_len, e);//插入
    }
}

对于复杂的个性化操作，就是把基本操作组合起来实现

2.3 线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。可以用一维数组来实现，一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间是固定的，一旦空间占满，就无法再新增数据，否则会导致数据溢出；而在动态分配时，存储数组的空间在程序执行过程中会动态调整大小，当空间占满时，可以另行开辟更大的存储空间来储存数据

顺序表最主要的特点是可以进行随机访问，即可以通过表头元素的地址和元素的编号（下标），在O(1)的时间复杂度内找到指定的元素。顺序表的不足之处是插入和删除操作需要移动大量的元素，从而保持逻辑上和物理上的连续性

函数	功能
insert(loc, value)	将value插入到顺序表中下标为loc的位置
expand()	扩大顺序表的容量
search(value)	寻找顺序表中值为value的元素
remove(index)	将顺序表下标为index的元素
print()	输出顺序表中所有元素

1. 插入操作实现方法：

   • 判断插入位置是否合法
   • 判断顺序表是否已满
   • 将目标位置及以后的元素后移一位
   • 将待插入的元素后移一位

2. 扩容操作实现方法：

   我们需要把原数组空间里的元素一一复制到新的空间内，因此扩容的时间复杂度为O(n)

   • 将原来的元素存储到临时存储空间
   • 扩大原来的存储空间
   • 将临时存储空间里的数据元素复制到新的存储空间里
   • 释放临时的存储空间

3. 查找操作实现方法：

   • 从下标为0的元素开始依次枚举顺序表中的所有元素
   • 发现和目标值相等的元素则返回它的下标
   • 枚举结束没有找到目标元素则返回 -1

4. 删除操作实现方法：

   • 判断传入参数是否合法，即下标是否在顺序表的范围内
   • 将目标下标之后所有的元素前移一位
   • 更新顺序表的长度

5. 遍历操作实现方法：

   • 从下标为0的元素开始遍历顺序表
   • 输出所有元素的值

顺序存储结构的三个属性：

• 存储空间的起始位置
• 线性表的最大存储容量：MAXSIZE
• 线性表的当前长度：length
• $logn$

注意区分数组长度和线性表长度，线性表长度应该小于等于数组的长度

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Status;
typedef char ElemType;
typedef struct {
    ElemType* elem;
    int length;
    int listsize;
}SqList;
Status InitList_Sq(SqList& L) {
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)
        exit(OVERFLOW);
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}
Status DestroyList_Sq(SqList& L) {
    free(L.elem);
    L.elem = NULL;
    L.length = 0;
    L.listsize = 0;
    return OK;
}
Status ClearList_Sq(SqList& L) {
    L.length = 0;
    return OK;
}
Status ListEmpty_Sq(SqList L) {
    if (L.length == 0)
        return TRUE;
    else return FALSE;
}
Status ListLength_Sq(SqList L) {
    return (L.length);
}
Status GetElem_Sq(SqList L, int i, ElemType& e) {
    if (i < 1 || i > L.length)
        return ERROR;
    e = L.elem[i - 1];
    return OK;
}
int LocateElem_Sq(SqList L, ElemType e) {
    int i = 0;
    while (i < L.length && L.elem[i] != e)
        ++i;
    if (i < L.length)
        return i + 1;
    else return 0;
}
Status ListInsert_Sq(SqList& L, int i, ElemType e) {
    ElemType* p, * q, * newbase;
    if (i < 1 || i > L.length + 1)
        return ERROR;
    if (L.length >= L.listsize) {
        newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase)
            exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    q = &(L.elem[i - 1]);
    for (p = &(L.elem[L.length - 1]); p >= q; --p)
        *(p + 1) = *p;
    *q = e;
    ++L.length;
    return OK;
}
Status ListDelete_Sq(SqList& L, int i, ElemType& e) {
    ElemType* p, * q;
    if (i < 1 || i>L.length + 1)
        return ERROR;
    p = &(L.elem[i - 1]); // p为被删除元素的位置
    e = *p; // 被删除元素的位置赋给e
    q = L.elem + L.length + 1; // 表尾元素的位置
    for (++p; p <= q; ++p)
        *(p - 1) = *p;
    --L.length;
    return OK;
}
void DispList_Sq(SqList& L) {
    for (int i = 0; i < L.length; i++)
        printf("%c ", L.elem[i]);
    printf("\n");
}

int main() {
    SqList L;
    ElemType e;
    printf("顺序表的基本运算如下：\n");
    printf("  （1）初始化顺序表L\n");
    InitList_Sq(L);
    printf("  （2）依次插入a, b, c, d, e元素\n");
    ListInsert_Sq(L, 1, 'a');
    ListInsert_Sq(L, 2, 'b');
    ListInsert_Sq(L, 3, 'c');
    ListInsert_Sq(L, 4, 'd');
    ListInsert_Sq(L, 5, 'e');
    printf("  （3）输出顺序表L：");
    DispList_Sq(L);
    printf("  （4）顺序表L长度：%d\n", ListLength_Sq(L));
    printf("  （5）顺序表L为%s\n", ListEmpty_Sq(L) ? "空" : "非空");
    GetElem_Sq(L, 3, e);
    printf("  （6）顺序表L的第3个元素：%c\n", e);
    printf("  （7）元素a的位置：%d\n", LocateElem_Sq(L, 'a'));
    printf("  （8）在第4个元素位置上插入f元素\n");
    ListInsert_Sq(L, 4, 'f');
    printf("  （9）输出顺序表L：");
    DispList_Sq(L);
    printf("  （10）删除L的第3个元素\n");
    ListDelete_Sq(L, 3, e);
    printf("  （11）输出顺序表L：");
    DispList_Sq(L);
    printf("  （12）释放顺序表L\n");
    DestroyList_Sq(L);
    return 0;
}

c++的动态内存分配

int *p1, *p2;
p1 = new int;
p2 = new int(10);
delete p1, p2;

2.4 线性表的链式存储结构

为了表示每个数据元素a1与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素a1来说，除了存储其本身的信息以外，还需存储一个指示其直接后继的 信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点。

n个结点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,…,an）的链式存储结构，因此此链表的每个结点只包含一个指针域，所以叫做单链表。链表第一个结点的存储位置叫做头指针。有时，为了方便操作，会在单链表的第一个结点前附设一个结点，称为头结点

头指针	头结点
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针	头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
头指针具有标识的作用，所以常用头指针冠以链表的名字	有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
无论链表是否为空，头指针均不为空。头指针是链表的必要元素	头结点不一定是链表必须要素

重复利用指针建立链表

1. 如果链表为空链表，那么就可以直接将head指针赋给NILL，而无须进行其他操作；
2. 如果链表不为空，那么首先使用一个malloc函数新建一个结点，使head、p1和p2都指向它。它就是这个链表的头结点；
3. 对结点内的数据进行赋值，从而完成该结点的初始化工作；
4. 开辟另外一个结点，并使p1指向这个新开辟的结点；
5. 如果链表还未满足结束条件，那么继续将这个新的结点链入链表，也就是将p1的值赋给p2->next（注意这个时候p2仍指向第一个结点），所以在执行了语句p2->next=p1之后，新结点就被成功链入链表了；
6. 让指针p2向后移动一个位置，即执行语句p2=p1，也就是使p2指向最新建立的结点；
7. 再次开辟一个新结点并初始化它；
8. 再次将指针p1指向这个新结点。如果链表仍然未满足结束条件，那么继续将这个新的结点链入链表，也就是将p1的值赋给p2->next=p1之后，新结点同样被成功链入链表；
9. 再像前面一样将指针p2向后移动一个位置，即执行语句p2=p1，也就是使p2再次指向最新建立的结点
10. 如果仍有新的数据被接收，那么就再次为该数据开辟一个结点，并让指针p1指向这个新结点，并按照前面的操作方式继续为链表添加新数据；
11. 如果链表满足结束条件或者达到事前预定的长度，那么循环操作就将被中止。新的结点也不再被链入链表中。这个时候即将NULL赋给p2->next，表示该结点为整个链表的尾结点。

函数	功能
insert(node, index)	将node插入到链表中下标为index的位置
output()	输出整个链表

链表的遍历

1. 以链表的表头结点作为输入；
2. 设一个指针变量p，先指向第一个结点，并输出该结点中的数据；
3. 将指针p向后移动一个结点，再输出结点数据；
4. 如此继续下去直到链表的尾结点。

结点由存放数据元素的数据域和存放后继结点地址的指针域组成

1. 链表插入操作的实现方法：

   • 找到链表中要插入的位置
   • 令待插入结点的next指针指向插入位置的当前结点
   • 令插入位置之前的当前结点的next指针指向待插入结点

2. 链表遍历操作的实现方法：

   • 定义一个用于遍历的变量，初始指向头结点
   • 输出遍历变量所在结点的值，并更新遍历变量为当前结点的下一个结点
   • 重复操作2，直到遍历完所有结点

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;

void CreateListF(LinkList &L, ElemType a[], int n) { // 头插法建立单链表
    LinkList s;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
}
void CreateListR(LinkList& L, ElemType a[], int n) { //尾插法建立单链表
    LinkList s, r;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    r = L;
    for (int i = 0; i < n; i++) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
}
void InitList(LinkList& L) { // 初始化线性表
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}
void DestoryList(LinkList& L) { // 销毁链表
    LinkList pre = L, p = pre->next;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}
bool ListEmpty(LinkList L) { // 判断链表是否为空表
    return (L->next == NULL);
}
int ListLength(LinkList L) {
    int i = 0;
    LinkList p = L;
    while (p->next != NULL) {
        i++;
        p = p->next;
    }
    return i;
}
void DispList(LinkList L) {
    LinkList p = L->next;
    while (p != NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}
bool GetElem(LinkList L, int i, ElemType& e) {
    int j = 0;
    LinkList p = L;
    if (i <= 0)
        return false;
    while (j < i && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else {
        e = p->data;
        return true;
    }
}
int LocateElem(LinkList L, ElemType e) {
    int i = 1;
    LinkList p = L->next;
    while (p != NULL && p->data != e) {
        p = p->next;
        i++;
    }
    if (p == NULL)
        return 0;
    else return i;
}
bool ListInsert(LinkList& L, int i, ElemType e) {
    int j = 0;
    LinkList p = L, s;
    if (i <= 0)
        return false;
    while (j < i - 1 && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }
}
bool ListDelete(LinkList& L, int i, ElemType& e) {
    int j = 0;
    LinkList p = L, q;
    if (i <= 0)
        return false;
    while (j < i - 1 && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else {
        q = p->next;
        if (q == NULL)
            return false;
        e = q->data;
        p->next = q->next;
        free(q);
        return true;
    }
}

int main() {
    LinkList h;
    ElemType e;
    printf("单链表的基本运算如下：\n");
    printf("（1）初始化单链表h\n");
    InitList(h);
    printf("（2）依次采用尾插法插入a, b, c, d, e元素\n");
    ListInsert(h, 1, 'a');
    ListInsert(h, 2, 'b');
    ListInsert(h, 3, 'c');
    ListInsert(h, 4, 'd');
    ListInsert(h, 5, 'e');
    printf("（3）输出单链表h：");
    DispList(h);
    printf("（4）单链表h长度：%d\n", ListLength(h));
    printf("（5）单链表h为%s\n", ListEmpty(h) ? "空" : "非空");
    GetElem(h, 3, e);
    printf("（6）单链表h上的第3个元素：%c\n", e);
    printf("（7）元素a的位置：%d\n", LocateElem(h, 'a'));
    printf("（8）在第4个元素位置上插入f元素\n");
    ListInsert(h, 4, 'f');
    printf("（9）输出单链表h：");
    DispList(h);
    printf("（10）删除h的第3个元素\n");
    ListDelete(h, 3, e);
    printf("（11）输出单链表h：");
    DispList(h);
    printf("（12）释放单链表h\n");
    DestoryList(h);
    return 0;
}

3 栈

3.1 栈的定义

栈是限定仅在表位进行插入和删除操作的线性表

我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LFO结构。只能对栈顶元素进行操作，我们把栈的插入，删除操作改名为push，pop

栈的插入操作， 叫做进栈，也称压栈，入栈

栈的删除操作， 叫做出栈，也有的叫做弹栈

3.2 栈的顺序存储结构

我们定义一个top变量来指示栈顶元素在数组中的位置，且其小于栈的长度StackSize，一般采用下标为0的一端作为栈底，当栈存在一个元素时，top等于0。因此空栈的判断条件为top = -1

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
typedef char SElemType;
typedef int Status;
typedef struct {
    SElemType* base;
    SElemType* top;
    int stacksize;
}SqStack;
Status InitStack(SqStack& S) {
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status DestoryStack(SqStack& S) {
    if (S.base) {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK;
}
Status ClearStack(SqStack& S) {
    if (S.base)
        S.top = S.base;
    return OK;
}
Status StackEmpty(SqStack S) {
    if (S.top == S.base)
        return TRUE;
    else
        return FALSE;
}
int StackLength(SqStack S) {
    return S.top - S.base;
}
Status Push(SqStack& S, SElemType e) {
    if (S.top - S.base >= S.stacksize) {
        S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!S.base)
            exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
Status Pop(SqStack& S, SElemType& e) {
    if (S.top == S.base)
        return ERROR;
    e = *--S.top;
    return OK;
}
Status GetTop(SqStack S, SElemType& e) {
    if (S.top == S.base)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}
int main() {
    SElemType e;
    SqStack S;
    printf("顺序栈s的基本运算如下：\n");
    printf("（1）初始化栈s\n");
    InitStack(S);
    printf("（2）栈为%s\n", (StackEmpty(S) ? "空" : "非空"));
    printf("（3）依次进栈元素a, b, c, d, e\n");
    Push(S, 'a');
    Push(S, 'b');
    Push(S, 'c');
    Push(S, 'd');
    Push(S, 'e');
    printf("（4）栈为%s\n", (StackEmpty(S) ? "空" : "非空"));
    printf("（5）出栈队列：");
    while (!StackEmpty(S)) {
        Pop(S, e);
        printf("%c ", e);
    }
    printf("\n");
    printf("（6）栈为%s\n", (StackEmpty(S) ? "空" : "非空"));
    printf("（7）释放栈\n");
    DestoryStack(S);
    return 0;
}

4 队列

4.1 基本知识

先进先出

1. 队列的插入操作实现方法：

   • 判断队列是否已满，实际上是由于队尾标记不断增加，需要判断队尾标记是否大于数组长度
   • 更新队尾标记，将新插入元素存入队尾

2. 队列的遍历操作实现方法：

   • 输出队首标记所在的元素
   • 队首标记后移一位
   • 若队尾标记和队首标记相等，输出最后一个元素，否则返回步骤1

3. 队列出队操作的实现方法：

   • 比较队尾标记和队首标记的大小，当队首标记大于队尾标记则说明队列为空了，此时出队操作是非法的
   • 令队首标记后移一位，队首标记后移即视作原队首出队了*

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1

typedef struct Queue {
    int *data;
    int head, tail, length;
}Queue;

void init(Queue *q, int length) {
    q->data = (int *)malloc(sizeof(int) * length);
    q->length = length;
    q->head = 0;
    q->tail = -1;
}

int push(Queue *q, int element) {
    if(q->tail + 1 >= q->length) {
        return ERROR;
    }
    q->tail++;
    q->data[q->tail] = element;
    return OK;
}

void output(Queue *q) {
    for (int i = q->head; i <= q->tail; i++) {
        printf("%d ", q->data[i]);
    }
    printf("\n");
}

// 队首元素输出函数 front
int front(Queue *q) {
    return q->data[q->head];
}

// 删除队首元素函数 pop
void pop(Queue *q) {
    q->head++;
}

// 判断队列是否为空的函数 empty
int empty(Queue *q) {
    return q->head > q->tail;
}

void clear(Queue *q) {
    free(q->data);
    free(q);
}

int main() {
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    init(queue, 100);
    for (int i = 1; i <= 10; i++) {
        push(queue, i);
    }
    output(queue);
    if(!empty(queue)) {
        printf("%d\n", front(queue));
        pop(queue);
    }
    output(queue);
    clear(queue);
    return 0;
}

4.2 循环队列

上面的队列实现方式有一个问题：假上溢

循环队列，当队尾标记tail到达队列上限后，如果队列内的元素没有达到上限，就跳转到数组的开始位置，也就是0的位置，也就是0的位置，队首标记到达队列上限也采取同样的处理。通过这样的方法，我们就能够最大化利用内存空间，避免“假上溢”的情况出现

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1

typedef struct Queue {
    int *data;
    int head, tail, length, count;
}Queue;

void init(Queue *q, int length) {
    q->data = (int *)malloc(sizeof(int) * length);
    q->length = length;
    q->head = 0;
    q->tail = -1;
    q->count = 0;
}

int push(Queue *q, int element) {
    if (q->count >= q->length) {
        return ERROR;
    }
    q->tail = (q->tail + 1) % q->length;
    q->data[q->tail] = element;
    q->count++;
    return OK;
}

void output(Queue *q) {
    int i = q->head;
    do {
        printf("%d ", q->data[i]);
        i = (i + 1) % q->length;
    } while(i != (q->tail + 1) % q->length);
    printf("\n");
}

int front(Queue *q) {
    return q->data[q->head];
}

void pop(Queue *q) {
    q->head = (q->head + 1) % q->length;
    q->count--;
}

int empty(Queue *q) {
    return q->count == 0;
}

void clear(Queue *q) {
    free(q->data);
    free(q);
}

int main() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    init(q, 100);
    for (int i = 1; i <= 10; i++) {
        push(q, i);
    }
    output(q);
    if (!empty(q)) {
        printf("%d\n", front(q));
        pop(q);        
    }
    output(q);
    clear(q);
    return 0;
}

5 树和二叉树

5.1 树

5.1.1 概念

树有且仅有一个上面的树根。树是由若干个有限结点组成的一个具有层次关系的集合，最上面的结点为树的根结点

结点拥有的子树个数我们称为结点的度

5.1.2 性质

每棵非空树有且仅有一个根结点

在树上，从一个结点出发可以访问到其余的结点，并且一个结点到另一个结点的路径有且仅有一条

父亲结点可以有多个孩子结点，除根结点外，其余的结点有且仅有一个父亲结点。

根结点没有父亲结点，叶结点没有孩子结点

5.2 二叉树

5.2.1 概念

二叉树的每个结点最多只有两个孩子结点。二叉树有5种基本形态：空二叉树（树为空没有结点）、只有根结点的二叉树、只有左子树的二叉树、只有右子树的二叉树、左右子树都有的二叉树

5.2.2 性质

二叉树的第 i 层最多有 $2^{i-1}$ 个结点。由定义可知，二叉树的每个结点最多有两个孩子结点，那么第 i 层最多的结点数等于第 i - 1 层最多结点数的2倍。而第 1 层最多只有1个结点，所以我们可以知道第 i 层最多有 $2^{i-1}$ 个结点

深度为 k 的二叉树最多有 $2^k$ - 1 个结点。由上一个性质，我们可以知道二叉树每层最多的结点个数，从第 1 层到第 k 层把最多结点数累加起来，我们就可以得到深度为 k 的二叉树最多有 $2^k$ - 1个结点

任意一棵二叉树上，其叶子结点个数 $n_0$ 比度为2的结点数 $n_2$ 多1。我们记树上结点总个数为n，度为1的结点个数为 $n_1$ ，则有 n = $n_0$ + $n_1$ + $n_2$。另外我们可以发现一棵二叉树一共有 n - 1条边，度为2的结点可以延伸出两条边，度为1的结点可以延伸出一条边，叶子结点没有边延伸出来，所以又有 n - 1 = $n_1$ + 2 $\times$ $n_2$。结合以上两个式子，我们可以得到 $n_0$ = $n_2$ + 1

5.2.3 两个特殊的二叉树

满二叉树：如果一棵树深度为 k 而且有 $2^k$ - 1个结点，那么我们称该二叉树为满二叉树，也就是说在此深度上，不能再添加结点了

完全二叉树：如果一棵树深度为k，从第 1 层到第 k - 1层该树是满二叉树，第 k 层的结点都集中在左边，那么我们称该二叉树为完全二叉树。完全二叉树因其结构的特殊性具有很高的效率，经常被用在算法的优化里

5.2.4 二叉树的广义表表达形式

我们可以用广义表来表示二叉树，形式为 a(b, c)，表示根结点a的左孩子结点为b，右孩子结点为c。中间用一个逗号隔开。如果左右孩子结点不为空，则用以上形式来替换；如果结点为空，则不填任何字符。以下是几种常见的格式：

• a：表示根结点为a，左右孩子结点均为空
• a(b)：表示根结点为a，左孩子结点为b，右孩子结点为空
• a(, c)：表示根结点为a，左孩子结点为空，右孩子结点为c
• a(b, c)：表示根结点为a，左孩子结点为b，右孩子结点为c

如 7(4(3, 6), 15(, 55)) 可以表示以下这棵二叉树：

如何将广义表创建成二叉树：

将广义表创建成二叉树，可以借助栈来实现，利用栈先进后出的特点，先将根结点压入栈中，如果左孩子结点不为空，则将其作为栈顶结点（即其父亲结点）的左孩子结点，并压入栈中，递归左子树，处理完之后左孩子节点出战；如果右孩子不为空，则将其作为栈顶结点（即其父亲结点）的右孩子结点，并压入栈中，递归右子树，处理完之后右孩子结点出栈

5.3 二叉树的存储结构

// 实现二叉树的各种基本运算
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef char ElemType;
typedef struct node {
    ElemType data;
    struct node* lchild;
    struct node* rchild;
}BTNode;

void CreateBTree(BTNode*& b, const char* str) {
    BTNode* St[MAXSIZE], * p;
    int top = -1, k, j = 0;
    char ch;
    b = NULL;
    ch = str[j];
    while (ch != '\0') {
        switch (ch) {
        case'(':
            top++;
            St[top] = p;
            k = 1;
            break;
        case')':
            top--;
            break;
        case',':
            k = 2;
            break;
        default:
            p = (BTNode*)malloc(sizeof(BTNode));
            p->data = ch;
            p->lchild = p->rchild = NULL;
            if (b == NULL)
                b = p;
            else {
                switch (k) {
                case 1:
                    St[top]->lchild = p;
                    break;
                case 2:
                    St[top]->rchild = p;
                    break;
                }
            }
        }
        j++;
        ch = str[j];
    }
}

void DestoryBTree(BTNode*& b) {
    if (b != NULL) {
        DestoryBTree(b->lchild);
        DestoryBTree(b->rchild);
        free(b);
    }
}

BTNode* FindNode(BTNode* b, ElemType x) {
    BTNode* p;
    if (b == NULL)
        return NULL;
    else if (b->data == x)
        return b;
    else {
        p = FindNode(b->lchild, x);
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);
    }
}

BTNode* LchildNode(BTNode* p) {
    return p->lchild;
}

BTNode* RchildNode(BTNode* p) {
    return p->rchild;
}

int BTHeight(BTNode* b) {
    int lchildh, rchildh;
    if (b == NULL)
        return 0;
    else {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh > rchildh ? (lchildh + 1) : (rchildh + 1));
    }
}

void DispBTree(BTNode* b) {
    if (b != NULL) {
        printf("&c", b->data);
        if (b->lchild != NULL || b->rchild != NULL) {
            printf("(");
            DispBTree(b->lchild);
            if (b->rchild != NULL)
                printf(",");
            DispBTree(b->rchild);
            printf(")");
        }
    }
}
int main() {
    BTNode* b, * p, * lp, * rp;
    printf("二叉树的基本运算如下：\n");
    printf("（1）创建二叉树\n");
    CreateBTree(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("（2）输出二叉树");
    DispBTree(b);
    printf("\n");
    printf("（3）H结点：");
    p = FindNode(b, 'H');
    if (p != NULL) {
        lp = LchildNode(p);
        if (lp != NULL)
            printf("左孩子为%c", lp->data);
        else
            printf("无左孩子");
        rp = RchildNode(p);
        if (rp != NULL)
            printf("右孩子为%c", rp->data);
        else
            printf("无右孩子");
    }
    printf("\n");
    printf("（4）二叉树b的高度：%d\n", BTHeight(b));
    printf("（5）释放二叉树b\n");
    DestoryBTree(b);
    return 0;
}

5.4 遍历二叉树

// 实现二叉树各种遍历算法
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef char ElemType;
typedef struct node {
    ElemType data;
    struct node* lchild;
    struct node* rchild;
}BTNode;

void CreateBTree(BTNode*& b, const char* str) {
    BTNode* St[MAXSIZE], * p;
    int top = -1, k, j = 0;
    char ch;
    b = NULL;
    ch = str[j];
    while (ch != '\0') {
        switch (ch) {
        case'(':
            top++;
            St[top] = p;
            k = 1;
            break;
        case')':
            top--;
            break;
        case',':
            k = 2;
            break;
        default:
            p = (BTNode*)malloc(sizeof(BTNode));
            p->data = ch;
            p->lchild = p->rchild = NULL;
            if (b == NULL)
                b = p;
            else {
                switch (k) {
                case 1:
                    St[top]->lchild = p;
                    break;
                case 2:
                    St[top]->rchild = p;
                    break;
                }
            }
        }
        j++;
        ch = str[j];
    }
}

void DestoryBTree(BTNode*& b) {
    if (b != NULL) {
        DestoryBTree(b->lchild);
        DestoryBTree(b->rchild);
        free(b);
    }
}

BTNode* FindNode(BTNode* b, ElemType x) {
    BTNode* p;
    if (b == NULL)
        return NULL;
    else if (b->data == x)
        return b;
    else {
        p = FindNode(b->lchild, x);
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);
    }
}

BTNode* LchildNode(BTNode* p) {
    return p->lchild;
}

BTNode* RchildNode(BTNode* p) {
    return p->rchild;
}

int BTHeight(BTNode* b) {
    int lchildh, rchildh;
    if (b == NULL)
        return 0;
    else {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh > rchildh ? (lchildh + 1) : (rchildh + 1));
    }
}

void DispBTree(BTNode* b) {
    if (b != NULL) {
        printf("&c", b->data);
        if (b->lchild != NULL || b->rchild != NULL) {
            printf("(");
            DispBTree(b->lchild);
            if (b->rchild != NULL)
                printf(",");
            DispBTree(b->rchild);
            printf(")");
        }
    }
}
// 以上为btree.cpp 包含二叉树的基本运算算法
void PreOrder(BTNode* b) {  // 先序遍历递归算法
    if (b != NULL) {
        printf("%c ", b->data);  // 访问根节点
        PreOrder(b->lchild);  // 递归访问左子树
        PreOrder(b->rchild);  //递归访问右子树
    }
}

void PreOrder1(BTNode* b) {  // 先序非递归遍历算法
    BTNode* St[MAXSIZE], * p;
    int top = -1;
    if (b != NULL) {
        top++;  // 根结点进栈
        St[top] = b;
        while (top > -1) {  // 栈不为空时循环
            p = St[top];  // 退栈并访问该结点
            top--;
            printf("%c ", p->data);
            if (p->rchild != NULL) {  // 有右孩子，将其进栈
                top++;
                St[top] = p->rchild;
            }
            if (p->lchild != NULL) {  // 有左孩子，将其进栈
                top++;
                St[top] = p->lchild;
            }
        }
        printf("\n");
    }
}

void InOrder(BTNode* b) {  // 中序遍历的递归算法
    if (b != NULL) {
        InOrder(b->lchild);  // 递归访问左子树
        printf("%c ", b->data);  // 访问根结点
        InOrder(b->rchild);  // 递归访问右子树
    }
}

void InOrder1(BTNode* b) {  // 中序非递归遍历算法
    BTNode* St[MAXSIZE], * p;
    int top = -1;
    if (b != NULL) {
        p = b;
        while (top > -1 || p != NULL) {
            while (p != NULL) {  // 扫描结点p的所有左下结点并进栈
                top++;
                St[top] = p;
                p = p->lchild;
            }
            if (top > -1) {
                p = St[top];  // 出栈结点p并访问
                top--;
                printf("%c ", p->data);
                p = p->rchild;
            }
        }
        printf("\n");
    }
}

void PostOrder(BTNode* b) {  // 后序遍历的递归算法
    if (b != NULL) {
        PostOrder(b->lchild);  // 递归访问左子树
        PostOrder(b->rchild);  // 递归访问右子树
        printf("%c ", b->data);  // 访问根结点
    }
}

void PostOrder1(BTNode* b) {  // 后序非递归遍历算法
    BTNode* St[MAXSIZE];
    BTNode* p;
    int top = -1;  // 栈指针置初值
    bool flag;
    if (b != NULL) {
        do {
            while (b != NULL) {  // 将b结点的所有左下结点进栈
                top++;
                St[top] = b;
                b = b->lchild;
            }
            p = NULL;  // p指向当前结点的前一个已访问的结点
            flag = true;  // flag为真表示正在处理栈顶结点
            while (top != -1 && flag) {
                b = St[top];  // 取出当前的栈顶元素
                if (b->rchild == p) {  // 右子树不存在或已被访问
                    printf("%c ", b->data);  // 访问b结点
                    top--;
                    p = b;  // p指向被访问的结点
                }
                else {
                    b = b->rchild;
                    flag = false;
                }
            }
        } while (top != -1);
        printf("\n");
    }
}

void TravLevel(BTNode* b) {
    BTNode* Qu[MAXSIZE];
    int front, rear;
    front = rear = 0;
    if (b != NULL)
        printf("%c ", b->data);
    rear++;
    Qu[rear] = b;
    while (rear != front) {
        front = (front + 1) % MAXSIZE;
        b = Qu[front];
        if (b->lchild != NULL) {
            printf("%c ", b->lchild->data);
            rear = (rear + 1) % MAXSIZE;
            Qu[rear] = b->lchild;
        }
        if (b->rchild != NULL) {
            printf("%c ", b->rchild->data);
            rear = (rear + 1) % MAXSIZE;
            Qu[rear] = b->rchild;
        }
    }
    printf("\n");
}

int main() {
    BTNode* b;
    CreateBTree(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("二叉树b：");
    DispBTree(b);
    printf("\n");
    printf("层次遍历序列：");
    TravLevel(b);
    printf("先序遍历序列：\n");
    printf("  递归算法：");
    PreOrder(b);
    printf("\n");
    printf("  非递归算法：");
    PreOrder1(b);
    printf("中序遍历序列：\n");
    printf("  递归算法：");
    InOrder(b);
    printf("\n");
    printf("  非递归算法：");
    InOrder1(b);
    printf("后序遍历序列：\n");
    printf("  递归算法：");
    PostOrder(b);
    printf("\n");
    printf("  非递归算法：");
    PostOrder1(b);
    DestoryBTree(b);
    return 0;
}

5.5 赫夫曼树及其应用

#include<stdio.h>
#include<string.h>
#define N 50  //叶子结点总数
#define M 2*N-1  // 树中结点总数
typedef struct {
    char data[5];  // 结点值
    int weight;  // 权重
    int parent;  // 双亲结点
    int lchild;  // 左孩子结点
    int rchild;  // 右孩子结点
}HTNode;
typedef struct {
    char cd[N];  // 存放哈夫曼编码
    int start;  // ch[start.n]存放哈夫曼编码
}HCode;
void CreateHT(HTNode ht[], int n) {  // 由ht的叶子结点构造完整的哈夫曼树
    int i, k, lnode, rnode;
    int min1, min2;
    for (i = 0; i < 2 * n - 1; i++)  // 所有结点的相关域置初值-1
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    for (i = n; i < 2 * n - 1; i++) {  // 构造哈夫曼树的分支结点
        min1 = min2 = 32767;  // lnode和rnode为最小权重的两个结点位置
        lnode = rnode = -1;
        for(k = 0; k <= i - 1; k++)  // 查找最小和次小结点
            if (ht[k].parent == -1) {  // 只在尚未构造二叉树的结点中查找
                if (ht[k].weight < min1) {
                    min2 = min1;
                    rnode = lnode;
                    min1 = ht[k].weight;
                    lnode = k;
                }
                else if (ht[k].weight < min2) {
                    min2 = ht[k].weight;
                    rnode = k;
                }
            }
        ht[lnode].parent = i;  // 合并两个最小和次小的结点
        ht[rnode].parent = i;
        ht[i].weight = ht[lnode].weight + ht[rnode].weight;
        ht[i].lchild = lnode;
        ht[i].rchild = rnode;
    }
}
void CreateHCode(HTNode ht[], HCode hcd[], int n) {  // 由哈夫曼树ht构造哈夫曼编码hcd
    int i, f, c;
    HCode hc;
    for (i = 0; i < n; i++) {  // 根据哈夫曼树构造所有叶子结点的哈夫曼编码
        hc.start = n;
        c = i;
        f = ht[i].parent;
        while (f != -1) {  // 循环直到树根结点
            if (ht[f].lchild == c)  // 处理左孩子结点
                hc.cd[hc.start--] = '0';
            else  // 处理右孩子结点
                hc.cd[hc.start--] = '1';
            c = f;
            f = ht[f].parent;
        }
        hc.start++;  // start指向哈夫曼编码最开始字符
        hcd[i] = hc;
    }
}
void DispHCode(HTNode ht[], HCode hcd[], int n) {  // 输出哈夫曼编码
    int i, k;
    int sum = 0, m = 0, j;
    printf("输出哈夫曼编码：\n");
    for (i = 0; i < n; i++) {
        j = 0;
        printf("   %s\t", ht[i].data);
        for (k = hcd[i].start; k <= n; k++) {
            printf("%c", hcd[i].cd[k]);
            j++;
        }
        m += ht[i].weight;
        sum += ht[i].weight * j;
        printf("\n");
    }
    printf("\n平均长度=%g\n", 1.0 * sum / m);
}
int main() {
    int n = 15, i;
    const char* str[] = { "The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be" };
    int fnum[] = { 1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123 };
    HTNode ht[M];
    HCode hcd[N];
    for (i = 0; i < n; i++) {
        strcpy(ht[i].data, str[i]);
        ht[i].weight = fnum[i];
    }
    CreateHT(ht, n);  // 创建哈夫曼树
    CreateHCode(ht, hcd, n);  // 构造哈夫曼编码
    DispHCode(ht, hcd, n);  // 输出哈夫曼编码
    return 0;
}

6 图

6.1 什么是图

图是由一系列顶点和若干连结顶点集合内两个顶点的边组成的数据结构。通常我们用G = (V, E) 表示一个图结构，其中V表示点集，E表示边集

在顶点集合所包含的若干个顶点之间，可能存在这某种两两对应关系——如果某两个点之间的确存在这样的关系的话，我们就在这两个点之间连边，这样就得到了边集的一个成员，也就是一条边。对应到社交网络上，顶点就是网络中的用户，边就是用户之间的好友关系

6.2 图的常用概念

如果图中所有边都是无向边，则称为无向图，反之称为有向图

有很少边或弧（如 e < nlogn，e指边数，n指点数）的图称为稀疏图，反之称为稠密图。顶点的度是指依附于某个顶点的边数。在有向图中，顶点的入度是指以顶点为弧头的弧的数目，也就是以该顶点为终点的弧的数目；顶点的出度是指以顶点为弧尾的弧的数目，也就是以该顶点为起点的弧的数目，在有向图里，顶点的度为入度和出度之和。在无向图里，图中的边数等于所有顶点度数和的一半

6.3 图的存储方式

两个常见的图的存储结构——邻接矩阵和邻接表。邻接矩阵就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系

对于有n个顶点的图 G = (V, E) 来说，我们可以用一个 n $\times$ n 的矩阵A来表示G中各顶点的相邻关系，如果$v_i$和$v_j$之间存在边（或弧），则A$[i]$[j]$ = 1，否则A$[i]$[j]$ = 0。下图为有向图$G_1$和无向图$G_2$对应的邻接矩阵：

图的邻接矩阵是唯一的，矩阵的大小只与顶点个数N有关，是一个N $\times$ N 的矩阵。在无向图里，如果顶点 $v_i$ 和 $v_j$ 之间有边，则可认为顶点 $v_i$ 到 $v_j$ 有边，顶点 $v_j$ 到 $v_i$ 也有边。对应到邻接矩阵里，则有A$[i]$ $[j]$ = A$[j]$$[i]$ = 1。无向图的邻接矩阵是一个对称矩阵

// 实现图的邻接矩阵和邻接表存储
#include<stdio.h>
#include<stdlib.h>
#define INF 32767
#define MAXV 100  // 最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct {
    int no;  // 顶点编号
    InfoType info;  // 顶点其他信息
}VertexType;

typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode {
    int adjvex;
    struct ANode* nextarc;
    int weight;
}ArcNode;

typedef struct Vnode {
    InfoType info;
    int count;
    ArcNode* firstarc;
}VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;
//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        printf("\n");
    }
}

// 邻接表的基本运算算法
void CreateAdj(AdjGraph*& G, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for(i = 0; i < n; i++)
        for(j = n-1; j < n;j--)
            if (A[i][j] != 0 && A[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
    G->n = n;
    G->e = n;
}

void DispAdj(AdjGraph* G) {
    ArcNode* p;
    for (int i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL) {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("^\n");
    }
}

void DestoryAdj(AdjGraph*& G) {
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) {
        pre = G->adjlist[i].firstarc;
        if (pre != NULL) {
            p = pre->nextarc;
            while (p != NULL) {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);
}
int main() {
    MatGraph g;
    AdjGraph* G;
    int A[MAXV][MAXV] = {
        {0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},
        {8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},
        {INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};
    int n = 6, e = 10;
    CreateMat(g, A, n, e);
    printf("(1)图G的邻接矩阵：\n");
    DispMat(g);
    CreateAdj(G, A, n, e);
    printf("(2)图G的邻接表：\n");
    DispAdj(G);
    printf("(3)销毁图G的邻接表\n");
    DestoryAdj(G);
    return 0;
}

6.4 图的遍历

#include<stdio.h>
#include<stdlib.h>
#define INF 32767
#define MAXV 100  // 最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct {
    int no;  // 顶点编号
    InfoType info;  // 顶点其他信息
}VertexType;

typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode {
    int adjvex;
    struct ANode* nextarc;
    int weight;
}ArcNode;

typedef struct Vnode {
    InfoType info;
    int count;
    ArcNode* firstarc;
}VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;
//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        printf("\n");
    }
}

// 邻接表的基本运算算法
void CreateAdj(AdjGraph*& G, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for(i = 0; i < n; i++)
        for(j = n-1; j >= 0;j--)
            if (A[i][j] != 0 && A[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
    G->n = n;
    G->e = n;
}

void DispAdj(AdjGraph* G) {
    ArcNode* p;
    for (int i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL) {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("^\n");
    }
}

void DestoryAdj(AdjGraph*& G) {
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) {
        pre = G->adjlist[i].firstarc;
        if (pre != NULL) {
            p = pre->nextarc;
            while (p != NULL) {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);
}

int visited[MAXV];
void DFS(AdjGraph* G, int v) {
    ArcNode* p;
    printf("%3d", v);
    visited[v] = 1;
    p = G->adjlist[v].firstarc;
    while (p != NULL) {
        if (visited[p->adjvex] == 0)
            DFS(G, p->adjvex);
        p = p->nextarc;
    }
}

void DFS1(AdjGraph* G, int v) {
    ArcNode* p;
    int St[MAXV];
    int top = -1, w, x, i;
    for (i = 0; i < G->n; i++)
        visited[i] = 0;
    printf("%3d", v);
    visited[v] = 1;
    top++;
    St[top] = v;
    while (top > -1) {
        x = St[top];
        p = G->adjlist[x].firstarc;
        while (p != NULL) {
            w = p->adjvex;
            if (visited[w] == 0) {
                printf("%3d", w);
                visited[w] = 1;
                top++;
                St[top] = w;
                break;
            }
            p = p->nextarc;
        }
        if (p == NULL)
            top--;
    }
    printf("\n");
}

void BFS(AdjGraph* G, int v) {
    ArcNode* p;
    int queue[MAXV], front = 0, rear = 0;
    int visited[MAXV];
    int w, i;
    for (i = 0; i < G->n; i++)
        visited[i] = 0;
    printf("%3d", v);
    visited[v] = 1;
    rear = (rear + 1) % MAXV;
    queue[rear] = v;
    while (front != rear) {
        front = (front + 1) % MAXV;
        w = queue[front];
        p = G->adjlist[w].firstarc;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) {
                printf("%3d", p->adjvex);
                visited[p->adjvex] = 1;
                rear = (rear + 1) % MAXV;
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
    printf("\n");
}
int main() {
    AdjGraph* G;
    int A[MAXV][MAXV] = {
        {0, 5, INF, 7, INF, INF}, {INF, 0, 4, INF, INF, INF},
        {8, INF, 0, INF, INF, 9}, {INF, INF, 5, 0, INF, 6},
        {INF, INF, INF, 5, 0, INF}, {3, INF, INF, INF, 1, 0} };
    int n = 6, e = 10;
    CreateAdj(G, A, n, e);
    printf("图G的邻接表：\n");
    DispAdj(G);
    printf("从顶点0开始的DFS（递归算法）：\n");
    DFS(G, 0);
    printf("\n");
    printf("从顶点0开始的DFS（非递归算法）：\n");
    DFS1(G, 0);
    printf("从顶点0开始的BFS：\n");
    BFS(G, 0);
    DestoryAdj(G);
    return 0;
}

6.5 最小生成树

构造连通网的最小代价生成树称为最小生成树

6.5.1 普利姆算法

// Prim
#include<stdio.h>
#include<stdlib.h>
#define INF 32767
#define MAXV 100  // 最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct {
    int no;  // 顶点编号
    InfoType info;  // 顶点其他信息
}VertexType;

typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode {
    int adjvex;
    struct ANode* nextarc;
    int weight;
}ArcNode;

typedef struct Vnode {
    InfoType info;
    int count;
    ArcNode* firstarc;
}VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;
//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        printf("\n");
    }
}

// 邻接表的基本运算算法
void CreateAdj(AdjGraph*& G, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for(i = 0; i < n; i++)
        for(j = n-1; j >= 0;j--)
            if (A[i][j] != 0 && A[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
    G->n = n;
    G->e = n;
}

void DispAdj(AdjGraph* G) {
    ArcNode* p;
    for (int i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL) {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("^\n");
    }
}

void DestoryAdj(AdjGraph*& G) {
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) {
        pre = G->adjlist[i].firstarc;
        if (pre != NULL) {
            p = pre->nextarc;
            while (p != NULL) {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);
}

void Prim(MatGraph g, int v) {
    int lowcost[MAXV], min, n = g.n;
    int closest[MAXV], i, j, k;
    for (i = 0; i < n; i++) {
        lowcost[i] = g.edges[v][i];
        closest[i] = v;
    }
    for (i = 1; i < n; i++) {
        min = INF;
        for(j = 0; j < n; j++)
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        printf("边（%d, %d）权为：%d\n", closest[k], k, min);
        lowcost[k] = 0;
        for(j = 0; j < n; j++)
            if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) {
                lowcost[j] = g.edges[k][j];
                closest[j] = k;
            }
    }
}

int main() {
    int v = 3;
    MatGraph g;
    int A[MAXV][MAXV] = {
        {0, 5, 8, 7, INF, 3}, {5, 0, 4, INF, INF, INF}, {8, 4, 0, 5, INF, 9},
        {7, INF, 5, 0, 5, 6}, {INF, INF, INF, 5, 0, 1}, {3, INF, 9, 6, 1, 0} };
    int n = 6, e = 10;
    CreateMat(g, A, n, e);
    printf("图G的邻接矩阵：\n");
    DispMat(g);
    printf("普利姆算法求解结果：\n");
    Prim(g, 0);
    return 0;
}

6.5.2 克鲁斯卡尔算法

// Kruskal
#include<stdio.h>
#include<stdlib.h>
#define INF 32767
#define MAXV 100  // 最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct {
    int no;  // 顶点编号
    InfoType info;  // 顶点其他信息
}VertexType;

typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode {
    int adjvex;
    struct ANode* nextarc;
    int weight;
}ArcNode;

typedef struct Vnode {
    InfoType info;
    int count;
    ArcNode* firstarc;
}VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;
//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        printf("\n");
    }
}

// 邻接表的基本运算算法
void CreateAdj(AdjGraph*& G, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for(i = 0; i < n; i++)
        for(j = n-1; j >= 0;j--)
            if (A[i][j] != 0 && A[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
    G->n = n;
    G->e = n;
}

void DispAdj(AdjGraph* G) {
    ArcNode* p;
    for (int i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL) {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("^\n");
    }
}

void DestoryAdj(AdjGraph*& G) {
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) {
        pre = G->adjlist[i].firstarc;
        if (pre != NULL) {
            p = pre->nextarc;
            while (p != NULL) {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);
}

#define MAXSIZE 100
typedef struct {
    int u;
    int v;
    int w;
}Edge;

void InsertSort(Edge E[], int n) {
    int i, j;
    Edge temp;
    for (i = 1; i < n; i++) {
        temp = E[i];
        j = i - 1;
        while (j >= 0 && temp.w < E[j].w) {
            E[j + 1] = E[j];
            j--;
        }
        E[j + 1] = temp;
    }
}

void Kruskal(MatGraph g) {
    int i, j, u1, v1, sn1, sn2, k;
    int vset[MAXV];
    Edge E[MAXSIZE];
    k = 0;
    for(i = 0; i < g.n; i++)
        for (j = 0; j <= i; j++) {
            if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
                E[k].u = i;
                E[k].v = j;
                E[k].w = g.edges[i][j];
                k++;
            }
        }
    InsertSort(E, g.e);
    for (i = 0; i < g.n; i++)
        vset[i] = i;
    k = 1;
    j = 0;
    while (k < g.n) {
        u1 = E[j].u;
        v1 = E[j].v;
        sn1 = vset[u1];
        sn2 = vset[v1];
        if (sn1 != sn2) {
            printf("(%d,%d):%d\n", u1, v1, E[j].w);
            k++;
            for (i = 0; i < g.n; i++)
                if (vset[i] == sn2)
                    vset[i] = sn1;
        }
        j++;
    }
}

int main() {
    int u = 3;
    MatGraph g;
    int A[MAXV][MAXV] = {
        {0, 5, 8, 7, INF, 3}, {5, 0, 4, INF, INF, INF}, {8, 4, 0, 5, INF, 9},
        {7, INF, 5, 0, 5, 6}, {INF, INF, INF, 5, 0, 1}, {3, INF, 9, 6, 1, 0} };
    int n = 6, e = 10;
    CreateMat(g, A, n, e);
    printf("图G的邻接矩阵：\n");
    DispMat(g);
    printf("克鲁斯卡尔算法求解结果：\n");
    Kruskal(g);
    return 0;
}

6.6 最短路径

6.6.1 迪杰斯特拉算法

// Dijkstra
#include<stdio.h>
#include<stdlib.h>
#define INF 32767
#define MAXV 100  // 最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct {
    int no;  // 顶点编号
    InfoType info;  // 顶点其他信息
}VertexType;

typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode {
    int adjvex;
    struct ANode* nextarc;
    int weight;
}ArcNode;

typedef struct Vnode {
    InfoType info;
    int count;
    ArcNode* firstarc;
}VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;
//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        printf("\n");
    }
}

// 邻接表的基本运算算法
void CreateAdj(AdjGraph*& G, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for(i = 0; i < n; i++)
        for(j = n-1; j >= 0;j--)
            if (A[i][j] != 0 && A[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
    G->n = n;
    G->e = n;
}

void DispAdj(AdjGraph* G) {
    ArcNode* p;
    for (int i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL) {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("^\n");
    }
}

void DestoryAdj(AdjGraph*& G) {
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) {
        pre = G->adjlist[i].firstarc;
        if (pre != NULL) {
            p = pre->nextarc;
            while (p != NULL) {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);
}

void Dispath(MatGraph g, int dist[], int path[], int S[], int v) {
    int i, j, k;
    int apath[MAXV], d;
    for(i = 0; i < g.n; i++)
        if (S[i] == 1 && i != v) {
            printf("从顶点%d到顶点%d的路径长度为：%d\t路径为：", v, i, dist[i]);
            d = 0;
            apath[d] = i;
            k = path[i];
            if (k == -1)
                printf("无路径\n");
            else {
                while (k != v) {
                    d++;
                    apath[d] = k;
                    k = path[k];
                }
                d++;
                apath[d] = v;
                printf("%d", apath[d]);
                for (j = d - 1; j >= 0; j--)
                    printf(",%d", apath[j]);
                printf("\n");
            }
        }
}

void Dijkstra(MatGraph g, int v) {
    int dist[MAXV], path[MAXV];
    int S[MAXV];
    int Mindis, i, j, u;
    for (i = 0; i < g.n; i++) {
        dist[i] = g.edges[v][i];
        S[i] = 0;
        if (g.edges[v][i] < INF)
            path[i] = v;
        else
            path[i] = -1;
    }
    S[v] = 1;
    path[v] = 0;
    for (i = 0; i < g.n - 1; i++) {
        Mindis = INF;
        for(j = 0; j < g.n; j++)
            if (S[j] == 0 && dist[j] < Mindis) {
                u = j;
                Mindis = dist[j];
            }
        S[u] = 1;
        for(j = 0; j < g.n;j++)
            if(S[j]==0)
                if (g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j]) {
                    dist[j] = dist[u] + g.edges[u][j];
                    path[j] = u;
                }
    }
    Dispath(g, dist, path, S, v);
}

int main() {
    int v = 0;
    MatGraph g;
    int A[MAXV][MAXV] = {
        {0, 5, INF, 7, INF, INF}, {INF, 0, 4, INF, INF, INF},
        {0, INF, 0, INF, INF, 9}, {INF, INF, 5, 0, INF, 6},
        {INF, INF, INF, 5, 0, INF}, {3, INF, INF, INF, 1, 0} };
    int n = 6, e = 10;
    CreateMat(g, A, n, e);
    printf("有向图G的邻接矩阵：\n");
    DispMat(g);
    printf("迪杰斯特拉算法求解结果：\n");
    Dijkstra(g, v);
    return 0;
}

6.6.2 弗洛伊德算法

// Floyd
#include<stdio.h>
#include<stdlib.h>
#define INF 32767
#define MAXV 100  // 最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct {
    int no;  // 顶点编号
    InfoType info;  // 顶点其他信息
}VertexType;

typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode {
    int adjvex;
    struct ANode* nextarc;
    int weight;
}ArcNode;

typedef struct Vnode {
    InfoType info;
    int count;
    ArcNode* firstarc;
}VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;
//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
    int i, j;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != INF)
                printf("%4d", g.edges[i][j]);
            else
                printf("%4s", "∞");
        printf("\n");
    }
}

// 邻接表的基本运算算法
void CreateAdj(AdjGraph*& G, int A[MAXV][MAXV], int n, int e) {
    int i, j;
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for(i = 0; i < n; i++)
        for(j = n-1; j >= 0;j--)
            if (A[i][j] != 0 && A[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
    G->n = n;
    G->e = n;
}

void DispAdj(AdjGraph* G) {
    ArcNode* p;
    for (int i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL) {
            printf("%3d[%d]->", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("^\n");
    }
}

void DestoryAdj(AdjGraph*& G) {
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) {
        pre = G->adjlist[i].firstarc;
        if (pre != NULL) {
            p = pre->nextarc;
            while (p != NULL) {
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);
}

void Dispath(MatGraph g, int A[][MAXV], int path[][MAXV]) {
    int i, j, k, s;
    int apath[MAXV], d;
    for(i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++) {
            if (A[i][j] != INF && i != j) {
                printf("从%d到%d的路径为：", i, j);
                k = path[i][j];
                d = 0;
                apath[d] = j;
                while (k != -1 && k != i) {
                    d++;
                    apath[d] = k;
                    k = path[i][k];
                }
                k++;
                apath[d] = i;
                printf("%d", apath[d]);
                for (s = d - 1; s >= 0; s--)
                    printf(",%d", apath[s]);
                printf("\t路径长度为：%d\n", A[i][j]);
            }
        }
}

void Floyd(MatGraph g) {
    int A[MAXV][MAXV], path[MAXV][MAXV];
    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];
            if (i != j && g.edges[i][j] < INF)
                path[i][j] = i;
            else
                path[i][j] = -1;
        }
    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[i][j] = path[k][j];
                }
    }
    Dispath(g, A, path);
}

int main() {
    MatGraph q;
    int A[MAXV][MAXV] = {
        {0, 5, INF, 7, INF, INF}, {INF, 0, 4, INF, INF, INF},
        {8, INF, 0, INF, INF, 9}, {INF, INF, 5, 0, INF, 6},
        {INF, INF, INF, 5, 0, INF}, {3, INF, INF, INF, 1, 0} };
    int n = 6, e = 10;
    CreateMat(g, A, n, e);
    printf("有向图G的邻接矩阵：\n");
    DispMat(g);
    printf("弗洛伊德算法求解结果：\n");
    Floyd(g);
    return 0;
}

6.7 拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系。这样的有向图为顶点表示活动的网，我们称为AOV网

设 G = (V, E) 是一个具有 n 个顶点的有向图，V 中的顶点序列 $v_1$ ，$v_2$，… $v_n$ , 满足若从 顶点 $v_i$ 到 $v_j$ 有一条路径， 则在顶点序列中顶点 $v_i$ 必在顶点 $v_j$ 之前。则我们称这样的顶点序列为一个拓扑序列

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环(回路)的 AOV网； 如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是 AOV 网。

在拓扑排序算法中，涉及的结构代码如下。

typedef struct EdgeNode {  // 边表结点
    int adjvex; // 邻接点域，存储该顶点对应的下标
    int weight; // 用于存储权值，对于非网图可以不需要
    struct EdgeNode* next; // 键域，指向下一个邻接点
}EdgeNode;
typedef struct VertexNode {  // 顶点表结点
        int in;  // 顶点入度
        int data;  // 顶点域，存储顶点信息
        EdgeNode *firstedge;  // 边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges;  // 图中当前顶点数和边数
}graphAdjList, * GraphAdjList;

具体代码

Status TopologicalSort(GraphAdjList GL) {
    EdgeNode* e;
    int i, k, gettop;
    int top = 0;  // 用于栈指针下标
    int count = 0;  // 用于统计输出顶点的个数
    int* stack;  // 建栈存储入度为0的顶点
    stack = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i<GL ->numVertexes; i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;  // 将入度为0的顶点入栈
    while (top != 0) {
        gettop = stack[top--]; // 出栈
        printf("%d -> ", GL->adjList[gettop].data);  // 打印此顶点
        count++;  // 统计输出顶点数
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {  // 对此顶点弧表遍历
            k = e->adjvex;
            if (!(--GL->adjList[k].in))  // 将k号顶点邻接点的入度减1
                stack[++top] = k;  // 若为0则入栈，以便于下次循环输出
        }
    }
    if (count < GL->numVertexes)  // 如果 count 小于顶点数，说明存在环
        return ERROR;
    else
        return OK;
    }

6.8 关键路径

拓扑排序主要是解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为 AOE 网

路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

7 查找

7.1 查找概论

查找表是由同一类型的数据元素（或记录）构成的集合

关键字是数据元素中某个数据项的值。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字。对于那些可以识别多个数据元素(或记 )的关键字，我们称为次关键字

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

查找表按照操作方式来分有两大种：静态查找表和动态查找表

静态查找表：只作查找操作的查找表。它的主要操作有：

• 查询某个”特定的”数据元素是否在查找表中。

• 检索某个”特定的”数据元素和各种属性。

动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个：

• 查找时插入数据元素。

• 查找时删除数据元素。

7.2 顺序表查找

要针对这一线性表进行查找操作，因此它就是静态查找表

顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功

7.2.1 顺序表查找算法

// 顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字
int Seguential_Search(int* a, int n, int key) {
    int i;
    for (i = 1; i <= n; i++) {
        if (a[i J == key)
            return i;
    }
    return 0;
}

7.2.2 顺序表查找优化

// 有哨兵顺序查找
int Sequential_Search2(int* a, int n, int key) {
    int i;
    a[0] = key;  // 设置a[0]为关键字值，我们称之为"哨兵"
    i = n;  // 循环从数组尾部开始
    while (a[i] != key) {
        i--;
    }
    return i;  // 返回0则说明查找失败
}

7.3 有序表查找

7.3.1 折半查找

折半查找技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是:在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止

// 折半查找
int Binaxy_Search(int* a, int n, int key) {
    int low, high, mid;
    low = 1;  // 定义最低下标为记录首位
    high = n;
    while (low <= high) {
        mid = (low + high) / 2;  // 折半
        if (key < a[mid])  // 若查找值比中值小
            high = mid - 1;  // 最高下标调整到中位下标大一位
        else if (key > a[mid])  // 若查找值比中值大
            low = mid + 1;  // 最低下标调整到中位下标大一位
        else
            return mid;  // 若相等则说明 mid 即为查找到的位置
    }
    return 0;
}

7.3.2 插值查找

根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法。

7.3.3 斐波那契查找

利用黄金分割原理实现

7.4 线性索引查找

7.4.1 稠密索引

稠密索引中的索引项一定是按照关键码有序的排列

7.4.2 分块索引

7.4.3 倒排索引

其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引。

7.5 二叉排序树

二叉排序树，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值
• 若它的右子树不空 ，则右子树上所有结点的值均大于它的根结点的值
• 它的左右子树也分别为二叉排序树

7.6 平衡二叉树

7.7 多路查找树（B树）

7.8 散列表查找

hash

8 排序

// 求各排序算法的绝对执行时间
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MaxSize 50001
typedef int KeyType;

// 基础函数
void swap(KeyType& x, KeyType& y) {
    KeyType tmp = x;
    x = y;
    y = tmp;
}

void initial(int R[], int low, int high) {
    int i;
    srand((unsigned)time(NULL));
    for (i = low; i < high; i++)
        R[i] = rand() % 99 + 1;
}

void copy(int R[], int R1[], int n) {
    for (int i = 0; i < n; i++)
        R1[i] = R[i];
}
void copy1(int R[], int R1[], int n) {
    for (int i = 0; i < n; i++)
        R1[i+1] = R[i];
}

bool test(KeyType R[], int low, int high) {
    int i;
    for (i = low; i < high - 1; i++)
        if (R[i] > R[i + 1])
            return false;
    return true;
}

//直接插入排序
void InsertSort(KeyType R[], int n) {
    int i, j;
    KeyType tmp;
    for (i = 1; i < n; i++) {
        if (R[i] < R[i - 1]) {
            tmp = R[i];
            j = i - 1;
            do {
                R[j + 1] = R[j];
                j--;
            } while (j >= 0 && R[j] > tmp);
            R[j + 1] = tmp;
        }
    }
}

void InsertSortTime(KeyType R[], int n) {
    clock_t t;
    printf("直接插入排序\t");
    t = clock();
    InsertSort(R, n);
    t = clock() - t;
    printf("%lf秒", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");
}

// 折半插入排序
void BinInsertSort(KeyType R[], int n) {
    int i, j, low, high, mid;
    KeyType tmp;
    for (i = 1; i < n; i++) {
        if (R[i] < R[i - 1]) {
            tmp = R[i];
            low = 0;
            high = i - 1;
            while (low <= high) {
                mid = (low + high) / 2;
                if (tmp < R[mid])
                    high = mid -1
                    ;
                else
                    low = mid + 1;
            }
            for (j = i - 1; j >= high + 1; j--)
                R[j + 1] = R[j];
            R[high + 1] = tmp;
        }
    }
}

void BinInsertSortTime(KeyType R[], int n) {
    clock_t t;
    printf("折半插入排序\t");
    t = clock();
    BinInsertSort(R, n);
    t = clock() - t;
    printf("%lf秒", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");
}

// 希尔排序算法
void ShellSort(KeyType R[], int n) {
    int i, j, d;
    KeyType tmp;
    d = n / 2;
    while (d > 0) {
        for (i = d; i < n; i++) {
            tmp = R[i];
            j = i - d;
            while (j >= 0 && tmp < R[j]) {
                R[j + d] = R[j];
                j = j - d;
            }
            R[j + d] = tmp;
        }
        d = d / 2;
    }
}

void ShellSortTime(KeyType R[],int n)
{
    clock_t t;
    printf("希尔排序\t");
    t = clock();
    ShellSort(R, n);
    t = clock()-t;
    printf("%lf秒", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");

}
//冒泡排序
void BubbleSort(KeyType R[], int n)
{
    int i, j;
    bool exchange;
    for (i = 0; i < n - 1; i++)
    {
        exchange = false;
        for(j=n-1;j>i;j--)
            if (R[j] < R[j - 1])
            {
                swap(R[j], R[j - 1]);
                exchange = true;
            }
        if (!exchange)
            return;
    }
}
void BubbleSortTime(KeyType R[], int n)
{
    clock_t t;
    printf("冒泡排序\t");
    t = clock();
    BubbleSort(R, n);
    t = clock() - t;
    printf("%lf秒", ((float)t )/ CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");
}
//快速排序
int partition(KeyType R[], int s, int t)
{
    int i = s, j = t;
    KeyType tmp = R[i];
    while (i < j)
    {
            while (j > i && R[j] >= tmp)
                j--;
        R[i] = R[j];
        while (i < j && R[i] <= tmp)
            i++;
        R[j] = R[i];
    }
    R[i] = tmp;
    return i;
}

void QuickSort(KeyType R[], int s, int t)
{
    int i;
    if (s < t)
    {
        i = partition(R, s, t);
        QuickSort(R, s, i - 1);
        QuickSort(R, i + 1, t);
    }
}

void QuickSortTime(KeyType R[], int n)
{
    clock_t t;
    printf("快速排序\t");
    t = clock();
    QuickSort(R, 0, n - 1);
    t = clock()-t;
    printf("%lf", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");
}
//简单选择排序
void SelectSort(KeyType R[], int n)
{
    int i, j, k;
    for (i = 0; i < n - 1; i++)
    {
        k = i;
        for (j = i + 1; j < n; j++)
            if (R[j] < R[k])
                k = j;
        if (k != 1)
            swap(R[i], R[k]);

    }
}

void SelectSortTime(KeyType R[], int n)
{
    clock_t t;
    printf("简单选择排序\t");
    t = clock();
    SelectSort(R, n);
    t = clock() - t;
    printf("%lf秒", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");
}
//堆排序
void sift(KeyType R[], int low, int high)
{
    int i = low, j = 2 * i;
    KeyType tmp = R[i];
    while (j <= high)
    {
        if (j < high && R[j] < R[j + 1])
            j++;
        if (tmp < R[j])
        {
            R[i] = R[j];
            i = j;
            j = 2 * i;
        }
        else break;
    }
    R[i] = tmp;
}

void HeapSort(KeyType R[], int n)
{
    int i;
    for (i = n / 2; i >= 1; i--)
        sift(R, i, n);
    for (i = n; i >= 2; i--)
    {
        swap(R[1], R[i]);
        sift(R, 1, i - 1);

    }
}

void HeapSortTime(KeyType R[], int n)
{
    clock_t t;
    printf("堆排序  \t");
    t = clock();
    HeapSort(R, n);
    t = clock() - t;
    printf("%lf秒", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 1, n))
        printf("\t正确\n");
    else
        printf("\t错误\n");
}
//二路归并排序
void Merge(KeyType R[], int low, int mid, int high)
{
    KeyType* R1;
    int i = low, j = mid + 1, k = 0;
    R1 = (KeyType*)malloc((high - low + 1) * sizeof(KeyType));
    while (i <= mid && j <= high)
        if (R[i] <= R[j])
        {
            R1[k] = R[i];
            i++; k++;
        }
        else
        {
            R1[k] = R[j];
            j++; k++;
        }
    while (i <= mid)
    {
        R1[k] = R[i];
        i++; k++;
    }
    while (j <= high)
    {
        R1[k] = R[j];
        j++; k++;
    }
    for (k = 0, i = low; i <= high; k++, i++)
        R[i] = R1[k];
    free(R1);
}

void MergePass(KeyType R[], int length, int n)
{
    int i;
    for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length )
        Merge(R, i, i + length - 1, i + 2 * length - 1);
    if (i + length - 1 < n - 1)
        Merge(R, i, i + length - 1, n - 1);
}

void MergeSort(KeyType R[], int n)
{
    int length;
    for (length = 1; length < n; length = 2 * length)
        MergePass(R, length, n);
}

void MergeSortTime(KeyType R[], int n)
{
    clock_t t;
    printf("二路归并排序  \t");
    t = clock();
    MergeSort(R, n);
    t = clock() - t;
    printf("%lf秒", ((float)t) / CLOCKS_PER_SEC);
    if (test(R, 0, n - 1))
        printf("\t正确\n");
    else
        printf("\t错误\n");

}

int main()
{
    KeyType R[MaxSize], R1[MaxSize];
    printf("随机产生50000个1-99的正整数，各种排序方法的比较\n");
    int n = 50000;
    printf("---------------------------------------------------\n");
    printf("排序方法         用时       结果验证\n");
    printf("---------------------------------------------------\n");
    initial(R, 0, n - 1);
    copy(R, R1, n);
    InsertSortTime(R1, n);
    copy(R, R1, n);
    BinInsertSortTime(R1, n);
    copy(R, R1, n);
    ShellSortTime(R1, n);
    copy(R, R1, n);
    BubbleSortTime(R1, n);
    copy(R, R1, n);
    QuickSortTime(R1, n);
    copy(R, R1, n);
    SelectSortTime(R1, n);
    copy(R, R1, n);
    HeapSortTime(R1, n);
    copy(R, R1, n);
    MergeSortTime(R1, n);
    printf("-------------------------------------------\n");
    return 1;
}