该资源包含了两个与数据结构相关的编程作业，分别是广工大学的数据结构课程中的排序算法实现。其中一个是插入排序（InsertSort），另一个是冒泡排序（BubbleSort）。代码涉及的数据结构为顺序列表（SqList），由键值对（KeyType key）组成，并用C语言实现。
首先，我们来详细解析插入排序的实现：
插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这里的代码实现了一个基于比较键值的插入排序方法：
```c
void InsertSort(SqList& L) {
int i, j;
for (i = 2; i <= L.length; ++i) { // 从第二个元素开始遍历
if (L.r[i].key < L.r[i - 1].key) { // 如果当前元素小于前一个元素
L.r[MAXSIZE] = L.r[i]; // 将当前元素暂存
L.r[i] = L.r[i - 1]; // 将前一个元素移到当前位置
for (j = i - 2; L.r[MAXSIZE].key < L.r[j].key && j > 0; --j) { // 查找合适的位置
L.r[j + 1] = L.r[j]; // 将元素向右移动
}
L.r[j + 1] = L.r[MAXSIZE]; // 插入暂存的元素
}
}
}
```
这段代码中，`L.r[MAXSIZE]` 用于暂存当前元素，避免在循环过程中改变原数组。`L.length` 表示列表的长度，`L.r` 是存储数据的数组。
接下来是冒泡排序的实现：
冒泡排序也是一种简单的排序算法，通过重复遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这里代码实现了一个基于比较的冒泡排序方法：
```c
void BubbleSort(SqList& L) {
int change = L.length;
while (change > 0) { // 当有元素交换时，change > 0，表示还需继续排序
change = 0;
for (int i = 1; i < L.length; ++i) {
if (LT(L.r[i], L.r[i - 1])) { // 如果当前元素小于前一个元素，进行交换
Swap(L.r[i], L.r[i - 1]);
++change;
}
}
}
}
```
这里定义了辅助函数 `StatusLT` 和 `StatusGT` 来进行元素之间的比较，以及 `voidSwap` 函数用于交换元素。冒泡排序的特点是每一轮遍历都能确定一个最大或最小元素的位置，因此当连续遍历无交换发生时，说明序列已经有序，可以提前结束排序。
总结起来，这两个作业主要涉及到数据结构中的顺序列表操作以及两种基础排序算法——插入排序和冒泡排序的实现。通过这样的练习，学生能够加深对数据结构和排序算法的理解，提高编程能力。
我的内容管理
展开
