实现线性表的顺序存储定义,完成顺序表的创建、插入、删除、查找、排序等常用操作,完成两个有序线性表的合并,要求同样的数据元素只出现一次,C语言
时间: 2024-09-13 15:18:37 浏览: 75
线性表的顺序存储是使用一段连续的存储单元依次存储线性表的数据元素。顺序表通常是通过数组来实现的,数组的下标可以非常方便地进行各种线性表操作。
在C语言中,顺序表的创建通常是从分配一段连续的内存空间开始的。插入操作意味着在数组的某个位置插入新元素,这通常涉及到移动原有元素来腾出空间。删除操作则是移除数组中的某个元素,并需要将后续元素向前移动。查找操作通过遍历数组来寻找特定元素。排序操作则可以使用各种排序算法,比如冒泡排序、选择排序等,对顺序表中的元素进行排序。
以下是使用C语言实现顺序表及其基本操作的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100 // 定义顺序表的最大长度
// 顺序表的结构定义
typedef struct {
int data[MAXSIZE]; // 数组存储数据元素
int length; // 顺序表当前长度
} SeqList;
// 创建顺序表
void CreateList(SeqList *L, int n) {
if (n > MAXSIZE) return;
L->length = n;
for (int i = 0; i < n; ++i) {
scanf("%d", &L->data[i]);
}
}
// 插入操作
bool InsertList(SeqList *L, int i, int e) {
if (L->length == MAXSIZE || i < 1 || i > L->length + 1) return false;
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i - 1] = e;
L->length++;
return true;
}
// 删除操作
bool DeleteList(SeqList *L, int i) {
if (i < 1 || i > L->length) return false;
for (int j = i; j < L->length; j++) {
L->data[j - 1] = L->data[j];
}
L->length--;
return true;
}
// 查找操作
int LocateElem(SeqList L, int e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) return i + 1;
}
return 0;
}
// 排序操作(使用冒泡排序)
void BubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 合并两个有序顺序表
void MergeList(SeqList *L1, SeqList *L2) {
int i = L1->length, j = L2->length, k = L1->length + L2->length;
int *arr = (int *)malloc(k * sizeof(int));
while (i > 0 && j > 0) {
if (L1->data[i - 1] > L2->data[j - 1]) {
arr[k - 1] = L1->data[i - 1];
i--;
} else if (L1->data[i - 1] < L2->data[j - 1]) {
arr[k - 1] = L2->data[j - 1];
j--;
} else {
arr[k - 1] = L1->data[i - 1]; // 同等元素只添加一个
i--;
j--;
}
k--;
}
while (i > 0) arr[k--] = L1->data[i-- - 1];
while (j > 0) arr[k--] = L2->data[j-- - 1];
L1->length = L1->length + L2->length;
for (i = 0; i < L1->length; i++) {
L1->data[i] = arr[i];
}
free(arr);
}
int main() {
SeqList L1, L2;
int n1, n2, num;
printf("请输入第一个顺序表的长度和元素:\n");
scanf("%d", &n1);
CreateList(&L1, n1);
printf("请输入第二个顺序表的长度和元素:\n");
scanf("%d", &n2);
CreateList(&L2, n2);
// 插入元素示例
if (InsertList(&L1, 3, 100)) {
printf("插入成功\n");
} else {
printf("插入失败\n");
}
// 删除元素示例
if (DeleteList(&L1, 2)) {
printf("删除成功\n");
} else {
printf("删除失败\n");
}
// 查找元素示例
int index = LocateElem(L1, 10);
if (index) {
printf("元素10的索引位置是:%d\n", index);
} else {
printf("未找到元素10\n");
}
// 排序顺序表示例
BubbleSort(L1.data, L1.length);
printf("排序后的顺序表为:\n");
for (int i = 0; i < L1.length; i++) {
printf("%d ", L1.data[i]);
}
printf("\n");
// 合并有序顺序表示例
MergeList(&L1, &L2);
printf("合并后的顺序表为:\n");
for (int i = 0; i < L1.length; i++) {
printf("%d ", L1.data[i]);
}
printf("\n");
return 0;
}
```
这段代码实现了顺序表的基本操作,包括创建、插入、删除、查找和排序。同时,它还展示了如何合并两个有序顺序表。请注意,在实际使用中,数组的大小和数据类型可以根据实际需求进行修改。
阅读全文