大话数据结构 【三】线性表2
顺序存储结构的插入与删除
1.获得 【将线性表L中的第i个位置元素值返回，即返回下标即可】
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
#此处返回值类型Status是一个整型，返回OK代表1，ERROR代表0
2.插入 【在线性表L中第i个位置插入新元素e】
插入算法思路：
3.删除
删除算法思路：
4.优缺点
线性表 存、读数据 时间复杂度为O（1）
插、删数据 时间复杂度为O（n）【平均时间复杂度】
线性表的链式存储结构
1.顺序存储结构不足的解决办法
链式存储结构 借助指针
2.线性表链式存储结构
3.头指针和头节点
两者区别：
4.线性表链式存储结构代码描述
结点由存放的数据元素的数据域和存放后继结点地址的指针域组成
假设p是指向线性表第i个元素的指针，则该结点的ai的数据域可以用p->data 表示
p->data 的值是一个数据元素
结点ai的指针域可以用p->next 表示
p->next 的值是一个指针，指向第i+1个元素
单链表的读取
获得链表第i个数据的算法思路：
#由于单链表的结构中没有定义表长，所以事先不知道要循环多少次，不方便用for控制循环，核心思想是“工作指针后移”
单链表的插入与删除
插入
单链表第i个数据插入结点的算法思路：
# malloc标准函数，作用是生成一个新的结点，实质是在内存中找了一小块空地，准备用来存放e数据s结点
删除【实质就是将要删除的数据元素的 前继指针绕过，指向后继结点】
单链表第i个数据删除结点的算法思路：
此处，q = p->next;是一个赋值操作，将欲删除的结点p->next赋值给q
q = p->next; 连同下一句可以等价转换为：
p->next = p->next->next;
# free标准函数，让系统回收一个Node结点，释放内存
在单链表的插入、删除操作中：时间复杂度都是O（n），与线性表的顺序结构是没有任何优势的
但是
如果希望从第i个位置插入10个元素，对顺序结构意味着每一次插入都要移动n-i个元素，每次都是O（n）
而单链表中，只需要第一次时，找到第i位置的指针【O（n）】，接下来只是简单的通过赋值移动指针而已【O（1）】
即
对于插入和删除数据越频繁的操作，单链表的效率优势越明显
单链表的整表创建
算法思路：
上述代码，采用的是插队的办法 —— 始终让新结点在第一的位置【头插法】
也可以把新结点放到最后 【尾插法】
