重生之“我打数据结构,真的假的?”--1.顺序表(无习题)

时间:2024-10-23 09:10:07

在这里插入图片描述

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

1. 概述

顺序表(Sequential List)是一种线性数据结构,用于存储具有相同数据类型的一组元素。顺序表采用一段连续的存储空间,使用数组来实现,能够高效地支持随机访问操作。在 C 语言中,顺序表的实现通常基于数组,并且用户需要手动管理内存。顺序表适合用来解决需要快速访问元素的场景,尤其是当元素的数量较为稳定、不需要频繁插入或删除时。本文将详细讨论顺序表的定义、实现、各种操作的具体实现代码,以及顺序表的优缺点和实际应用场景。

2. 顺序表的基本概念

2.1 顺序表的定义

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

2.2 顺序表的特点

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

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

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

3.1 顺序表的数据结构定义

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

#include <stdio.h>
#include <stdlib.h>

#define INITIAL_CAPACITY 10

// 顺序表结构体定义
typedef struct {
    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 插入元素

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

// 插入元素
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;
}

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

3.4 删除元素

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

// 删除元素
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;
}

该函数首先检查删除位置是否合法,然后将删除位置之后的所有元素向前移动一个位置,最后减少顺序表的长度。

3.5 查找元素

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

  • 按值查找:找到指定值在顺序表中的位置。
// 查找元素(按值查找)
int findElementByValue(SequentialList *list, int value) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) {
            return i;  // 返回找到的索引
        }
    }
    return -1;  // 未找到
}

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

  • 按索引查找:获取指定索引处的元素。
// 查找元素(按索引查找)
int getElementByIndex(SequentialList *list, int index, int *value) {
    if (index < 0 || index >= list->length) {
        printf("索引无效\n");
        return 0;
    }
    *value = list->data[index];
    return 1;
}

该函数检查索引是否合法,然后通过索引获取元素的值。

3.6 遍历顺序表

遍历顺序表中的所有元素并打印出来。

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

该函数从头到尾遍历顺序表中的所有元素,并将它们打印到控制台。

4. 顺序表的优缺点

4.1 优点

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

4.2 缺点

  1. 插入和删除效率低:在顺序表中插入或删除元素时,可能需要移动大量的元素,时间复杂度为 O(n)。
  2. 内存分配不灵活:顺序表需要预先分配连续的内存,当需要扩展容量时,可能需要重新分配内存并复制原有数据,成本较高。
  3. 空间利用率问题:如果预分配的容量过大,会造成内存浪费;如果容量不足,需要频繁扩展,会影响性能。

5. 顺序表的应用场景

顺序表适用于以下场景:

  • 频繁随机访问:顺序表支持 O(1) 的随机访问,适合需要频繁访问任意位置元素的场景。
  • 元素数量相对固定:如果元素数量相对固定,不需要频繁插入和删除,顺序表是一个较好的选择。
  • 需要遍历操作:由于顺序表的元素存储在连续的内存空间中,遍历顺序表时可以充分利用 CPU 缓存,提高效率。

6. 示例代码汇总

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

#include <stdio.h>
#include <stdlib.h>

#define INITIAL_CAPACITY 10

// 顺序表结构体定义
typedef struct {
    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;
}

// 插入元素
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;
}

// 查找元素(按索引查找)
int getElementByIndex(SequentialList *list, int index, int *value) {
    if (index < 0 || index >= list->length) {
        printf("索引无效\n");
        return 0;
    }
    *value = list->data[index];
    return 1;
}

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

// 主函数
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. 总结

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