重生之“我打数据结构，真的假的？”--1.顺序表（无习题）
C语言中的顺序表详细总结
1. 概述
顺序表（Sequential List）是一种线性数据结构，用于存储具有相同数据类型的一组元素。顺序表采用一段连续的存储空间，使用数组来实现，能够高效地支持随机访问操作。在 C 语言中，顺序表的实现通常基于数组，并且用户需要手动管理内存。顺序表适合用来解决需要快速访问元素的场景，尤其是当元素的数量较为稳定、不需要频繁插入或删除时。本文将详细讨论顺序表的定义、实现、各种操作的具体实现代码，以及顺序表的优缺点和实际应用场景。
2. 顺序表的基本概念
2.1 顺序表的定义
顺序表是一种存储线性表的顺序存储结构，其存储单元采用一段连续的内存区域，可以直接通过索引来访问任意元素。这使得顺序表在进行随机访问时效率非常高，时间复杂度为 O(1)。然而，由于内存是连续的，所以在插入或删除元素时，可能需要移动大量的数据，因此插入和删除操作的时间复杂度较高。
2.2 顺序表的特点
- 连续存储：顺序表的元素存储在连续的内存空间中。
- 随机访问：可以通过下标直接访问元素，时间复杂度为 O(1)。
- 内存分配：顺序表的内存大小通常在初始化时分配，若需要动态扩展，则需要重新分配内存。
3. 顺序表的基本操作实现
顺序表的基本操作包括初始化、插入、删除、查找和遍历。以下我们通过 C 语言代码实现这些操作，以帮助理解顺序表的工作原理。
3.1 顺序表的数据结构定义
首先，定义顺序表的结构体。该结构体包含一个指针指向存储数据的数组，以及顺序表的当前长度和最大容量。
#include<stdio.h>#include<stdlib.h>#defineINITIAL_CAPACITY10// 顺序表结构体定义typedefstruct{int*data;// 存储数据的数组int length;// 当前顺序表的长度int capacity;// 顺序表的容量} SequentialList;在上述代码中，我们定义了一个名为 SequentialList 的结构体，其中 data 是一个指向 int 类型数组的指针，length 表示当前顺序表中的元素个数，capacity 表示顺序表的最大容量。
3.2 初始化顺序表
接下来，实现初始化顺序表的函数。该函数分配一段内存作为顺序表的存储空间，并初始化其长度和容量。
// 初始化顺序表 SequentialList*initList(int capacity){ SequentialList *list =(SequentialList*)malloc(sizeof(SequentialList));if(list ==NULL){printf("内存分配失败\n");exit(1);} list->data =(int*)malloc(sizeof(int)* capacity);if(list->data ==NULL){printf("内存分配失败\n");free(list);exit(1);} list->length =0; list->capacity = capacity;return list;}该函数首先为 SequentialList 结构体本身分配内存，然后为数据数组分配内存，并设置初始长度为 0，容量为传入的参数值。
3.3 插入元素
顺序表支持在指定位置插入元素。如果插入的位置无效或者顺序表已满，则需要进行相应处理。
// 插入元素intinsertElement(SequentialList *list,int index,int value){if(index <0|| index > list->length){printf("插入位置无效\n");return0;}// 如果顺序表已满，扩展容量if(list->length == list->capacity){int newCapacity = list->capacity *2;int*newData =(int*)realloc(list->data,sizeof(int)* newCapacity);if(newData ==NULL){printf("内存扩展失败\n");return0;} list->data = newData; list->capacity = newCapacity;}// 从插入位置开始，向后移动元素for(int i = list->length; i > index; i--){ list->data[i]= list->data[i -1];}// 插入新元素 list->data[index]= value; list->length++;return1;}该函数首先检查插入位置是否合法，然后判断顺序表是否已满，若已满则通过 realloc 扩展顺序表的容量。接着，将插入位置之后的元素依次后移，最后将新元素插入到指定位置。
3.4 删除元素
顺序表的删除操作同样涉及到移动元素。删除指定位置的元素后，需要将后续元素前移，以保持顺序表的连续性。
// 删除元素intdeleteElement(SequentialList *list,int index){if(index <0|| index >= list->length){printf("删除位置无效\n");return0;}// 从删除位置开始，向前移动元素for(int i = index; i < list->length -1; i++){ list->data[i]= list->data[i +1];} list->length--;return1;}该函数首先检查删除位置是否合法，然后将删除位置之后的所有元素向前移动一个位置，最后减少顺序表的长度。
3.5 查找元素
查找元素的操作可以分为按值查找和按索引查找。
- 按值查找：找到指定值在顺序表中的位置。
// 查找元素（按值查找）intfindElementByValue(SequentialList *list,int value){for(int i =0; i < list->length; i++){if(list->data[i]== value){return i;// 返回找到的索引}}return-1;// 未找到}该函数遍历顺序表中的所有元素，找到与指定值匹配的元素，并返回其索引。如果没有找到，返回 -1。
- 按索引查找：获取指定索引处的元素。
// 查找元素（按索引查找）intgetElementByIndex(SequentialList *list,int index,int*value){if(index <0|| index >= list->length){printf("索引无效\n");return0;}*value = list->data[index];return1;}该函数检查索引是否合法，然后通过索引获取元素的值。
3.6 遍历顺序表
遍历顺序表中的所有元素并打印出来。
// 遍历顺序表voidtraverseList(SequentialList *list){for(int i =0; i < list->length; i++){printf("%d ", list->data[i]);}printf("\n");}该函数从头到尾遍历顺序表中的所有元素，并将它们打印到控制台。
4. 顺序表的优缺点
4.1 优点
- 随机访问效率高：顺序表支持通过下标访问任意元素，时间复杂度为 O(1)，这使得其在需要频繁随机访问的场景中表现优异。
- 内存紧凑：顺序表中的元素存储在连续的内存空间中，因此不存在指针的额外内存开销。
- 遍历效率高：由于顺序表使用连续的存储空间，遍历顺序表时可以很好地利用 CPU 缓存，提高访问效率。
4.2 缺点
- 插入和删除效率低：在顺序表中插入或删除元素时，可能需要移动大量的元素，时间复杂度为 O(n)。
- 内存分配不灵活：顺序表需要预先分配连续的内存，当需要扩展容量时，可能需要重新分配内存并复制原有数据，成本较高。
- 空间利用率问题：如果预分配的容量过大，会造成内存浪费；如果容量不足，需要频繁扩展，会影响性能。
5. 顺序表的应用场景
顺序表适用于以下场景：
- 频繁随机访问：顺序表支持 O(1) 的随机访问，适合需要频繁访问任意位置元素的场景。
- 元素数量相对固定：如果元素数量相对固定，不需要频繁插入和删除，顺序表是一个较好的选择。
- 需要遍历操作：由于顺序表的元素存储在连续的内存空间中，遍历顺序表时可以充分利用 CPU 缓存，提高效率。
6. 示例代码汇总
下面是一个完整的示例代码，展示了顺序表的基本操作，包括初始化、插入、删除、查找和遍历。
#include<stdio.h>#include<stdlib.h>#defineINITIAL_CAPACITY10// 顺序表结构体定义typedefstruct{int*data;int length;int capacity;} SequentialList;// 初始化顺序表 SequentialList*initList(int capacity){ SequentialList *list =(SequentialList*)malloc(sizeof(SequentialList));if(list ==NULL){printf("内存分配失败\n");exit(1);} list->data =(int*)malloc(sizeof(int)* capacity);if(list->data ==NULL){printf("内存分配失败\n");free(list);exit(1);} list->length =0; list->capacity = capacity;return list;}// 插入元素intinsertElement(SequentialList *list,int index,int value){if(index <0|| index > list->length){printf("插入位置无效\n");return0;}if(list->length == list->capacity){int newCapacity = list->capacity *2;int*newData =(int*)realloc(list->data,sizeof(int)* newCapacity);if(newData ==NULL){printf("内存扩展失败\n");return0;} list->data = newData; list->capacity = newCapacity;}for(int i = list->length; i > index; i--){ list->data[i]= list->data[i -1];} list->data[index]= value; list->length++;return1;}// 删除元素intdeleteElement(SequentialList *list,int index){if(index <0|| index >= list->length){printf("删除位置无效\n");return0;}for(int i = index; i < list->length -1; i++){ list->data[i]= list->data[i +1];} list->length--;return1;}// 查找元素（按值查找）intfindElementByValue(SequentialList *list,int value){for(int i =0; i < list->length; i++){if(list->data[i]== value){return i;}}return-1;}// 查找元素（按索引查找）intgetElementByIndex(SequentialList *list,int index,int*value){if(index <0|| index >= list->length){printf("索引无效\n");return0;}*value = list->data[index];return1;}// 遍历顺序表voidtraverseList(SequentialList *list){for(int i =0; i < list->length; i++){printf("%d ", list->data[i]);}printf("\n");}// 主函数intmain(){ SequentialList *list =initList(INITIAL_CAPACITY);insertElement(list,0,10);insertElement(list,1,20);insertElement(list,2,30);traverseList(list);deleteElement(list,1);traverseList(list);int index =findElementByValue(list,30);if(index !=-1){printf("元素 30 的索引为: %d\n", index);}int value;if(getElementByIndex(list,1,&value)){printf("索引 1 处的元素为: %d\n", value);}// 释放内存free(list->data);free(list);return0;}7. 总结
顺序表是一种使用连续内存存储线性数据的结构，适合需要快速随机访问的应用场景。通过本文的总结，介绍了顺序表的定义、实现、基本操作、优缺点及应用场景。顺序表的实现虽然简单，但其对内存的要求较高，适用于元素数量固定、插入和删除操作较少的情况。在实际开发中，顺序表是基础数据结构之一，可以有效帮助理解和构建更复杂的数据结构。
