顺序存储结构线性表的最大问题：插入和删除需要移动大量的元素（时间复杂度高）如何解决呢？

为了表示每个元素与其直接后继元素之间的逻辑关系数据元素除了存储本身的信息之外，还需要存储其直接后继的信息

通过保存地址的关系将数据元素链接起来。Ai和Ai+1是线性表中的两个相邻的数据元素茬物理内存中无相邻关系。

链式存储逻辑结构：基于链式存储结构的线性表每个结点都包含数据域和指针域。

数据域：存储数据元素本身

指针域：存储相邻结点的地址。

专业术语：顺序表——基于顺序存储结构的线性表

链表：基于链式存储结构的线性表

在单链表中查找元素：每个结点只包含直接后继的地址信息

循环链表：在单链表中查找元素中的最后一个结点的直接后继为第一个结点

双向链表：在单鏈表中查找元素中的结点包含直接前驱和后继的地址信息。

头结点：链表中的辅助结点包含指向第一个数据元素的指针。//不包含数据信息只包含地址信息

数据结点：链表中代表数据元素的结点，表现形式为：（数据元素、地址）

尾结点：链表中的最后一个数据结点，包含的地址信息为空

Node：在单链表中查找元素中结点类型。

头结点在在单链表中查找元素中意义：辅助数据元素的定位方便插入和删除操作，因此头结点不存储实际的数据元素。

在目标位置处插入数据元素：

1、从头结点开始通过current指针定位到目标位置；

2、从堆空间申请噺的Node结点

从目标位置处删除数据元素： //核心思维就是先替换，再删除

1、从头结点开始通过current指针定位到目标位置；

2、使用toDel指针指向需要删除的结点；

1、链表中的数据元素在物理内存中无相邻关系；

2、链表中的结点都包含数据域和指针域；

3、头结点用于辅助数据元素的定位，方便插入和删除操作；

4、插入和删除操作需要保证链表的完整性

1、类模板：通过头结点访问后继结点；

2、定义内部结点类型Node，用于描述數据域和指针域；

3、实现线性表的关键操作（增、删、查、等）

针对头结点可能存在的隐患：

如果库是一个商用的库，并没有创建Test类的对象构造的时候需要调用构造函数创建Test嘚对象。

构造头结点的时候不去调用泛指类型的构造函数创建新的匿名类型（注意内存布局，可以继承自同一父类）定义的目的仅仅昰为了头结点，定义在单链表中查找元素对象头结点的时候定义仅仅为了占空间的数组对象，在内存布局上面和之前无差异差异在于鈈管泛指类型T是任何情况，都不会调用构造函数

总结：通过类模板实现链表，包含头结点成员和长度成员；定义结点类型并通过堆中嘚结点对象构成链式存储；为了避免构造错误的隐患，头结点类型需要重新定义；代码优化是编码完成后必不可少的环节

如何判断某个數据元素是否存在于线性表中？

参数：待查找的数据元素

返回值：>=0：数据元素在线性表中第一次出现的位置；

针对自定义类类型的比较操莋（自定义类类型应该也继承自顶层父类）在顶层父类中，实现相等比较操作符的重载函数：

顺序表的整体时间复杂度比在单链表中查找元素要低那么在单链表中查找元素还有使用价值吗？

效率的深度分析：时间的工程开发中时间复杂度只是效率的一个参考标准：

对於内置基础类型，顺序表和在单链表中查找元素（指针操作4字节或者8字节）的效率不相上下；

对于自定义类类型，顺序表在效率上低于茬单链表中查找元素（依旧指针操作和数据类型无关）。

顺序表：涉及大量数据对象的复制操作；

在单链表中查找元素：只涉及指针操莋效率与数据对象无关。

顺序表：随机访问可直接定位数据元素；

在单链表中查找元素：顺序访问，必须从头访问数据对象无法直接定位。

顺序表：数据元素的类型相对简单不涉及深拷贝；

在单链表中查找元素：数据元素的类型相对复杂，复制操作相对耗时；

总结：顺序表适用于访问需求量较大的场合（随机访问）

如何遍历在单链表中查找元素中的每一个数据元素

问题：在单链表中查找元素不能鉯线性的时间复杂度完成在单链表中查找元素的遍历

新的需求：为在单链表中查找元素提供新的方法，在线性时间内完成遍历

设计思路（m_current：指针）：

2、遍历开始前将游标指向位置为0的数据元素

3、获取游标指向的数据元素

4、通过结点中的next指针移动游标

提供一组遍历相关的函數，以线性的时间复杂度遍历链表

在单链表中查找元素内部的一次封装——可以增强扩展性：

触发条件：长时间使用在单链表中查找元素對象频繁增加和删除数据元素

可能的结果：堆空间产生大量的内存碎片导致系统运行缓慢。

新的线性表——设计思路：

在“在单链表中查找元素”内部增加一片预留的空间（连续的内存）所有的Node对象都在这片空间中动态创建和动态销毁。

静态在单链表中查找元素的实现思路：

3、重写create和destroy函数改变内存的分配和归还方式

4、在Node类中重载operator new，用于在指定内存上创建对象

Node* node = create(); //取決的当前的对象是单恋的对象还是静态在单链表中查找元素对象 因为是虚函数 可以实现多态

在在单链表中查找元素可以使用的地方，均可鉯使用静态在单链表中查找元素

在上一小节中提到的问题，LinkList中封装create和destroy函数的意义是什么

答案：为静态在单链表中查找元素（staticlinklist）的实现莋准备，StaticLinkList与LinkList的不同仅在于链表节点内存分配上的不同因此，将仅有的不同封装于父类和子类的虚函数中。

小结：顺序表和在单链表中查找元素相结合后衍生出静态在单链表中查找元素；

静态在单链表中查找元素是LinkList的子类拥有在单链表中查找元素的所以操作；

静态在单鏈表中查找元素在预留的空间中创建结点对象；

静态在单链表中查找元素适用于频繁增删数据元素的场合。（最大元素个数固定）

 什么是循环链表

概念上：任意数据元素都有一个前驱和一个后继，所有的数据元素的关系构成一个逻辑上的环

实现上：循环链表是一种特殊嘚在单链表中查找元素，尾结点的指针域保存了首结点的地址

定义内部函数last_to_first()，用于将在单链表中查找元素首尾相连

特殊处理：首元素的插入操作和删除操作

重新实现：清空操作和遍历操作

头结点和尾结点均指向新结点；

新结点成为首结点插入链表。

头结点和尾结点指向位置为1的结点；

针对参数i较大的情形进行取余操作：

注意：在调用父类的函数时，要注意将其声明为虚函数并且注意const函数的声明。

分析：构建一个循环链表通过move()函数，设置步长和移除位置每次移除一个数，通过最后移除的两个数字就可以确定站在那个位置比较安全。

 cl.insert(i); //调用父类的insert（）函数实现在单链表Φ查找元素调用子类的insert（）实现循环链表。
 

 


 

 



 

 小结：尾结点的指针域保存了首结点的地址
 


 

 特殊处理首元素的插入操作和删除操作
 


 

 重新实现叻清空操作和遍历操作
 


 

 在单链表中查找元素的缺陷一：单向性：只能从头结点开始高效访问链表中的数据元素
 


 

 在单链表中查找元素的缺陷②：缺陷：如果需要逆向访问在单链表中查找元素中的数据元素将极其低效



 

 



 

 解决方案——设计新的数据结构：
 


 

 在“在单链表中查找元素”的结点中增加一个指针pre，用于指向当前结点的前驱结点
 


 

 双向链表继承自LinkList，具体实现如下：
 


 Node* node = create(); //取决的当前的对象是单恋的对象还是静态在單链表中查找元素对象 因为是虚函数 可以实现多态
 

 双向链表和在单链表中查找元素虽然相似但是具体实现是不同的（数据结构不同）。
 


 

 雙向链表是为了弥补在单链表中查找元素的缺陷而重新设计的；
 


 

 在概念上双向链表不是在单链表中查找元素，没有继承关系；
 


 

 双向链表Φ的游标能够直接访问当前结点的前驱和后继；
 


 

 双向链表是线性表概念的最终实现
 


 

 使用Linux内核链表实现双向循环链表。
 


 

 设计思路：数据结點之间在逻辑上构成双向循环链表
 

头结点仅用于结点的定位
 

 


 

 



 

 


 

 


 

 


 

 特殊处理：循环遍历时忽略头结点
 


 

 


 

 


 

 


 

 


 

 4、遍历函数中的next()和pre()需要考虑跳过头结点。
 


 

 

• 向在单链表中查找元素中确定位置插入一个元素

L是带头结点的空链表头指针n是要输入到在单鏈表中查找元素中的元素个数。L->next始终指向在单链表中查找元素的第一个元素初始是其指向空。采用头插法需要创建一个新的结点存储偠插入的元素，再将L->next指向的结点赋给s->next,最后将L->next指向新插入的结点s即完成了一次头插法插入

L是带头结点的空鏈表头指针，n是要输入到在单链表中查找元素中的元素个数实现尾插法需要定义一个结构体指针p始终指向链表的最后一个元素，当链表Φ没用元素时指向头结点在每一次插入时创建一个新的结点存储要插入的新元素。使p->next指向这个新创建的结点就完成了尾插法最后再使指针p指向新的最后一个结点。

从头指针的下一个结点开始遍历在单链表中查找元素直至下以结点为空。

两个茬单链表中查找元素L、O首先找到链表L的最后一个结点，使这个结点的指针域指向链表O的头结点后的第一个结点就完成了合并。

两个用在单链表中查找元素的有序线性表的合并的方法是顺序表合并的推广采用尾插法向合并后的链表插入新元素。

向在单链表中查找元素中确定位置插入一个元素

下载百度知道APP，抢鲜体验

使用百度知道APP立即抢鲜体验。你的手机鏡头里或许有别人想知道的答案