数据结构：顺序表- 惊觉

一、什么是顺序表

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素的线性结构。它是线性表的顺序存储实现，在C语言中通常用数组来实现。

核心特点

二、顺序表的两种实现方式

方式1：静态分配（定长数组）

#define MAXSIZE 100
typedef int ElemType;

typedef struct 
{
    ElemType data[MAXSIZE];  // 定长数组
    int length;              // 当前长度
} SqList;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

方式2：动态分配（推荐）

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

#define INIT_SIZE 10      // 初始容量
#define INCREMENT 10      // 扩容增量

typedef int ElemType;

typedef struct
{
    ElemType *data;       // 指向动态数组的指针
    int length;           // 当前元素个数
    int capacity;         // 当前最大容量
} SqList;

优点：可按需扩容，更灵活

三、基本操作完整实现

1. 初始化

bool InitList(SqList *L) 
{
    L->data = (ElemType *)malloc(INIT_SIZE * sizeof(ElemType));
    if (L->data == NULL) 
    {
        return false;               // 内存分配失败
    }
    L->length = 0;
    L->capacity = INIT_SIZE;
    return true;
}

2. 销毁

void DestroyList(SqList *L) {
    free(L->data);
    L->data = NULL;
    L->length = 0;
    L->capacity = 0;
}

3. 扩容（关键辅助函数）

static bool ExpandCapacity(SqList *L) 
{
    if (L->length < L->capacity) return true;  // 无需扩容

    int newCap = L->capacity + INCREMENT;
    ElemType *newData = (ElemType *)realloc(L->data, newCap * sizeof(ElemType));
    if (newData == NULL) return false;         // 扩容失败

    L->data = newData;
    L->capacity = newCap;
    return true;
}

realloc 可能返回新地址，必须用临时变量接收，避免原指针丢失导致内存泄漏

4. 插入（在第 i 个位置插入，1 ≤ i ≤ length+1）

bool ListInsert(SqList *L, int i, ElemType e) 
{
    if (i < 1 || i > L->length + 1) 
    return false;  // 位置非法
    if (!ExpandCapacity(L)) 
    return false;          // 容量不足则扩容

    // 从后往前，将第 i 到 length 个元素后移一位
    for (int j = L->length; j >= i; j--) 
    {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;   // 注意下标转换：第 i 个 -> 下标 i-1
    L->length++;
    return true;
}

时间复杂度：最好 O(1)（表尾插入），最坏 O(n)（表头插入），平均 O(n)

5. 删除

bool ListDelete(SqList *L, int i, ElemType *e)
{
    if (i < 1 || i > L->length) 
    return false;   // 位置非法
    *e = L->data[i - 1];                        // 保存被删元素

    // 将第 i+1 到 length 个元素前移一位
    for (int j = i; j < L->length; j++) 
    {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return true;
}

6. 按位查找

bool GetElem(const SqList *L, int i, ElemType *e) 
{
    if (i < 1 || i > L->length) 
    return false;
    *e = L->data[i - 1];
    return true;
}

时间复杂度：O(1) —— 顺序表的核心优势

7. 按值查找

int LocateElem(const SqList *L, ElemType e) 
{
    for (int i = 0; i < L->length; i++) 
    {
        if (L->data[i] == e) return i + 1;   // 返回位序（1-based）
    }
    return 0;   // 未找到
}

8. 遍历打印

void PrintList(const SqList *L) 
{
    printf("List[%d/%d]: ", L->length, L->capacity);
    for (int i = 0; i < L->length; i++) 
    {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2502_92937908/article/details/170242677

数据结构：顺序表