1.python数据结构及算法基础学习笔记思维导图
2.程序代码演示
1.链表模型：linklist.py
1 """ 2 功能: 实现单链表的构建和操作 3 4 """ 5 6 # 创建节点类 7 class Node: 8 """ 9 思路 : *自定义类视为节点类,类中的属性为数据内容 10 *写一个next属性,用来和下一个 节点建立关系 11 """ 12 def __init__(self,val,next = None): 13 """ 14 val: 有用数据 15 next: 下一个节点引用 16 """ 17 self.val = val 18 self.next = next 19 20 21 # 链式线性表操作类 22 class LinkList: 23 """ 24 思路 : 生成单链表,通过实例化的对象就代表一个链表 25 可以调用具体的操作方法完成各种功能 26 """ 27 def __init__(self): 28 # 链表的初始化节点,没有有用数据,但是便于标记链表的开端 29 self.head = Node(None) 30 31 # 初始化链表,添加一组节点 32 def init_list(self,list_): 33 p = self.head # p 作为移动变量 34 for i in list_: 35 # 遍历到一个值就创建一个节点 36 p.next = Node(i) 37 p = p.next 38 39 # 遍历链表 40 def show(self): 41 p = self.head.next # p代表第一个有值的节点 42 while p is not None: 43 print(p.val) 44 p = p.next # p向后移动 45 46 # 判断链表为空 47 def is_empty(self): 48 if self.head.next is None: 49 return True 50 else: 51 return False 52 53 # 清空链表 54 def clear(self): 55 self.head.next = None 56 57 # 尾部插入 58 def append(self,val): 59 p = self.head 60 # p移动到最后一个节点 61 while p.next is not None: 62 p = p.next 63 p.next = Node(val) # 最后添加节点 64 65 # 头部插入 66 def head_insert(self,val): 67 node = Node(val) 68 node.next = self.head.next 69 self.head.next = node 70 71 # 指定位置插入 72 def insert(self,index,val): 73 # 设置个p 移动到待插入位置的前一个 74 p = self.head 75 for i in range(index): 76 # 如果index超出了最大范围跳出循环 77 if p.next is None: 78 break 79 p = p.next 80 # 插入节点 81 node = Node(val) 82 node.next = p.next 83 p.next = node 84 85 # 删除节点 86 def remove(self,val): 87 p = self.head 88 # p 移动,待删除节点上一个 89 while p.next is not None and p.next.val != val: 90 p = p.next 91 92 if p.next is None: 93 raise ValueError("x not in linklist") 94 else: 95 p.next = p.next.next 96 97 98 # 获取某个节点的值 (通过索引获取) 99 def search(self,index): 100 if index < 0: 101 raise IndexError("index out of range") 102 103 p = self.head.next 104 # 循环移动p 105 for i in range(index): 106 if p is None: 107 raise IndexError("index out of range") 108 p = p.next 109 return p.val 110 111 112 if __name__ == "__main__": 113 # 想有一个链表 114 link = LinkList() 115 # 初始化一组数据 116 l = [1,2,3,4] 117 link.init_list(l) 118 # link.clear() 119 print(link.search(0)) 120 # 链表遍历 121 # link.show() 122 # link.insert(2,88) 123 # link.show() 124 # link.clear() 125 # print(link.is_empty()) 126 # Abby = Node((1,'Abby',18,'w')) 127 # Emma = Node((2,'Emma',17,'w')) 128 # Alex = Node((3,'Alex',19,'m')) 129 # Abby.next = Emma 130 # Emma.next = Alex
2.栈的顺序存储：sstack.py
""" 栈模型的顺序存 思路 : 1. 顺序存储可以使用列表实现,但是列表功能丰富,不符合栈模型要求 2. 将列表功能封装,实现顺序栈的类,只提供栈的操作功能 功能: 出栈, 入栈,判断栈空,查看栈顶元素 """ # 自定义异常 class StackError(Exception): pass # 顺序栈 class SStack: def __init__(self): # 空列表就是栈的存储空间 # 列表的最后一个元素作为栈顶元素 self.__elems = [] # 入栈 def push(self,val): self.__elems.append(val) # 判断栈空 def is_empty(self): return self.__elems == [] # 出栈 def pop(self): if self.is_empty(): raise StackError("pop from empty stack") return self.__elems.pop() # 查看栈顶 def top(self): if self.is_empty(): raise StackError("pop from empty stack") return self.__elems[-1] if __name__ == '__main__': st = SStack() st.push(10) st.push(20) st.push(30) while not st.is_empty(): print(st.pop()) st.pop()
3.栈的链式存储：lstack.py
1 """ 2 栈的链式模型 3 4 思路: 5 1. 通过节点存储数据达到链式存储的目的 6 2. 封装方法,实现栈的基本操作(入栈,出栈,栈空,查看栈顶) 7 3. top为栈顶,在链表的头作为栈顶位置 (不许要遍历) 8 """ 9 10 # 自定义异常 11 class StackError(Exception): 12 pass 13 14 # 节点类 15 class Node: 16 def __init__(self,val,next = None): 17 self.val = val 18 self.next = next 19 20 # 链式栈模型 21 class LStack: 22 def __init__(self): 23 # top作为栈顶的标记 24 self.__top = None 25 26 def is_empty(self): 27 return self.__top is None 28 29 # 入栈 30 def push(self,val): 31 self.__top = Node(val,self.__top) 32 33 # node = Node(val) 34 # node.next = self.__top 35 # self.__top = node 36 37 # 出栈 38 def pop(self): 39 if self.__top is None: 40 raise StackError("pop from empty stack") 41 data = self.__top.val 42 self.__top = self.__top.next 43 return data 44 45 # 查看栈顶元素 46 def top(self): 47 if self.__top is None: 48 raise StackError("pop from empty stack") 49 return self.__top.val 50 51 52 if __name__ == '__main__': 53 ls = LStack() 54 ls.push(10) 55 ls.push(20) 56 ls.push(30) 57 print(ls.pop()) 58 print(ls.pop())
4.队列的顺序存储：squeue.py
1 """ 2 队列的顺序存储 3 4 思路 : 5 1. 基于列表完成数据存储 6 2. 对列表功能进行封装 7 3. 列表的头部作为队头,尾部作为队尾 8 功能: 入队(enqueue),出队(dequeue),判断队列为空 9 """ 10 11 # 自定义异常 12 class QueueError(Exception): 13 pass 14 15 class SQueue: 16 # 设置空列表作为队列存储空间 17 def __init__(self): 18 self.__elems = [] 19 20 # 判断队列是否为空 21 def is_empty(self): 22 return self.__elems == [] 23 24 # 入队 25 def enqueue(self,val): 26 self.__elems.append(val) 27 28 # 出对 29 def dequeue(self): 30 if not self.__elems: 31 raise QueueError("Queue is empty") 32 return self.__elems.pop(0) 33 34 if __name__ == '__main__': 35 sq = SQueue() 36 37 sq.enqueue(10) 38 sq.enqueue(20) 39 sq.enqueue(30) 40 41 while not sq.is_empty(): 42 print(sq.dequeue())
5.队列的链式存储：lqueue.py
1 """ 2 链式队列 3 4 思路: 5 1. 基于链表构建队列模型 6 2. 链表的开端作为队头, 结尾作为队尾 7 3. 对头队尾分别添加标记,避免每次插入数据都遍历链表 8 4. 队头和队尾重叠时认为队列为空 9 """ 10 11 # 自定义异常 12 class QueueError(Exception): 13 pass 14 15 # 节点类 16 class Node: 17 def __init__(self,val,next = None): 18 self.val = val 19 self.next = next 20 21 # 队列操作 22 class LQueue: 23 def __init__(self): 24 # 定义队头,队尾 25 self.front = self.rear = Node(None) 26 27 def is_empty(self): 28 return self.front == self.rear 29 30 # 如队 rear动 31 def enqueue(self,val): 32 self.rear.next = Node(val) 33 self.rear = self.rear.next 34 35 # 出队 front动 36 def dequeue(self): 37 if self.front == self.rear: 38 raise QueueError("Queue is empty") 39 40 # front移动到的节点已经出队 41 self.front = self.front.next 42 return self.front.val 43 44 if __name__ == '__main__': 45 lq = LQueue() 46 lq.enqueue(10) 47 lq.enqueue(20) 48 lq.enqueue(30) 49 print(lq.dequeue())
6.递归函数：recursion.py
1 """ 2 求一个数的阶乘 n! 3 """ 4 5 def fun(n): 6 result = 1 7 for i in range(1, n + 1): 8 result *= i 9 return result 10 11 12 def recursion(n): 13 if n <= 1: 14 return 1 15 return n * recursion(n - 1) 16 17 18 print(fun(5)) 19 print(recursion(5))
7.二叉树的链式存储：btree.py
1 """ 2 二叉树的遍历实践 3 4 思路分析: 5 1. 使用链式结构存储二叉树的节点数据 6 2. 节点中存储 数据, 左孩子链接,右孩子链接 三个属性 7 """ 8 from squeue import * 9 10 # 二叉树节点类 11 class Node: 12 def __init__(self,val,left=None,right=None): 13 self.val = val 14 self.left = left 15 self.right = right 16 17 # 二叉树遍历方法 18 class Bitree: 19 def __init__(self,root): 20 self.root = root 21 22 # 先序遍历 23 def preOrder(self,node): 24 if node is None: 25 return 26 print(node.val) 27 self.preOrder(node.left) 28 self.preOrder(node.right) 29 30 # 中序遍历 31 def inOrder(self, node): 32 if node is None: 33 return 34 self.inOrder(node.left) 35 print(node.val) 36 self.inOrder(node.right) 37 38 # 后序遍历 39 def postOrder(self, node): 40 if node is None: 41 return 42 self.postOrder(node.left) 43 self.postOrder(node.right) 44 print(node.val) 45 46 # 层次遍历 47 def levelOrder(self,node): 48 """ 49 node先入队,循环判断,队列不为空时,出队表示遍历, 50 同时让出队元素的左右孩子入队 51 """ 52 sq = SQueue() 53 sq.enqueue(node) 54 while not sq.is_empty(): 55 node = sq.dequeue() 56 print(node.val) # 遍历元素 57 if node.left: 58 sq.enqueue(node.left) 59 if node.right: 60 sq.enqueue(node.right) 61 62 63 64 if __name__ == '__main__': 65 b = Node('B') 66 f = Node('F') 67 g = Node('G') 68 d = Node('D',f,g) 69 h = Node('H') 70 i = Node('I') 71 e = Node('E',h,i) 72 c = Node('C',d,e) 73 a = Node('A',b,c) # 整个树根 74 75 bt = Bitree(a) # 把a作为根节点进行遍历 76 77 bt.preOrder(bt.root) 78 print("========================") 79 bt.inOrder(bt.root) 80 print("========================") 81 bt.postOrder(bt.root) 82 print("========================") 83 bt.levelOrder(bt.root)
8.排序算法选择、冒泡、插入、归并、快速排序：sort.py
1 def selection_sort(arr): 2 """ 3 1.选择排序：外层循环一次，就可排好一个数,从前往后排。 4 用选定元素与其后的所有元素进行比较，较大（小）交换 5 """ 6 for i in range(len(arr) - 1): # 需要比较n-1轮 7 for j in range(i + 1, len(arr)): # 每一轮需要比较j次 8 if arr[i] > arr[j]: # 升序排列 9 arr[i], arr[j] = arr[j], arr[i] 10 11 12 def buble_sort(arr): 13 """ 14 2.冒泡排序：外层循环一次，就可排好最后一个数,从后往前排。 15 所有相邻元素依次进行比较，较大（小）交换 16 """ 17 for i in range(len(arr) - 1): # 需要比较n-1轮 18 for j in range(len(arr) - 1 - i): # 每轮比较中，索引j的取值0到(n-1)-i 19 if arr[j] > arr[j + 1]: 20 arr[j], arr[j + 1] = arr[j + 1], arr[j] 21 22 23 def insert_sort(arr): 24 """ 25 3.插入排序：将第一个元素看做有序序列，从后向前扫描有序序列，将为排序元素依次插入对应位置 26 """ 27 for i in range(1, len(arr)): # 只需要对第二个到最后一个元素进行排序 28 preindex = i - 1 29 current = arr[i] 30 while preindex >= 0 and arr[preindex] > current: 31 arr[preindex + 1] = arr[preindex] # 将前一个元素赋值给当前元素位置上 32 preindex -= 1 33 arr[preindex + 1] = current # 将当前元素赋值给“对应”位置上 34 35 36 def merge_sort(arr): 37 """ 38 4.归并排序：递归的将arr一分为二的拆分为一个二叉树（每个叶子节点只有一个数）， 39 定义空列表result=[]，回归的将叶子结点合并到result中，回归到根节点 40 """ 41 if len(arr) < 2: 42 return arr # 递归结束条件：拆分后的最终列表中只有一个元素 43 middle = len(arr) // 2 44 left, right = arr[:middle], arr[middle:] 45 return merge(merge_sort(left), merge_sort(right)) 46 47 48 def merge(left, right): 49 result = [] 50 while left and right: # 回归阶段：将左右子节点合并到父节点 51 if left[0] <= right[0]: 52 result.append(left.pop(0)) 53 else: 54 result.append(right.pop(0)) 55 while left: 56 result.append(left.pop(0)) 57 while right: 58 result.append(right.pop(0)) 59 return result 60 61 62 def quick_sort(arr): 63 """ 64 5.快速排序：选定第一个元素为基准，将后面的元素“依次”与基准比较， 65 较大的放基准右边区域，较小的放基准左边区域。 66 递归的对左右区域进行分区操作，直至该区域中只有一个元素了 67 """ 68 sort(arr, 0, len(arr) - 1) 69 70 71 def sort(arr, left, right): 72 if left >= right: # 递归终止条件：被分区区域内只有1个元素了 73 return 74 pivot = partition(arr, left, right) 75 # 递归的进行分区 76 sort(arr, left, pivot - 1) 77 sort(arr, pivot + 1, right) 78 79 80 # 分区，返回基准值的索引 81 def partition(arr, left, right): 82 pivotkey = arr[left] # 选定第一个元素为基准值 83 while left < right: 84 while arr[right] >= pivotkey and right > left: 85 right -= 1 86 arr[left] = arr[right] # 小于基准值的元素放到左边区域：小的往前甩 87 while arr[left] < pivotkey and left < right: 88 left += 1 89 arr[right] = arr[left] # 大于等于基准值的元素放到右边区域：大的往后甩 90 arr[left] = pivotkey 91 return left 92 93 94 arr = [9, 8, 7, 6, 5, 4, 3, 2, 1] 95 # selection_sort(arr) 96 # buble_sort(arr) 97 # insert_sort(arr) 98 # print(merge_sort(arr)) 99 quick_sort(arr) 100 print(arr)
9.二分法查找：search.py
1 def search(l,val): 2 low,high = 0,len(l) - 1 # 查找范围的开始和结束索引位 3 # 循环查找,每次去除一半 4 while low <= high: 5 mid = (low + high) // 2 # 中间数索引 6 if l[mid] < val: 7 low = mid + 1 8 elif l[mid] > val: 9 high = mid - 1 10 else: 11 return mid 12 13 14 l = [1,2,3,4,5,6,7,8,9,10] 15 print("Key index:",search(l,666))