1、封装一套数据结构和算法，包含：顺序表、单链表、顺序栈、循 环队列、二叉树的二叉链表、图的邻接矩阵或邻接表、基本排序算法（直接插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序至少任选3个）

以下是一套数据结构和算法的实现，包含顺序表、单链表、顺序栈、循环队列、二叉树的二叉链表、图的邻接矩阵和邻接表、基本排序算法（直接插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序）： ```python # 顺序表 class SeqList: def __init__(self, maxsize=None): self.maxsize = maxsize self._items = [None] * self.maxsize self.length = 0 def __getitem__(self, index): if index < self.length: return self._items[index] else: raise IndexError('Index out of range') def __setitem__(self, index, value): if index < self.length: self._items[index] = value else: raise IndexError('Index out of range') def __len__(self): return self.length def __repr__(self): return str(self._items[:self.length]) def insert(self, index, value): if self.length >= self.maxsize: raise Exception('Full') if index < 0: index += self.length if index < 0: index = 0 if index > self.length: index = self.length for i in range(self.length-1, index-1, -1): self._items[i+1] = self._items[i] self._items[index] = value self.length += 1 def delete(self, index): if self.length == 0: raise Exception('Empty') if index < 0: index += self.length if index < 0 or index >= self.length: raise IndexError('Index out of range') for i in range(index, self.length-1): self._items[i] = self._items[i+1] self.length -= 1 # 单链表 class Node: def __init__(self, value=None, next=None): self.value = value self.next = next class LinkedList: def __init__(self): self.head = Node() self.length = 0 def __len__(self): return self.length def __repr__(self): values = [] current_node = self.head.next while current_node: values.append(current_node.value) current_node = current_node.next return '->'.join(str(value) for value in values) def insert(self, index, value): if index < 0: index += self.length if index < 0: index = 0 if index > self.length: index = self.length prev_node = self.head for i in range(index): prev_node = prev_node.next new_node = Node(value) new_node.next = prev_node.next prev_node.next = new_node self.length += 1 def delete(self, index): if index < 0: index += self.length if index < 0 or index >= self.length: raise IndexError('Index out of range') prev_node = self.head for i in range(index): prev_node = prev_node.next current_node = prev_node.next prev_node.next = current_node.next self.length -= 1 # 顺序栈 class SeqStack: def __init__(self, maxsize=None): self.maxsize = maxsize self._items = [None] * self.maxsize self.top = -1 def __len__(self): return self.top + 1 def __repr__(self): return str(self._items[:self.top+1]) def push(self, value): if self.top == self.maxsize - 1: raise Exception('Full') self.top += 1 self._items[self.top] = value def pop(self): if self.top == -1: raise Exception('Empty') value = self._items[self.top] self.top -= 1 return value # 循环队列 class CircularQueue: def __init__(self, maxsize): self.maxsize = maxsize self._items = [None] * self.maxsize self.head = 0 self.tail = 0 def __len__(self): return (self.tail - self.head + self.maxsize) % self.maxsize def __repr__(self): if self.tail >= self.head: return str(self._items[self.head:self.tail]) else: return str(self._items[self.head:] + self._items[:self.tail]) def push(self, value): if (self.tail + 1) % self.maxsize == self.head: raise Exception('Full') self._items[self.tail] = value self.tail = (self.tail + 1) % self.maxsize def pop(self): if self.tail == self.head: raise Exception('Empty') value = self._items[self.head] self.head = (self.head + 1) % self.maxsize return value # 二叉树的二叉链表 class BinTNode: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right class BinTree: def __init__(self): self._root = None def is_empty(self): return self._root is None def root(self): return self._root def leftchild(self, node): return node.left def rightchild(self, node): return node.right def set_root(self, rootnode): self._root = rootnode def set_left(self, node, leftchild): node.left = leftchild def set_right(self, node, rightchild): node.right = rightchild def preorder_elements(self, node): if node is not None: yield node.data yield from self.preorder_elements(node.left) yield from self.preorder_elements(node.right) def inorder_elements(self, node): if node is not None: yield from self.inorder_elements(node.left) yield node.data yield from self.inorder_elements(node.right) def postorder_elements(self, node): if node is not None: yield from self.postorder_elements(node.left) yield from self.postorder_elements(node.right) yield node.data # 图的邻接矩阵 class Graph: def __init__(self, mat, unconn=0): vnum = len(mat) for x in mat: if len(x) != vnum: raise ValueError('Argument for Graph') self._mat = [mat[i][:] for i in range(vnum)] self._unconn = unconn self._vnum = vnum def vertex_num(self): return self._vnum def _invalid(self, v): return 0 > v or v >= self._vnum def add_vertex(self): raise ValueError('Adj-Matrix does not support "add_vertex"') def add_edge(self, vi, vj, val=1): if self._invalid(vi) or self._invalid(vj): raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.') self._mat[vi][vj] = val def get_edge(self, vi, vj): if self._invalid(vi) or self._invalid(vj): raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.') return self._mat[vi][vj] def out_edges(self, vi): if self._invalid(vi): raise ValueError(str(vi) + ' is not a valid vertex.') return self._out_edges(self._mat[vi], self._unconn) @staticmethod def _out_edges(row, unconn): edges = [] for i in range(len(row)): if row[i] != unconn: edges.append((i, row[i])) return edges # 图的邻接表 class GraphAL(Graph): def __init__(self, mat=[], unconn=0): vnum = len(mat) for x in mat: if len(x) != vnum: raise ValueError('Argument for Graph') self._mat = [Graph._out_edges(mat[i], unconn) for i in range(vnum)] self._vnum = vnum self._unconn = unconn def add_vertex(self): self._mat.append([]) self._vnum += 1 return self._vnum - 1 def add_edge(self, vi, vj, val=1): if self._vnum == 0: raise ValueError('Cannot add edge to empty graph.') if self._invalid(vi) or self._invalid(vj): raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.') row = self._mat[vi] i = 0 while i < len(row): if row[i][0] == vj: self._mat[vi][i] = (vj, val) return if row[i][0] > vj: break i += 1 self._mat[vi].insert(i, (vj, val)) def get_edge(self, vi, vj): if self._invalid(vi) or self._invalid(vj): raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.') for i, val in self._mat[vi]: if i == vj: return val return self._unconn def out_edges(self, vi): if self._invalid(vi): raise ValueError(str(vi) + ' is not a valid vertex.') return self._mat[vi] # 直接插入排序 def insert_sort(lst): n = len(lst) for i in range(1, n): value = lst[i] j = i - 1 while j >= 0 and lst[j] > value: lst[j+1] = lst[j] j -= 1 lst[j+1] = value # 希尔排序 def shell_sort(lst): n = len(lst) gap = n // 2 while gap > 0: for i in range(gap, n): value = lst[i] j = i - gap while j >= 0 and lst[j] > value: lst[j+gap] = lst[j] j -= gap lst[j+gap] = value gap //= 2 # 简单选择排序 def select_sort(lst): n = len(lst) for i in range(n-1): min_index = i for j in range(i+1, n): if lst[j] < lst[min_index]: min_index = j if min_index != i: lst[i], lst[min_index] = lst[min_index], lst[i] # 快速排序 def quick_sort(lst): if len(lst) <= 1: return lst pivot = lst[0] left = [x for x in lst[1:] if x < pivot] right = [x for x in lst[1:] if x >= pivot] return quick_sort(left) + [pivot] + quick_sort(right) # 堆排序 def heap_sort(lst): def sift_down(start, end): root = start while True: child = 2 * root + 1 if child > end: break if child + 1 <= end and lst[child] < lst[child+1]: child += 1 if lst[root] < lst[child]: lst[root], lst[child] = lst[child], lst[root] root = child else: break for start in range((len(lst)-2)//2, -1, -1): sift_down(start,