阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

四、链接表

  • 顺序表结构是组织一组元素的最重要方式
    • 可以直接地实现线性表
    • 也是许多其他数据结构的实现基础
  • 如果一个表在使用中经常需要修改结构,使用顺序表操作代价可能很高,根源在于元素存储的集中方式和连续性
  • 线性表实现的基本需要:
    • 能够找到表中的首元素
    • 从表中任一元素出发,可以找到它之后的下一个元素
    • 将元素保存在连续存储区,自然满足这两个需求,顺序关联是隐含的。但满足这两种需求,并不一定要连续存储元素
  • 实现线性表的另一方式是基于链接结构,用链接显示地表示元素之间的顺序关联。基于链接技术实现的线性表称为链接表或链表
  • 基本想法:
    • 把元素分别存储在一批独立的存储块(称为结点)里
      • 保证从一个元素的结点可找到与其相关的下一元素的结点
      • 在结点里用链接的方式显示记录元素(结点)之间的关联
    • 只需知道表中第一个结点,就能顺序找到表中其它元素

1.单链表

  • 每个结点里中记录着下一元素所在结点的标识
  • 表中的n个元素对应的n个结点通过链接形成一条结点链。从表中的任一结点都可以找到保存下一个元素的结点
  • 要掌握一个单链表,仅需要掌握其首结点
    • 可以找到表的首元素
    • 可以找到表中下一结点的位置,以此下去,就可以找到表中所有数据元素
  • 表头变量:保存着链表第一个结点的标识(链接)的变量
  • 概括如下:一个具体的表由一些具体结点构成
    • 每个结点有自己的标识(下面也常直接称为链接)
    • 结点之间通过结点链接建立起顺序联系
    • 给表的最后一个结点的链接域设置一个不会作为结点对象标识的值(python里自然应该用None),称为空链接
  • 通过判断是否空链接,可以知道是否到了表尾
    • 做检索工作时,据此判断是否结束工作
    • 如果表头指针的值是空链接,说明‘它所引用的表已经结束’,没有元素就已结束,说明是空表
  • 在实现算法时,并不需要关系各结点的具体链接的值,只需关系链表的逻辑结构
    • 链表的操作也只需根据链表的逻辑结构考虑和实现

2.基本操作

  • 创建空链表:只需将表头变量设置为空链接
    • python中设置为None
  • 删除链表:丢弃表的所有结点
    • 在一些语言中需要做许多事情,释放所有存储
    • python只需将表指针设为None即可。存储管理系统会自动回收不用的存储
  • 判断是否为空:将表头变量的值与空链接比较
    • python中检查其是否为None
  • 判断是否满:链接表不会满,除非存储空间用完
a.加入元素
  • 基本情况
    • 分为首端、尾端、定位加入,不同位置的操作复杂性可能不同
    • 无需移动已有数据,只需为新元素安排一个新结点,然后把其连接到表中所需的位置
  • 首端加入:
    • 创建一个新结点将元素存入
    • 设置新结点的链接域指向链表首结点
    • 修改表头变量使其引用新结点
  • 尾端加入:
    • 创建一个新结点将元素存入
    • 设置新结点的链接域指向None
    • 表空时,设置表头变量引用新结点,否则设置表尾结点的链接域指向新结点
  • 定位加入:
    • 找到加入位置的前一结点,不存在则结束
    • 创建一个新结点将元素存入,设置新结点链接域的指向为前一结点的链接域指向
    • 设置前一结点的链接域指向为新结点
b.删除元素
  • 首端删除:设置表头变量引用原表头变量链接域所指向的结点
  • 尾端删除:找到链接域为None的前一结点,设置其链接域指向为None;若不存在则将表头变量设为None
  • 定位删除:找到删除结点的前一结点,设置其链接域指向删除结点的链接域指向;若不存在则设置表头变量引用删除结点链接域所指向结点
c.扫描和遍历
  • 许多操作需要扫描表里一个个结点,可能检查其中的元素,该过程称为遍历,顺序检查一个数据结构的所有元素,如
    • 求元素个数
    • 查找特定位置的元素,或满足某些条件的元素
d.操作复杂性
  • 创建空表、删除表、判断空表都是O(1)
  • 首端加入为O(1),尾端加入和定位加入都是O(n)
  • 首端删除为O(1),尾端删除和定位删除都是O(n)
  • 其它操作:如需要扫描整个表或其中一部分,都是O(1)操作;有时可根据需要改造表的表示方式,如经常要用到表长度,可以考虑首结点的元素区存放长度值,需要在加入和删除操作中维护个数记录

4.python实现

  • 实现单链表需要定义相应的类,首先是表示结点的类
    class LNode(object)
    def __init__(self,elm,nxt):
        self.elem = elm
        self.next = nxt
  • 简单使用,
    
    llist = Lnode(1, None), pnode = llist
    for i in range(2, 7):
    pnode.next = LNode(i, None)
    pnode = ponde.next

n = llist
while n is not None:
print(n.elem)
n = n.next


##### **a.基本操作**
* 我们希望基于结点LNode定义一种链接表类型,为此定义一个表类

class LList(object):
def init(self):
self.head = None

def isEmpty(self):
    return self.head == None

# 首端加入
def prepend(self, elem):
    self.head = LNode(elem, self.head)
* 尾端加入,复杂性(最坏情况)为O(n),需要循环找到最后一个结点
```python
def append(self, elem):
    p = self.head
    if p is None: # 判断原表是否为空
        self.head = LNode(elem, None)
        return
    while p.next is not None
        p = p.next
    p.next = LNode(elem, None)
  • 首尾端弹出
    
    def pop(self):
    if self.head is None:
        raise ValueError
    e = self.head.elem
    self.head = self.head.next
    return e

def poplast(self): # 尾端弹出,复杂性为O(n)
if self.head is None:
raise ValueError
p = self.head
if p.next is None
e = p.elem
self.head = None
return e
while p.next is not None:
pre = p
p = p.next
e = p.elem
pre.next = None
return e

* 其它操作
```python
def find(self, pred):
    p = self.head
    while p is not None:
        if pred(p.elem):
            return p.elem
        p = p.next
    return None

def printall(self):
    p = self.head
    while p is not None:
        print(p.elem)
        p = p.next
X定位删除

5.单链表变形

  • 实际中可根据具体需求做相应调整,例如加入尾端结点的引用,结构变化应该只影响到表的变动操作,非变动操作不需要修改,可以重用LList的一些定义

    class LList1(LList):
    def __init__(self)
        LList.__init__(self)
        self.rear = None
    
    def prepend(self, elem):
        self.head = LNode(elem, self.head)
        if self.rear is None:
            self.rear = self.head
    
    def append(self, elem):
        if self.head is None:
            preend(self, elem)
        else:
            self.rear.next = LNode(elem, None)
            self.rear = self.rear.next
    
    def pop(self):
        if self.head is None:
            return ValueError
        e = self.head.elem
        if self.rear is self.head:
            self.rear = None
        self.head = self.head.next
        return e
    
    def poplast(self):
        #return None
        # to be implemented or simply use this
        if self.rear is None:
            return ValueError
        e = self.rear.elem
        if self.head is self.rear:
            self.head = None
        p = self.head
        while p is not self.rear:
            pre = p
            p = p.next
        pre.next = None
        self.rear = pre
        return e

思考

  • 数据结构首先应定义好结构单元
  • 数据结构的实现是一系列结构单元的内在联系及外部组织的体现
  • 如单链表,预先定义好结点的结构,在构建一序列相关结点时,形成内部的链接关系,通过外部指定表头变量,从而体现出单链表的结构完整性
最后由 oucb 编辑于2016年05月03日 16:53