使用顺序存储结构,完成顺序表的创建,并实现对顺序表的直接插入排序、冒泡排序的问题。
时间: 2024-03-10 16:49:31 浏览: 57
数据结构中的排序(直接插入,冒泡等算法)
好的,我可以回答你的问题。
首先,顺序存储结构是一种使用连续的存储单元依次存储数据元素的方法。在创建顺序表时,我们需要定义一个数组来存储数据元素,同时记录顺序表的长度。下面是一个简单的示例代码:
```c
#define MAXSIZE 100 // 定义顺序表的最大长度
typedef struct {
int data[MAXSIZE]; // 用数组存储数据元素
int length; // 顺序表的长度
} SqList;
// 创建一个顺序表
void createList(SqList *L, int a[], int n) {
int i;
for (i = 0; i < n; i++) {
L->data[i] = a[i];
}
L->length = n;
}
```
接下来是直接插入排序的实现。直接插入排序的思路是将一个无序序列中的每个元素插入到已经排好序的序列中,使之成为一个新的有序序列。具体步骤如下:
1. 将序列的第一个元素看作是已排序的序列,从第二个元素开始遍历。
2. 每次取出一个元素,在已排序的序列中从后往前比较,找到第一个比它小的元素的位置。
3. 将该元素插入到该位置之后,已排序序列长度加1。
4. 重复步骤2-3,直到遍历完所有元素。
下面是直接插入排序的代码实现:
```c
// 直接插入排序
void insertSort(SqList *L) {
int i, j;
for (i = 1; i < L->length; i++) {
if (L->data[i] < L->data[i-1]) { // 需要插入到已排序序列中
int temp = L->data[i]; // 暂存待插入元素
j = i - 1;
while (j >= 0 && temp < L->data[j]) { // 在已排序序列中找到待插入位置
L->data[j+1] = L->data[j]; // 元素后移
j--;
}
L->data[j+1] = temp; // 插入元素
}
}
}
```
最后是冒泡排序的实现。冒泡排序的基本思想是相邻元素比较,如果逆序就交换,每次遍历都会将一个最大的元素“冒泡”到序列的最后面。具体步骤如下:
1. 比较相邻的两个元素,如果逆序就交换。
2. 从头开始遍历序列,重复步骤1,直到遍历到倒数第二个元素。
3. 重复步骤1-2,直到序列完全有序。
下面是冒泡排序的代码实现:
```c
// 冒泡排序
void bubbleSort(SqList *L) {
int i, j;
for (i = 0; i < L->length-1; i++) {
for (j = 0; j < L->length-i-1; j++) {
if (L->data[j] > L->data[j+1]) { // 相邻元素逆序
int temp = L->data[j];
L->data[j] = L->data[j+1];
L->data[j+1] = temp;
}
}
}
}
```
以上就是顺序表的创建、直接插入排序、冒泡排序的实现。希望能够帮到你。
阅读全文