python 提供了很多现成的数据结构类型,系统定义好的称为内置数据结构,比如:列表(list),元组(tuple),字典(dict),还有部分pythoh系统中没有直接定义,需要我们自己去定义实现的数据结构,称为python的扩展数据结构,比如,栈,队列等.
在程序中需要将一组数据元素作为整体进行管理和使用,要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。
对于这种需求,最简单的解决方案便是将这样一组元素看成一个序列,用元素在序列里的位置和顺序,表示实际应用中的某种有意义的信息,或者表示数据之间的某种关系。
这样的一组序列元素的组织形式,我们可以将其抽象为线性表。一个线性表是某类元素的一个集合,还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一,在实际程序中应用非常广泛,它还经常被用作更复杂的数据结构的实现基础。
根据线性表的实际存储方式,分为两种实现模型:
顺序表,将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。
链表,将元素存放在通过链接构造起来的一系列存储块中。
图a 表示的是顺序表的基本形式,
Loc(ei) = Loc(e0) + c*i
故,访问指定元素时无需从头遍历,通过计算便可获得对应地址(l.index('x')),其时间复杂度为O(1)。
图b这样的顺序表也被称为对实际数据的索引,这是最简单的索引结构。
完整的顺序表结构包含2个部分,
顺序表的两种基本实现方式
采用分离式结构的顺序表,若将数据区更换为存储空间更大的区域,则可以在不改变表对象的前提下对其数据存储区进行了扩充,所有使用这个表的地方都不必修改。只要程序的运行环境(计算机系统)还有空闲存储,这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表,因为其容量可以在使用中动态变化。
扩充的两种策略
如图所示,为顺序表增加新元素111的三种方式
a. 尾端加入元素,时间复杂度为O(1)
b. 非保序的加入元素(不常见),时间复杂度为O(1)
插入元素到指定位置,将原来指定位置的元素放到最后'
c. 保序的元素加入,时间复杂度为O(n)
插入元素到指定位置,其余元素往后退格,腾出空位,考虑最坏情况插入位置为0,所以时间复杂度为O(n)
a. 删除表尾元素,时间复杂度为O(1)
b. 非保序的元素删除(不常见),时间复杂度为O(1)
删除指定位置的元素,将表尾的元素放入该空余位置上
c. 保序的元素删除,时间复杂度为O(n)
删除指定位置的元素, 往后的元素均往前挪,直至表结构连续不断为止,考虑最坏情况删除位置为0,所以时间复杂度为O(n)
python中的顺序表
python 的基本类型 list tuple 均为顺序表结构,
tuple 为不可变类型,即不可变的顺序表,其余与list相似
python中 list 的基本实现
list 特点:
总结:
单向链表的节点包含:
单向链表的结构:
单向链表的实现:
节点实现
class SingleNode(object):
"""单链表的结点"""
def __init__(self,item):
# item存放数据元素
self.item = item
# next是下一个节点的标识
self.next = None
单链表的操作
单链表的实现
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 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 <= 0:
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 < (pos-1):
count += 1
pre = pre.next
# 先将新节点node的next指向插入位置的节点
node.next = pre.next
# 将插入位置的前一个节点的next指向新节点
pre.next = node
删除节点
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
单向循环链表,是单向表的变形, 尾元素的链接域修改为指向链表的 头节点
双向链表节点:
指定位置插入节点
删除节点
栈,也可以称为堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
栈结构实现
栈可以用顺序表实现,也可以用链表实现。
栈的操作
class Stack(object):
"""栈"""
def __init__(self):
self.items = []
def is_empty(self):
"""判断是否为空"""
return self.items == []
def push(self, item):
"""加入元素"""
self.items.append(item)
def pop(self):
"""弹出元素"""
return self.items.pop()
def peek(self):
"""返回栈顶元素"""
return self.items[len(self.items)-1]
def size(self):
"""返回栈的大小"""
return len(self.items)
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出的(First In First Out)的线性表,简称FIFO。允许插入的一端为队尾,允许删除的一端为队头。队列不允许在中间部位进行操作!假设队列是q=(a1,a2,……,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,总是在队列最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后。
队列的实现
同栈一样,队列也可以用顺序表或者链表实现。
操作
class Queue(object):
"""队列"""
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, item):
"""进队列"""
self.items.insert(0,item)
def dequeue(self):
"""出队列"""
return self.items.pop()
def size(self):
"""返回大小"""
return len(self.items)
双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
操作
class Deque(object):
"""双端队列"""
def __init__(self):
self.items = []
def is_empty(self):
"""判断队列是否为空"""
return self.items == []
def add_front(self, item):
"""在队头添加元素"""
self.items.insert(0,item)
def add_rear(self, item):
"""在队尾添加元素"""
self.items.append(item)
def remove_front(self):
"""从队头删除元素"""
return self.items.pop(0)
def remove_rear(self):
"""从队尾删除元素"""
return self.items.pop()
def size(self):
"""返回队列大小"""
return len(self.items)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。