数据结构算法

### 数据结构算法知识点详解 #### 一、线性表 线性表是计算机科学中最基本的数据结构之一，它由相同类型的元素组成，并按照一定的顺序排列。对于线性表的操作包括了增删改查等基本操作。 ##### 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; } } ``` **解析**：此段代码中定义了一个名为`Reverse`的函数，接受一个整型数组`A`及其长度`n`作为参数。在循环中，通过使用临时变量`t`，将数组首尾元素进行交换，实现逆转效果。 --- ##### 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); } } ``` **解析**：此段代码通过两个指针`p`和`q`来遍历链表。`p`用于指向当前正在检查的节点，而`q`总是指向`p`的前一个节点。这样当遇到值为`item`的节点时，可以直接通过`q`更新指针跳过该节点并释放内存。 --- ##### 3. 逆转线性链表 **算法思想**：该算法采用三个指针`p`、`q`和`r`来遍历链表并逆转指针方向。`p`指向当前节点，`q`始终指向逆转后的链表头，`r`保存`q`的前一个节点的信息。 **代码示例**： ```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; } ``` **解析**：通过迭代的方式，每次移动`p`到下一个节点的同时，将当前节点的指针逆转至`r`，最终实现了链表的逆转。 --- ##### 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; } } ``` **解析**：此段代码定义了一个名为`Copy`的递归函数，用于复制链表。首先判断传入的链表是否为空，如果为空则返回`NULL`；否则，创建一个新节点，并将原节点的数据复制到新节点上，然后递归地复制剩余部分。 --- ##### 5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表 **算法思想**：该算法合并两个有序链表，生成一个新的有序链表。首先确定两个链表头节点的大小关系，然后依次比较两个链表中的节点，并将较小的节点链接到结果链表中。 **代码示例**： ```c LinkList MergeList(LinkList lista, LinkList listb) { LinkList listc, p = lista, q = listb, r; // listc指向lista和listb所指结点中较小者 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; } ``` **解析**：这段代码通过两个指针`p`和`q`分别遍历两个链表，并根据节点值的大小决定哪个节点应该排在前面。合并后的链表头节点由`listc`记录，而`r`则记录合并链表的当前位置。最后将未处理完的部分链接到合并链表的末尾。 --- #### 二、树 树是一种非线性的数据结构，它是由多个节点组成的集合。每个节点包含数据以及指向其他节点的连接（称为“分支”或“指针”）。在二叉树中，每个节点最多有两个子节点，通常称为左子节点和右子节点。 ##### 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; } } ``` **解析**：该算法首先初始化一个栈`STACK`和栈顶指针`top`。遍历过程中，每当遇到非空节点时，就访问该节点并将其压入栈中，然后继续遍历其左子树。当遇到空节点时，则从栈中弹出一个节点，并转向其右子树。此过程重复进行，直到栈为空且当前节点也为`NULL`。 --- ##### 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; } } ``` **解析**：此算法与先序遍历类似，不同之处在于访问节点的时机。在中序遍历中，当从栈中弹出一个节点时，才访问该节点。这样就可以确保按照左根右的顺序访问二叉树中的节点。