数据结构算法-背诵篇

### 数据结构算法-背诵篇 #### 一、线性表 ##### 1. 逆转顺序表中的所有元素 **算法思想**： 本算法通过交换数组两端的元素来实现顺序表的逆置。具体地，从数组的第一个元素与最后一个元素开始，依次交换，直至中间位置为止。 **代码实现**： ```c void Reverse(int A[], int n) { int i, t; for (i = 0; i < n / 2; i++) { t = A[i]; A[i] = A[n - i - 1]; A[n - i - 1] = t; } } ``` **解析**： - **输入**：整型数组`A`和数组长度`n`。 - **输出**：数组`A`被逆置后的结果。 - **时间复杂度**：O(n)，其中n为数组长度。 - **空间复杂度**：O(1)，因为只用了几个额外的变量进行临时存储。 ##### 2. 删除线性链表中数据域为item的所有结点 **算法思想**： 首先从链表的第二个结点开始检查，如果当前结点的数据域等于指定值`item`，则删除该结点；如果不是，则继续检查下一个结点。再次检查链表的第一个结点是否符合删除条件。 **代码实现**： ```c void PurgeItem(LinkList &list) { LinkList p, q = list; p = list->next; while (p != NULL) { if (p->data == item) { q->next = p->next; free(p); p = q->next; } else { q = p; p = p->next; } } if (list->data == item) { q = list; list = list->next; free(q); } } ``` **解析**： - **输入**：链表的头结点引用`list`。 - **输出**：删除了所有数据域为`item`的结点后的链表。 - **时间复杂度**：O(n)，其中n为链表长度。 - **空间复杂度**：O(1)，没有使用额外的空间。 ##### 3. 逆转线性链表 **算法思想**： 通过三个指针（前驱、当前、后继），将每个结点的指针域反转，最终将链表反转。 **代码实现**： ```c void Reverse(LinkList &list) { LinkList p, q, r; p = list; q = NULL; while (p != NULL) { r = q; q = p; p = p->next; q->next = r; } list = q; } ``` **解析**： - **输入**：链表的头结点引用`list`。 - **输出**：链表的逆置版本。 - **时间复杂度**：O(n)，其中n为链表长度。 - **空间复杂度**：O(1)，没有使用额外的空间。 ##### 4. 复制线性链表（递归） **算法思想**： 使用递归来复制链表。对于每个结点，创建一个新的结点，然后递归地复制下一个结点。 **代码实现**： ```c LinkList Copy(LinkList lista) { LinkList listb; if (lista == NULL) return NULL; else { listb = (LinkList)malloc(sizeof(LNode)); listb->data = lista->data; listb->next = Copy(lista->next); return listb; } } ``` **解析**： - **输入**：原始链表的头结点`lista`。 - **输出**：原始链表的一个完整副本。 - **时间复杂度**：O(n)，其中n为链表长度。 - **空间复杂度**：O(n)，需要为新链表分配空间。 ##### 5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表 **算法思想**： 合并两个已排序的链表。每次比较两个链表头部的值，将较小值的结点添加到新的链表中，直到其中一个链表为空，然后将另一个链表的剩余部分连接到新链表上。 **代码实现**： ```c LinkList MergeList(LinkList lista, LinkList listb) { LinkList listc, p = lista, q = listb, r; if (lista->data <= listb->data) { listc = lista; r = lista; p = lista->next; } else { listc = listb; r = listb; q = listb->next; } while (p != NULL && q != NULL) { if (p->data <= q->data) { r->next = p; r = p; p = p->next; } else { r->next = q; r = q; q = q->next; } } r->next = (p != NULL) ? p : q; return listc; } ``` **解析**： - **输入**：两个已排序的链表`lista`和`listb`。 - **输出**：一个新的链表，包含`lista`和`listb`中所有结点，并保持升序排序。 - **时间复杂度**：O(m+n)，其中m和n分别是两个链表的长度。 - **空间复杂度**：O(1)，没有使用额外的空间。 #### 二、树 ##### 1. 二叉树的先序遍历（非递归算法） **算法思想**： 非递归实现二叉树的先序遍历。使用栈辅助，首先访问根节点，然后将其压入栈中。之后不断访问当前节点的左孩子，直到左孩子为空，此时从栈中弹出节点并访问其右孩子。重复这一过程，直至遍历完所有节点。 **代码实现**： ```c #define MAX_STACK 50 void PreOrderTraverse(BTree T) { BTree STACK[MAX_STACK], p = T; int top = -1; while (p != NULL || top != -1) { while (p != NULL) { VISIT(p); STACK[++top] = p; p = p->lchild; } p = STACK[top--]; p = p->rchild; } } ``` **解析**： - **输入**：二叉树的根节点`T`。 - **输出**：二叉树的先序遍历序列。 - **时间复杂度**：O(n)，其中n为二叉树的结点数。 - **空间复杂度**：O(h)，h为二叉树的高度，最坏情况下为O(n)。 ##### 2. 二叉树的中序遍历（非递归算法） **算法思想**： 非递归实现二叉树的中序遍历。使用栈辅助，首先不断访问当前节点的左孩子，直至左孩子为空。此时从栈中弹出节点并访问，然后访问该节点的右孩子。重复这一过程，直至遍历完所有节点。 **代码实现**： ```c #define MAX_STACK 50 void InOrderTraverse(BTree T) { BTree STACK[MAX_STACK], p = T; int top = -1; while (p != NULL || top != -1) { while (p != NULL) { STACK[++top] = p; p = p->lchild; } p = STACK[top--]; VISIT(p); p = p->rchild; } } ``` **解析**： - **输入**：二叉树的根节点`T`。 - **输出**：二叉树的中序遍历序列。 - **时间复杂度**：O(n)，其中n为二叉树的结点数。 - **空间复杂度**：O(h)，h为二叉树的高度，最坏情况下为O(n)。 以上算法涵盖了线性表的基本操作及二叉树的非递归遍历方法，是数据结构学习的重要组成部分，尤其适用于准备考研的同学复习和巩固基础知识点。