数据结构 线性表习题
假设我们有一个顺序表 L，其中存储了一些元素。我们将通过这个算法来删除顺序表中最后一个大于其后继元素的元素。
1. 首先，我们初始化两个变量 i 和 j。
- 变量 i 作为循环变量，用于遍历顺序表 L 的元素。
- 变量 j 初始化为 0，用于记录最后一个满足条件的元素的位置。
2. 开始循环遍历顺序表 L。从位置 l（注意，这里 l 是一个变量）开始，一直遍历到顺序表的最后一个元素（索引为 L->length - 1）。
3. 在每次循环中，我们比较当前元素 L->data[i] 与其后继元素 L->data[i+1] 的值。
- 如果当前元素大于其后继元素，说明我们找到了满足条件的元素。我们将 j 更新为当前的位置 i，以便后续操作中删除该元素。
4. 循环结束后，我们得到顺序表 L 中最后一个大于其后继元素的元素的位置 j。
5. 接下来，我们使用另一个循环，从位置 j 开始，将顺序表 L 中后续元素依次左移一位，以覆盖掉最后一个大于其后继元素的元素。
- 也就是将 L->data[i] 的值更新为 L->data[i+1]，直到顺序表的倒数第二个元素（索引为 L->length - 2）。
6. 最后，我们将顺序表 L 的长度减一（L->length--），表示删除了一个元素。
这样，最后一个大于其后继元素的元素将被删除，并且顺序表的长度减小了一。
请注意，这段代码是使用 C 语言编写的，其中出现的 "->" 操作符用于访问指向结构体的指针中的成员。
该算法的目标是将元素 x 插入到顺序表 L 中，同时保持顺序表的有序性。
具体的执行过程如下：
1.声明两个变量 i 和 j，并将 j 初始化为 0。
2.使用一个循环从位置 l（变量 l 作为起始位置）开始遍历顺序表 L 的元素，直到遍历到顺序表的末尾。
3.在每次循环中，将当前元素 L->data[i] 与变量 j 所指向的元素进行比较。
4.如果当前元素 L->data[i] 小于或等于元素 L->data[j]，则将变量 j 更新为当前位置，以便记录最后一个小于或等于 x 的元素的位置。
5.循环结束后，变量 j 指向了顺序表 L 中最后一个小于或等于 x 的元素的位置。
6.接下来，使用另一个循环，从顺序表 L 的最后一个元素开始，依次将后续的元素向右移动一位，以腾出位置给新插入的元素 x。
7.在这个循环中，从位置 L->length 开始，直到位置 j，将 L->data[i] 的值更新为 L->data[i-1]，实现元素的右移。
8.在循环结束后，将元素 x 插入到位置 j 处，即将 L->data[j] 的值设置为 x。
9.最后，将顺序表 L 的长度加一，表示成功插入了一个元素。
这段代码的功能是将单链表 L1 的后一半元素截断，并将截断部分连接到另一个单链表 L2 中。具体步骤如下：
1. 遍历单链表 L1，统计单链表的长度 n。
2. 将指针 p 重新指向单链表 L1 的头结点。
3. 通过循环，将指针 p 移动到单链表的中间位置。
4. 将指针 L2 指向指针 p 的下一个结点，即单链表的后一半部分。
5. 将指针 p 的 next 指针置空，截断单链表 L1。
6. 最终得到的结果是，单链表 L1 包含前一半的元素，单链表 L2 包含后一半的元素。
为了设计一个高效的算法删除顺序表 L 中所有值在范围 [x, y] 内的元素，可以采用以下步骤：
1. 定义两个指针，一个指向遍历顺序表的当前位置，另一个指向将被覆盖的位置，初始时两个指针都指向顺序表的第一个位置。
2. 遍历整个顺序表，当当前元素的值在范围 [x, y] 内时，将指向当前位置的指针向后移动，直到指向的元素不在范围内。
3. 将指向当前位置的指针指向的元素复制到指向被覆盖位置的指针指向的位置，并将指向被覆盖位置的指针向后移动一位。
4. 重复步骤2和3直到遍历完整个顺序表。
5. 根据指向被覆盖位置的指针的当前位置，更新顺序表的长度。
以下是相应的代码实现：
```cpp
void fun(SqList *&L, ElemType x, ElemType y) {
int i, j;
int count = 0; // 计数，用于更新顺序表的长度
for (i = 0, j = 0; i < L->length; i++) {
if (L->data[i] < x || L->data[i] > y) {
L->data[j] = L->data[i];
j++;
} else {
count++;
}
}
L->length -= count;
}
```
这个算法的时间复杂度为 O(n)，其中 n 是顺序表中元素的个数。相比原始算法，只需一次遍历顺序表，无需在删除元素后移动其他元素，因此效率更高。