python数据结构教程 Day5

python数据结构教程 Day5

本节重点：

1. 有序表
2. 链表实现list的算法分析
3. 线性结构小结

一、有序表

1、定义

有序表是一种数据项依照其某可比性质（ 如整数大小、字母表先后）来决定在列表中的位置，越“小”的数据项越靠近列表的头，越靠 “前”。

2、有序表的ADT实现

step1、定义其操作

• OrderedList()：创建一个空的有序表
• add(item)：在表中添加一个数据项，并保持整体顺序， 此项原不存在
• remove(item)：从有序表中移除一个数据项，此项应存在，有序表被修改
• search(item)：在有序表中查找数据项，返回是否存在
• isEmpty()：是否空表
• size()：返回表中数据项的个数
• index(item)：返回数据项在表中的位置，此项应存在
• pop()：移除并返回有序表中最后一项，表中应至少存在 一项
• pop(pos)：移除并返回有序表中指定位置的数据项，此位 置应存在

step2、实现其操作

对于isEmpty/size/remove这些方法，与节点的次序无关，所以其实现跟 UnorderedList是一样的。 search/add方法则需要有修改

class OrderedList(UnorderedList):
    def __init__(self):
        super.__init__()
    
    def search(self, item):
        '''
        利用有序性，只要是大于目标值，直接返回False
        '''
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            elif current.getData() > item:
                stop = True
            else:
                current = current.getNext()
        return found

    def add(self, item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        temp = Node(item)
        if previous == None: # 特殊情况插在头部
            temp.setNext = self.head
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

在实现有序表的时候，需要记住的是，数据项的相对位置，取决于它们之间的“大小”比较。由于Python的扩展性，下面对数据项的讨论并不仅适用于整数，可适用于所有定义了__ gt __ 方法（即'>'操作符）的数据类型。

3、链表实现List的算法分析

对于一个包含节点数为n的链表

• isEmpty是O(1)，因为仅需要检查head是否为None
• size是O(n)，因为除了遍历到表尾，没有其它办法得知节点的数量
• search/remove以及有序表的add方法，则是O(n)， 因为涉及到链表的遍历，按照概率其平均操作的次数 是n/2
• 无序表的add方法是O(1)，因为仅需要插入到表头

实际上Python内置的列表数据类型 是基于顺序存储来实现的，并进行了优化

四、线性结构小结

线性数据结构Linear DS将数据项，以某种线性的次序组织起来。

1、栈：

维持了数据项后进先出LIFO的次序，基本操作包括push, pop, isEmpty。

2、队列：

维持了数据项先进先出FIFO 的次序，基本操作包括enqueue, dequeue, isEmpty。

3、双端队列：

可以同时具备栈和队列的功能，基本操作包括addFront, addRear, removeFront, removeRear, isEmpty

4、List：

List是数据项能够维持相对位置的数据集。

注意：

链表的实现，可以保持列表维持相对位置的特点，而不需要连续的存储空间。链表实现时，其各种方法，对链表头部head需要特别的处理。
上一篇：python数据结构教程 Day4
下一篇：python数据结构教程 Day6