博客

大家好，我是晴天学长，这马上就到了一学一度的期末考试了，刚好这学期学习了数据结构，我做在老师的知识范围内做了一个总结，需要的小伙伴自取哦，想要word版的小伙伴可以一键三连（点赞+评论+关注），私聊我💪💪💪

第一章：

（1）算法的定义及相关（特性、效率、衡量好的算法的标准：时间复杂度等）

1.1定义：

算法是一组解决特定问题的明确指令，是一种计算机程序或计算的描述。

1.2特性：

算法具有以下特性：

输入和输出：算法应该明确输入和输出的内容，以便能够正确地解决问题。

确定性：算法中每一步操作都应该是确定的、无歧义的，以便能够得到唯一的输出结果。

有限性：算法必须在执行有限的步骤后终止，不能无限循环或死循环。

可行性：算法应该是可行的，能够在有限的时间和空间内完成计算。

1.3效率：

算法的效率是指算法在计算问题时所需的时间和空间资源。

1.4衡量好的算法的标准

衡量好的算法的标准包括时间复杂度和空间复杂度。

时间复杂度是指算法执行所需的时间量级，通常用大O符号表示。对于一个算法来说，其时间复杂度越低，执行所需的时间就越少，效率越高。常见的时间复杂度有常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n

^{2)、立方阶O(n}

3)等。

空间复杂度是指算法执行所需的空间量级，也通常用大O符号表示。对于一个算法来说，其空间复杂度越低，所需的内存空间就越少，效率越高。常见的空间复杂度有常数阶O(1)、线性阶O(n)、平方阶O(n^2)等。

因此，在设计算法时，我们应该尽可能地降低时间复杂度和空间复杂度，以获得更高的效率和更好的性能。

（2）数据结构的定义、术语及关系

2.1定义：

数据结构是指数据的逻辑结构和物理结构。逻辑结构是指数据元素之间的逻辑关系，包括线性结构、树形结构和图形结构等；物理结构则是指数据在计算机内的存储方式，包括顺序存储和链式存储等。

2.2术语：

数据元素：数据结构中的基本单位，通常是指一个数据项。

数据项：数据元素中具体的数据内容，可以是一个数字、一个字符或一个对象等。

数据结构：数据元素之间的组织方式，通常包括线性结构、树形结构和图形结构等。

线性结构：数据元素之间存在一对一的关系，常见的线性结构有数组、链表、栈和队列等。

树形结构：数据元素之间存在一对多的关系，常见的树形结构有二叉树、多叉树、堆和哈希表等。

图形结构：数据元素之间存在多对多的关系，通常用来描述复杂的实际问题，比如社交网络中的用户关系、路网中的道路连接等。

算法：操作数据结构的具体步骤，用来实现对数据的增删改查等操作。

2.3关系：

数据结构和算法之间存在密切的关系，数据结构提供了数据的存储和组织方式，而算法则是对数据进行操作的具体步骤。

第二章：（大题）

（1）线性表的逻辑结构、存储结构

1.1逻辑结构：

线性表是一种逻辑结构，它是由n个数据元素（可以是任意类型）组成的有限序列。这些数据元素按照线性的顺序排列，并且每个元素最多只有一个直接前驱和一个直接后继。

线性表具有以下特点：

元素个数有限：线性表中的元素个数是有限的，且每个元素都可以通过一个唯一的序号来访问。

有序性：线性表中的元素按照一定的顺序排列，每个元素都有一个唯一的前驱和后继。

可以为空：线性表中的元素个数可以为0，此时表被称为空表。

1.2存储结构：

线性表的存储方式有两种：顺序存储和链式存储。

顺序存储：线性表的顺序存储是指将所有的元素按照线性顺序依次存放在一段连续的存储空间中。在顺序存储中，每个元素都可以通过下标来访问，因此支持随机访问，但插入、删除操作需要移动大量元素，效率较低。

链式存储：线性表的链式存储是指将所有的元素存放在任意的存储空间中，通过指针来表示元素之间的关系。在链式存储中，每个元素都包含一个数据域和一个指针域，指针域指向下一个元素的存储位置，因此支持快速的插入和删除操作，但不支持随机访问。

顺序存储和链式存储具有各自的优缺点，在实际应用中需要根据具体情况选择适合的存储方式。

（2）顺序表、链表的表示及优、缺点及使用情况

1.1顺序表的表示：

顺序表是一种线性表的存储方式，它的每个元素都存储在一段连续的存储空间中，可以通过下标来随机访问元素。顺序表通常用数组来实现，数组的下标就是顺序表中元素的位置。

1.2顺序表的优点：

（1）支持随机访问：顺序表中的元素都存储在一段连续的存储空间中，因此可以通过下标来直接访问任意一个元素。

（2）空间利用率高：顺序表中的元素都存储在一段连续的存储空间中，因此不需要额外的指针空间来维护元素之间的关系，空间利用率较高。

1.3顺序表的缺点：

（1）插入、删除操作效率低：在顺序表中插入或删除一个元素时，需要将其它元素向后或向前移动，效率较低。

（2）空间不易动态调整：顺序表的存储空间是静态分配的，因此在创建时需要预先分配一定的空间，如果后续需要存储更多的元素，就需要重新分配更大的空间。

1.4顺序表的使用情况

顺序表适用于元素个数比较小、固定不变或者元素的插入、删除操作较少、随机访问较多的情况。比如，静态的配置表、查找表等。

2.1链表的表示

链表是一种线性表的存储方式，它的每个元素都包含一个数据域和一个指针域，指针域指向下一个元素的存储位置，通过指针来表示元素之间的关系。链表分为单向链表、双向链表、循环链表等多种形式。

2.2链表的优点

（1）插入、删除操作效率高：在链表中插入或删除一个元素时，只需要改变相邻两个元素之间的指针，效率较高。

（2）空间易于动态调整：链表的存储空间是动态分配的，可以根据需要动态增加或减少存储空间。

2.3链表的缺点

（1）不支持随机访问：在链表中访问一个元素时，需要从头节点开始依次遍历，效率较低。

（2）空间利用率较低：链表中每个元素都需要一个指针域来指向下一个元素的存储位置，因此空间利用率较低。

2.4链表的使用情况

链表适用于元素个数动态变化、插入、删除操作较多、随机访问较少的情况。比如，图的表示、计算器程序的计算等。

（3）顺序表、单链表（头插法、尾插法、插入、删除等）的操作算法实现

    顺序表
    （1）顺序表的初始化： 
    void init(SeqList&L){
    L.length=0;  // 初始化顺序表的长度为0
    }
    （2）顺序表的插入：
    bool insert(SeqList&L,int pos,int val){
    if(pos< 1||pos>L.length+1||L.length==MAXSIZE){ // 判断插入位置是否合法，以及顺序表是否已满
    return false;
    }
    for(int i=L.length;i>=pos;i--){ // 将pos位置之后的元素依次向后移动一位
    L.data[i]=L.data[i-1];
    }
    L.data[pos-1]=val; // 在pos位置插入元素
    L.length++; // 顺序表长度加1
    return true;
    }
    （3）顺序表的删除：
    bool del(SeqList&L,int pos){
    if(pos< 1||pos>L.length){ // 判断删除位置是否合法
    return false;
    }
    for(int i=pos;i<L.length;i++){ // 将pos位置之后的元素依次向前移动一位
    L.data[i-1]=L.data[i];
    }
    L.length--; // 顺序表长度减1
    return true;
    }
    单链表（头插法、尾插法、插入、删除）
    （1）单链表的初始化：
    void init(LinkList&L){
    L=NULL; // 初始化链表为空链表
    }
    （2）单链表的头插法：
    void headInsert(LinkList&L,int val){
    ListNode*p=new ListNode(val);
    p->next=L;
    L=p;
    }
    （3）单链表的尾插法：
    void tailInsert(LinkList&L,int val){
    if(L==NULL){ // 如果链表为空，直接插入
    L=new ListNode(val);
    }else{
    ListNode*p=L;
    while(p->next!=NULL){ // 找到链表的最后一个节点
    p=p->next;
    }
    p->next=new ListNode(val); // 在最后一个节点后插入新的节点
    }
    }
    （4）单链表的插入:
    bool insert(LinkList&L,int pos,int val){
    if(pos< 1){ // 判断插入位置是否合法
    return false;
    }
    ListNode*p=L;
    int i=1;
    while(p!=NULL&&i<pos){ // 找到插入位置的前一个节点
    p=p->next;
    i++;
    }
    if(p==NULL){ // 如果插入位置超出了链表的长度，则插入失败
    return false;
    }
    ListNode*q=new ListNode(val); // 创建新节点
    q->next=p->next; // 将新节点插入到链表中
    p->next=q;
    return true;
    }
    （5）单链表的删除：
    bool del(LinkList&L,int pos){
    if(pos< 1){ // 判断删除位置是否合法
    return false;
    }
    ListNode*p=L;
    int i=1;
    while(p!=NULL&&i<pos){ // 找到删除位置的前一个节点
    p=p->next;
    i++;
    }
    if(p==NULL||p->next==NULL){ // 如果删除位置超出了链表的长度，则删除失败
    return false;
    }
    ListNode*q=p->next; // 将删除节点从链表中删除
    p->next=q->next;
    delete q;
    return true;
    }

第三章：

(1)栈和队列的表示和特点

1.1栈的表示和特点

栈是一种只允许在一端进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。栈的插入操作叫做入栈（push），删除操作叫做出栈（pop）。栈的特点如下：

（1）后进先出：栈的元素入栈和出栈都是在栈顶进行的，所以最后入栈的元素最先出栈。

（2）限制性：栈只允许在栈顶进行插入和删除操作，不支持随机访问，因此具有一定的限制性。

栈可以用数组或链表来实现，数组实现的栈叫做顺序栈，链表实现的栈叫做链式栈。

1.2队列的表示和特点

队列是一种只允许在队尾进行插入操作，在队头进行删除操作的线性表，队列的插入操作叫做入队（enqueue），删除操作叫做出队（dequeue）。队列的特点如下：

（1）先进先出：队列的元素入队和出队都是在队头和队尾进行的，所以最先入队的元素最先出队。

（2）限制性：队列只允许在队尾进行插入操作，在队头进行删除操作，不支持随机访问，因此具有一定的限制性。

队列可以用数组或链表来实现，数组实现的队列叫做顺序队列，链表实现的队列叫做链式队列。队列还有一种循环队列的实现方式，可以有效地避免队列满时的空间浪费问题。

(2)栈和队列的实现

栈的实现

（1）顺序栈的实现：

使用数组实现顺序栈，需要定义一个栈顶指针 top，初始值为 -1，表示栈为空。入栈操作就是将元素插入到 top+1 的位置，然后将 top 加 1；出栈操作就是将 top 对应位置的元素弹出，然后将 top 减 1。下面是部分代码实现：

#define MAXSIZE 100 // 定义栈的最大长度

    typedef struct {
    int data[MAXSIZE];
    int top; // 栈顶指针
    } SeqStack;

    void initStack(SeqStack &S) {
    S.top = -1; // 初始化栈顶指针为-1
    }

    bool push(SeqStack &S, int val) {
    if (S.top == MAXSIZE - 1) { // 栈满，插入失败
    return false;
    }
    S.top++;
    S.data[S.top] = val; // 将元素插入到栈顶
    return true;
    }

    bool pop(SeqStack &S, int &val) {
    if (S.top == -1) { // 栈空，弹出失败
    return false;
    }
    val = S.data[S.top]; // 将栈顶元素弹出
    S.top--;
    return true;
    }
    （2）链式栈的实现：

    使用链表实现链式栈，需要定义一个栈顶指针 top，初始值为 NULL，表示栈为空。入栈操作就是将新元素插入到链表的头部，然后将 top 指向新节点；出栈操作就是将 top 对应的节点弹出，然后将 top 指向下一个节点。下面是部分代码实现：
    typedef struct ListNode {
    int val;
    struct ListNode *next;
    } ListNode;

    typedef struct {
    ListNode *top; // 栈顶指针
    } LinkedStack;

    void initStack(LinkedStack &S) {
    S.top = NULL; // 初始化栈顶指针为null
    }

    bool push(LinkedStack &S, int val) {
    ListNode *p = new ListNode;
    p->val = val; // 创建新节点
    p->next = S.top; // 将新节点插入到链表头部
    S.top = p; // 更新栈顶指针
    return true;
    }

    bool pop(LinkedStack &S, int &val) {
    if (S.top == NULL) { // 栈空，弹出失败
    return false;
    }
    ListNode *p = S.top; // 将栈顶元素弹出
    val = p->val;
    S.top = p->next; // 更新栈顶指针
    delete p; // 释放节点内存
    return true;
    }
    队列的实现
    （1）顺序队列的实现：

    使用数组实现顺序队列，需要定义一个队头指针 front 和一个队尾指针 rear，初始值都为 0，表示队列为空。入队操作就是将元素插入到 rear+1 的位置，然后将 rear 加 1；出队操作就是将 front 对应位置的元素弹出，然后将 front 加 1。下面是部分代码实现：
    #define MAXSIZE 100 // 定义队列的最大长度

    typedef struct {
    int data[MAXSIZE];
    int front, rear; // 队头指针和队尾指针
    } SeqQueue;

    void initQueue(SeqQueue &Q) {
    Q.front = Q.rear = 0; // 初始化队头指针和队尾指针都为0
    }

    bool enqueue(SeqQueue &Q, int val) {
    if (Q.rear == MAXSIZE) { // 队满，插入失败
    return false;
    }
    Q.data[Q.rear] = val; // 将元素插入到队尾
    Q.rear++;
    return true;
    }

    bool dequeue(SeqQueue &Q, int &val) {
    if (Q.front == Q.rear) { // 队空，弹出失败
    return false;
    }
    val = Q.data[Q.front]; // 将队头元素弹出
    Q.front++;
    return true;
    }
    （2）链式队列的实现：

    使用链表实现链式队列，需要定义一个队头指针 front 和一个队尾指针 rear，初始值都为 NULL，表示队列为空。入队操作就是将新元素插入到链表的尾部，然后将 rear 指向新节点；出队操作就是将 front 对应的节点弹出，然后将 front 指向下一个节点。下面是部分代码实现：
    typedef struct ListNode {
    int val;
    struct ListNode *next;
    } ListNode;

    typedef struct {
    ListNode *front, *rear; // 队头指针和队尾指针
    } LinkedQueue;

    void initQueue(LinkedQueue &Q) {
    Q.front = Q.rear = NULL; // 初始化队头指针和队尾指针都为null
    }

    bool enqueue(LinkedQueue &Q, int val) {
    ListNode *p = new ListNode;
    p->val = val; // 创建新节点
    p->next = NULL;
    if (Q.rear == NULL) { // 队列为空，插入新节点
    Q.front = Q.rear = p;
    } else {
    Q.rear->next = p; // 将新节点插入到链表尾部
    Q.rear = p; // 更新队尾指针
    }
    return true;
    }

    bool dequeue(LinkedQueue &Q, int &val) {
    if (Q.front == NULL) { // 队空，弹出失败
    return false;
    }
    ListNode *p = Q.front; // 将队头元素弹出
    val = p->val;
    Q.front = p->next; // 更新队头指针
    if (Q.rear == p) { // 如果队头元素是队列中唯一的元素，更新队尾指针
    Q.rear = NULL;
    }
    delete p; // 释放节点内存
    return true;
    }
    循环队列的实现
    循环队列是一种通过将队列头尾相连来避免队列满时的空间浪费的队列实现方式。它可以使用数组来实现，需要定义一个数组和两个指针 front 和 rear，分别指向队头和队尾元素的位置。入队操作就是将元素插入到 rear 的位置，然后将 rear 指向下一个位置（如果数组下标越界，则将 rear 指向 0）；出队操作就是将 front 对应位置的元素弹出，然后将 front 指向下一个位置（如果数组下标越界，则将 front 指向 0）。下面是部分代码实现：
    #define MAXSIZE 100 // 定义队列的最大长度

    typedef struct {
    int data[MAXSIZE];
    int front, rear; // 队头指针和队尾指针
    } CircularQueue;

    void initQueue(CircularQueue &Q) {
    Q.front = Q.rear = 0; // 初始化队头指针和队尾指针都为0
    }

    bool enqueue(CircularQueue &Q, int val) {
    if ((Q.rear + 1) % MAXSIZE == Q.front) { // 队满，插入失败
    return false;
    }
    Q.data[Q.rear] = val; // 将元素插入到队尾
    Q.rear = (Q.rear + 1) % MAXSIZE; // 更新队尾指针
    return true;
    }

    bool dequeue(CircularQueue &Q, int &val) {
    if (Q.front == Q.rear) { // 队空，弹出失败
    return false;
    }
    val = Q.data[Q.front]; // 将队头元素弹出
    Q.front = (Q.front + 1) % MAXSIZE; // 更新队头指针
    return true;
    }

(3)循环队列的队空、队满的判断条件

循环队列是一种通过将队列头尾相连来避免队列满时的空间浪费的队列实现方式。循环队列的队空和队满状态可以根据队头和队尾指针的位置关系来判断。

1.1队空状态判断条件：

当队头指针 front 等于队尾指针 rear 时，队列为空。

1.2队满状态判断条件：

当队尾指针 rear 等于队头指针 front 的下一个位置时，队列为满。因为循环队列是通过将队列头尾相连来避免队列满时的空间浪费的，因此当 rear 指向数组最后一个位置时，下一个位置应该是数组的第一个位置，即 0。因此队满状态的判断条件为：

rear + 1 % MAXSIZE == front

其中，MAXSIZE 是数组的长度。

第四章

(1)串的定义、表示、特点

1.1串的定义

串是由零个或多个字符组成的有限序列，通常用来表示文本中的一段字符串。

1.2串的表示

表示串的常用方式有两种：顺序存储和链式存储。

（1）顺序存储

顺序存储是将串中的每个字符按照顺序存储在一段连续的存储空间中，通常使用数组来实现。例如，下面是一个用数组存储的字符串 “hello world”：

char str[] = {‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ’ ‘, ‘w’, ‘o’, ‘r’, ‘l’, ‘d’, ‘\0’};

其中，’\0’ 表示字符串的结束符，它的 ASCII 码为 0。

（2）链式存储

链式存储是将串中的每个字符存储在一个节点中，通过节点之间的指针链接起来形成一个链表。例如，下面是一个用链表存储的字符串 “hello world”：

typedef struct ListNode {


char data;

struct ListNode *next;

} ListNode;

ListNode *str = new ListNode;

str->data = ‘h’;

str->next = new ListNode;

str->next->data = ‘e’;

str->next->next = new ListNode;

str->next->next->data = ‘l’;

str->next->next->next = new ListNode;

str->next->next->next->data = ‘l’;

str->next->next->next->next = new ListNode;

str->next->next->next->next->data = ‘o’;

str->next->next->next->next->next = new ListNode;

str->next->next->next->next->next->data = ’ ‘;

str->next->next->next->next->next->next = new ListNode;

str->next->next->next->next->next->next->data = ‘w’;

str->next->next->next->next->next->next->next = new ListNode;

str->next->next->next->next->next->next->next->data = ‘o’;

str->next->next->next->next->next->next->next->next = new ListNode;

str->next->next->next->next->next->next->next->next->data = ‘r’;

str->next->next->next->next->next->next->next->next->next = new ListNode;

str->next->next->next->next->next->next->next->next->next->data = ‘l’;

str->next->next->next->next->next->next->next->next->next->next = new ListNode;

str->next->next->next->next->next->next->next->next->next->next->data = ‘d’;

str->next->next->next->next->next->next->next->next->next->next->next = NULL;

1.3串的特点

串的特点主要在于：

（1）串是由字符组成的有限序列，长度可以为 0；

（2）串的字符集合可以是任意的，例如 ASCII 码、Unicode 码等；

（3）串的插入、删除、替换等操作比较耗时，因为需要移动其他字符；

（4）串的匹配操作是比较常用的操作，例如字符串匹配、模式匹配等。

(2)串的模式匹配

串的模式匹配指的是在一个主串中查找一个模式串出现的位置，常见的算法有暴力匹配算法、KMP 算法和 Boyer-Moore 算法。

1.1暴力匹配算法

暴力匹配算法也称为朴素匹配算法，它的基本思想是从主串的第一个字符开始，依次比较主串和模式串的每个字符，如果匹配失败，则从下一个字符开始重新匹配。时间复杂度为 O(mn)，其中 m 和 n 分别是模式串和主串的长度。

1.2KMP 算法

KMP 算法是一种优化的字符串匹配算法，它的核心思想是利用已经匹配成功的信息，尽可能减少比较次数。具体来说，算法维护一个 next 数组，用来存储模式串的前缀和后缀的最长公共子串长度，然后根据 next 数组来决定下一步匹配的位置。时间复杂度为 O(m+n)。

1.3Boyer-Moore 算法

Boyer-Moore 算法是一种高效的字符串匹配算法，它对模式串和主串从右往左比较，利用了坏字符规则和好后缀规则来减少比较次数。具体来说，算法会先预处理出模式串中每个字符最后一次出现的位置，然后从模式串的末尾开始匹配，当匹配失败时，根据坏字符规则和好后缀规则来决定下一步匹配的位置。时间复杂度为 O(mn) 的最坏情况下，但在实际应用中通常能够达到线性时间复杂度。

(3)二维数组的顺序存储方式（按行、按列优先存储）

二维数组是由多行多列的元素组成的数据结构，可以通过顺序存储方式来实现。常见的顺序存储方式有按行优先存储和按列优先存储两种。

1.1按行优先存储

按行优先存储是指将二维数组的每一行依次存储在一段连续的存储空间中，例如：

int a[3][4] = {


{1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12}

};

    int b[12] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    在按行优先存储的方式中，相邻的两个元素在内存中的地址是连续的，因此可以通过一维数组来实现。二维数组的元素 a[i][j] 可以通过下标 b[i * n + j] 来访问，其中 n 是数组的列数。

1.2按列优先存储

按列优先存储是指将二维数组的每一列依次存储在一段连续的存储空间中，例如：

int a[3][4] = {


{1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12}

};

int b[12] = {1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12};

在按列优先存储的方式中，相邻的两个元素在内存中的地址不一定是连续的，因此需要使用一定的计算来访问二维数组的元素。二维数组的元素 a[i][j] 可以通过下标 b[j * m + i] 来访问，其中 m 是数组的行数。

(4)稀疏矩阵的三元组表的存储表示

稀疏矩阵是指大部分元素为零的矩阵，因此使用三元组表可以有效地压缩存储空间。三元组表是将矩阵中所有非零元素的行列坐标及其值存储在一个三元组序列中，常用于稀疏矩阵的存储表示。

三元组表的定义如下：

    typedef struct {
    int row;  // 非零元素所在的行号
    int col;  // 非零元素所在的列号
    int val;  // 非零元素的值
    } Triple;

    typedef struct {
    Triple data[MAXSIZE+1];  // 非零元素三元组表，下标从 1 开始
    int rows;                // 矩阵的行数
    int cols;                // 矩阵的列数
    int nums;                // 非零元素的个数
    } TSMatrix;
    其中，MAXSIZE 是三元组表的最大容量，可以根据实际情况进行设置。TSMatrix 结构体中的 rows 和 cols 分别表示矩阵的行数和列数，nums 表示非零元素的个数，data 数组存储了所有非零元素的三元组。

    例如，一个 4x5 的稀疏矩阵：
    0 0 0 0 0
    5 8 0 0 0
    0 0 3 0 0
    0 6 0 0 0
    可以表示为以下三元组表：
    (2, 1, 5), (2, 2, 8), (3, 3, 3), (4, 2, 6)
    其中，第一个三元组表示第 2 行第 1 列的元素为 5，第二个三元组表示第 2 行第 2 列的元素为 8，以此类推。

(5)特殊矩阵的压缩存储

特殊矩阵是指具有一定特殊性质的矩阵，例如对称矩阵、三对角矩阵、对角矩阵等。这些矩阵通常具有比较规律的结构，因此可以使用压缩存储方式来节省存储空间和提高运算效率。

1.1对称矩阵的压缩存储

对称矩阵是指满足 A[i][j] = A[j][i] 的矩阵，它的主对角线上方和下方的元素是完全对称的。因此，可以只存储矩阵的上三角或下三角部分，从而将一个 nn 的对称矩阵压缩为一个一维数组，其长度为 (n(n+1))/2。

以下三角存储为例，定义一个一维数组 a，其前 k 个元素存储矩阵的第一行到第 k 行的对角线元素和下三角部分元素，即 a[0] 存储 A[1][1]，a[1] 存储 A[2][1]，a[2] 存储 A[2][2]，a[k-1] 存储 A[k][k]，以此类推。从 a[k] 开始，存储矩阵下三角部分的非对角线元素，按照行优先顺序存储，即 a[k] 存储 A[2][1]，a[k+1] 存储 A[3][1]，a[k+2] 存储 A[3][2]，以此类推。

1.2三对角矩阵的压缩存储

三对角矩阵是指除了主对角线和其相邻的两条对角线上的元素外，其余元素都为零的矩阵。因此，可以只存储矩阵的主对角线和其相邻的两条对角线上的元素，从而将一个 n*n 的三对角矩阵压缩为一个一维数组，其长度为 3n-2。

定义一个一维数组 a，其前 n 个元素存储矩阵的主对角线上的元素，即 a[i-1] 存储 A[i][i]，以此类推。从 a[n] 开始，存储矩阵上方和下方相邻的对角线上的元素，按照从左到右、从上到下的顺序存储，即 a[n] 存储 A[i][i+1]，a[n+1] 存储 A[i+1][i]，以此类推。

1.3对角矩阵的压缩存储

对角矩阵是指除了主对角线上的元素外，其余元素都为零的矩阵。因此，可以只存储矩阵的主对角线上的元素，从而将一个 n*n 的对角矩阵压缩为一个一维数组，其长度为 n。

定义一个一维数组 a，其前 n 个元素存储矩阵的主对角线上的元素，即 a[i-1] 存储 A[i][i]，以此类推。其他元素都为零，不需要存储。

(6)广义表的存储、表头、表尾、长度和广度

广义表是由原子和广义表构成的一种递归结构，类似于树的结构，可以使用链式存储方式来表示。

1.1存储

广义表的链式存储结构可以使用一个结构体来表示，如下所示：

    typedef struct GLNode {
    int tag;              // 标志域，0 表示原子，1 表示子表
    union {
    AtomType atom;    // 原子结点的值域
    struct GLNode *hp; // 表结点的表头指针
    } hp;
    struct GLNode *tp;    // 表结点的表尾指针
    } GLNode, *GList;
    其中，tag 是标志域，用来区分广义表结点是原子结点还是子表结点，0 表示原子结点，1 表示子表结点。hp 是值域，当结点是原子结点时，hp 存储原子的值；当结点是子表结点时，hp 存储子表的表头指针。tp 是指向下一个结点的指针，当结点是子表结点时，tp 指向子表的表尾结点，即子表的下一个结点。

1.2表头和表尾

广义表的表头是指广义表中第一个元素，可以是原子或子表。广义表的表尾是指广义表中第一个元素之后的所有元素组成的广义表，也可以为空表。因此，可以使用 hp 和 tp 指针来表示广义表的表头和表尾。

1.3长度

广义表的长度是指广义表中元素的个数，可以通过递归遍历广义表来计算长度。如果当前结点是原子结点，则长度为 1；如果当前结点是子表结点，则长度为表头长度加表尾长度。

1.4广度

广义表的广度是指广义表中子表的个数，可以通过递归遍历广义表来计算广度。如果当前结点是原子结点，则广度为 0；如果当前结点是子表结点，则广度为 1 加上表头的广度和表尾的广度之和。

第五章

(1)树和二叉树的概念、术语

1.1树是一种非线性的数据结构

由若干个结点和它们之间的边组成。树中有一个特殊的结点，称为根节点，其他结点可以分为若干个互不相交的子树。一个节点可以有零个或多个子节点，同时每个子节点也可以有零个或多个子节点，因此树是一种递归的数据结构。

1.2二叉树是一种特殊的树

它的每个节点最多只有两个子节点，分别称为左子节点和右子节点。二叉树可以为空，也可以是一棵非空的树，其中每个非空节点都有左右两个子节点。二叉树具有以下特点：

    左子树和右子树是有顺序的，不能交换。

    即使树中某个节点只有一棵子树，也要区分它是左子树还是右子树。

    没有子节点的节点称为叶子节点或终端节点，其他节点称为非终端节点或分支节点。

    一个节点的左子树和右子树分别称为它的左子树和右子树。

    如果将二叉树中节点的左子树和右子树交换，得到的仍是原来的二叉树，称为镜像二叉树。

    在二叉树中，一个节点可以有零个、一个或两个子节点。如果一个节点只有一个子节点，那么这个子节点可以是左子节点或右子节点，但是不能同时是两个子节点。如果一个节点没有子节点，那么它就是叶子节点。

    在二叉树中，还有一些常用的术语：

    深度（Depth）：指从根节点到该节点的唯一路径上的节点数，根节点的深度为 0。

    高度（Height）：指从该节点到叶子节点的最长路径上的节点数，叶子节点的高度为 0。

    层数（Level）：指深度加 1，根节点的层数为 1。

    子树：一个节点及其所有的后代节点组成的树称为该节点的子树。

    祖先节点：从根节点到该节点路径上的所有节点。

    后代节点：该节点的子树中的所有节点。

    兄弟节点：具有同一个父节点的节点称为兄弟节点。

    满二叉树：每一层上的所有节点都有两个子节点，最后一层上的所有节点都是叶子节点。

    完全二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层上的节点都集中在左侧连续位置上。

(2)二叉树的性质（5个）

二叉树是一种特殊的树

其中每个节点最多只有两个子节点，分别称为左子节点和右子节点。二叉树具有以下性质：

性质一：二叉树的第 i 层上最多有 2^(i-1) 个节点。

    性质二：深度为 k 的二叉树最多有 2^k - 1 个节点。

    性质三：对于任意一棵二叉树，如果其叶子节点数为 n0，度为 2 的非叶子节点数为 n2，则 n0 = n2 + 1。

    性质四：具有 n 个节点的完全二叉树的深度为 floor(log2(n)) + 1，其中 floor 表示取整函数。

    性质五：对于一棵深度为 k，且有 2^k-1 个节点的二叉树，如果按照层次编号，则对于任意一个节点 i，其左子节点的编号为 2i，右子节点的编号为 2i+1，其父节点的编号为 i/2（向下取整）。

    这些性质对于二叉树的操作和分析非常重要，例如计算二叉树的深度、宽度、节点个数等，以及实现二叉树的遍历、搜索、插入、删除等操作。

(3)二叉树的基本形态（还可以是指定结点个数的情况）

二叉树可以有多种不同的形态，下面介绍几种常见的基本形态：

斜树：所有节点都只有左子节点或右子节点的二叉树称为斜树。如果所有节点都只有左子节点，则称为左斜树；如果所有节点都只有右子节点，则称为右斜树。斜树的形态类似于链表，因此它的深度等于节点数。

满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层上的所有节点都是叶子节点。满二叉树的节点数满足 2^k-1，其中 k 表示深度。

完全二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层上的节点都集中在左侧连续位置上。完全二叉树的深度为 log2(n)+1 或 log2(n)（向上取整），其中 n 表示节点个数。

    二叉搜索树：也称为二叉查找树，是一种特殊的二叉树，其中每个节点的值都大于其左子树中任意节点的值，小于其右子树中任意节点的值。二叉搜索树常用于实现快速查找、插入和删除操作。
    平衡二叉树：也称为自平衡二叉树，是一种特殊的二叉树，它的左右子树的高度差不超过 1。常见的平衡二叉树包括红黑树、AVL 树、B 树等，它们可以保证二叉树的操作时间复杂度为 O(log n)。
    如果要指定二叉树的节点个数，可以按照完全二叉树的形式构建二叉树，先构建满二叉树，然后在最后一层上依次添加节点，直到达到指定的节点个数。如果添加节点后破坏了二叉树的平衡性，可以进行相应的调整操作来保持平衡。

(4)二叉树的遍历（各种遍历方法的概念和区别；根据遍历序列，画出二叉树，或是根据二叉树写出遍历序列）

二叉树的遍历指的是按照一定的顺序遍历二叉树中的所有节点，遍历的顺序可以分为前序遍历、中序遍历和后序遍历。二叉树的遍历可以通过递归或栈来实现。

    前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。前序遍历的遍历顺序为根节点、左子树、右子树。

    中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。中序遍历的遍历顺序为左子树、根节点、右子树。

    后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。后序遍历的遍历顺序为左子树、右子树、根节点。

    层次遍历：从根节点开始，按照从上到下、从左到右的顺序遍历二叉树的所有节点。层次遍历可以通过队列来实现。

    下面通过一个例子来演示二叉树的遍历：

    假设有如下二叉树：
    1
    / \
    2   3
    / \    \
    4   5   6
    前序遍历：1 -> 2 -> 4 -> 5 -> 3 -> 6

    中序遍历：4 -> 2 -> 5 -> 1 -> 3 -> 6

    后序遍历：4 -> 5 -> 2 -> 6 -> 3 -> 1

    层次遍历：1 -> 2 -> 3 -> 4 -> 5 -> 6

    根据遍历序列画出二叉树的方法：

    假设给定二叉树的中序遍历和前序遍历序列，可以通过递归的方法重构二叉树。具体步骤如下：

    在前序遍历序列中，第一个节点为根节点。

    在中序遍历序列中，根节点左侧的所有节点都在二叉树的左子树中，右侧的所有节点都在右子树中。

    根据中序遍历序列中根节点的位置，可以确定二叉树的左子树和右子树的中序遍历序列。

    在前序遍历序列中，根节点后面的若干个节点对应左子树的前序遍历序列，剩余的节点对应右子树的前序遍历序列。

    对左右子树分别进行递归操作，重构整个二叉树。

    例如，给定如下二叉树的中序遍历和前序遍历序列：

    中序遍历：4 2 5 1 3 6

    前序遍历：1 2 4 5 3 6

    可以通过如下方式重构二叉树：
     1
    /  \
    2    3
    /  \    \
    4   5   6
    根据二叉树写出遍历序列的方法：

    遍历序列的输出顺序与具体的遍历方式有关，可以通过递归或栈的方式实现。例如，对于如下二叉树：
     1
    /  \
    2   3
        / \
       4   5
    前序遍历序列为：1 2 3 4 5

    中序遍历序列为：2 1 4 3 5

    后序遍历序列为：2 4 5 3 1

    层次遍历序列为：1 2 3 4 5

(5)树和二叉树的转换

（

详解

）

树和二叉树是两种不同的树形结构，它们之间可以相互转换。具体地，可以从一棵树构造出一棵二叉树，也可以从一棵二叉树构造出一棵树。

    从树转换为二叉树：

    将一棵任意的树转换为一棵二叉树的方法是，对于每个节点，将它的子节点按照从左到右的顺序连成一个链式结构，然后在这个链式结构上添加虚拟节点，将其转换为一棵二叉树。具体步骤如下：

    对于树中的每个节点，将它的所有子节点按照从左到右的顺序排列，形成一个链式结构。

    在链式结构中每个节点的右侧添加一个虚拟节点，表示它的兄弟节点。

    将链式结构转换为二叉树，对于每个节点，将其左侧的子节点作为左子节点，右侧的虚拟节点的左子节点作为右子节点。

    例如，将如下树转换为二叉树：


       1
     /  |  \
    2  3  4
    /|     |\
    5 6   7 8
    得到的二叉树如下所示：
       1
      /
     2
     / \
    5   6
        / \
       3   4
           / \
          7   8
    从二叉树转换为树：

    将一棵二叉树转换为一棵树的方法是，将二叉树中的右子树按照从左到右的顺序连接到左子树的最右侧节点上，然后递归地将左子树转换为树。具体步骤如下：

    对于每个节点，将其右子树中的所有节点按照从左到右的顺序连接到左子树的最右侧节点上。

    将根节点的左子树转换为树。

    例如，将如下二叉树转换为树：

       1
       / \
     2    3
    / \     \
    4   5   6
    得到的树如下所示：
       1
      /
     2
     / \
    4   5
       /
      3
       \
       6
    需要注意的是，二叉树转换为树的过程中，右子树会被完全压缩到左子树的最右侧节点上，因此得到的树可能不是平衡的。

(6)哈夫曼树（构造过程、带权路径长度）

哈夫曼树是一种特殊的二叉树，通常用来构建最优二叉树编码。它的构造方法是，对于给定的一组权值，通过贪心策略构建一棵满足最小带权路径长度的二叉树。

1.1构造哈夫曼树的步骤如下：

    将权值从小到大排序，得到一个有序的权值序列。

    选取权值最小的两个节点作为左右子节点，构造一棵二叉树，将它们的权值之和作为新节点的权值。

    将新节点插入到权值序列中，并将序列重新排序。

    重复步骤2和步骤3，直到序列中只剩下一个节点为止，得到的树即为哈夫曼树。

    例如，对于如下的权值序列：

  
    5 2 4 7 1
    构造哈夫曼树的过程如下：

    选取权值最小的1和2作为左右子节点，构造一棵二叉树，得到序列：
 
    4 5 7 3
    选取权值最小的3和4作为左右子节点，构造一棵二叉树，得到序列：
   
    5 7 7
    选取权值最小的5和7作为左右子节点，构造一棵二叉树，得到序列：

    12 7
    选取权值最小的7和12作为左右子节点，构造一棵二叉树，得到序列：
 
    19
    得到的哈夫曼树如下所示：

  
      19
      /  \
     7    12
     / \
    5   2
        / \
       4   1

1.2哈夫曼树的带权路径长度

每个叶节点的权值和其到根节点的路径长度的乘积之和。可以通过递归的方式计算哈夫曼树的带权路径长度。具体步骤如下：

    如果当前节点是叶节点，则返回该节点的权值乘以路径长度。

    如果当前节点不是叶节点，则返回左子树和右子树的带权路径长度之和。

    例如，对于上面的哈夫曼树，它的带权路径长度计算如下：

 
    5*3 + 2*2 + 4*3 + 7*1 + 1*4 = 49
    其中，叶节点5的路径长度为3，叶节点2的路径长度为2，叶节点4的路径长度为3，叶节点7的路径长度为1，叶节点1的路径长度为4。

第六章

(1)图的定义和术语

1.1定义：

图是一种数学结构，它由一些节点（也称为顶点）和它们之间的连接（也称为边）组成。图可以用于表示各种实际问题，如道路交通、社交网络、通信网络等。

在图中，节点可以表示某些实体，如人、城市或计算机等，边可以表示它们之间的关系，如道路、友谊或通信线路等。图可以是有向的，也可以是无向的。有向图中的边是有方向的，表示节点之间的单向关系；无向图中的边是无方向的，表示节点之间的双向关系。

1.2图的术语包括：

    节点（vertex）：也称为顶点，表示图中的一个元素。

    边（edge）：连接两个节点的线段，表示它们之间的关系。

    权重（weight）：表示边的值或者边的长度，用于表示节点之间的距离或者花费。

    路径（path）：由节点和它们之间相连的边构成的序列。

    简单路径（simple path）：不经过重复节点的路径。

    环（cycle）：起点和终点相同的路径。

    连通（connected）：在无向图中，如果从一个节点可以到达另一个节点，则称这两个节点是连通的；在有向图中，如果从一个节点可以到达另一个节点，并且也可以从另一个节点到达这个节点，则称这两个节点是强连通的。

    子图（subgraph）：由图中的一部分节点和它们之间的边组成的图。

    度数（degree）：表示与节点相邻的边的数量，在有向图中分为入度和出度两种。

    完全图（complete graph）：每两个节点之间都有边的无向图。

    带权图（weighted graph）：每条边都带有权重的图。权重可以表示边的长度、花费或其它指标。

    二分图（bipartite graph）：可以将节点分为两个集合，使得同一个集合中的节点之间没有边相连。

    最短路径（shortest path）：连接两个节点的路径中，权重最小的路径。

(2)图的存储结构（邻接矩阵、邻接表）

图的存储结构主要有两种：邻接矩阵和邻接表。

图的存储结构有两种常见的方式，分别是邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一种二维数组，用于表示图中节点之间的连接关系。对于无向图来说，矩阵中第 i 行第 j 列的元素表示节点 i 和 j 之间是否有边相连；对于有向图来说，则需要分别表示节点 i 到 j 和节点 j 到 i 之间的连接关系。

下面是一个无向图的邻接矩阵示例：

A B C D E

————-

A | 0 1 1 1 0

B | 1 0 1 0 1

C | 1 1 0 0 1

D | 1 0 0 0 1

E | 0 1 1 1 0

在这个邻接矩阵中，行和列的索引分别代表节点的编号，1 表示对应节点之间有边相连，0 表示没有边相连。

邻接矩阵的优点是查询两个节点之间是否存在边的效率很高，只需要访问矩阵中对应的元素即可。但是在表示稀疏图时，矩阵中会存在大量的 0 元素，造成了空间浪费。

邻接表

邻接表是一种链式存储结构，用于表示图中节点之间的连接关系。对于每个节点，它都有一个对应的链表，链表中存储了与该节点相邻的节点的编号。

下面是一个无向图的邻接表示例：

A -> B -> C -> D

B -> A -> C -> E

C -> A -> B -> E

D -> A -> E

E -> B -> C -> D

在这个邻接表中，每个节点的编号都表示为一个字母，箭头表示链表的指向关系。例如，节点 A 的链表中依次存储了与节点 A 相邻的节点 B、C、D 的编号。

    邻接表的优点是可以有效地表示稀疏图，节省了存储空间。但是在查询两个节点之间是否存在边时，需要遍历其中一个节点的链表来查找另一个节点的编号，效率较低。

    根据具体的应用场景和图的特征，选择合适的存储结构可以提高算法的效率。

(3)图的遍历（广度、深度优先遍历）

图的遍历是指按照某种顺序依次访问图中的所有节点。常用的图遍历算法有广度优先遍历和深度优先遍历。

1.1广度优先遍历（BFS）：

广度优先遍历从起始节点开始，依次访问所有与之相邻的节点，再依次访问这些节点的相邻节点，直到遍历完所有节点。在遍历过程中，使用一个队列来存储待访问节点，每次从队列的头部取出一个节点进行访问，访问完这个节点后将它的未被访问过的相邻节点加入队列的尾部，直到队列为空为止。

    广度优先遍历可以用来查找两个节点之间的最短路径，因为它会先访问距离起始节点最近的节点。

1.2深度优先遍历（DFS）：

深度优先遍历从起始节点开始，沿着一条路径尽可能深地访问节点，直到遇到一个没有未访问过的相邻节点的节点，然后回溯到前面的节点，尝试访问其他未被访问过的相邻节点，直到遍历完所有节点。

    在遍历过程中，使用一个栈来存储待访问节点，每次从栈的顶部取出一个节点进行访问，访问完这个节点后将它的未被访问过的相邻节点加入栈的顶部。

    深度优先遍历的优点是可以快速地找到一条路径，缺点是可能陷入死循环或者栈溢出。因此，在实际应用中通常需要在算法中加入判断条件，避免陷入死循环或者栈溢出的情况。

    综上所述，广度优先遍历和深度优先遍历各有优缺点，可以根据具体情况选择合适的算法

(4)图的最小生成树（要求要画出构造过程）、最短路径（要求要画出求解过程）、拓扑排序（要求要画出构造过程）

1.1图的最小生成树

假设我们有以下带权重的无向图：

5 2

A —– B —– C

| \ / | / |

| 4 | 1 |

| / \ | / |

D —– E —– F

3 6

我们可以使用 Prim 算法来构建这个图的最小生成树。Prim 算法的基本思路是从一个起始节点开始，逐步加入与已有节点相邻的最小权重边，直到生成树包含了所有的节点。下面是 Prim 算法的构造过程：

选取一个起始节点，假设为 A。将 A 标记为已访问。

找到与 A 相邻的最小权重边，即 A-D，将其加入生成树，并将 D 标记为已访问。

找到与已有节点相邻的最小权重边，即 D-B，将其加入生成树，并将 B 标记为已访问。

找到与已有节点相邻的最小权重边，即 B-E，将其加入生成树，并将 E 标记为已访问。

找到与已有节点相邻的最小权重边，即 E-C，将其加入生成树，并将 C 标记为已访问。

找到与已有节点相邻的最小权重边，即 C-F，将其加入生成树。

最终得到的最小生成树为：

      5      2
 A ----- B ----- C
          |     / |
          |   1   |
          | /     |
          E ----- F
               6

1.2图的最短路径

假设我们有以下带权重的有向图：

         2        3
   (A)---->(B)---->(C)
    |       | ^     |
    |  1    | |4    | 1
    v       v |     v
   (D)---->(E)---->(F)
       1        2

我们可以使用 Dijkstra 算法来找到从起始节点 A 到其他节点的最短路径。Dijkstra 算法的基本思路是从起始节点开始，逐步扩展到与已有节点相邻的节点中距离最短的节点。下面是 Dijkstra 算法的求解过程：

初始化距离数组，假设起始节点为 A，则距离数组为 [0, INF, INF, INF, INF, INF]，其中 INF 表示无穷大。

从距离数组中找到距离最小的节点，即 A，将其标记为已访问。

遍历与 A 相邻的节点，更新它们到起始节点的距离。在这个例子中，与 A 相邻的节点为 B 和 D，更新后的距离数组为 [0, 2, 1, 1, INF, INF]。

从距离数组中找到距离最小的节点，即 D，将其标记为已访问。

遍历与 D 相邻的节点，更新它们到起始节点的距离。在这个例子中，与 D 相邻的节点为 E，更新后的距离数组为 [0, 2, 1, 1, 2, INF]。

从距离数组中找到距离最小的节点，即 B，将其标记为已访问。

遍历与 B 相邻的节点，更新它们到起始节点的距离。在这个例子中，与 B 相邻的节点为 C 和 E，更新后的距离数组为 [0, 2, 1, 1, 2, 5]。

从距离数组中找到距离最小的节点，即 C，将其标记为已访问。

遍历与 C 相邻的节点，更新它们到起始节点的距离。在这个例子中，与 C 相邻的节点为 F，更新后的距离数组为 [0, 2, 1, 1, 2, 4]。

从距离数组中找到距离最小的节点，即 E，将其标记为已访问。

遍历与 E 相邻的节点，更新它们到起始节点的距离。在这个例子中，与 E 相邻的节点为 F，更新后的距离数组为 [0, 2, 1, 1, 2, 4]。

从距离数组中找到距离最小的节点，即 F，将其标记为已访问。

完成算法，得到从起始节点 A 到其他节点的最短路径长度为 [0, 2, 1, 1, 2, 4]。

最短路径的求解过程可以用一个表格来表示，其中每一行表示一个节点，包括该节点的距离、前驱节点和是否已经访问。下面是求解过程的表格：

可以看到，最短路径的构造过程就是不断更新距离数组和表格，直到所有节点都被访问。

1.3图的拓扑排序

假设我们有以下有向无环图：

      A
     / \
    B   C
   / \   \
  D   E   F

我们可以使用拓扑排序算法来对这个图进行排序，使得所有边的起始节点排在其终止节点前面。拓扑排序算法的基本思路是从入度为零的节点开始，逐步删除它们和与之相连的边，直到所有节点都被删除。下面是拓扑排序算法的构造过程：

统计每个节点的入度，假设初始的入度数组为 [0, 1, 1, 1, 1, 1]。

找到入度为零的节点，即 A，将其加入排序结果中，并删除与 A 相连的边。在这个例子中，删除 A 的出边后，入度数组变为 [0, 0, 0, 1, 1, 1]。

找到入度为零的节点，即 B 和 C，选择其中一个加入排序结果中，并删除与它相连的边。在这个例子中，假设选择 B，删除 B 的出边后，入度数组变为 [0, 0, 0, 0, 1, 1]。

找到入度为零的节点，即 D 和 E，选择其中一个加入排序结果中，并删除与它相连的边。在这个例子中，假设选择 D，删除 D 的出边后，入度数组变为 [0, 0, 0, 0, 0, 1]。

第七章查找

(1)折半查找

折半查找（Binary Search），也称二分查找，是一种用于在有序数组中查找某个元素的算法。它的基本思想是将查找范围不断缩小一半，直到找到目标元素或确定目标元素不存在。

具体实现步骤如下：

将要查找的元素与数组的中间元素进行比较。

如果要查找的元素等于中间元素，则查找成功，返回中间元素的下标。

如果要查找的元素小于中间元素，则在数组的左半部分继续查找。

如果要查找的元素大于中间元素，则在数组的右半部分继续查找。

重复执行步骤 1-4，直到找到目标元素或确定目标元素不存在。

折半查找的时间复杂度为 O(log n)，其中 n 是数组的长度。与顺序查找相比，折半查找的效率更高，特别是在大型有序数组中查找时更加明显。

需要注意的是，折半查找只适用于有序数组，如果数组没有经过排序，则需要先进行排序操作。此外，由于折半查找是基于下标的访问方法，因此只适用于数组这种数据结构，不适用于链表等其他数据结构。

(2)二叉排序树

二叉排序树（Binary Search Tree，BST），也称二叉搜索树或二叉查找树，是一种二叉树，其中每个节点都存储一个关键字，并且节点的左子树的所有关键字都小于节点的关键字，节点的右子树的所有关键字都大于节点的关键字。

二叉排序树的特点是：

        左子树的所有节点的关键字都小于根节点的关键字。
        右子树的所有节点的关键字都大于根节点的关键字。
        左右子树本身也是二叉排序树。
        二叉排序树的插入操作是将新节点插入到合适的位置，使得插入后仍然满足二叉排序树的特性。具体实现步骤如下：
        如果二叉排序树为空，则直接插入新节点。
        如果新节点的关键字小于当前节点的关键字，则在当前节点的左子树中插入新节点。
        如果新节点的关键字大于当前节点的关键字，则在当前节点的右子树中插入新节点。
        重复执行步骤 2-3，直到找到合适的位置插入新节点。

    二叉排序树的查找操作也很简单，只需要从根节点开始，如果要查找的关键字小于当前节点的关键字，则进入左子树继续查找，如果大于当前节点的关键字，则进入右子树继续查找，直到找到目标节点或者无法继续查找。
    二叉排序树的时间复杂度与树的高度有关，对于一个平衡的二叉排序树，其时间复杂度为 O(log n)，其中 n 是节点个数。但是如果树不平衡，可能会出现最坏情况，时间复杂度退化为 O(n)，此时相当于一个链表，效率极低。因此，为了保证二叉排序树的高效性，需要考虑如何维护树的平衡性，例如使用 AVL 树、红黑树等平衡二叉树

(3)平衡二叉树

平衡二叉树（Balanced Binary Tree），也称自平衡二叉树（Self-Balancing Binary Tree），是一种二叉树，它的左右子树的高度差不超过 1，因此根节点的左右子树也是一棵平衡二叉树。

平衡二叉树的目的是为了解决二叉排序树退化成链表的问题，保证树的高度不会太深，从而使得插入、查找等操作的时间复杂度仍然能够维持在 O(log n) 的水平。

常见的平衡二叉树有 AVL 树、红黑树、B 树等。

1.1AVL 树

AVL 树是一种最早被发明的自平衡二叉树，它的平衡性是通过旋转操作来实现的。在 AVL 树中，每个节点都存储一个平衡因子，表示当前节点的左子树高度与右子树高度的差值。如果某个节点的平衡因子超过了 1，就需要进行旋转操作来调整平衡。

    AVL 树的旋转操作一般分为四种情况：左旋、右旋、左右旋和右左旋。其中左旋和右旋是最基本的旋转操作，左右旋和右左旋是基于左旋和右旋的组合操作。具体的旋转操作可以参考 AVL 树的相关资料。

    AVL 树的优点是查询、插入、删除等操作的时间复杂度都为 O(log n)，并且对于任何操作序列，AVL 树的高度始终保持在 O(log n) 的范围内。但是 AVL 树的缺点是需要维护平衡因子，因此需要额外的存储空间，同时插入、删除操作可能需要进行多次旋转，导致操作效率较低。

1.2红黑树

红黑树是一种类似于 AVL 树的自平衡二叉树，它的平衡性是通过颜色标记和简单的旋转操作来实现的。在红黑树中，每个节点都被标记为红色或黑色，并且满足以下性质：

    根节点为黑色。
    所有叶子节点（即空节点）为黑色。
    如果一个节点为红色，则它的两个子节点都必须为黑色。
    从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
    这些性质保证了红黑树的平衡性，并且可以证明，任何一棵 n 个节点的红黑树的高度不超过 2log2(n+1)。

    红黑树的优点是插入、删除等操作的平均时间复杂度为 O(log n)，而且旋转操作较少，维护平衡的效率较高。缺点是红黑树的实现较为复杂，不如 AVL 树直观易懂。

(4)哈希函数

哈希函数（Hash Function）是一种将任意长度的输入（消息）映射为固定长度输出（哈希值）的函数。哈希函数通常用于数据加密、数据压缩、唯一标识等方面。

    哈希函数的特点是：
    输入的任意长度消息经过哈希函数处理后，输出的哈希值长度是固定的，通常为 128 位、256 位、512 位等。
    哈希函数的输出值是不可逆的，即无法从哈希值反推出原始输入消息。
    哈希函数应该是高效的，即对于任意输入消息，能够快速地计算出其哈希值。
    哈希函数应该尽可能地避免哈希冲突，即不同的输入消息计算出相同的哈希值的概率应该很小。
    哈希函数的应用非常广泛，例如：
    数据加密：哈希函数可以将明文加密为哈希值，从而保证数据的安全性。
    数据压缩：哈希函数可以将大量数据压缩为较小的哈希值，从而减少存储空间和传输带宽。
    数字签名：哈希函数可以将消息的哈希值与发送者的私钥进行加密，从而实现数字签名的功能。
    唯一标识：哈希函数可以将大量数据映射为唯一的哈希值，从而实现数据的唯一标识。
    常见的哈希函数有 MD5、SHA-1、SHA-256 等。但是随着计算能力的提高和哈希碰撞攻击技术的发展，这些哈希函数的安全性也逐渐受到质疑。为此，一些新的哈希算法被提出，例如 SHA-3、BLAKE、Skein 等。

第八章排序

(1)排序的概念、稳定性；堆的特点

1.1

排序是将一组数据按照某种规则进行排列的过程。排序算法是计算机程序中常用的基本算法之一，它可以对数据进行分类、归纳和概括，是各种算法和数据结构的基础。

    排序算法有很多种，常见的包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。这些算法的实现方式和时间复杂度不同，各有优缺点，可根据具体情况选择使用。

1.2

排序算法的稳定性是指对于值相同的元素，在排序前后它们的相对位置是否发生变化。如果排序前后相对位置没有改变，那么排序算法就是稳定的；如果排序前后相对位置发生了变化，那么排序算法就是不稳定的。

例如，对于以下数组：

[(3, A), (2, B), (3, C)]

其中每个元素由一个数字和一个字母组成，数字相同的元素按照它们在原数组中的顺序排序。如果使用稳定的排序算法对该数组进行排序，那么排序后的结果应该是：

[(2, B), (3, A), (3, C)]

可以看到，数字相同的元素在排序前后的相对位置没有发生变化。

1.3

堆是一种特殊的数据结构，它是一棵完全二叉树，并满足堆属性：对于每个节点，它的值都大于或等于（或小于或等于）其左右子节点的值。大于等于的堆称为大根堆，小于等于的堆称为小根堆。

    堆的特点包括：

    堆是一种完全二叉树，可以使用数组来实现。

    对于大根堆，任意节点的值都大于或等于其左右子节点的值；对于小根堆，任意节点的值都小于或等于其左右子节点的值。

    堆的根节点（即数组的第一个元素）是堆中的最大值或最小值。

    堆的插入和删除操作的时间复杂度均为 O(log n)。

    堆主要有两种类型：最大堆和最小堆。最大堆的根节点是堆中的最大值，最小堆的根节点是堆中的最小值。堆常用于优先队列、排序算法（如堆排序）以及图算法中。

(2)冒泡排序

冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们的位置，直到没有任何一对数字需要比较为止。

    具体实现过程如下：
    从数组的第一个元素开始，依次比较相邻的两个元素，如果前面的元素大于后面的元素，就交换它们的位置。

    对于数组中的所有元素都执行上述操作，这样第一轮比较后，最后一个元素应该是整个数组中的最大值。

    对于剩余的元素，重复上述操作，直到所有的元素都排序完成。

    下面是冒泡排序的示例代码（以升序排序为例）：

       
#include <stdio.h>

void bubble_sort(int arr[], int n) {
   int i, j, temp;
   for (i = 0; i < n - 1; i++) {  // 外层循环控制比较的轮数，最多比较n-1轮
       for (j = 0; j < n - i - 1; j++) {  // 内层循环依次比较相邻的两个元素，将较大的数往后移动
           if (arr[j] > arr[j+1]) {
               temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
           }
       }
   }
}

int main() {
   int arr[] = {5, 2, 8, 4, 7, 1, 3, 6};
   int n = sizeof(arr) / sizeof(arr[0]);
   bubble_sort(arr, n);
   printf("排序后的数组：\n");
   for (int i = 0; i < n; i++) {
       printf("%d ", arr[i]);
   }
   return 0;
}

冒泡排序的时间复杂度为 O(n^2)，其中 n 是待排序数组的长度。虽然冒泡排序的时间复杂度较高，但由于其简单易懂，实现容易，因此在一些小规模的数据排序中仍然有一定的应用价值。

(3)希尔排序

希尔排序是一种基于插入排序的改进算法，也称为缩小增量排序。其基本思想是将待排序数组分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终完成排序。

    具体实现过程如下：

    选择一个增量序列 t1，t2，…，tk，其中 ti > tj，tk = 1。

    按增量序列个数 k 对序列进行 k 趟排序。

    每趟排序，根据对应的增量 ti，将待排序数组分割成若干个长度为 ti 的子序列，分别对每个子序列进行插入排序。

    将各个子序列中排序好的元素合并，得到完整的排序结果。

    下面是希尔排序的示例代码:

#include <stdio.h>

void shell_sort(int arr[], int n) {
    int gap, i, j, temp;
    // 设置增量序列，使用 Knuth 增量序列
    for (gap = 1; gap < n / 3; gap = gap * 3 + 1);
    // 增量为 1 时，即为插入排序
    for (; gap > 0; gap /= 3) {
        // 对每个子序列进行插入排序
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {5, 2, 8, 4, 7, 1, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    shell_sort(arr, n);
    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

希尔排序的时间复杂度为 O(n log n) 到 O(n^2) 不等，具体取决于增量序列的选择。在实际应用中，希尔排序的效率通常比冒泡排序和插入排序要高，尤其是对于大规模数据的排序。

(4)归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法。它的基本思路是将待排序的序列分成两部分，分别对每一部分进行归并排序，然后将两个有序的子序列合并成一个有序的序列。

    具体的归并排序算法可以分为以下三个步骤：

    分解：将待排序的序列分成两个长度相等的子序列，分别对这两个子序列进行归并排序。
    合并：将两个有序的子序列合并成一个有序的序列。合并时，需要借助一个临时数组，将两个子序列中的元素逐个比较，将较小（或较大）的元素先放入临时数组中，直到其中一个子序列的元素全部放入临时数组中，然后再将另一个子序列中的剩余元素依次放入临时数组中。
    组合：递归地将两个子序列合并成一个有序的序列，直到整个序列有序为止。
    归并排序的时间复杂度为 O(nlogn)，它的稳定性得到保证。归并排序虽然具有较高的时间复杂度，但是它的优点是不会产生额外的空间开销，因此在空间复杂度有限制的场合下，它是一种非常有用的排序算法。

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

void merge(int arr[], int p, int q, int r) {
    int n1 = q - p + 1, n2 = r - q;
    int *L = (int*) malloc((n1 + 1) * sizeof(int));
    int *R = (int*) malloc((n2 + 1) * sizeof(int));
    int i, j, k;
    for (i = 0; i < n1; i++) {
        L[i] = arr[p + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[q + 1 + j];
    }
    L[n1] = R[n2] = INT_MAX;  // 设置哨兵，表示序列的结尾
    i = j = 0;
    for (k = p; k <= r; k++) {
        if (L[i] <= R[j]) {
            arr[k] = L[i++];
        } else {
            arr[k] = R[j++];
        }
    }
    free(L);
    free(R);
}

void merge_sort(int arr[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(arr, p, q);
        merge_sort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

int main() {
    int arr[] = {5, 2, 8, 4, 7, 1, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    merge_sort(arr, 0, n - 1);
    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

(5)直接插入排序

直接插入排序（Insertion Sort）是一种简单的排序算法，它的基本思路是将待排序的序列分为已排序区间和未排序区间，初始时已排序区间只有一个元素，然后依次将未排序区间中的元素插入到已排序区间的合适位置，直到未排序区间中的元素全部插入完毕，整个序列就变成了有序序列。

具体的直接插入排序算法可以分为以下几个步骤：

    将待排序序列的第一个元素看作已排序区间，将剩余元素看作未排序区间。
    从未排序区间中取出第一个元素，将其插入到已排序区间中的合适位置，保证插入后仍然是有序的。
    重复第2步，直到未排序区间中的元素全部插入完毕，整个序列就变成了有序序列。
    直接插入排序的时间复杂度为 O(n^2)，但是在实际应用中，它的性能常常优于其他复杂度相同的排序算法，因为直接插入排序在大部分情况下都是一种稳定的排序算法，且对于小规模的数据集，它的性能比较优秀，而且它是一种在线排序算法，即可以在不关闭数据流的情况下进行排序。

以下是直接插入排序的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;
       void insertionSort(vector<int>& nums) {
       int n = nums.size();
       for (int i = 1; i < n; i++) {
       int j = i - 1, temp = nums[i];

       while (j >= 0 && nums[j] > temp) {
       nums[j + 1] = nums[j];
       j--;
       }

       nums[j + 1] = temp;
       }
       }
       int main() {
       vector<int> nums = {5, 2, 4, 6, 1, 3};
       insertionSort(nums);

       for (auto num : nums) {
       cout << num << " ";
       }
       cout << endl;

       return 0;
       }

(6)简单选择排序

简单选择排序（Selection Sort）是一种简单的排序算法，它的基本思路是将待排序的序列分为已排序区间和未排序区间，初始时已排序区间为空，然后每次从未排序区间中选取最小的元素插入到已排序区间的末尾，直到未排序区间中的元素全部插入完毕，整个序列就变成了有序序列。

具体的简单选择排序算法可以分为以下几个步骤：

将待排序序列的第一个元素看作已排序区间，将剩余元素看作未排序区间。

从未排序区间中选取最小的元素，将其插入到已排序区间的末尾，保证插入后仍然是有序的。

重复第2步，直到未排序区间中的元素全部插入完毕，整个序列就变成了有序序列。

简单选择排序的时间复杂度为 O(n^2)，它的优点是实现简单，不需要额外的空间开销，但是在实际应用中，它的性能相比其他排序算法较低，因为它每次只能将一个元素插入到已排序区间的末尾，而不能进行并行处理。

  以下是简单选择排序的C++代码实现：
#include <iostream>
#include <vector>
using namespace std;

        void selectionSort(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
        if (nums[j] < nums[minIndex]) {
        minIndex = j;
        }
        }

        swap(nums[i], nums[minIndex]);
        }
        }

        int main() {
        vector<int> nums = {5, 2, 4, 6, 1, 3};
        selectionSort(nums);

        for (auto num : nums) {
        cout << num << " ";
        }
        cout << endl;

        return 0;
        }