【初探数据结构】线性表———顺序表的详解和实现

我想吃余

发布于 2025-03-31 16:26:22

2350

文章被收录于专栏：数据结构初阶数据结构初阶 C语言学习

线性表——顺序表详解与实现

一、线性表概述

线性表是n个具有相同特性的数据元素的有限序列，其特点为逻辑上连续，但在物理存储上可分为顺序存储和链式存储。常见实现包括：

顺序表（本文重点）
链表
栈
队列
字符串

二、顺序表核心概念

2.1 基本结构

顺序表通过地址连续的存储单元依次存储数据元素，底层通常用数组实现。根据容量管理方式分为两类：

1. 静态顺序表（不推荐）

使用固定长度数组存储
特点：容量不可变，易造成空间浪费或不足

2. 动态顺序表（推荐）

使用动态数组存储
特点：支持按需扩容，内存利用率高

三、动态顺序表实现

3.1 数据结构定义

// SeqList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define INIT_CAPACITY 4  // 初始容量

typedef int SLDataType;
typedef struct {
    SLDataType* data;  // 数据存储数组
    int size;          // 当前元素个数
    int capacity;      // 当前分配的总容量
} SeqList;

3.2 核心接口说明

接口函数	功能说明
SeqListInit	初始化顺序表
SeqListDestroy	释放顺序表内存
SeqListPrint	打印顺序表内容
SeqListPushBack	尾部插入元素
SeqListPushFront	头部插入元素
SeqListInsert	在指定位置插入元素
SeqListPopBack	删除尾部元素
SeqListPopFront	删除头部元素
SeqListErase	删除指定位置元素
SeqListFind	查找元素返回下标

3.3 关键代码实现（部分）

初始化与销毁

// SeqList.c
void SeqListInit(SeqList* ps) {
    assert(ps);
    ps->data = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    if (!ps->data) {
        perror("[Error] Malloc failed");
        exit(EXIT_FAILURE);
    }
    ps->size = 0;
    ps->capacity = INIT_CAPACITY;
}

void SeqListDestroy(SeqList* ps) {
    assert(ps);
    free(ps->data);
    ps->data = NULL;
    ps->size = ps->capacity = 0;
}

动态扩容机制

// 内部扩容函数
static void CheckCapacity(SeqList* ps) {
    if (ps->size == ps->capacity) {
        SLDataType* new_data = realloc(ps->data, 
            sizeof(SLDataType) * ps->capacity * 2);
        if (!new_data) {
            perror("[Error] Realloc failed");
            exit(EXIT_FAILURE);
        }
        ps->data = new_data;
        ps->capacity *= 2;
        printf("扩容至 %d 容量\n", ps->capacity);
    }
}

元素插入示例

// 头插法
void SeqListPushFront(SeqList* ps, SLDataType x) {
    assert(ps);
    CheckCapacity(ps);  // 确保容量足够
    
    // 元素后移
    for (int i = ps->size; i > 0; i--) {
        ps->data[i] = ps->data[i-1];
    }
    ps->data[0] = x;
    ps->size++;
}

3.4 测试用例

// test.c
int main() {
    SeqList list;
    SeqListInit(&list);
    
    // 插入测试
    SeqListPushBack(&list, 10);
    SeqListPushFront(&list, 5);
    SeqListInsert(&list, 1, 7);
    
    // 打印结果应为：5 7 10
    SeqListPrint(&list);
    
    // 删除测试
    SeqListPopFront(&list);
    SeqListErase(&list, 1);
    
    // 打印结果应为：7
    SeqListPrint(&list);
    
    SeqListDestroy(&list);
    return 0;
}

四、复杂度分析

操作	时间复杂度	说明
随机访问	O(1)	通过下标直接访问
头部插入	O(n)	需移动所有元素
尾部插入	均摊O(1)	可能触发扩容
中间插入	O(n)	需移动后续元素
删除操作	O(n)	与插入类似