python数据结构之链表

一、线性结构元素的存储

线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的各个数据元素。又称为顺序存储结构或顺序映像。
（1）逻辑关系上相邻的两个元素在物理位置上也相邻。即线性表的逻辑结构与存储结构一致
（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
这种存取元素的方法被称为随机存取法
顺序表的优缺点
优点：
①存储密度大，即空间单元利用率高（结点本身所占存储量/结点结构所占存储量）
②可以随机存取表中任一元素
缺点：在插入、删除某一元素时，需要移动大量元素
所以，为克服这一缺点，我们采用链式存储

二、线性结构元素的链式存储

元素在存储器中的位置是任意的，逻辑上相邻元素在物理上不一定相邻；前后逻辑关系通过指针表示，因此除了保存元素值外还需保存下一个元素的逻辑信息。
必须按指针关系顺序访问。
线性表的链式表示又称为非顺序映像或链式映像。
链式存储结构的线性表称为线性链表。表中元素由结点构成，每个结点包含数据域（值域）与指针域（链）。

data：数据域
next：指针域

三、单链表

特征：构成链表的结点只有一个指针域

存储地址	数据域	指针域
1	ZHANG	13
7	WANG	1
13	LI	null
19	ZHAO	37
25	WU	7
31	ZHOU	19
37	SUN	25

（一）建立单链表

单链表是由带指针的结点构成的序列，指针表示结点的先后（逻辑）关系。单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名，如单链表L。
结点的结构定义如下：(python类的定义)

python

class NODE:
     def __init__(self):
          self.data=‘ ‘
          self.next=None

学生成绩表可以用下面的程序来创建：

python

#学生成绩结点类
class student:
    def  __init__(self):
        self.name=' '
        self.score=0
        self.next=None

head=student()  #建立头结点
head.next=None  #当前为空链表
ptr=head
select=0
while select!=2:
    print("(1)新增；(2)离开 =>")
    try:
        select=int(input("请输入一个选项："))
    except ValueError:
        print("输入错误！请重新输入！\n")
    if select==1:
        new_data=student()  #新定义一个结点元素
        new_data.name=input("姓名：")
        new_data.score=eval(input("成绩："))
        ptr.next=new_data   #挂到ptr后面
        new_data.next=None  #当前结点为最后一个
        ptr=ptr.next

（二）遍历单链表

对于链表来说，由于存储位置通过指针来链接，故如何利用指针遍历链表是多数算法的基础。
利用单根指针遍历：

python

1
2
3

cp=L.next
while cp!=None:
    cp=cp.next

若涉及插入和删除，需要一前一后两根指针。ap为cp的前驱

python

ap=L
cp=L.next
while cp!=None:
    ap=cp
    cp=cp.next

学生成绩表举例：

python

class student:
    def  __init__(self):
        self.name=' '
        self.score=0
        self.next=None

head=student()  #建立头结点
head.next=None  #当前为空链表
ptr=head
select=0
while select!=2:
    print('(1)新增；(2)离开 =>')
    try:
        select=int(input("请输入一个选项："))
    except ValueError:
        print("输入错误！请重新输入！\n")
    if select==1:
        new_data=student()  #新定义一个结点元素
        new_data.name=input('姓名：')
        new_data.score=eval(input('成绩：'))
        ptr.next=new_data   #挂到ptr后面
        new_data.next=None  #当前结点为最后一个
        ptr=ptr.next

ptr=head.next
while ptr!=None:
    print(' ---> %s,%d'%(ptr.name,ptr.score),end='')
    ptr=ptr.next

运行结果：

(1)新增；(2)离开 =>
请输入一个选项：1
姓名：zhang
成绩：87
(1)新增；(2)离开 =>
请输入一个选项：1
姓名：li
成绩：76
(1)新增；(2)离开 =>
请输入一个选项：1
姓名：wang
成绩：91
(1)新增；(2)离开 =>
请输入一个选项：1
姓名：liu
成绩：98
(1)新增；(2)离开 =>
请输入一个选项：2
 ---> zhang,87 ---> li,76 ---> wang,91 ---> liu,98

（三）插入新结点

对于顺序表来说，由于是存储地址连续的，插入和删除都需要移动元素。
对于链表来说，由于存储位置通过指针来链接，插入和删除操作只需修改结点间的指针关系。
一般插入分3种情形：
(1) 头插入，即新插入结点成为表首元素。
(2) 尾插入，即新插入结点成为表尾元素。
(3) 中间位置插入，当然首先应该确定插入位置。
①中间位置插入（一般情形）
在链表的某个位置插入一个结点，一般有两种形式：
(1)指定位置插入，如在第3个位置插入
(2)在某个元素的前(后)面插入，如在‘B’的后面插入
如：在单链表第3个位置插入结点s(或在‘B’的后面)，因要修改链接关系，显然必须找到要插入位置的前驱结点p

代码：

python

1 2	s.next=p.next p.next=s

②头插入：新插入结点成为表首元素

③尾插入：新插入结点成为表尾元素

三种不同插入，执行语句都一样（带头结点链表的优势），关键是要确定插入点的前驱结点

（四）删除结点

删除链表的某个结点，一般有两种形式：
(1) 指定位置删除，如删除第3个元素
(2)条件删除，如删除值为‘C’的元素
同样，要删除元素也必须修改链接关系，显然同样必须找到被删元素的前驱结点p
执行语句

python

1	p.next=p.next.next

（五）链表的常用操作

①求表长

python

def countlength(L):
    p=L.next
    linklen=0
    while p!=None:
        linklen=linklen+1
        p=p.next
    return linklen

②查找值为e的数据元素

python

def  LocateELem( L,e) :
    #在带头结点单链表L中查找值为e的元素
    #若找到返回指向该结点的指针，否则返回None
    p=L.next 
    while p!=None and p.data!=e  #遍历找值为e结点
        p=p.next                		
    return p  #p要么指向所找结点,要么为None

③找单链表L中第i个元素

python

def  GetElem(L, i ):
    #返回带头结点单链表L中第i个结点 p，找不到返回None 
    p=L.next
    j=1     #计数器j为1，当前第 1 个，往后走i步
    while  p!=None and j<i :    #直到p为空或指向第i个 
       p=p.next     #p往后走，指向下一个
       j+=1
    return p

四、环形（循环）链表

与单链表的最大区别在于：循环链表的最后一个结点的指针指向头结点，整个链表形成一个环。
最大优势在于：从表中任意一个结点出发都可找到表中其他结点。

循环单链表的操作与单链表基本一致，但由于循环链表结点中不存在为None的指针域，故只需改变两处判断：
1.空表：L.next==L (单：L.next==None)
2.表尾：p.next==L (单：p.next==None)
循环链表和单链表计算长度方式大同小异

python

def countlength(L):
    #求循环单链表L的长度
    p=L.next
    linklen=0
    while p!=L:
        linklen=linklen+1
        p=p.next
    return linklen

python

def countlength(L):
    #求单链表L的长度
    p=L.next
    linklen=0
    while p!=None:
        linklen=linklen+1
        p=p.next
    return linklen

五、双向链表

对于单链表来说，由于结点结构中只设置一根指向后继的指针next，即只能通过next指针按顺序往后找，不能立即找某一结点的前驱（需编程实现）。
对于双向链表来说，结点结构中除设置一根指向后继的指针外，再设置一根指向前驱的指针，故既能往后找后继，又能往前找前驱。

python

class DLNode:
    def __init__(self):
        self.data=‘ ‘
        self.rlink=None
        self.llink=None

双向链表的指针关系

python

p.data==‘B’
p.rlink.data==‘C’
p.llink.data==‘A’
p.llink.rlink==p
p.rlink.llink==p

双向链表也可以有循环，称双向循环链表。此时存在两个环，一个通过rlink，另一个通过llink。

双向链表的插入（p结点前插入s）

python

#按顺序（可以有多种方法）
s.llink = p.llink
p.llink.rlink = s
s.rlink = p
p.llink = s
`

双向链表的删除操作

python

1 2	p.llink.rlink = p.rlink p.rlink.llink = p.llink #若p为表尾结点，则不需要此步骤

六、链表（链式存储结构）的特点

（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等
★这种存取元素的方法被称为顺序存取法
链表的优缺点：
优点：
①数据元素的个数可以自由扩充
②插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点：
①元素逻辑关系需要添加一指针域，需较多内存，存储密度低
②算法相对复杂些，顺序存储