想神带你学数据结构 第五期

叁研伴学路，良语暖人心。考研路漫漫，功在每日勤。日推价值文，资料资讯精。何不速关注，大业或可行？

1、链表

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

注意：1、区分头指针与头结点的异同。

头指针：

1、头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。

2、头指针具有标识作用，所以常用头指针冠以链表的名字。

3、无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

1、头结点是为了操作的统一和方便设立的，放在第一元素的结点之前，其数据域一般无意义（也可以存放链表的长度）。

2、有了头结点，对在意义元素节点前插入结点和删除第一结点，其操作与其他结点的操作就统一了。

3、头结点不一定是链表必须元素。

2、单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

1、表元素域elem用来存放具体的数据。

2、链接域next用来存放下一个节点的位置（python中的标识）

3、变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

如图，若带有头结点的单链表，如图所示

此图来源于《大话数据结构》

空链表如图所示

此图来源于《大话数据结构》

节点实现：

Python版

class SingleNode(object):

"""单链表的结点"""

def __init__(self,item):

# _item存放数据元素

self.item = item

# _next是下一个节点的标识

self.next = None

C/C++版：

/*线性表的单链表存储结构*/

typedef struct Node{

ElemType data;

struct Node *next;

}Node；

typedef struct Node *LinkList;/*定义LinkList*/

从这两个结构定义中，我们也就知道，结点由存放数据元素的数据域存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i+1个元素，即指向ai+1的指针。也就是说，如果p->data=ai，那么p->next>data=ai+1，如图所示：

此图来源于《大话数据结构》

单链表的操作

1、is_empty() 链表是否为空

2、length() 链表长度

3、travel() 遍历整个链表

4、add(item) 链表头部添加元素

5、append(item) 链表尾部添加元素

6、insert(pos, item) 指定位置添加元素

7、remove(item) 删除节点

8、search(item) 查找节点是否存在

单链表的读取：

Python版本：

class SingleLinkList(object):

"""单链表"""

def __init__(self):

self._head = None

def is_empty(self):

"""判断链表是否为空"""

return self._head == None

def length(self):

"""链表长度"""

# cur初始时指向头节点

cur = self._head

count = 0

# 尾节点指向None，当未到达尾部时

while cur != None:

count += 1

# 将cur后移一个节点

cur = cur.next

return count

def travel(self):

"""遍历链表"""

cur = self._head

while cur != None:

print cur.item,

cur = cur.next

print ""

def GetElem(self, pos):

"""读取第pos位置的元素"""

cur = self._head

if pos (self.length() -1):

return False

count = 0

while count

cur = cur.next

item = cur.item

print item

C/C++版本

获取链表第i个数据算法思路：

1、声明一个结点p指向链表的第一个结点，初始化j从1开始

2、当j

3、若到链表末尾p为空，则说明第i个元素不存在

4、否则查找成功，返回结点p的数据

实现代码如下：

/*初始条件：顺序线性表工已存在，1≤i≤ListLength（L）*/

/*操作结果：用e返回工中第i个数据元素的值*/

Status GetElem(LinkList L,int i,Elemrype *e)

{

int j；

LinkList p;/*声明一结点p*/

p=L->next；/*让p指向链表L的第一个结点*/

j=1；/*与为计数器*/

while(p&& j

{

p=p->next；/*让p指向下一个结点*/

++j;

}

if(!p || j > i)

return ERROR;

*e = p->data;

return OK

}

头部添加元素

def add(self, item):

"""头部添加元素"""

# 先创建一个保存item值的节点

node = SingleNode(item)

# 将新节点的链接域next指向头节点，即_head指向的位置

node.next = self._head

# 将链表的头_head指向新节点

self._head = node

尾部添加元素

def append(self, item):

"""尾部添加元素"""

node = SingleNode(item)

# 先判断链表是否为空，若是空链表，则将_head指向新节点

if self.is_empty():

self._head = node

# 若不为空，则找到尾部，将尾节点的next指向新节点

else:

cur = self._head

while cur.next != None:

cur = cur.next

cur.next = node

指定位置添加元素

def insert(self, pos, item):

"""指定位置添加元素"""

# 若指定位置pos为第一个元素之前，则执行头部插入

if pos

self.add(item)

# 若指定位置超过链表尾部，则执行尾部插入

elif pos > (self.length()-1):

self.append(item)

# 找到指定位置

else:

node = SingleNode(item)

count = 0

# pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置

pre = self._head

while count

count += 1

pre = pre.next

# 先将新节点node的next指向插入位置的节点

node.next = pre.next

# 将插入位置的前一个节点的next指向新节点

pre.next = node

C/C++版：

在任何结点插入元素e，结点为s，要实现结点p、p->next和s之间的逻辑关系的变化，只需将结点s插入到结点p和p->next涨价即可，可如何插入呢？

答案就是：s->next = p->next; p ->next = s；

这两句话的意思就似乎，让p的后继结点改成s的后继结点，再把结点s编程p的后继结点。注意：顺序不能颠倒，如果颠倒了，就是p->next=s; s->next= p->next，这样子s->next是找不到后继是谁的 因为先断开了。插入过程如图所示：

此图来源于《大话数据结构》

单链表第i个数据插入结点的算法思想：

1、声明一结点p指向链表的一个结点，初始化j从1开始，

2、当j

3、若到了链表末尾p为空，则说明第i个元素不存在

4、否则查找成功，在系统生成一个空结点s

5、将数据元素e赋值给s->data;

6、单链表的插入标准语句为：s->next=p->next p->next=s

7、返回成功

具体代码如下：

/*初始条件：顺序线性表工已存在，1≤i≤Listlength（L），*/

/*操作结果：在工中第1个位置之前插入新的数据元素e，L的长度加1*/

Status ListInsert(LinkList *L,int i,ElemType e)

{

int j；

LinkList p,s;

p=*L；

j=1；

while (p&j

{

p=p->next;

++j；

}

if (!p || j>i)

return ERROR;/*第i个元素不存在*！

s=(LinkList)malloc(sizeof(Node))；/*生成新结点（C标准函数）*/

s->data=e;

s->next=p->next；/*将p的后继结点赋值给s的后继*）

p->next=s;/*将s赋值给p的后继*/

return OK;

}

删除节点

def remove(self,item):

"""删除节点"""

cur = self._head

pre = None

while cur != None:

# 找到了指定元素

if cur.item == item:

# 如果第一个就是删除的节点

if not pre:

# 将头指针指向头节点的后一个节点

self._head = cur.next

else:

# 将删除位置前一个节点的next指向删除位置的后一个节点

pre.next = cur.next

break

else:

# 继续按链表后移节点

pre = cur

cur = cur.next

C/C++版：

设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将他的前继结点的指针绕过，指向他的后继结点激即可，代码实现其实就是：p->netx = p->next->next用q来替代p->next即是：q = p->next; p->next = q ->next;如图所示：

此图来源于《大话数据结构》

删除第i个数据算法思路如下：

1、声明一个结点p指向链表的第一个结点，初始化j从1开始

2、当j

3、若到了链表末尾p为空，则说明第i个元素不存在

4、否则查找成功，将欲删除的结点p->next赋值给q

5、单链表的删除标准语句p->next = q->next

6、将q结点中的数据赋值给e，作为返回

7、释放q结点

8、返回成功

实现代码如下：

/*初始条件：顺序线性表工已存在，1≤isListLength（L）*/

/*操作结果：删除工的第i个数据元素，并用e返回其值，工的长度减1*/

Status ListDelete(LinkList *L,int i,ElemType *e)

{

int j;

LinkList p,q;

p=*L；

j=1；

while (p->next && j

{

p=p->next;

++j；

}

if（！(p->next) || j>i)

return ERROR;/*第1个元素不存在*/

q = p->next;

p->next = q->next；/*将q的后继赋值给p的后继*/

*e = q-> data；/*将q结点中的数据给e*/

free(q);/*让系统回收此结点，释放内存*/

return OK;

}

查找节点是否存在

def search(self,item):

"""链表查找节点是否存在，并返回True或者False"""

cur = self._head

while cur != None:

if cur.item == item:

return True

cur = cur.next

return False

链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。