重生之“我打数据结构，真的假的？”--1.顺序表（无习题） ...

C语言中的顺序表详细总结

1. 概述

顺序表（Sequential List）是一种线性数据结构，用于存储具有相同数据类型的一组元素。顺序表采用一段连续的存储空间，利用数组来实现，可以或许高效地支持随机访问操纵。在 C 语言中，顺序表的实现通常基于数组，而且用户必要手动管理内存。顺序表得当用来解决必要快速访问元素的场景，尤其是当元素的数目较为稳固、不必要频繁插入或删除时。本文将详细讨论顺序表的定义、实现、各种操纵的详细实现代码，以及顺序表的优缺点和实际应用场景。
2. 顺序表的基本概念

2.1 顺序表的定义

顺序表是一种存储线性表的顺序存储结构，其存储单元采用一段连续的内存区域，可以直接通过索引来访问任意元素。这使得顺序表在进行随机访问时服从非常高，时间复杂度为 O(1)。然而，由于内存是连续的，以是在插入或删除元素时，大概必要移动大量的数据，因此插入和删除操纵的时间复杂度较高。
2.2 顺序表的特点

• 连续存储：顺序表的元素存储在连续的内存空间中。
  
• 随机访问：可以通过下标直接访问元素，时间复杂度为 O(1)。
  
• 内存分配：顺序表的内存大小通常在初始化时分配，若必要动态扩展，则必要重新分配内存。
  

3. 顺序表的基本操纵实现

顺序表的基本操纵包括初始化、插入、删除、查找和遍历。以下我们通过 C 语言代码实现这些操纵，以帮助理解顺序表的工作原理。
3.1 顺序表的数据结构定义

首先，定义顺序表的结构体。该结构体包含一个指针指向存储数据的数组，以及顺序表的当前长度和最大容量。

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define INITIAL_CAPACITY 10
6. // 顺序表结构体定义
7. typedef struct {
8.     int *data;       // 存储数据的数组
9.     int length;      // 当前顺序表的长度
10.     int capacity;    // 顺序表的容量
11. } SequentialList;

复制代码

在上述代码中，我们定义了一个名为 SequentialList 的结构体，其中 data 是一个指向 int 类型数组的指针，length 表现当前顺序表中的元素个数，capacity 表现顺序表的最大容量。
3.2 初始化顺序表

接下来，实现初始化顺序表的函数。该函数分配一段内存作为顺序表的存储空间，并初始化其长度和容量。

1. // 初始化顺序表
2. SequentialList* initList(int capacity) {
3.     SequentialList *list = (SequentialList*)malloc(sizeof(SequentialList));
4.     if (list == NULL) {
5.         printf("内存分配失败\n");
6.         exit(1);
7.     }
8.     list->data = (int*)malloc(sizeof(int) * capacity);
9.     if (list->data == NULL) {
10.         printf("内存分配失败\n");
11.         free(list);
12.         exit(1);
13.     }
14.     list->length = 0;
15.     list->capacity = capacity;
16.     return list;
17. }

复制代码

该函数首先为 SequentialList 结构体本因素配内存，然后为数据数组分配内存，并设置初始长度为 0，容量为传入的参数值。
3.3 插入元素

顺序表支持在指定位置插入元素。如果插入的位置无效或者顺序表已满，则必要进行相应处理惩罚。

1. // 插入元素
2. int insertElement(SequentialList *list, int index, int value) {
3.     if (index < 0 || index > list->length) {
4.         printf("插入位置无效\n");
5.         return 0;
6.     }
7.     // 如果顺序表已满，扩展容量
8.     if (list->length == list->capacity) {
9.         int newCapacity = list->capacity * 2;
10.         int *newData = (int*)realloc(list->data, sizeof(int) * newCapacity);
11.         if (newData == NULL) {
12.             printf("内存扩展失败\n");
13.             return 0;
14.         }
15.         list->data = newData;
16.         list->capacity = newCapacity;
17.     }
18.     // 从插入位置开始，向后移动元素
19.     for (int i = list->length; i > index; i--) {
20.         list->data[i] = list->data[i - 1];
21.     }
22.     // 插入新元素
23.     list->data[index] = value;
24.     list->length++;
25.     return 1;
26. }

复制代码

该函数首先检查插入位置是否合法，然后判断顺序表是否已满，若已满则通过 realloc 扩展顺序表的容量。接着，将插入位置之后的元素依次后移，最后将新元素插入到指定位置。
3.4 删除元素

顺序表的删除操纵同样涉及到移动元素。删除指定位置的元素后，必要将后续元素前移，以保持顺序表的连续性。

1. // 删除元素
2. int deleteElement(SequentialList *list, int index) {
3.     if (index < 0 || index >= list->length) {
4.         printf("删除位置无效\n");
5.         return 0;
6.     }
7.     // 从删除位置开始，向前移动元素
8.     for (int i = index; i < list->length - 1; i++) {
9.         list->data[i] = list->data[i + 1];
10.     }
11.     list->length--;
12.     return 1;
13. }

复制代码

该函数首先检查删除位置是否合法，然后将删除位置之后的全部元素向前移动一个位置，最后镌汰顺序表的长度。
3.5 查找元素

查找元素的操纵可以分为按值查找和按索引查找。

• 按值查找：找到指定值在顺序表中的位置。
  

1. // 查找元素（按值查找）
2. int findElementByValue(SequentialList *list, int value) {
3.     for (int i = 0; i < list->length; i++) {
4.         if (list->data[i] == value) {
5.             return i;  // 返回找到的索引
6.         }
7.     }
8.     return -1;  // 未找到
9. }

复制代码

该函数遍历顺序表中的全部元素，找到与指定值匹配的元素，并返回其索引。如果没有找到，返回 -1。

• 按索引查找：获取指定索引处的元素。
  

1. // 查找元素（按索引查找）
2. int getElementByIndex(SequentialList *list, int index, int *value) {
3.     if (index < 0 || index >= list->length) {
4.         printf("索引无效\n");
5.         return 0;
6.     }
7.     *value = list->data[index];
8.     return 1;
9. }

复制代码

该函数检查索引是否合法，然后通过索引获取元素的值。
3.6 遍历顺序表

遍历顺序表中的全部元素并打印出来。

1. // 遍历顺序表
2. void traverseList(SequentialList *list) {
3.     for (int i = 0; i < list->length; i++) {
4.         printf("%d ", list->data[i]);
5.     }
6.     printf("\n");
7. }

复制代码

该函数从头到尾遍历顺序表中的全部元素，并将它们打印到控制台。
4. 顺序表的优缺点

4.1 优点

• 随机访问服从高：顺序表支持通过下标访问任意元素，时间复杂度为 O(1)，这使得其在必要频繁随机访问的场景中表现优异。
  
• 内存紧凑：顺序表中的元素存储在连续的内存空间中，因此不存在指针的额外内存开销。
  
• 遍历服从高：由于顺序表利用连续的存储空间，遍历顺序表时可以很好地利用 CPU 缓存，提高访问服从。
  

4.2 缺点

• 插入和删除服从低：在顺序表中插入或删除元素时，大概必要移动大量的元素，时间复杂度为 O(n)。
  
• 内存分配不机动：顺序表必要预先分配连续的内存，当必要扩展容量时，大概必要重新分配内存并复制原有数据，本钱较高。
  
• 空间利用率问题：如果预分配的容量过大，会造成内存浪费；如果容量不足，必要频繁扩展，会影响性能。
  

5. 顺序表的应用场景

顺序表实用于以了局景：

• 频繁随机访问：顺序表支持 O(1) 的随机访问，得当必要频繁访问任意位置元素的场景。
  
• 元素数目相对固定：如果元素数目相对固定，不必要频繁插入和删除，顺序表是一个较好的选择。
  
• 必要遍历操纵：由于顺序表的元素存储在连续的内存空间中，遍历顺序表时可以充实利用 CPU 缓存，提高服从。
  

6. 示例代码汇总

下面是一个完整的示例代码，展示了顺序表的基本操纵，包括初始化、插入、删除、查找和遍历。

1. #include <stdio.h>#include <stdlib.h>#define INITIAL_CAPACITY 10// 顺序表结构体定义typedef struct {    int *data;    int length;    int capacity;} SequentialList;// 初始化顺序表
2. SequentialList* initList(int capacity) {
3.     SequentialList *list = (SequentialList*)malloc(sizeof(SequentialList));
4.     if (list == NULL) {
5.         printf("内存分配失败\n");
6.         exit(1);
7.     }
8.     list->data = (int*)malloc(sizeof(int) * capacity);
9.     if (list->data == NULL) {
10.         printf("内存分配失败\n");
11.         free(list);
12.         exit(1);
13.     }
14.     list->length = 0;
15.     list->capacity = capacity;
16.     return list;
17. }
18. // 插入元素int insertElement(SequentialList *list, int index, int value) {    if (index < 0 || index > list->length) {        printf("插入位置无效\n");        return 0;    }    if (list->length == list->capacity) {        int newCapacity = list->capacity * 2;        int *newData = (int*)realloc(list->data, sizeof(int) * newCapacity);        if (newData == NULL) {            printf("内存扩展失败\n");            return 0;        }        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++;    return 1;}// 删除元素int deleteElement(SequentialList *list, int index) {    if (index < 0 || index >= list->length) {        printf("删除位置无效\n");        return 0;    }    for (int i = index; i < list->length - 1; i++) {        list->data[i] = list->data[i + 1];    }    list->length--;    return 1;}// 查找元素（按值查找）int findElementByValue(SequentialList *list, int value) {    for (int i = 0; i < list->length; i++) {        if (list->data[i] == value) {            return i;        }    }    return -1;}// 查找元素（按索引查找）
19. int getElementByIndex(SequentialList *list, int index, int *value) {
20.     if (index < 0 || index >= list->length) {
21.         printf("索引无效\n");
22.         return 0;
23.     }
24.     *value = list->data[index];
25.     return 1;
26. }
27. // 遍历顺序表
28. void traverseList(SequentialList *list) {
29.     for (int i = 0; i < list->length; i++) {
30.         printf("%d ", list->data[i]);
31.     }
32.     printf("\n");
33. }
34. // 主函数int main() {    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);    return 0;}

复制代码

7. 总结

顺序表是一种利用连续内存存储线性数据的结构，得当必要快速随机访问的应用场景。通过本文的总结，介绍了顺序表的定义、实现、基本操纵、优缺点及应用场景。顺序表的实现虽然简朴，但其对内存的要求较高，实用于元素数目固定、插入和删除操纵较少的情况。在实际开发中，顺序表是底子数据结构之一，可以有效帮助理解和构建更复杂的数据结构。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。