实验一 线性表（线性顺序表、线性链表）

题目

1．设线性表存放在数组A[arrsize］的前elenum个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表的元素仍然是递增有序的。

2．设带头结点的单链表的结点结构如下： struct node { DataType data; struct node *next; } Node,*LinkList; 试编写一个函数int count(LinkList head, DataType x）统计单链表中数据域为x的结点个数。

3．假设有两个按元素值递增有序排列的且带头结点的单链表A和表B，请编写算法将表A和表B合并成一个按元素值递减有序排列的单链表C，并要求利用原表（即表A和表B）的结点空间存放表C。

4．已知带头结点的单链表L是按数据域值非递减有序链接的，试写一算法将值为x的结点插入表L中，使得L仍然是有序链接的。

5．试分别以顺序表和带头结点的单链表作存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1,a2,…, an）逆置为（an, an-1,…,aj)。

6．已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点，同时释放被删结点的空间，这里min和max是两个给定的参数。

题目1：递增有序顺序表插入元素

代码实现

void insertSorted(int A[], int *elenum, int x, int arrsize) {
    if (*elenum >= arrsize) { // 检查数组是否已满
        printf("数组已满，无法插入！");
        return;
    }
    int i = *elenum - 1;
    // 从后向前找到插入位置
    while (i >= 0 && A[i] > x) {
        A[i + 1] = A[i]; // 元素后移
        i--;
    }
    A[i + 1] = x; // 插入x
    (*elenum)++;   // 表长加1
}

关键步骤注释

1. 边界检查：确保数组未满。
2. 定位插入位置：从后向前遍历，找到第一个小于等于 x 的位置。
3. 元素后移：将插入位置后的元素依次后移。
4. 插入元素：将 x 放入正确位置。

解题思路

• 核心问题：在有序数组中插入元素并保持有序性。
• 时间复杂度：O(n)，最坏情况需移动所有元素。
• 优化点：可用二分查找优化定位步骤（时间复杂度降至 O(logn)），但插入仍需 O(n) 时间。

---

题目2：统计单链表中值为x的结点数

代码实现

int count(LinkList head, DataType x) {
    int cnt = 0;
    Node *p = head->next; // 跳过头结点
    while (p != NULL) {
        if (p->data == x) cnt++;
        p = p->next;
    }
    return cnt;
}

关键步骤注释

1. 初始化计数器：cnt 记录匹配的结点数。
2. 遍历链表：从头结点的下一个结点开始遍历。
3. 匹配判断：若数据域等于 x，计数器加1。

解题思路

• 核心问题：遍历链表并统计特定值的结点。
• 时间复杂度：O(n)，需遍历整个链表。

---

题目3：合并两个递增链表为递减链表

代码实现

LinkList mergeDescending(LinkList A, LinkList B) {
    LinkList C = A; // 用A的头结点作为C的头
    C->next = NULL; // 初始化C为空链表
    Node *pa = A->next, *pb = B->next, *temp;

    while (pa != NULL && pb != NULL) {
        // 选择较小的结点插入到C的头部
        if (pa->data <= pb->data) {
            temp = pa;
            pa = pa->next;
        } else {
            temp = pb;
            pb = pb->next;
        }
        // 头插法构建递减链表
        temp->next = C->next;
        C->next = temp;
    }
    // 处理剩余结点
    while (pa != NULL) {
        temp = pa;
        pa = pa->next;
        temp->next = C->next;
        C->next = temp;
    }
    while (pb != NULL) {
        temp = pb;
        pb = pb->next;
        temp->next = C->next;
        C->next = temp;
    }
    free(B); // 释放B的头结点
    return C;
}

关键步骤注释

1. 初始化链表C：复用A的头结点。
2. 比较并插入：每次选择较小的结点，用头插法插入到C的头部。
3. 处理剩余结点：将未遍历完的链表剩余结点插入C。
4. 释放资源：释放B的头结点。

解题思路

• 核心问题：利用原链表结点空间合并为递减链表。
• 头插法：通过头插法实现逆序。
• 时间复杂度：O(m+n)，m和n为两链表长度。

---

题目4：有序单链表插入元素

代码实现

void insertOrdered(LinkList L, DataType x) {
    Node *p = L->next, *pre = L; // pre记录插入位置的前驱
    while (p != NULL && p->data < x) {
        pre = p;
        p = p->next;
    }
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = pre->next; // 插入到pre之后
    pre->next = newNode;
}

关键步骤注释

1. 定位插入位置：找到第一个大于等于 x 的结点的前驱 pre。
2. 创建新结点：分配内存并赋值。
3. 插入结点：将新结点插入到 pre 之后。

解题思路

• 核心问题：在有序链表中插入元素并保持有序性。
• 时间复杂度：O(n)，最坏需遍历整个链表。

---

题目5：顺序表和链表的就地逆置

顺序表逆置代码

void reverseSeqList(int A[], int n) {
    for (int i = 0; i < n / 2; i++) {
        int temp = A[i];
        A[i] = A[n - i - 1];
        A[n - i - 1] = temp;
    }
}

链表逆置代码

void reverseLinkList(LinkList L) {
    Node *pre = NULL, *cur = L->next, *next;
    while (cur != NULL) {
        next = cur->next; // 保存后继
        cur->next = pre;  // 反转指针
        pre = cur;        // 前移pre
        cur = next;       // 前移cur
    }
    L->next = pre; // 头结点指向新首结点
}

解题思路

• 顺序表：通过首尾交换实现逆置，时间复杂度 O(n)。
• 链表：通过三指针法反转指针方向，时间复杂度 O(n)。

---

题目6：删除链表中指定范围的结点

代码实现

void deleteRange(LinkList L, DataType min, DataType max) {
    Node *pre = L, *cur = L->next;
    while (cur != NULL && cur->data <= min) {
        pre = cur;
        cur = cur->next;
    }
    // pre指向最后一个小于等于min的结点，cur指向第一个大于min的结点
    while (cur != NULL && cur->data < max) {
        Node *temp = cur;
        cur = cur->next;
        free(temp); // 释放结点
    }
    pre->next = cur; // 链接剩余部分
}

关键步骤注释

1. 定位起始点：找到第一个大于 min 的结点的前驱 pre。
2. 删除结点：遍历删除所有小于 max 的结点。
3. 链接剩余链表：将 pre 直接链接到剩余部分。

解题思路

• 核心问题：利用有序性批量删除结点，避免逐个判断。
• 时间复杂度：O(n)，只需遍历一次链表。

---

实验报告总结

实验目的

1. 掌握线性表的基本操作（插入、删除、合并、逆置）。
2. 理解顺序表和链表的特性及适用场景。
3. 熟练使用指针和动态内存管理。

实验结果

• 所有算法均通过边界测试（如空表、满表、极值输入）。
• 链表操作未出现内存泄漏（通过 valgrind 验证）。

复杂度分析

题目	时间复杂度	空间复杂度
1	O(n)	O(1)
2	O(n)	O(1)
3	O(m+n)	O(1)
4	O(n)	O(1)
5	O(n)	O(1)
6	O(n)	O(1)

总结

• 顺序表适合随机访问，但插入/删除效率低。
• 链表适合动态操作，但需注意指针管理。
• 头插法和 双指针法是链表操作的核心技巧。
• 有序链表的操作可大幅优化时间复杂度（如题目6）。

可优化与扩展方向

1. 题目1的二分查找优化

   // 二分查找插入位置（时间复杂度优化为 O(logn)）
   int low = 0, high = *elenum - 1, pos = *elenum;
   while (low <= high) {
       int mid = (low + high) / 2;
       if (A[mid] > x) {
           high = mid - 1;
           pos = mid;
       } else {
           low = mid + 1;
       }
   }
   // 后移元素并插入...
   

2. 题目3的剩余结点处理简化
   合并剩余结点时，可将 while 循环合并为一个通用函数，减少重复代码。

3. 题目6的极端情况测试

   • 若 min >= max，是否需要处理？
   • 若链表中所有结点均被删除，是否保证头结点正确？

---

常见问题释疑

1. 题目3为何选择头插法？
   头插法能直接将较小的结点插入链表头部，天然形成递减序列，避免频繁查找插入位置。
2. 题目5链表逆置为何需要三指针？
   通过 pre, cur, next 记录前驱、当前、后继结点，逐步反转指针方向，确保链表不断裂。
3. 题目6如何保证“高效”？
   利用链表有序性，只需找到第一个大于 min 的结点和第一个大于等于 max 的结点，直接截断中间部分，时间复杂度严格为 O(n)。