【本节目标】线性表顺序表链表顺序表和链表的区别和联系目录【本节目标】1.线性表2.顺序表2.1 概念及结构2.2 接口实现2.3 数组相关面试题2.4 顺序表的问题及思考3.链表3.1 链表的概念及结构3.2 链表的分类3.3 链表的实现3.4 链表面试题3.5 双向链表的实现4.顺序表和链表的区别1.线性表线性表linear list是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串……线性表在逻辑上是线性结构也就是说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。2.顺序表2.1 概念及结构顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为静态顺序表使用定长数组存储元素。动态顺序表使用动态开辟的数组存储。2.2 接口实现静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态地分配空间大小所以下面我们实现动态顺序表。typedefintSLDataType;// 顺序表的动态存储typedefstructSeqList{SLDataType*array;// 指向动态开辟的数组size_tsize;// 有效数据个数size_tcapicity;// 容量空间的大小}SeqList;// 基本增删查改接口// 顺序表初始化voidSeqListInit(SeqList*psl);// 检查空间如果满了进行增容voidCheckCapacity(SeqList*psl);// 顺序表尾插voidSeqListPushBack(SeqList*psl,SLDataType x);// 顺序表尾删voidSeqListPopBack(SeqList*psl);// 顺序表头插voidSeqListPushFront(SeqList*psl,SLDataType x);// 顺序表头删voidSeqListPopFront(SeqList*psl);// 顺序表查找intSeqListFind(SeqList*psl,SLDataType x);// 顺序表在 pos 位置插入 xvoidSeqListInsert(SeqList*psl,size_tpos,SLDataType x);// 顺序表删除 pos 位置的值voidSeqListErase(SeqList*psl,size_tpos);// 顺序表销毁voidSeqListDestory(SeqList*psl);// 顺序表打印voidSeqListPrint(SeqList*psl);2.3 数组相关面试题原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。OJ 链接删除排序数组中的重复项。OJ 链接合并两个有序数组。OJ 链接2.4 顺序表的问题及思考问题中间/头部的插入删除时间复杂度为O(N)。增容需要申请新空间、拷贝数据、释放旧空间会有不小的消耗。增容一般是呈 2 倍的增长势必会有一定的空间浪费。例如当前容量为 100满了以后增容到 200我们再继续插入了 5 个数据后面没有数据插入了那么就浪费了 95 个数据空间。**思考**如何解决以上问题呢下面给出了链表的结构来看看。3.链表3.1 链表的概念及结构**概念**链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。现实中数据结构中3.2 链表的分类实际中链表的结构非常多样以下情况组合起来就有 8 种链表结构单向或者双向带头或者不带头循环或者非循环虽然有这么多的链表结构但是我们实际中最常用还是两种结构无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。3.3 链表的实现// 1、无头单向非循环链表增删查改实现typedefintSLTDateType;typedefstructSListNode{SLTDateType data;structSListNode*next;}SListNode;// 动态申请一个结点SListNode*BuySListNode(SLTDateType x);// 单链表打印voidSListPrint(SListNode*plist);// 单链表尾插voidSListPushBack(SListNode**pplist,SLTDateType x);// 单链表的头插voidSListPushFront(SListNode**pplist,SLTDateType x);// 单链表的尾删voidSListPopBack(SListNode**pplist);// 单链表头删voidSListPopFront(SListNode**pplist);// 单链表查找SListNode*SListFind(SListNode*plist,SLTDateType x);// 单链表在 pos 位置之后插入 x// 分析思考为什么不在 pos 位置之前插入voidSListInsertAfter(SListNode*pos,SLTDateType x);// 单链表删除 pos 位置之后的值// 分析思考为什么不删除 pos 位置voidSListEraseAfter(SListNode*pos);3.4 链表面试题删除链表中等于给定值val的所有结点。203. 移除链表元素反转一个单链表。206. 反转链表给定一个带有头结点head的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。876. 链表的中间结点输入一个链表输出该链表中倒数第k个结点。面试题 02.02. 返回倒数第 k 个节点将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。21. 合并两个有序链表编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前。CM11 链表分割链表的回文结构。OR36 链表的回文结构输入两个链表找出它们的第一个公共结点。160. 相交链表给定一个链表判断链表中是否有环。141. 环形链表【思路】快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行。如果链表带环则一定会在环中相遇否则快指针就率先走到链表的末尾。比如陪女朋友到操场跑步减肥。【扩展问题】为什么快指针每次走两步慢指针走一步可以假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情况。因此在慢指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。快指针一次走 3 步走 4 步……n 步行吗此时按照上述方法来绕环移动每次快指针走 3 步慢指针走 1 步是永远不会相遇的快指针刚好将慢指针套圈了因此不行。只有快指针走 2 步慢指针走 1 步才可以因为环的最小长度是 1即使套圈了两个也在相同的位置。给定一个链表返回链表开始入环的第一个结点。如果链表无环则返回NULL。OJ 链接【结论】让一个指针从链表起始位置开始遍历链表同时让一个指针从判环时相遇点的位置开始绕环运行两个指针都是每次均走一步最终肯定会在入口点的位置相遇。【证明】给定一个链表每个结点包含一个额外增加的随机指针该指针可以指向链表中的任何结点或空结点。要求返回这个链表的深度拷贝。138. 随机链表的复制3.5 双向链表的实现// 2、带头双向循环链表增删查改实现typedefintLTDataType;typedefstructListNode{LTDataType _data;structListNode*next;structListNode*prev;}ListNode;// 创建返回链表的头结点ListNode*ListCreate();// 双向链表销毁voidListDestory(ListNode*plist);// 双向链表打印voidListPrint(ListNode*plist);// 双向链表尾插voidListPushBack(ListNode*plist,LTDataType x);// 双向链表尾删voidListPopBack(ListNode*plist);// 双向链表头插voidListPushFront(ListNode*plist,LTDataType x);// 双向链表头删voidListPopFront(ListNode*plist);// 双向链表查找ListNode*ListFind(ListNode*plist,LTDataType x);// 双向链表在 pos 的前面进行插入voidListInsert(ListNode*pos,LTDataType x);// 双向链表删除 pos 位置的结点voidListErase(ListNode*pos);4.顺序表和链表的区别不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低备注缓存利用率参考存储体系结构以及局部性原理。与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell
