数据结构
2020-05-22 本文已影响0人
不羁者的璀璨星空丶
数据结构
1. 栈
- 先进后出
- 栈顶，栈底
- 应用：浏览器的后退按钮
实现一个栈：
- Stack() 创建一个新的空栈。
- push(item) 添加一个元素item到栈顶。无返回值。
- pop() 从栈顶删除一个元素。返回该元素。
- peek() 获取栈顶的元素，不改变栈的结构。
- isEmpty() 判断该栈是否为空。
- size() 返回栈的元素个数。
代码实现：
class Stack():
def __init__(self):
self.items = []
def push(self,item):
"""添加一个元素item到栈顶"""
self.items.append(item)
def pop(self):
"""从栈顶删除一个元素并返回"""
return self.items.pop()
def peek(self):
"""获取栈顶的元素"""
return self.items[-1]
def isEmpty(self):
"""判断栈是否为空"""
return self.items == []
def size(self):
"""获取栈的元素个数"""
return len(self.items)
2. 队列
- 先进先出
- 应用：需要排队的任务。
实现一个队列：
- Queue() 创建一个新的空队列。
- enqueue(item) 添加一个元素item到队尾。
- dequeue() 从队首移除一个元素。并返回item。
- isEmpty() 判断队列是否为空。
- size() 获取队列的长度。
代码实现：
class Queue():
def __init__(self):
self.items = []
def enqueue(self,item):
"""向对尾插入一个元素item"""
self.items.insert(0,item)
def dequeue(self):
"""从队尾删除一个元素"""
return self.items.pop()
def isEmpty(self):
"""判断队列是否为空"""
return self.items == []
def size(self):
"""获取队列的长度"""
return len(self.items)
3. 链表
- 一种线性表。
- 不像顺序表一样连续存储数据，而是每一个节点（数据存储单元）存储数据和存储下一个节点的地址。
实现一个链表：
- Node() 创建一个新的空节点。
- Link() 封装一个链表结构。
- add() 新增一个链表节点。
- append(item) 链表尾部添加节点item。
- insert(item,index) 把节点item插入到指定的index下标处。
- travel() 遍历整个链表。
- length() 获取链表的长度。
- remove(item) 删除节点
- search(item) 查找节点是否存在。
- isEmpty() 判断链表是否为空。
代码实现：
class Node():
def __init__(self,item):
self.item = item
self.next = None
class Link():
def __init__(self):
self._head = None
def add(self,item):
"""新增一个链表节点"""
node = Node(item)
if self._head == None:
self._head = node
return
node.next = self._head
self._head = node
def append(self,item)：
"""链表尾部添加节点item"""
node = Node(item)
cur = self._head
pre = None
while cur:
pre = cur
cur = cur.next
pre.next = node
def travel(self):
cur = self._head
while cur:
print(cur.item)
cur = cur.next
def search(item):
isFind = False
cur = self._head
while cur:
if cur.item == item:
isFind = True
return isFind
def length(self):
cur = self._head
num = 0
while cur:
num += 1
cur = cur.next
return num
def isEmpty(self):
return self._head.item == None
def insert(self,item,index):
"""向指定的位置index，插入节点item"""
node = Node(item)
cur = self._head
point = 0
if index <= 0:
self.add(item)
elif index >= self.length():
self.append(item)
else:
while cur:
pre = cur
cur = cur.next
if point == index - 1:
node.next = cur
pre.next = node
point += 1
def remove(self,item):
cur = self._head
pre = None
if self.search(item):
if cur.item == item:
self._head = cur.next
return
while cur:
pre = cur
cur = cur.next
if cur.item == item:
pre.next = cur.next
cur.next = None
break
link = Link()
link.add(1)
link.add(2)
link.add(3)
link.add(4)
link.add(5)
link.append(6)
link.travel()
print(link.search(6))
print(link.isEmpty())
print(link.length())
link.insert(200,4)
print(link.search(200))
link.travel()
print("===========")
link.remove(200)
link.travel()
3. 二叉树
- 节点：
- 数值：保存节点数据
- left：指向左叶子节点
- right：指向右叶子节点
- 跟节点：
- 最上层的一个节点叫做跟节点
定义一个二叉树：
- Node() 创建一个节点。
- Tree() 封装一个二叉树。
- insert(item) 向二叉树中插入数据。
- travel() 遍历二叉树。
class Node():
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class Tree():
def __init__(self):
self.root = None
def insert(self,item):
node = Node(item)
if self.root == None:
self.root = node
return
cur = self.root
node_list = [cur]
while True:
node_pop = node_list.pop(0)
if node_pop.left == None:
node_pop.left = node
break
else:
node_list.append(node_pop.left)
if node_pop.right== None:
node_pop.right= node
break
else:
node_list.append(node_pop.right)
def travel(self):
cur = self.root
node_list = [cur]
while node_list:
node_pop = node_list.pop(0)
print(node_pop.item)
if node_pop.left != None:
node_list.append(node_pop.left)
if node_pop.right != None:
node_list.append(node_pop.right)
t = Tree()
t.insert(1)
t.insert(2)
t.insert(3)
t.insert(4)
t.insert(5)
t.travel()
查找算法
1. 顺序查找
- 顺序查找原理剖析：
- 从列表中的第一个元素开始，我们按照基本的顺序排序，简单地从一个元素移动到另一个元素，直到找到我们正在寻找的元素或遍历完整个列表。如果我们遍历完整个列表，则说明正在搜索的元素不存在。
def search(alist,item):
isFind = False
pos = 0
while True:
if alist[pos] == item:
isFind = True
break
else:
pos += 1
if pos == len(alist):
break
return isFind
alist = [1,2,3,4,5,6,7,8,9]
print(search(alist,5))
2. 二分查找
- 只作用于有序集合。
def search(alist,item):
isFind = False
left = 0
right = len(alist) - 1
while left <= right:
mid = (left + right) // 2
if item < alist[mid]:
right = mid - 1
elif item > alist[mid]:
left = mid + 1
else:
isFind = True
break
return isFind
alist = [1,2,3,4,5,6,7,8,9]
print(search(alist,5))
排序算法
1. 冒泡排序
- 相邻元素，两两比较，大的放后面。
def sort(item):
for i in range(len(item)):
for j in range(len(item)-i-1):
if item[j] > item[j+1]:
item[j],item[j+1] = item[j+1],item[j]
return item
alist = [3,7,4,2,6,8,2,1,9]
print(sort(alist))
2. 选择排序
- 每次遍历整个列表，选择最大的一个元素，和最后一个元素交换。每次遍历只交换一次数据。
def sort(item):
for j in range(len(item)-1):
max = 0
for i in range(1,len(item)-j):
if item[max] < item[i]:
max = i
item[max],item[len(item)-j-1] = item[len(item)-j-1],item[max]
return item
alist = [3,7,4,2,6,8,2,1,9]
print(sort(alist))
3. 插入排序
- 把列表当做两部分：有序部分和无序部分，每次取一个无序元素，和有序元素比较，插入到有序部分。
- 有序部分：默认第一个元素是有序的
- 无序部分：非第一个元素是无序的
- 引入一个变量 i：表示有序元素的个数和无序元素的第一个元素下标
def sort(alist):
for i in range(len(alist)):
while i > 0:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
break
return alist
alist = [3,7,4,2,6,8,2,1,9]
print(sort(alist))
4. 希尔排序
- 增量gap，初始值：元素个数整除2
- gap表示分组的个数
- gap表示每组数据的间隔
- 然后每次用分组个数整除2获取新的gap值
- 插入排序就是增量为1的希尔排序，可以处理大数据量的排序。
def sort(alist):
gap = len(alist) // 2
while gap > 0:
for i in range(len(alist)):
while i > 0:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
break
gap //= 2
return alist
alist = [3,7,4,2,6,8,2,1,9]
print(sort(alist))
5. 快速排序
- 定义两个变量：
- low：序列的最左边的元素
- high：序列的最右边的元素
- 把列表的第一个元素赋值给基准数字mid变量，使基准值右边的值都大于mid，使左边的值都小于mid。
-
- 实现过程：
- 移动high：用mid值和high值比较，若high值大于mid值，则high-1，否则把high值赋给low。
- 移动low： 用mid值和low值比较，若low值小于mid值，则low+1，否则把low值赋给high。
- 完成以上的逻辑之后，把mid左边的元素当做一个序列，右边的元素当做一个序列，然后重复上面的逻辑（使用递归实现）。
def sort(alist,start,end):
low= start
high= end
if low > high:
return
mid = alist[low]
while low < high:
while low < high:
if mid > alist[high]:
alist[low] = alist[high]
break
else:
high -= 1
while low < high:
if mid < alist[low]:
alist[high] = alist[low]
break
else:
low += 1
if low == high:
alist[low] = mid
break
sort(alist,start,high-1)
sort(alist,low+1,end)
return alist
alist = [5,7,8,3,2,1,4,6,9]
sort(alist,0,len(alist)-1)
