从python来看数据结构基础
数组
概念
数组是有限个相同类型的变量所组成的有序集合。在内存中顺序存储,可以实现逻辑上的顺序表。
python中主要使用列表(list)和元组(tuple)两种集合,本质上都是对数组的封装。
基本操作
#初始化列表
my_list = [3,1,2,5,4,9,7,2]
#读取元素
print(my_list[2])
2
#更新元素
my_list[3] = 10
print(my_list[3])
10
#插入元素
#尾部插入
#尾部插入元素
my_list.append(6)
#中间插入元素
my_list.insert(5,11)
print(my_list)
[3, 1, 2, 10, 4, 11, 9, 7, 2, 6]
以数组的方式理解插入操作:
class MyArray:
def __init__(self,capacity):
self.array = [None] * capacity
self.size = 0
def insert(self,index,element):
#判断访问下标是否超出范围
if index < 0 or index > self.size:
raise Exception("超出数组实际元素范围!")
#从右向左循环,逐个元素向右挪一位
for i in range(self.size - 1,-1,-1):
self.array[i + 1] = self.array[i]
#腾出的位置放入新元素
self.array[index] = element
self.size += 1
def output(self):
for i in range(self.size):
print(self.array[i])
输出结果如下:
array = MyArray(4)
array.insert(0,10)
array.insert(0,11)
array.insert(0,15)
array.output()
15
11
10
但是这种方式一旦元素数量超过了数组的最大长度,数组就会被认为是非法输入,因此我们需要使用超范围插入。
class MyArray:
def __init__(self,capacity):
self.array = [None] * capacity
self.size = 0
def insert_v2(self,index,element):
#判断访问下标是否超出范围
if index < 0 or index > self.size:
raise Exception("超出数组实际元素范围!")
#如果实际元素达到数组容量上限,数组扩容
if self.size >= len(self.array):
self.resize()
#从右向左循环,逐个元素向右挪一位
for i in range(self.size - 1,-1,-1):
self.array[i + 1] = self.array[i]
#腾出的位置放入新元素
self.array[index] = element
self.size += 1
def resize(self):
array_new = [None] * len(self.array) * 2
#从旧数组复制到新数组
for i in range(self.size):
array_new[i] = self.array[i]
self.array = array_new
def output(self):
for i in range(self.size):
print(self.array[i])
array = MyArray(4)
array.insert_v2(0,10)
array.insert_v2(0,11)
array.insert_v2(0,12)
array.insert_v2(0,14)
array.insert_v2(0,15)
array.insert_v2(0,16)
array.output()
16
15
14
12
11
10
删除操作也是如下方法实现:
def remove(self,index):
#判断访问下表是否超出范围
if index < 0 or index >= self.size:
raise Exception("超出数组实际元素范围!")
#从左到右,所有元素依次挪动一位
for i in range(index,self.size):
self.array[i] = self.array[i + 1]
self.size -= 1
这种操作的方式时间复杂度为 O ( n ) O(n) O(n),但是如果我们将最后一个元素给复制到需要删除元素的位置,再删除最后一个元素,则无需进行大量元素移动,时间复杂度将变为 O ( 1 ) O(1) O(1)。
数组适用于读操作多、写操作少的场景。
链表
概念
链表是一种在物理上非连续、非顺序的数据结构,由若干节点所组成。
- 单向链表:存放数据的变量data和指向下一个节点的指针next组成
- 双向链表:还拥有指向前置节点的prev指针
链表在内存中存储的方式是随机存储。
基本操作
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.size = 0
self.head = None
self.last = None
def get(self,index):
if index < 0 or index > self.size:
raise Exception("超出链表节点范围!")
p = self.head
for i in range(index):
p = p.next
return p
def insert(self,data,index):
if index < 0 or index > self.size:
raise Exception("超出链表节点范围!")
node = Node(data)
if self.size == 0:
#空链表
self.head = node
self.last = node
elif index == 0:
#插入头部
node.next = self.head
self.head = node
elif self.size == index:
#插入尾部
self.last.next == node
self.last = node
else:
#插入中间
prev_node = self.get(index - 1)
node.next = prev_node.next
prev_node.next = node
self.size += 1
def remove(self,index):
if index < 0 or index >= self.size:
raise Exception("超出链表节点范围!")
#暂存被删除的节点,用于返回
if index == 0:
#删除头节点
removed_node = self.head
self.head = self.head.next
elif index == self.size - 1:
#删除尾节点
prev_node = self.get(index - 1)
removed_node = prev_node.next
prev_node.next = None
self.last = prev_node
else:
#删除中间节点
prev_node = self.get(index - 1)
next_node = prev_node.next.next
removed_node = prev_node.next
prev_node.next = next_node
self.size -= 1
return removed_node
def output(self):
p = self.head
while p is not None:
print(p.data)
p = p.next
linkedList = LinkedList()
linkedList.insert(3,0)
linkedList.insert(4,0)
linkedList.insert(5,0)
linkedList.insert(9,2)
linkedList.insert(5,3)
linkedList.insert(6,1)
linkedList.output()
5
6
4
9
5
3
linkedList.remove(0)
linkedList.output()
6
4
9
5
3
- 数组和链表的性能对比
查找 | 更新 | 插入 | 删除 | |
---|---|---|---|---|
数组 | O ( 1 ) O(1) O(1) | O ( 1 ) O(1) O(1) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) |
链表 | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) | O ( 1 ) O(1) O(1) | O ( 1 ) O(1) O(1) |
如果需要频繁插入和删除元素,链表更适合。
栈和队列
数组和链表是存储结构,而逻辑结构依赖于物理结构而存在。
逻辑结构分为线性结构和非线性结构
线性结构:例如顺序表、栈、队列等
非线性结构:例如树、图等。
栈
栈是一种线性数据结构,栈中的元素只能先入后出(FILO)。最早进入的是栈底,最后进入的是栈顶。
栈的基本操作有入栈(push)和出栈(pop)
python中列表已经很好地实现了栈的功能,append相当于入栈,pop相当于出栈。
队列
队列是一种线性数据结构,队列的元素只能先入先出(FIFO)。队列的出口端为队头,入口端为队尾。
用数组实现时,为了入队操作的方便,将队尾位置规定为入队元素的下一个位置。
队列的基本操作有入队(enqueue)和出队(dequeue)。
用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。直到(队尾下标+1)%数组长度=对头下标时,则代表队列满了。由于队尾指针指向的位置永远空出1位,所以队列最大容量比数组长度小1。
python中提供了多种队列工具,比如collections.deque
,queue.Queue
等。
我们尝试自己实现一个队列:
class MyQueue:
def __init__(self,capacity):
self.list = [None] * capacity
self.front = 0
self.rear = 0
def enqueue(self,element):
if (self.rear + 1) % len(self.list) == self.front:
raise Exception("队列已满!")
self.list[self.rear] = element
self.rear = (self.rear + 1) % len(self.list)
def dequeue(self):
if self.rear == self.front:
raise Exception("队列已满!")
dequeue_element = self.list[self.front]
self.front = (self.front + 1) % len(self.list)
return dequeue_element
def output(self):
i = self.front
while i != self.rear:
print(self.list[i])
i = (i + 1) % len(self.list)
myqueue = MyQueue(6)
myqueue.enqueue(3)
myqueue.enqueue(5)
myqueue.enqueue(6)
myqueue.dequeue()
myqueue.dequeue()
myqueue.output()
6
栈和队列的应用
栈可以用于实现递归的逻辑,还有面包屑导航(用户在浏览过程中回溯上一级的页面)。
队列可以运用于多线程中争夺公平锁的等待队列,网络爬虫也可以将URL存入队列中。
双端队列综合了栈和队列的优点,从队头可以入队和出队,队尾一端也可以入队和出队。
优先队列遵循谁的优先级高谁先出队,但是是基于二叉堆实现的。
哈希表
哈希表也称为散列表,这个数据结构提供了键(key)和值(value)的映射关系。
在python中,哈希表对应的集合是字典。通过哈希函数,可以将key和数组下标进行转换。
哈希表的读写操作
写操作就是在哈希标中插入新的键值对(Entry)。
当写的过程中发生了哈希冲突,我们可以通过开放寻址法或链表法解决。
- 开放寻址法:寻找被占用的数组下标的下一个位置。
- 链表法:哈希表数组的每一个元素还是一个链表的头节点,只需要插入对应的链表中即可。
读操作就是通过给定的key在哈希表中查找对应的value。
有些语言采用了链表法:Java中的HashMap;而python中的dict采用的是开放寻址法。