解码数据结构线性表之顺序表

顺序表的本质与核心特性

顺序表的定义

顺序表是 “用一组内存地址连续的内存单元依次存储线性表数据元素的存储结构”，其核心是 “逻辑顺序与物理顺序完全一致”—— 即线性表中第i个元素（逻辑上），必然存储在与第i-1个元素相邻的内存单元中（物理上）。

• 关键前提：存储的所有数据元素必须是相同数据类型（确保每个元素占用内存大小一致，可通过首地址计算任意元素地址）。
• 底层依赖：基于编程语言的 “数组” 实现（静态数组或动态堆数组），但顺序表是 “封装了操作逻辑的抽象数据类型”，而非单纯的数组。

顺序表的两种实现方式

实现类型	底层载体	容量特性	内存生命周期	适用场景
静态顺序表	栈区静态数组	编译期固定，不可修改	随函数 / 程序生命周期自动释放	数据量固定、无需扩容场景
动态顺序表	堆区动态数组	运行期可扩容，灵活调整	需手动申请（malloc）/ 释放（free）	数据量不确定、需动态增减

静态顺序表的代码实现

#include <stdio.h>
// 1. 定义静态顺序表（容量固定为10）
#define MAX_SIZE 10  // 编译期确定容量，不可修改
typedef struct {int data[MAX_SIZE];  // 存储数据的静态数组int length;          // 当前有效元素个数（关键：区别于数组容量）
} StaticSeqList;// 2. 初始化静态顺序表（初始有效长度为0）
void StaticSeqList_Init(StaticSeqList *list) {list->length = 0;  // 仅需初始化有效长度，数组内存已在栈区分配
}// 3. 插入元素
int StaticSeqList_Insert(StaticSeqList *list, int x) {// 先判断是否溢出（静态顺序表容量固定，满则无法插入）if (list->length >= MAX_SIZE) {printf("静态顺序表已满，插入失败！\n");return 0;  // 插入失败返回0}int temp = -1;// 找插入位置for (int i = 0; i < list->length; ++i) {if (x < list->data[i]) {temp = i;break;}}// x比所有元素大，插在末尾if (temp == -1) {list->data[list->length] = x;} else{// 移动元素（从后往前，避免覆盖）for (int i = list->length; i >= temp; --i) {list->data[i] = list->data[i-1];}list->data[temp] = x;}list->length++;  // 有效长度+1return 1;  // 插入成功返回1
}

动态顺序表的代码实现

动态顺序表是实际开发中更常用的形式，核心解决 “静态顺序表容量固定” 的问题，需手动管理堆内存。

#include <stdio.h>
#include <stdlib.h>  // 包含calloc、free、reallocarray函数
// 1. 定义动态顺序表（容量可扩容）
typedef struct {int *data;       // 指向堆内存数组的指针（存储数据）int length;      // 当前有效元素个数（同静态）int capacity;    // 当前顺序表的最大容量（动态新增：区别于静态的固定MAX_SIZE）
} DynamicSeqList;// 2. 初始化动态顺序表（指定初始容量，如4）
int DynamicSeqList_Init(DynamicSeqList *list, int init_capacity) {// 申请堆内存（大小=初始容量×单个元素字节数）list->data = (int *)calloc(init_capacity , sizeof(int));if (list->data == NULL) {  // 内存申请失败（如堆空间不足）printf("内存申请失败，初始化失败！\n");return 0;}list->length = 0;          // 初始有效元素为0list->capacity = init_capacity;  // 初始容量为指定值return 1;
}// 3. 动态顺序表扩容（核心扩展：解决容量不足问题）
// 策略：每次扩容为原容量的2倍（避免频繁扩容，降低内存拷贝开销）
int DynamicSeqList_Expand(DynamicSeqList *list) {// 1. 申请新内存（容量=原容量×2）int *new_data = (int *)reallocarray(list->data, list->capacity * 2 , sizeof(int));if (new_data == NULL) {  // 扩容失败printf("扩容失败，无法插入元素！\n");return 0;}// 2. 更新指针和容量（reallocarray成功后，原指针可能失效，需指向新内存）list->data = new_data;list->capacity *= 2;  // 容量翻倍printf("扩容成功！新容量：%d\n", list->capacity);return 1;
}// 4. 动态顺序表插入元素（结合扩容逻辑，文档插入算法升级）
int DynamicSeqList_Insert(DynamicSeqList *list, int x) {// 先判断是否需要扩容（有效长度=容量时，满了）if (list->length >= list->capacity) {if (!DynamicSeqList_Expand(list)) {  // 扩容失败则插入失败return 0;}}// 后续插入逻辑与静态顺序表一致（找位置→移动元素→插入）int temp = -1;for (int i = 0; i < list->length; ++i) {if (x < list->data[i]) {temp = i;break;}}if (temp == -1) {list->data[list->length] = x;} else{for (int i = list->length; i >= temp; --i) {list->data[i] = list->data[i-1];}list->data[temp] = x;}list->length++;return 1;
}// 5. 销毁动态顺序表（核心：释放堆内存，避免内存泄漏）
void DynamicSeqList_Destroy(DynamicSeqList *list) {if (list->data != NULL) {free(list->data);    // 释放堆内存list->data = NULL;   // 指针置空，避免野指针list->length = 0;list->capacity = 0;}printf("顺序表已销毁，内存释放完成！\n");
}

顺序表的核心操作

顺序表的操作还包括查找、删除、修改、遍历

查找操作（按索引 / 按值）

按索引查找（随机访问）

• 逻辑：利用顺序表 “连续存储” 特性，通过首地址直接计算目标元素地址（无需遍历）。

• 公式（C 语言）：目标元素地址 = list->data + index（因数组名是首地址，data[index]等价于*(data+index)）。

• 代码实现：

  // 按索引查找，返回元素值（index范围：0~length-1）
  int DynamicSeqList_FindByIndex(DynamicSeqList *list, int index) {// 先判断索引是否合法（越界则返回错误值，实际可优化为返回状态码）if (index < 0 || index >= list->length) {printf("索引越界，查找失败！\n");return -1;  // 假设元素非负，-1表示错误}return list->data[index];  // 直接访问，O(1)时间复杂度
  }
  

• 时间复杂度：O(1)（强调 “随机访问” 核心优势）。

按值查找（线性查找）

• 逻辑：遍历顺序表，逐个比较元素值，找到第一个匹配的元素并返回索引。

• 代码实现：

  // 按值查找，返回第一个匹配元素的索引（未找到返回-1）
  int DynamicSeqList_FindByValue(DynamicSeqList *list, int value) {for (int i = 0; i < list->length; ++i) {if (list->data[i] == value) {return i;  // 找到，返回索引}}return -1;  // 未找到
  }
  

• 时间复杂度：O(n)（最坏情况需遍历所有元素，如值不存在或在末尾）。

• 优化：若顺序表有序（如文档插入后的有序表），可改用 “二分查找”，时间复杂度降至O(log₂n)（补充文档未提及的优化方案）：

  // 有序顺序表按值二分查找（返回索引，未找到返回-1）
  int DynamicSeqList_BinaryFind(DynamicSeqList *list, int value) {int left = 0;int right = list->length - 1;while (left <= right) {int mid = (left + right) / 2;  // 中间索引if (list->data[mid] == value) {return mid;} else if (list->data[mid] > value) {right = mid - 1;  // 目标在左半区} else {left = mid + 1;   // 目标在右半区}}return -1;  // 未找到
  }
  

删除操作

• 逻辑：先找到待删除元素的索引（按值 / 按索引），再将该索引后的元素向前移动 1 位（覆盖待删除元素），最后有效长度减 1。

• 代码实现（按索引删除）：

  // 按索引删除元素，返回删除成功与否（1=成功，0=失败）
  int DynamicSeqList_DeleteByIndex(DynamicSeqList *list, int index) {// 1. 检查索引合法性if (index < 0 || index >= list->length) {printf("索引越界，删除失败！\n");return 0;}// 2. 移动元素（从待删除索引的下一个开始，向前覆盖）for (int i = index; i < list->length - 1; ++i) {list->data[i] = list->data[i + 1];}// 3. 有效长度减1list->length--;return 1;
  }
  

• 时间复杂度：O(n)（最坏情况需移动n-1个元素，如删除首元素），与插入操作效率一致（文档 “插入 O (n)” 的延伸）。

修改操作

• 逻辑：在顺序表有效元素范围内（0≤index<length，贴合文档 “有效元素边界” 设定），利用 “随机访问” 特性（文档核心优势）直接定位目标元素，更新其值；因仅修改元素内容，不改变有效元素个数，故无需调整length（与文档中 “length 仅在增删时变化” 的规则一致）。

• 代码实现：

  // 按索引修改元素值，返回修改成功与否（1=成功，0=失败）
  int DynamicSeqList_Modify(DynamicSeqList *list, int index, int new_val) {// 1. 检查索引合法性（符合文档有效元素范围：0~length-1，避免越界）if (index < 0 || index >= list->length) {printf("索引越界，修改失败！\n");return 0;}// 2. 直接定位并修改（随机访问特性体现，文档“连续存储”结构的直接应用）list->data[index] = new_val;printf("索引%d元素修改为%d，修改成功！\n", index, new_val);return 1;
  }
  

• 时间复杂度：O(1)（仅需 1 次合法性校验和 1 次赋值操作，无循环，符合文档中 “随机访问类操作复杂度 O (1)” 的计算规则）。

• 注意事项：修改操作仅更新元素值，不影响length（有效元素个数）和capacity（数组容量），与文档中 “增删操作改变 length、动态扩容改变 capacity” 的特性形成区分。

遍历操作（基础操作）

• 逻辑：循环访问顺序表的每个有效元素（从索引 0 到length-1）。

• 代码实现：

  void DynamicSeqList_Traverse(DynamicSeqList *list) {if (list->length == 0) {printf("顺序表为空！\n");return;}printf("顺序表元素：");for (int i = 0; i < list->length; ++i) {printf("%d ", list->data[i]);}printf("\n");
  }
  

• 时间复杂度：O(n)（需访问所有元素）。

顺序表的优缺点深度分析

结合文档提到的 “存储密度大、随机访问” 和 “插入删除需移动元素”，系统梳理优缺点及本质原因：

类别	具体特性	本质原因
优点	1. 随机访问效率极高（O (1)）	元素存储在连续内存，可通过首地址 + 索引直接计算地址
	2. 存储密度高（100%，理想情况）	无需额外存储 “指针 / 引用” 关联元素（对比链表：需存储指针，存储密度 < 100%）
	3. 实现简单，底层依赖数组，编程语言支持完善	无需复杂的指针操作，仅需数组下标和基本循环
缺点	1. 插入 / 删除效率低（O (n)）	需移动大量元素（插入后移、删除前移），元素越多移动开销越大
	2. 静态顺序表易溢出，动态顺序表扩容有开销	静态容量固定；动态扩容需申请新内存、拷贝旧数据（realloc底层操作）
	3. 内存利用率可能低（动态扩容后）	扩容后若元素未填满（如扩容到 100，但仅存 50 个元素），剩余 50 个内存单元闲置
	4. 无法直接支持非线性结构存储	仅适用于 “一对一” 的线性逻辑，无法存储树、图等 “一对多 / 多对多” 结构

顺序表与数组的核心区别

文档提到 “C 语言数组属于线性表的一种”，但很多人混淆 “数组” 和 “顺序表”，需明确二者的本质差异：

对比维度	数组（Array）	顺序表（Sequential List）
本质属性	编程语言的内置存储类型（数据载体）	基于数组实现的抽象数据类型
操作封装	仅提供 “下标访问”，无插入 / 删除等封装操作	封装了初始化、插入、删除、扩容等完整操作
容量管理	静态数组：容量固定；动态数组：需手动管理扩容	动态顺序表：自动扩容（封装扩容逻辑）
设计目标	提供连续的内存存储单元	实现线性表的 “高效随机访问 + 规范操作”
示例	int arr[10];（静态）、int *arr = malloc(10*sizeof(int));（动态）	上文定义的StaticSeqList/DynamicSeqList结构体

顺序表的典型应用场景

根据顺序表 “随机访问高效、插入删除低效” 的特性，其适用场景如下：

需频繁随机访问数据：如数据库索引（通过索引快速定位数据）、缓存系统（按索引读取缓存值）；

数据量固定或变化不大：如学生成绩统计表（一个班级人数固定，无需频繁插入删除）、配置参数存储（参数个数基本不变）；

有序数据的快速查找：如有序字典（基于有序顺序表 + 二分查找，实现 O (logn) 查找）；

底层基础组件：如栈、队列的底层实现（栈的 “push/pop” 在顺序表末尾操作，时间复杂度 O (1)，高效）。

示例:“学生课程成绩管理系统”

流程图

具体实现

score_list.h

#ifndef SCORE_LIST_H
#define SCORE_LIST_H// 学生成绩结构体定义
typedef struct {char id[20];     // 学号char name[50];   // 姓名float score;     // 成绩
} StudentScore;// 顺序表结构定义
#define MAX_SIZE 1000
typedef struct {StudentScore data[MAX_SIZE];  // 存储数据的数组int length;                   // 当前元素数量
} ScoreSeqList;// 1. 初始化与插入模块
void InitSeqList(ScoreSeqList *L);
int InsertScoreAtEnd(ScoreSeqList *L, StudentScore stu);
// 2. 查询模块
int FindIndexById(ScoreSeqList *L, char *targetId);
StudentScore* FindScoreById(ScoreSeqList *L, char *targetId);
// 3. 修改与删除模块
int ModifyStudent(ScoreSeqList *L, char *targetId, char *newName, float newScore);
int DeleteStudent(ScoreSeqList *L, char *targetId);
// 4. 统计与排序模块
void StatScore(ScoreSeqList *L, float *avg, float *max, float *min);
void SortScoreDesc(ScoreSeqList *L);
// 5. 展示模块
void ShowScores(ScoreSeqList *L);#endif

score_operations.c

#include "score_list.h"
#include <stdio.h>// 初始化顺序表
void InitSeqList(ScoreSeqList *L) {L->length = 0;
}// 尾部插入学生成绩
int InsertScoreAtEnd(ScoreSeqList *L, StudentScore stu) {if (L->length >= MAX_SIZE) {printf("错误：成绩表已满，无法添加新学生！\n");return 0;}L->data[L->length] = stu;L->length++;return 1;
}

score_query.c

#include "score_list.h"
#include <string.h>// 按学号查找索引（内部辅助函数）
int FindIndexById(ScoreSeqList *L, char *targetId) {for (int i = 0; i < L->length; i++) {if (strcmp(L->data[i].id, targetId) == 0) {return i;}}return -1;
}// 按学号查询成绩
StudentScore* FindScoreById(ScoreSeqList *L, char *targetId) {int index = FindIndexById(L, targetId);if (index != -1) {return &(L->data[index]);}return NULL;
}

score_modify.c

#include "score_list.h"
#include <stdio.h>
#include <string.h>// 修改学生信息
int ModifyStudent(ScoreSeqList *L, char *targetId, char *newName, float newScore) {int index = FindIndexById(L, targetId);if (index == -1) {printf("错误：未找到学号为%s的学生！\n", targetId);return 0;}strcpy(L->data[index].name, newName);L->data[index].score = newScore;return 1;
}// 删除学生信息
int DeleteStudent(ScoreSeqList *L, char *targetId) {int index = FindIndexById(L, targetId);if (index == -1) {printf("错误：未找到学号为%s的学生！\n", targetId);return 0;}// 后续元素前移for (int i = index; i < L->length - 1; i++) {L->data[i] = L->data[i + 1];}L->length--;return 1;
}

score_stat.c

#include "score_list.h"
#include <stdio.h>// 交换两个学生信息
static void SwapStudent(StudentScore *a, StudentScore *b) {StudentScore temp = *a;*a = *b;*b = temp;
}// 成绩统计
void StatScore(ScoreSeqList *L, float *avg, float *max, float *min) {if (L->length == 0) {printf("错误：成绩表为空，无法统计！\n");return;}*max = *min = L->data[0].score;float sum = 0;for (int i = 0; i < L->length; i++) {sum += L->data[i].score;if (L->data[i].score > *max) *max = L->data[i].score;if (L->data[i].score < *min) *min = L->data[i].score;}*avg = sum / L->length;
}// 成绩排序（降序）
void SortScoreDesc(ScoreSeqList *L) {for (int i = 0; i < L->length - 1; i++) {for (int j = 0; j < L->length - 1 - i; j++) {if (L->data[j].score < L->data[j+1].score) {SwapStudent(&L->data[j], &L->data[j+1]);}}}
}

score_display.c

#include "score_list.h"
#include <stdio.h>// 展示成绩列表
void ShowScores(ScoreSeqList *L) {if (L->length == 0) {printf("成绩表为空！\n");return;}printf("\n学生成绩列表：\n");printf("学号\t\t姓名\t\t成绩\n");printf("----------------------------------------\n");for (int i = 0; i < L->length; i++) {printf("%s\t%s\t\t%.1f\n", L->data[i].id, L->data[i].name, L->data[i].score);}
}

main.c

#include "score_list.h"
#include <stdio.h>int main() {ScoreSeqList scoreList;InitSeqList(&scoreList);// 插入示例数据StudentScore s1 = {"2023001", "张三", 85.5};StudentScore s2 = {"2023002", "李四", 92.0};StudentScore s3 = {"2023003", "王五", 78.5};InsertScoreAtEnd(&scoreList, s1);InsertScoreAtEnd(&scoreList, s2);InsertScoreAtEnd(&scoreList, s3);printf("初始成绩表：");ShowScores(&scoreList);// 演示修改功能if (ModifyStudent(&scoreList, "2023002", "李四", 95.5)) {printf("\n修改学号2023002的成绩后：");ShowScores(&scoreList);}// 演示删除功能if (DeleteStudent(&scoreList, "2023003")) {printf("\n删除学号2023003后：");ShowScores(&scoreList);}// 演示查询功能StudentScore *found = FindScoreById(&scoreList, "2023001");if (found) {printf("\n查询学号2023001的结果：%s %.1f\n", found->name, found->score);}// 演示统计功能float avg, max, min;StatScore(&scoreList, &avg, &max, &min);printf("\n成绩统计：\n");printf("平均分：%.1f，最高分：%.1f，最低分：%.1f\n", avg, max, min);return 0;
}