线性表的C语言实现

### 线性表的C语言实现 #### 知识点概述 本文将详细介绍如何用C语言实现一种基本的数据结构——线性表，并通过具体的代码示例来展示其操作过程。线性表是一种常见的数据结构，它是由n(n≥0)个相同类型的元素构成的一个有限序列，通常包括以下几种基本操作： 1. **初始化**（创建一个空的线性表）。 2. **插入元素**（在指定位置插入一个新元素）。 3. **删除元素**（移除指定位置的元素）。 4. **查找元素**（搜索特定值的位置）。 5. **获取元素**（根据索引返回元素值）。 6. **计算长度**（返回线性表中的元素个数）。 7. **清空列表**（将线性表中的所有元素清除）。 #### C语言实现细节 ##### 定义线性表结构体 线性表可以通过一个结构体来表示，该结构体包含三个成员：一个指向元素数组的指针`data`、一个表示当前元素数量的整型变量`length`以及一个表示数组最大容量的整型变量`listsize`。 ```c typedef struct { ElemType *data; // 指向元素的指针 int length; // 当前线性表的实际长度 int listsize; // 线性表的最大容量 } SqList; ``` 这里`ElemType`被定义为`int`类型，意味着我们的线性表存储的是整数。 ##### 初始化线性表 初始化线性表时，我们需要分配一块内存用于存放元素，并设置`length`和`listsize`的初始值。 ```c int InitList(SqList *L) { L->data = (ElemType *)malloc(Initsize * sizeof(ElemType)); if (!L->data) return Error; L->length = 0; L->listsize = Initsize; return OK; } ``` 这里`Initsize`定义了初始容量大小，默认为100。 ##### 插入元素 插入操作需要判断是否需要扩展存储空间，并移动相应位置之后的所有元素。 ```c int ListInsert(SqList *L, int i, ElemType e) { if (i < 0 || i > L->length + 1) return Error; if (L->length >= L->listsize) { L->data = (ElemType *)realloc(L->data, (L->listsize + ListIncrement) * sizeof(ElemType)); L->listsize += ListIncrement; } if (!L->data) return Error; ElemType *p = &L->data[i - 1]; ElemType *q; for (q = L->data + L->length - 1; q >= p; q--) *(q + 1) = *q; *p = e; L->length++; return OK; } ``` ##### 删除元素 删除操作需要将待删元素之后的所有元素向前移动一位。 ```c int DeleteList(SqList *L, int i) { if (i < 0 || i > L->length) return Error; ElemType *p = &L->data[i - 2]; for (p++; p <= L->data + L->length - 2; p++) { *p = *(p + 1); } L->length--; return OK; } ``` ##### 查找元素 查找操作需要遍历线性表，找到满足条件的元素。 ```c int LocateElem(SqList *L, ElemType e) { int i; ElemType *p = L->data; for (i = 0; i < L->length; i++) if (compare(*(p + i), e)) return i; return 0; } ``` 其中`compare`函数用于比较两个元素是否相等。 ```c int compare(ElemType a, ElemType b) { if (a == b) return 1; else return 0; } ``` ##### 获取元素 获取操作返回线性表中指定位置的元素值。 ```c int GetElem(SqList L, int i, ElemType *p) { if (i < 0 || i > L.length) return 0; *p = L.data[i]; // 注意这里传递的是值，而不是指针 return OK; } ``` ##### 计算长度 计算线性表的长度即返回`length`字段的值。 ```c int ListLength(SqList L) { return L.length; } ``` ##### 清空线性表 清空操作会将`length`和`listsize`重置为0。 ```c int ClearList(SqList *L) { if (!L->data) return Error; L->length = L->listsize = 0; return OK; } ``` #### 示例代码解析 在主函数中，我们先初始化了一个线性表，并插入了一些初始数据，然后进行了插入、删除等操作，并输出结果，以此来验证各项功能的正确性。 ```c int main() { SqList list; InitList(&list); // 新建数据测试 int flag = 0; for (int i = 0; i < 10; i++) { list.data[i] = i + 1; } list.length = 10; printf("初始数据：\n"); for (int i = 0; i < 10; i++) { printf("%-3d", list.data[i]); } putchar('\n'); // 插入数据测试 flag = ListInsert(&list, 2, 2); printf("在第二个元素前插入元素2：\n此时线性表长度：\n"); printf("%d\n", list.length); for (int i = 0; i < list.length; i++) { printf("%-3d", list.data[i]); } putchar('\n'); DeleteList(&list, 5); printf("删除第五个元素：\n此时顺序表长度：\n"); printf("%d\n", list.length); for (int i = 0; i < list.length; i++) { // 获取数据测试 } return 0; } ``` 以上就是线性表的C语言实现方法及具体代码解析。通过这些基本操作，我们可以构建出更复杂的数据处理逻辑。