前言
今天开了个新正式进入数据结构的学习，这两天颈椎病需要治一治所以有些拖更，治好我就满血复活0.0大家注意身体呀！
另外今天竟然接到了第一个实习的面试邀请，惊喜，这两天也会加油更新的同时看看面经，相关的过程记录我也想更新，如果大家想看的话（疯狂暗示）。
主要内容为：
三连即可提高学习效率0.0
🧑🏻作者简介：一个学嵌入式的年轻人
✨联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/study_qianrushi
⏳全文大约阅读时间： 60min
文章目录
前言
线性表
线性表的顺序存储
顺序存储的定义方式
代码的写作规范
线性表的基本运算
建立一个空表：list_create(L)
置空表：list_clear(L)
判空：list_empty(L) 空返回``1``，非空为``0``
求表长：length(L)
插入：Insert(L,x,i)将元素x插入到表L中第i个元素``a~i~``之前，且表长``+1``
释放空间：list_free(sqlink L);
显示所有元素：list_show(sqlink L);
显示所有元素：list_delete(sqlink L, int pos);
合并链表：list_merge(sqlink L1, sqlink L2)
删除线性表中重复的元素：list_purge(sqlink L)
线性表的顺序存储优缺点
写在最后
线性表
线性表是包含若干数据元素的一个线性序列
记为：L=(a0,…ai-1,ai,ai+1,…an-1)
L为表名，ai(0 ⩽ \leqslant⩽i⩽ \leqslant⩽n-1)为数据元素；
n为表长,n>0是，线性表L为非空表，否则为空表。
线性表L可用二元组形式描述：L=(D,R)
即线性表L包含数据元素集合D和关系集合R
举个例子：
设L={1,2,3,4,5,6}关系如图：
使用二元组描述为L=(D,R)其中D={1,2,3,4,5,6}(n=6),R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}
线性表的特征
对非空表，a0是表头，无前驱；
an-1是表尾，无后继；
其它的每个元素ai有且仅有一个直接前驱ai-1和一个直接后继ai+1。
其实就是上图的表示方式
线性表的顺序存储
将线性表L=(a0,…ai-1,ai,ai+1,…an-1)中各元素依次存储在计算机一片连续的存储空间。
则假设Loc(ai)为ai的地址，Loc(a0)=b,则有：Loc(a~i~) = b + i * d
顺序存储的特点：
优点
逻辑上相邻的元素ai，ai+1，其存储位置也相邻
对数据元素ai的存取为随机存取或按地址存取
存储密度高
存储密度D = (数据结构中元素所占存储空间)/(整个数据结构所占空间)
缺点
对表的插入和删除等运算时间复杂度高
看问题应用场景，其实任何方式都有优缺点都有其应用场景，只有相对较好的解决方案，没有正确的解决方案！
顺序存储的定义方式
在C语言中，可借助于一维数组类型来描述。
线性表的顺序存储结构
#define N 100 typedef int data_t; //可以改变数据类型定义其他的类型数据 typedef struct{ data_t data[n]; //表的存储空间 int last; }sqlist,*sqlink;
代码的写作规范
一般的写作包含三部分内容sqlist.h、sqlist.c、test.c
sqlist.h包含定义、运算
sqlist.c包含函数的接口实现
代码分层的原因：
其中外包公司用的时候为了保护公司核心资产所以只会给.h和编译好的.s.o。所以.h文件一般暴露接口定义和基本的数据结构定义。
所以可以使用两种方式编译：
#一个个编译 gcc -c test.c sqlist.c #编译生成test.o和sqlist.o gcc *.o -o a.out #编译生成a.out #一起编译 gcc *.c -o a.out
所以给外包公司汇编好的.o即可，头文件也需要给到就完事了。
线性表的基本运算
建立一个空表：list_create(L)
sqlink list_create(){ //malloc sqlink L; L = (sqlink)malloc(sizeof(sqlist)); if ( L == NULL){ printf("list malloc failed\n"); return L; } //initialize memset(L, 0, sizeof(sqlist)); L->last = -1; //return return L; }
置空表：list_clear(L)
/* * @ret 0-success -1-failed * */ int list_clear(sqlink L){ if(L == NULL) return -1; memset(L, 0, sizeof(sqlist)); L->last = -1; return 0; }
