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

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

文章目录

• • @[toc]
• 线性表——顺序表详解与实现
• • 一、线性表概述
  • 二、顺序表核心概念
  • • 2.1 基本结构
    • • 1. 静态顺序表（不推荐）
      • 2. 动态顺序表（推荐）
  • 三、动态顺序表实现
  • • 3.1 数据结构定义
    • 3.2 核心接口说明
    • 3.3 关键代码实现（部分）
    • • 初始化与销毁
      • 动态扩容机制
      • 元素插入示例
    • 3.4 测试用例
  • 四、复杂度分析
  • 五、优劣分析

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

一、线性表概述

线性表是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 核心接口说明

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;
}

四、复杂度分析

五、优劣分析

1. 中间头部插入数据，需要挪动整体数据，效率低下。
2. 扩容时有一定的消耗，并且还可能会有一定的空间浪费（占着茅坑不拉屎）。

而这些问题，链表都可以解决、

它们各有各自的优势，更多的是你的使用场景，顺序表与链表是相辅相成的。

下一篇文章我会详细介绍链表。