数据结构线性表(二)

1、 线性表的链式存储结构

1、线性表的链式存储结构—链表

（1）如果每个结点只设置一个指向其后继结点的指针成员，这样的链表称为线性单向链接表，简称单链表。

（2）如果每个结点中设置两个指针成员，分别用以指向其前驱结点和后继结点，这样的链表称之为线性双向链接表，简称双链表。

2、单链表

每个结点为LinkNode类对象，包括存储元素的数据列表data和存储后继结点的指针属性next。

单链表类LinkList

结点引用方式：

插入结点操作：将结点s插入到单链表中p结点的后面。

删除结点操作：删除单链表中p结点的后继结点。

整体建立单链表

通过一个含有n个元素的a数组来建立单链表。

建立单链表的常用方法有两种：头插法和尾插法。

头插法建表

从一个空表开始，依次读取数组a中的元素。

生成新结点s，将读取的数据存放到新结点的数据成员中。

将新结点s插入到当前链表的表头上。

头插法建立的单链表中数据结点的次序与a数组中的次序正好相反

尾插法建表

从一个空表开始，依次读取数组a中的元素。

生成新结点s，将读取的数据存放到新结点的数据成员中。

将新结点s插入到当前链表的表尾上。

头插法建立的单链表中数据结点的次序与a数组中的次序正好相同

3、线性表基本运算在单链表中的实现

查找序号为i（0≤i≤n-1，n为单链表中数据结点个数）的结点

将元素e添加的线性表末尾Add(e)

求线性表的长度getsize()

求线性表中序号为i的元素GetElem(i)

设置线性表中序号为i的元素SetElem(i，e)

求线性表中第一个值为e的元素的逻辑序号GetNo(e)

在线性表中插入e作为第i个元素Insert(i，e)

在线性表中删除第i个数据元素Delete(i)

删除第i个结点算法

输出线性表所有元素display()

4、基于单链表基本操作的算法设计

练习1：有一个长度大于2的整数单链表L，设计一个算法查找L中中间位置的元素。

例如，L=（1，2，3），返回元素为2；L=（1，2，3，4），返回元素为2。

计数法：计算出L的长度n，假设首结点的编号为1，则满足题目要求的结点的编号为(n-1)/2+1（这里的除法为整除）。置j=1，指针p指向首结点，让其后移(n-1)/2-1个结点即可。

快慢指针法：设置快慢指针fast和slow，首先均指向首结点，当fast结点后面至少存在两个结点时，让慢指针slow每次后移动一个结点，让快指针fast每次后移动两个结点。否则slow指向的结点就是满足题目要求的结点。

练习2有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法查找L中最大值结点的个数。

解：先让p指向首结点，用maxe记录首结点值，将其看成是最大值结点，cnt置为1。按以下方式循环直到p指向尾结点为止：

（1）若p.next.data>maxe，将p.next看成新的最大值结点，置maxe=p.next.data，cnt=1。

（2）若p.next.data==maxe，maxe仍为最大结点值，置cnt++。

（3）p后移一个结点。

最后返回cnt即为最大值结点个数。

练习3有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法删除L中所有最大值的结点。

解：过程如下：

先遍历L的所有结点，求出最大结点值maxe。

再遍历一次删除所有值为maxe的结点，在删除中，通过（pre，p）一对指针指向相邻的两个结点，若p.data==maxe，再通过pre结点删除p结点。

练习4有一个整数单链表L，设计一个算法逆置L中的所有结点。例如L=(1，2，3，4，5)，逆置后L=(5，4，3，2，1)。

练习5有一个含2n个整数的单链表L=（a0，b0，a1，b1，…，an-1，bn-1），设计一个算法将其拆分成两个带头结点的单链表A和B。

其中A=（a0，a1，…，an-1），B=（bn-1，bn-2，…，b0）。

练习6有两个递增有序整数单链表A和B，设计一个算法采用二路归并方法将A和B的所有数据结点合并到递增有序单链表C中。

要求算法的空间复杂度为O(1)。

练习7有两个递增有序整数单链表A和B，假设每个单链表中没有值相同的结点，但两个单链表中存在相同值的结点，设计一个尽可能高效的算法建立一个新的递增有序整数单链表C，其中包含A和B相同值的结点，要求算法执行后不改变单链表A和B。

本算法的时间复杂度为O(n+m)。

空间复杂度为O(MIN(n，m))。

其中m、n分别为A、B单链表中的数据结点个数，MIN为取最小值函数，因为单链表C中最多只有MIN(n，m)个结点。