【札记】基本数据结构(Python实现)

本文是学习数据结构和python的个人札记。

原文: Problem Solving with Algorithms and Data Structures using python


Stack - 栈

概述

栈(Stack)是一种后进先出(LIFO)的数据结构。

抽象数据类型ADT

Stack的ADT接口主要包括:

  • Stack() 创建空栈
  • clear() 清空栈
  • is_empty() 判断栈是否为空
  • push(item) 将item压入栈
  • pop() 返回栈顶内容,并弹出栈
  • size() 返回栈元素个数
  • get_top() 返回栈顶元素但不弹出

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Stack(object):
def __init__(self):
self.items = []

def is_empty(self):
return self.items == []

def clear(self):
self.items = []

def push(self,item):
self.items.append(item)

def pop(self):
return self.items.pop()

def size(self):
return len(self.items)

def get_top(self):
return self.items[len(self.items)-1]

应用

  1. 中缀表达式(infix)转换为后缀表达式(postfix)并运算结果
  2. 判断括号层数是否匹配

Queue - 队列

概述

队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行。

抽象数据类型ADT

Queue的ADT接口主要包括:

  • Queue() 创建空队列
  • clear() 清空队列
  • is_empty() 判断队列是否为空
  • enqueue(item) 将item送入队尾
  • dequeue() 返回队首内容,并从队列删除该元素
  • size() 返回队列长度
  • get_head() 返回队首元素但不出队

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Queue(object):
def __init__(self):
self.items = []

def is_empty(self):
return self.items == []

def clear(self):
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)

def get_head(self):
if len(self.items) == 0:
return None
else:
return self.items[len(self.items)-1]

应用

  1. 流水线作业
  2. 改进成环形队列

Deque - 双端队列

概述

双端队列(Deque)是一种兼顾队列和栈性质的数据结构,元素可以从队首(front)或者队尾(rear)进出队列。

抽象数据类型ADT

  • Deque() 创建空双端队列
  • clear() 清空双端队列
  • is_empty() 判断队列是否为空
  • add_front(item) 将item送入队首
  • add_rear(item) 将item送入队尾
  • remove_front() 返回队首内容,并从队列删除该元素
  • remove_rear() 返回队尾内容,并从队列删除该元素
  • size() 返回栈元素内容
  • get_head() 返回队首元素但不出队

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Deque(object):
def __init__(self):
self.items = []

def is_empty(self):
return self.items == []

def clear(self):
self.items = []

def add_front(self,item):
self.items.append(item)

def add_rear(self,item):
self.items.insert(0,item)

def remove_front(self):
return self.items.pop()

def remove_rear(self):
return self.items.pop(0)

def size(self):
return len(self.items)

def get_head(self):
if len(self.items) == 0:
return None
else:
return self.items[len(self.items)-1]

应用

  1. 验证回文(palindrome),将字符串输入双端队列,分别从首尾取字符进行逐一比较。

Linked List - 链表

概述

链表(linked list)是一种动态储存数据的集合,由结点组成,前后结点之间存在引用或链接指向关系。
链表可以分为单链表、双链表、循环链表等形式,这里我们只考虑单向循环链表,其他类型的链表实现方式类似。

抽象数据类型ADT

  • SinCycLinkedList() 初始化单向循环链表
  • add(item) 插入结点
  • is_empty() 判断链表是否为空
  • search(item) 判断某数据项受否存在与链表中
  • remove(item) 删除链表结点
  • size() 返回链表数据个数

python实现

Implementing an Unordered List: Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Node(object):
'''
Definiton of the node of the single linked list.
'''
def __init__(self,init_data):
#prevent external access
self.__data = init_data
self.__next = None

def get_data(self):
return self.__data

def get_next(self):
return self.__next

def set_data(self,data):
self.__data = data

def set_next(self,next_node):
self.__next = next_node


class SinCycLinkedList(object):
'''
Implementation of Single Cicular Linked List.
'''
def __init__(self):
self.head = Node(None)
self.head.set_next(self.head)

def is_empty(self):
# check if the reference of the head node leads to itself
return self.head.get_next() == self.head

def add(self,item):
temp_node = Node(item)
temp_node.set_next(self.head.get_next())
self.head.set_next(temp_node)

def remove(self,item):
previous = self.head
while previous.get_next() != self.head:
current = previous.get_next()
if current.get_data() == item:
previous.set_next(current.get_next())
return True
previous = previous.get_next()
return False

def search(self,item):
current = self.head.get_next()
while current != self.head:
if current.get_data() == item:
return True
current = current.get_next()
return False

def size(self):
count = 0
current = self.head.get_next()
while current != self.head:
count += 1
current = current.get_next()

应用

  1. 非连续空间申请,充分利用内存。

Hash table 哈希表

概述

哈希表(Hash table)是用于快速查询和访问的数据结构。通过hash函数将元数据进行映射。
构建hash的方式很多,有乘法、除法、全域hash等。

抽象数据类型ADT

  • HashTable() 创建新的空Hash表
  • put(key,value) 在表中加入新的键值对
  • get(key) 通过键值查询表中元素,若不存在则返回None
  • del HashTable[key] 通过键值删除表中元素
  • len() 返回表中的键值对数量
  • key in HashTable 查询某键值是否存在于表中,是则True

python实现

Implementing HashTable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Node(object):
'''
Definiton of the node of the single linked list.
'''
def __init__(self,initdata):
#prevent external access
self.__data = initdata
self.__next = None


def get_data(self):
return self.__data


def get_next(self):
return self.__next


def set_data(self,data):
self.__data = data


def set_next(self,next_node):
self.__next = next_node


class SinCycLinkedList(object):
'''
Implementation of Single Cicular Linked List.
'''
def __init__(self):
self.head = Node(None)
self.head.set_next(self.head)


def is_empty(self):
# check if the reference of the head node leads to itself
return self.head.get_next() == self.head


def add(self,item):
temp_node = Node(item)
temp_node.set_next(self.head.get_next())
self.head.set_next(temp_node)


def remove(self,item):
previous = self.head
while previous.get_next() != self.head:
current = previous.get_next()
if current.get_data() == item:
previous.set_next(current.get_next())
return True
previous = previous.get_next()
return False


def search(self,item):
current = self.head.get_next()
while current != self.head:
if current.get_data() == item:
return True
current = current.get_next()
return False


def size(self):
count = 0
current = self.head.get_next()
while current != self.head:
count += 1
current = current.get_next()

应用

  1. 快速插入和查询数据

Heap - 堆

概述

堆(Heap)是一种用于高效操作集合中最小或最大元素的数据结构,使用堆可以实现优先队列并在O(logn)时间复杂度下插入或删除元素。
堆可以分为最大堆和最小堆,在结构上类似于二叉树,同时满足子结点元素值均大于(小于)父结点的条件。
一般二项堆的基本形式的完全二叉树,因此父子结点之间存在系数关系:left_son = 2p; right_son = 2*p+1。因此而堆可以通过数组形式实现。

抽象数据类型ADT(以最小堆为例,最大堆类似)

  • BinHeap() 初始化堆
  • build_heap() 将数组转化为堆
  • insert(k) 插入元素并保持堆性质
  • find_min() 返回堆中最小元素,但保留
  • del_min() 返回堆中最小元素,同时删除元素
  • is_empty() 检查堆是否为空
  • size() 返回当前堆中元素数

python实现

Binary Heap Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class MinBinHeap(object):
# implemention using list
def __init__(self):
self.heap_list = [0]
self.current_size = 0


def insert(self,element):
self.heap_list.append(element)
self.current_size += 1
self.prec_up(self.current_size)

def prec_down(self,i):
while (i * 2) <= self.current_size:
mc = self.min_child(i)
if self.heap_list[i] > self.heap_list[mc]:
self.heap_list[i],self.heap_list[mc] = self.heap_list[mc],self.heap_list[i]
i = mc


def min_child(self,i):
if i * 2 + 1 > self.current_size:
return i * 2
else:
if self.heap_list[2*i] < self.heap_list[2*i+1]:
return i * 2
else:
return i * 2 + 1



def prec_up(self,i):
while i // 2 > 0:
if self.heap_list[i] < self.heap_list[i//2]:
self.heap_list[i],self.heap_list[i//2] = self.heap_list[i//2],self.heap_list[i]
i = i // 2


def del_min(self):
result = self.heap_list[1]
self.heap_list[1] = self.heap_list[self.current_size]
self.current_size -= 1
self.heap_list.pop()
self.prec_down(1)


return result


def build_heap(self,list):
i = len(list) // 2
self.current_size = len(list)
self.heap_list = [0] + list[:]


while i > 0:
self.prec_down(i)
i -= 1

def is_empty(self):
return self.heap_list == [0]


def size(self):
return self.current_size


def find_min(self):
return self.heap_list[1]

应用

  1. 非连续空间申请,充分利用内存。