C语言之数据结构初见篇（1）：顺序表专题
目录
一：课程的目标
C语言语法基础到数据结构与算法，前面我们基本已经掌握了扎实的C语言基础，为什么要学习数据结构的课程？-----为了通讯录项目
二：需要准备的储备知识
简单的理解，通讯录具备增加、删除、修改、查找联系人等操作，要实现通讯录项目有两个技术关键
- C语语法基础
- 数据结构之顺序表和链表
三：数据结构的相关概念
1.什么是数据结构？
数据结构是计算机科学中一个非常核心的概念。简单来说，它是计算机存储、组织数据的方式。
就像生活中我们需要用合理的方式来整理物品一样（比如用衣架挂衣服、用书架摆书、用收纳盒放杂物），计算机也需要用特定的结构来管理数据，以便能高效地访问和修改它们。
一个核心公式
在计算机领域，有一个著名的公式：
程序 = 数据结构 + 算法
-
数据结构：解决数据在计算机中如何存储和组织的问题。
-
算法：解决数据在计算机中如何处理和计算的问题。
两者相辅相成。选择合适的数据结构，往往能让算法的效率大大提升。
生活中的类比
想象一下管理一家图书馆的藏书：
-
如果不使用数据结构：书买回来随便往架子上堆。结果找一本书可能需要翻遍整个图书馆，耗时极长。
-
如果使用数据结构：
-
你决定按类别摆放（文学、历史、科学）——这是一种结构。
-
在每一类里，按书名的拼音首字母排序——这是更精细的结构。
-
你把所有书的存放位置记录在一个电子表格里——这也是结构。
-
有了这个结构，读者来找书，你只需要查一下电子表格，就能直接走到对应的书架位置，几秒钟就能找到。
数据结构在计算机中的作用，就是这个道理。
2.常见的数据结构
数据结构通常分为线性结构和非线性结构。以下是几种最基础的：
1. 数组
就像一排连在一起的信箱，每个信箱都有编号（索引）。
-
特点：在内存中占据一块连续的空间。
-
优点：查找速度快（只要知道编号，就能直接找到）。
-
缺点：增加或删除一个数据比较麻烦（可能需要移动后面所有的数据）。
2. 链表
就像寻宝游戏，每张线索纸条上都写着下一个线索的藏匿地点。
-
特点：数据在内存中随意存放，每个数据（节点）都附带一个“指针”，指向下一个数据的位置。
-
优点：增加或删除数据非常灵活、快速（只需要修改指针指向）。
-
缺点：查找数据较慢（必须从第一个开始，顺着指针一个个找下去）。
3. 栈
像一个装羽毛球的圆筒。你只能从最上面拿球，也只能把球放回最上面。
-
特点：后进先出。
-
应用：比如浏览器的“后退”按钮（最后看的页面，后退时最先出现）。
3.为什么数据结构很重要？
-
效率：处理海量数据时，不同的结构速度天差地别。用错结构，程序可能会慢到无法使用。
-
资源利用：好的数据结构可以节省内存空间，或者用空间换取宝贵的时间。
-
问题建模：现实世界的问题是复杂的，数据结构提供了在代码中表达这种复杂关系（如网络、层级关系）的工具。
总的来说，数据结构是程序设计的基础功。无论是开发操作系统、游戏，还是编写一个简单的手机App，理解和选择合适的数据结构，都是写出高效、健壮代码的关键。
四：定义顺序表的结构
第1种：静态顺序表(不推荐使用)
代码如下：
#define N 100 //宏的定义
struct Seqlist
{
int arr[N];
int size;
};第2种：动态顺序表（推荐使用）
代码如下：
typedef int SLDataType; //重新命名*arr的类型，这里可以是 int *arr，也可以是其他的类型 ,此外SLDataType的中文意思是‘顺序表的数据类型’
typedef struct Seqlist // Seqlist是结构体的名称，即‘顺序表’它是两个单词的简写
{
SLDataType* arr; //SLDataType中文是‘顺序表数据类型的意思’(这里可以是 int *arr) 因为我们存入的数据类型可能是字符类型，通过指针地址可以更加应对动态空间的变化，所以这里是*arr数组
int size; //有效的数据个数，即我们目前要真正存入的数据
int capacity; //空间大小，即当我们申请新的空间之后的数组空间大小
}SL; //SL是结构体，将Seqlist替换为SL结构体，不是命名
//上面这行代码 == typedef struct Seqlist SL ; (二选一就行了)
优缺点对比表
| 特性 | 静态顺序表 | 动态顺序表 |
|---|---|---|
| 大小 | 固定，不可改变 | 可变，可自动扩容 |
| 内存分配 | 编译时或早于运行前 | 运行时动态分配 |
| 存储位置 | 栈或全局数据区 | 堆 |
| 执行效率 | 高（无需考虑扩容，直接存取） | 稍低（扩容时有内存拷贝开销） |
| 空间利用率 | 容易浪费（提前申请太多）或溢出 | 随用随取，利用率高，但需要管理 |
| 使用复杂度 | 简单 | 较复杂（需要实现扩容逻辑或管理内存） |
总结
-
当你明确知道数据量不会很大，且数据量基本固定不变时，可以使用静态顺序表，简单高效。
-
当你无法预知数据规模，或者数据量变化较大时，动态顺序表是你的最佳选择，它以少量的性能开销换取了宝贵的内存灵活性和安全性。
五：顺序表的具体介绍
步骤：
- 顺序表初始化
- 顺序表的销毁
- 头部和尾部的插入
- 头部和尾部的删除
接下来我会从上面的几个步骤一一给大家进行详细的解析
（以下的所有代码都是在多个文件中进行了的，注意区分我写的代码文件是哪个，这里我们会有三个文件，一个头文件，一个链表文件，一个测试文件）
1.顺序表初始化
代码如下
Seqlist.h的文件
void SLInit(SL *ps); //传入一个参数然后进行初始化 //SLInit中文的意思是‘顺序表的初始化’
Seqlist.h的文件
//顺序表的初始化 （类似于结构体的初始化）
void SLInit(SL *ps) //这里我们给结构体的参数命名为 ps ，由于我们传过来的是sl的地址，所以我们必须用指针来接收
{
//结构体非指针的初始化，即使用点 . 来进行解引用
//ps.arr = NULL;
//ps.size = 0;
//ps.capacity = 0;
//但是由于我们接收的是指针地址，所以我们必须用指针的解引用，即使用 -> 进行解引用,而不是点 .
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
test.c的文件
void SLTest01() //SLTest01中文意思‘顺序表的测试01’
{
SL sl; //这里我们给SL进行取名字，即sl
SLInit(&sl); //初始化，这里必须传递址才行，因为实参sl是传值过去，此时数据还没有初始化，所以会冲突
}
完整代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef int SLDataType; // 数据元素类型
typedef struct SeqList
{
SLDataType* arr; // 动态数组指针
int size; // 当前元素个数
int capacity; // 当前容量
} SL;
// 现在编译器已经知道 SL 是什么了，再声明函数
void SLInit(SL* ps);
void SLInit(SL* ps)
{ // 定义
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}初始化完成后的内存状态：
名称 值 类型
sl {arr=0x00000000...} SL
arr 0x00000000 <NULL> int*
size 0 int
capacity 0 int
2.顺序表的销毁
代码如下：
void SLDestroy(SL* ps);代码如下：
//顺序表的销毁 （向系统申请空间的时候，必须的释放空间，否则会导致空间泄漏）
void SLDestroy(SL* ps)
{
if (ps->arr) //等价于 if(ps->arr != NULL)
{
free(ps->arr); //释放空间
}
ps->arr = NULL;
ps->size ;
ps->capacity = 0;
}
代码如下：
void SLTest02()
{
SL sl;
SLInit(&sl); // 先初始化
SLDestroy(&sl); // 直接销毁
// 在这里打个断点，监视 sl 的成员变量
// 看 arr、size、capacity 是否都变成了 0/NULL
}完整的代码如下：
void SLDestroy(SL* ps);
//顺序表的销毁 （向系统申请空间的时候，必须的释放空间，否则会导致空间泄漏）
void SLDestroy(SL* ps)
{
if (ps->arr) //等价于 if(ps->arr != NULL)
{
free(ps->arr); //释放空间
}
ps->arr = NULL;
ps->size;
ps->capacity = 0;
}
void SLTest02()
{
SL sl;
SLInit(&sl); // 先初始化
SLDestroy(&sl); // 直接销毁
// 在这里打个断点，监视 sl 的成员变量
// 看 arr、size、capacity 是否都变成了 0/NULL
}监视结果就是：三个成员全部是 0/NULL，前后没变化。
后面的步骤我们放到下一章来给大家讲解！！！！
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)