C算法
数据结构入门：顺序表的定义、分类及动态实现
顺序表是线性表的顺序存储结构，底层通常采用数组实现。文章对比了静态与动态顺序表的区别，重点讲解了动态顺序表的三文件协同实现方法。内容包括初始化、尾部插入、头部插入及空间增容逻辑。通过 C 语言代码展示了结构体定义、内存分配及指针操作细节，分析了不同操作的效率特点，为后续链表等结构学习奠定基础。
顺序表是线性表的顺序存储结构，底层通常采用数组实现。文章对比了静态与动态顺序表的区别，重点讲解了动态顺序表的三文件协同实现方法。内容包括初始化、尾部插入、头部插入及空间增容逻辑。通过 C 语言代码展示了结构体定义、内存分配及指针操作细节，分析了不同操作的效率特点，为后续链表等结构学习奠定基础。
--线性表是 n 个有相同特性的数据元素的有限序列，是广泛应用的数据结构。常见的：顺序表、链表、栈、队列、字符串……
--线性表，逻辑上是线性结构（连续的一条线）。物理结构不一定是连续的，线性表在物理上存储，通常以顺序结构、链式结构存储。
--定义：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况采用数组存储。（顺序表底层是数组）
那顺序表就是数组？
--不！顺序表是对数组的封装，实现了常用的增删查改等接口。
--静态顺序表使用定长数组存储元素。
--不足：可能空间不够用，初始化给多有可能浪费。
--将 int 重新命名为 SLDataType；
--size 指向有效数据的下一位；
--动态顺序表的空间按需申请
--两种顺序表在不同的应用场景中各有作用。
--实现动态顺序表，用以下三个文件：
//SeqList.h 头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
//定义动态顺序表的结构
typedef int SLTDataType;
typedef struct SeqList {
SLTDataType* arr; //存储数据
int size; //有效数据个数
int capacity; //空间大小
} SL;
//SL 是对结构体重命名
//定义顺序表初始化函数声明
void SLInit(SL* ps);
//SeqList.c 文件（配合 SeqList.h 文件）
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
//定义、实现函数
void SLInit(SL* ps) //指针接收地址
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
void test01() {
SL s1;
SLInit(&s1); //传地址，传址调用
}
int main() {
test01();
return 0;
}
--这里要注意，使用的是传址调用：将地址传过去，希望对指向的结构体成员进行初始化（修改指向的内容）；
--如果是传值调用，只是将结构体成员的内容传过去，形参是实参的临时拷贝（二者是独立的个体），改变了形参的值对实参没有影响。
--经过上面操作，就得到了一个空顺序表，进行应用。
//SeqList.c 文件
//尾插
void SLPushBack(SL* ps, SLTDataType x) {
//空间不够
if (ps->size == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//增容
SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够
ps->arr[ps->size++] = x;
}
//输出_函数
void SLPrint(SL* ps) {
for (int i = 0; i < ps->size; i++) {
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//test.c 文件
//实现尾插
void test02() {
SL s2; //创建结构体变量
SLInit(&s2); //初始化
SLPushBack(&s2, 1);
SLPrint(&s2);
SLPushBack(&s2, 2);
SLPrint(&s2);
SLPushBack(&s2, 3);
SLPrint(&s2);
SLPushBack(&s2, 4);
SLPrint(&s2);
}
int main() {
test02();
return 0;
}
--对于增容操作：一般进行成倍数增加（而不是插一个数就申请一个）——>最好 2 倍增容——>有效降低增容次数，虽存在空间浪费，但不会太多——>默认插入的数据越多，并表示将来存储的数据也越多（概率学）。
//SeqList.c
#include "SeqList.h"
//扩容_函数
void SLCheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//增容
SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//头插_函数
void SLPushFront(SL* ps, SLTDataType x) {
assert(ps); //空间不够
SLCheckCapacity(ps);
//空间足够 - 循环进行移位
for (int i = ps->size; i > 0; i--) {
ps->arr[i] = ps->arr[i - 1];
}
//空出第一位，插入
ps->arr[0] = x;
ps->size++; //有效数据 +1
}
//test.c 文件
#include "SeqList.h"
void test02() {
SL s2; //创建结构体变量
SLInit(&s2); //初始化
//实现头插
SLPushFront(&s2, 1);
SLPrint(&s2);
SLPushFront(&s2, 2);
SLPrint(&s2);
SLPushFront(&s2, 3);
SLPrint(&s2);
}
int main() {
test02();
return 0;
}
--后续会频繁进行空间的判断，所以进行函数封装，直接调用函数。
--其次进行了断言操作，防止传参为空。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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