数据结构
概念
数据结构是计算机存储、组织数据的方式
为什么需要数据结构
在这之前我们学过数组，数组是最基础的数据结构
那为什么学了数组还用学数据结构呢？
最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现
使用数据结构的效果
1）能够将数据存储
（顺序表、链表等结构）
2）方便查看存储的数据
线性表
概念
线性表（Linear List）是数据结构中的一种基础且重要的数据结构，它是一组具有相同数据类型的元素的有限序列。
线性表中的数据元素之间存在一对一的关系，即除了首元素外，每个元素有且只有一个前驱元素；除了尾元素外，每个元素有且只有一个后继元素。
线性表有两种基本的存储结构：顺序存储结构和链式存储结构。
| 顺序存储结构 | 链式存储结构 | |
| 概念 | 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素 | 线性表的链式存储结构是通过链表来表示的。在链表中，每个数据元素包含两部分：数据域和指针域。 |
| 优点 | 这种存储结构具有存取速度快、节省存储空间等优点 | 链表结构可以动态地分配存储空间，插入和删除操作也比较方便 |
| 缺点 | 但需要预先分配较大的存储空间，而且在插入和删除操作时，可能需要移动大量的元素 | 存取速度相对较慢，且需要额外的存储空间来存储指针。 |
线性表的应用非常广泛，可以用于实现栈、队列等数据结构，也可以用于实现各种算法，如排序、查找等。
结构特点
线性表在逻辑上是线性结构，也就是说是连续的一条直线
但在物理结构上并不一定是连续的
线性表在物理上存储时，通常以数组和链式结构的形式存储,在数组上完成增删查改
常见的线性表：
顺序表、链表、栈、队列、字符串
顺序表与数组的联系
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口
顺序表导图
动态顺序表
SX.h：定义顺序表的结构，顺序要实现的接口/方法
SX.c：具体实现顺序表里定义的接口/方法
test.c：测试顺序表
typedef定义结构的两种方法
//第一种方法 //数据类型 typedef int datatype; //结构体 struct shunxu { datatype* arr; //存储数据的底层结构：数组 int size; //顺序表空间大小 int nowsize; //顺序表有效数据个数 }; typedef struct shunxu SX;
//第二种方法 //数据类型 typedef int datatype; //结构体 typedef struct shunxu { datatype* arr; //存储数据的底层结构：数组 int size; //顺序表空间大小 int nowsize; //顺序表有效数据个数 }SX;
以下是在SX.c中实现顺序表
空间不够，扩容
//空间不够，扩容 void publicKUOR(SX* ps) { //如果顺序表空间大小 = 顺序表空间有效个数 if (ps->size == ps->nowsize) { //三目操作符 int newnowsize = ps->nowsize == 0 ? 4 : 2 * sizeof(datatype); //新建一个临时变量，因为如果realloc扩容失败，会造成技术事故 datatype* tmp = (datatype*)realloc(ps->arr, newnowsize * sizeof(datatype)); if (tmp == NULL) { perror("realloc"); exit(1); } //扩容后的数组 ps->arr = tmp; //扩容后的有效空间大小 ps->nowsize = newnowsize; } }
尾部插入数据
//顺序表的尾插 void CHARUback(SX* ps, datatype x) { //方式一：断言 -- 暴力方式 --会报错且知道具体错误位置 assert(ps); //方式二：断言 -- 温柔方式--会报错，不知道具体错误位置 /*if (ps == NULL) { return; }*/ //空间不够，扩容 publicKUOR(ps); //空间足够，直接插入 /*第一种写法*/ //ps->arr[ps->size] = x; //ps->size++; /*第二种写法*/ ps->arr[ps->size++] = x; }
头部插入数据
//头插 void CHARUfront(SX* ps, datatype x) { //判断ps是否为空指针 assert(ps); //空间不够，扩容 publicKUOR(ps); //空间足够，数据往后挪一位 int i = 0; for (i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; }
尾部数据删除
//尾部删除 void SXdestroyback(SX* ps) { //判断ps是否为有效指针 assert(ps); //判断顺序表中有无数据 assert(ps->size); //顺序表不为空 ps->size--; }
头部数据删除
//头部删除 void SXdestroyfront(SX* ps) { //判断ps是否为有效指针 assert(ps); //判断顺序表是否有数据 assert(ps->size); //顺序表不为空，往前挪 for (int i = 0; i < ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; }
指定位置之前插入数据
//指定位置之前插入数据 //顺序表下标位置pos void SXpointfrontestroy(SX* ps,int pos,datatype x) { //判断ps是否为有效指针 assert(ps); //断言，保证下标pos>=0且pos小于等于顺序表空间大小size assert(pos >= 0 && pos <= ps->size); for (int i = ps->size; i < pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; }
删除指定位置数据
//删除指定位置数据 void SXpointdestroy(SX* ps, int pos) { //判断ps是否为有效指针 assert(ps); //断言，保证下标pos>=0且pos小于顺序表空间大小size assert(pos >= 0 && pos < ps->size); for (int i = pos; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; }
查找顺序表中元素位置
//查找顺序表元素位置 int SXfind(SX* ps, datatype x) { for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { return i; } } return -1; }
销毁
void SXdestroy(SX* ps) { //保证指针有效 assert(ps); if (ps->arr) { free(ps->arr); } ps->arr = NULL; ps->size = ps->nowsize = 0; }
注:
在测试中,在指定位置之前插入数据/删除指定位置的数据,可以直接用下标,不用另外查找顺序表
