数据结构基础：顺序表
一、数据结构简介
1. 什么是数据结构？
数据结构是计算机存储、组织数据的方式。
C算法
数据结构基础：顺序表的定义与实现
顺序表是线性表的顺序存储结构，底层为数组，分为静态和动态两种。动态顺序表支持内存自动扩容。核心功能包括初始化、销毁、尾插、头插、指定位置插入、尾删、头删、指定位置删除、查找及修改。实现时需注意内存管理、指针传递及边界检查，确保数据安全。
顺序表是线性表的顺序存储结构，底层为数组，分为静态和动态两种。动态顺序表支持内存自动扩容。核心功能包括初始化、销毁、尾插、头插、指定位置插入、尾删、头删、指定位置删除、查找及修改。实现时需注意内存管理、指针传递及边界检查，确保数据安全。
数据结构是计算机存储、组织数据的方式。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
在学习了数组概念后，如果数据量过大，仅用数组可能难以高效管理。数据结构以结构化的形式进行数据管理，提高效率和可维护性。
线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。常见的线性表包括：顺序表、链表、栈、队列、字符串等。 线性表在逻辑上是线性结构，但在物理结构上并不一定是连续的。通常以数组和链式结构的形式存储。
顺序表是一种线性表的顺序存储结构，底层结构为数组，即以一组地址连续的存储单元进行存储。 顺序表中可以存储任何类型的数据（整型、字符型、结构体、指针等）。
大小固定不可改变，采用定长数组创建。
// 静态顺序表
typedef int SLDataType;
#define N 10
typedef struct SeqList {
SLDataType arr[N];
int size;
} SL;
缺点：空间确定，给多了浪费，给少了不够。
拥有动态改变内存大小的功能，运用 malloc、realloc 按需求申请或改变内存大小。
// 动态顺序表
typedef int SLDataType;
typedef struct SeqList {
SLDataType* arr;
int size; // 有效数据个数
int capacity; // 空间大小
} SL;
顺序表应包含增删查改等功能。建议将代码分为头文件（SeqList.h）、功能文件（SeqList.c）和测试文件（test.c）。
// SeqList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList {
SLDataType* arr;
int size;
int capacity;
} SL;
初始化需改变实参，因此传递指针。
void SLInit(SL* sl) {
assert(sl);
sl->arr = NULL;
sl->size = 0;
sl->capacity = 0;
}
由于内存由动态申请，需要释放堆区内存。回收后手动置空指针，防止野指针。
void SLDestroy(SL* sl) {
assert(sl);
free(sl->arr);
sl->arr = NULL;
sl->size = 0;
sl->capacity = 0;
}
核心思路：检查空间是否充足，若不足则扩容，然后在末尾插入数据。
void SLCheckCapacity(SL* sl) {
assert(sl);
if (sl->size == sl->capacity) {
int newCapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(sl->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL) {
perror("realloc");
exit(1);
}
sl->capacity = newCapacity;
sl->arr = tmp;
}
}
void SLPushBack(SL* sl, SLDataType x) {
assert(sl);
SLCheckCapacity(sl);
sl->arr[sl->size] = x;
sl->size++;
}
核心思路：整体元素向后移动，然后将数据添加在首元素位置。移动时应从后往前，避免数据覆盖丢失。
void SLPushFront(SL* sl, SLDataType x) {
assert(sl);
SLCheckCapacity(sl);
for (int i = sl->size; i > 0; i--) {
sl->arr[i] = sl->arr[i - 1];
}
sl->arr[0] = x;
sl->size++;
}
void SLPushInsert(SL* sl, int pos, SLDataType x) {
assert(sl);
assert(pos >= 0 && pos <= sl->size);
SLCheckCapacity(sl);
for (int i = sl->size; i > pos; i--) {
sl->arr[i] = sl->arr[i - 1];
}
sl->arr[pos] = x;
sl->size++;
}
减少有效数据个数即可。
void SLPopBack(SL* sl) {
assert(sl);
if (sl->size > 0) {
sl->size--;
}
}
首元素后面的元素依次往前移动一个位置。
void SLPopFront(SL* sl) {
assert(sl);
if (sl->size > 0) {
for (int i = 0; i < sl->size - 1; i++) {
sl->arr[i] = sl->arr[i + 1];
}
sl->size--;
}
}
void SLErase(SL* sl, int pos) {
assert(sl);
assert(pos >= 0 && pos < sl->size);
for (int i = pos; i < sl->size - 1; i++) {
sl->arr[i] = sl->arr[i + 1];
}
sl->size--;
}
通过遍历找寻给定数据。
int SLFind(SL* sl, SLDataType x) {
assert(sl);
for (int i = 0; i < sl->size; i++) {
if (sl->arr[i] == x) {
return i;
}
}
return -1;
}
找到数据后覆盖即可。
void SLModify(SL* sl, SLDataType x, SLDataType y) {
assert(sl);
for (int i = 0; i < sl->size; i++) {
if (sl->arr[i] == x) {
sl->arr[i] = y;
break;
}
}
}
通过学习顺序表，可以完成如通讯录等项目，只需将数组改为存放姓名、联系方式的结构体即可。