1.线性表线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。2.顺序表2.1概念与结构概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构⼀般情况下采⽤数组存储。顺序表的底层结构是数组顺序表是用数组来实现的。2.2 分类顺序表分为静态顺序表和动态顺序表。静态顺序表使用定⻓数组存储元素缺陷是空间给少了不够⽤给多了造成空间浪费。动态顺序表按需申请可增容。2.3 动态顺序表的实现#pragma once #includestdio.h #includestdlib.h #includeassert.h //定义动态顺序表的结构 typedef int SLDataType; typedef struct SeqList { SLDataType* arr; int size; //有效数据个数 int capacity; //空间容量 }SL; //typedef struct SeqList SL; void SLPrint(SL* ps); //初始化 void SLInit(SL* ps); //销毁 void SLDestroy(SL* ps); //尾插 void SLPushBack(SL* ps, SLDataType x); //头插 void SLPushFront(SL* ps, SLDataType x); //尾删 void SLPopBack(SL* ps); //头删 void SLPopFront(SL* ps); //指定位置之前插⼊数据 void SLInsert(SL* ps, int pos, SLDataType x); // 删除POS位置的数据 void SLErase(SL* ps, int pos); //查找 int SLFind(SL* ps, SLDataType x);3. 单链表3.1 概念与结构概念链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。3.1.1 结点与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“结点”结点的组成主要有两个部分当前结点要保存的数据和保存下⼀个结点的地址指针变量。3.1.2 链表的性质1、链式机构在逻辑上是连续的在物理结构上不⼀定连续2、结点⼀般是从堆上申请的3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续假设当前保存的结点为整型我们可以给出每个结点对应的结构体代码struct SListNode { int data; //结点数据 struct SListNode* next; //指针变量⽤保存下⼀个结点的地址 };3.1.3 链表的打印void SLTPrint(SLTNode* phead) { SLTNode* pcur phead; while (pcur) //pcur ! NULL { printf(%d - , pcur-data); pcur pcur-next; } printf(NULL\n); }3.2 实现单链表#pragma once #includestdio.h #includestdlib.h #includeassert.h //定义链表的结构---结点的结构 typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//存储的数据 struct SListNode* next; //指向下一个结点 }SLTNode; //typedef struct SListNode SLTNode; //链表的打印 void SLTPrint(SLTNode* phead); //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x); //尾删 void SLTPopBack(SLTNode** pphead); //头删 void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在指定位置之前插⼊数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在指定位置之后插⼊数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos之后的结点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDestroy(SLTNode** pphead);3.3 链表的分类链表的结构⾮常多样以下情况组合起来就有8种2 x 2 x 2链表结构3.4 单链表算法题以下给出几道单链表中经典的算法题大家着重学习掌握其中的算法思想。反转链表https://leetcode.cn/problems/reverse-linked-list/description/思路创建三个指针typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { //链表为空 if(head NULL) { return head; } //创建三个指针 ListNode*n1, *n2, *n3; n1 NULL,n2 head , n3 n2-next; while(n2) { n2-next n1; n1 n2; n2 n3; if(n3) { n3 n3-next; } } return n1; }链表的中间结点:https://leetcode.cn/problems/middle-of-the-linked-list/description/思路快慢指针慢指针每次走一步快指针每次走两步。typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { //定义快慢指针 ListNode* slow head; ListNode* fast head; //fast为空或者fast-next为空就跳出循环 while(fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }4. 双向链表4.1 概念与结构4.2 实现双向链表typedef int LTDataType; typedef struct ListNode { struct ListNode* next; //指针保存下⼀个结点的地址 struct ListNode* prev; //指针保存前⼀个结点的地址 LTDataType data; }LTNode; //void LTInit(LTNode** pphead); LTNode* LTInit(); void LTDestroy(LTNode* phead); void LTPrint(LTNode* phead); bool LTEmpty(LTNode* phead); void LTPushBack(LTNode* phead, LTDataType x); void LTPopBack(LTNode* phead); void LTPushFront(LTNode* phead, LTDataType x); void LTPopFront(LTNode* phead); //在pos位置之后插⼊数据 void LTInsert(LTNode* pos, LTDataType x); void LTErase(LTNode* pos); LTNode *LTFind(LTNode* phead,LTDataType x);5. 顺序表与链表的分析不同点顺序表链表单链表存储空间上物理上⼀定连续逻辑上连续但物理上不⼀定连续随机访问⽀持O(1)不⽀持O(N)任意位置插⼊或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插⼊动态顺序表空间不够时需要扩容和空间浪费没有容量的概念按需申请释放不存在空间浪费应⽤场景元素⾼效存储频繁访问任意位置⾼效插⼊和删除
)
