1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。 arr[N]
2. 动态顺序表：使用动态开辟的数组存储。 T* arr
主要来介绍一下动态顺序表
2.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空 间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间 大小，所以下面我们实现动态顺序表。通过 typedef 来实现接口的引入
增强可读性（模拟接口）: 结构体struct def SeqList
增强可修改性： 类型(int) def SLDataType
一些增删查改的模拟实现：
typedef int SLDataType; // 顺序表的动态存储 typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 size_t size; // 有效数据个数 size_t capicity; // 容量空间的大小 }SeqList; // 基本增删查改接口 void SeqListInit(SeqList* psl); // 检查空间，如果满了，进行增容 void CheckCapacity(SeqList* psl); // 顺序表尾插 void SeqListPushBack(SeqList* psl, SLDataType x); // 顺序表尾删 void SeqListPopBack(SeqList* psl); // 顺序表头插 void SeqListPushFront(SeqList* psl, SLDataType x); // 顺序表头删 void SeqListPopFront(SeqList* psl); // 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* psl, size_t pos); // 顺序表销毁 void SeqListDestory(SeqList* psl); // 顺序表打印 void SeqListPrint(SeqList* psl); }
一些典型的例题:
27.移除元素--双指针法
26.删除相同元素 
88.合并两个有序数组
2.3 顺序表的问题及思考
问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
补充：顺序表扩容的代码（是以size记数的 通过 ：？来实现
/检查容量 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int Newcapacity; Newcapacity = (ps->capacity == 0) ? 4 : (2 * ps->capacity);//扩容的实现 SLDataType* p = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * Newcapacity); if (p == NULL) { perror("realloc fail"); exit(1); } else { ps->a = p; ps->capacity = Newcapacity;//realloc没错就将其赋值给ps->capacity } } }
思考：如何解决以上问题呢？下面给出了链表的结构来看看。
3.链表
3.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
3.2 链表的分类
分为: 1.带头 2.单双向 3.循环 共八种
有许多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。//*next
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。//*prev *next
3.3 链表的实现
// 1、无头+单向+非循环链表增删查改实现 typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个结点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); …………
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
A: 简化插入操作的逻辑，避免处理头节点的特殊情况
以删除结点之后的代码为例：
// 删除pos之后的节点 void SLTEraseAfter(SLTNode * pos) { assert(pos); //pos->next不能为空 assert(pos->next); SLTNode* del = pos->next;//将下一个位置取名为del pos->next = pos->next->next;//跳过改变指向 free(del);//释放下一个位置 del = NULL; }
3.4 链表面试题
1. dummy新的头返回
2.pre cur next 三指针法
3. 快慢指针 （二分类
3.5 双向链表的实现
//灵魂仍然是我们的增删查改~
typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* next; struct ListNode* prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* plist); // 双向链表打印 void ListPrint(ListNode* plist); // 双向链表尾插 void ListPushBack(ListNode* plist, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* plist); // 双向链表头插 void ListPushFront(ListNode* plist, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* plist); // 双向链表查找 ListNode* ListFind(ListNode* plist, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的结点 void ListErase(ListNode* pos);
以循环的尾插为例（第一个定为phead
代码实现：
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* new = creat(x); phead->pre->next =new; new->pre = phead->pre; new->next = phead; phead->pre = new; }
4.顺序表和链表的区别
主机的存储要带电，本地磁盘可断电
暑假新增书单：《深入理解计算机系统》~
