1.顺序表：
class Seq:N = 32 # 顺序表的最大容量def __init__(self):self.last = -1 # 顺序表中最后一个有效元素的下标self.data = [0] * Seq.N # 顺序表的数据存储# 2.向顺序表的指定位置插入数据,index第几个位置，data插入的数据def insert(self, index: int, data: int):# 容错判断if self.is_full() or index < 0 or index > self.last + 1:print("insert error")returnfor i in range(self.last, index - 1, -1):self.data[i + 1] = self.data[i]self.data[index] = dataself.last += 1# 3.遍历顺序表sequence 顺序表def show(self):for i in range(self.last + 1):print("buf[%s] = %s" % (i, self.data[i]))# 4.判断顺序表是否为满,满返回true 未满返回falsedef is_full(self):return self.last + 1 == Seq.N# 5.判断顺序表是否为空def is_empty(self):return self.last == -1# 6.删除顺序表中指定位置的数据index删除位置def del_index(self, index: int):if self.is_empty() or index > self.last or index < 0:print("del error")returnfor i in range(index, self.last):self.data[i] = self.data[i + 1]self.last -= 1# 7.清空顺序表def clear(self):self.last = -1# 8.修改指定位置的数据,index被修改的位置，data修改成的数据def change(self, index: int, data: int):if self.is_empty() or index < 0 or index > self.last:print("change error")returnself.data[index] = data# 9.查找指定数据出现的位置def search(self, data: int): # data代表被查找的数据if self.is_empty():print("search error")returnfor i in range(self.last + 1):if self.data[i] == data:return ireturn -1# endifif __name__ == '__main__':seq_list = Seq()seq_list.insert(0, 888)seq_list.insert(1, 777)seq_list.insert(2, 666)seq_list.show()seq_list.insert(0, 999)seq_list.show()seq_list.del_index(0)seq_list.show()seq_list.change(0, 999)seq_list.show()print(seq_list.search(999))
2.链表
单向链表
class Node:"""创建单链表节点"""def __init__(self, data=None, next_node=None):self.data = dataself.next = next_nodeclass LinkedList:def __init__(self):# 初始化一个头节点，它不包含实际数据，仅作为链表的起始标志self.head = Node()# 2.向单向链表的指定位置插入数据# post 插入的位置 data插入的数据def insert(self, position, data):# 容错判断if position < 0 or position > self.length():print("insert error")return# node新节点new_node = Node(data)# 移动伪指针到插入位置的前一个位置current = self.headfor _ in range(position):current = current.next# 插入动作(先连后面，再连前面)new_node.next = current.nextcurrent.next = new_node# 3.遍历单向链表def show(self):current = self.headwhile current.next:current = current.nextprint(current.data, end=' ')print()# 4.求单向链表长度的函数def length(self):current = self.headlength = 0while current.next:current = current.nextlength += 1return length# 5.删除单向链表中指定位置的数据 post 代表的是删除的位置def delete_position(self, position):# 容错判断if self.is_empty() or position < 0 or position >= self.length():print("delete_position error")returncurrent = self.head# current走到删除位置的前一个位置for _ in range(position):current = current.next# 删除动作current.next = current.next.next# 6.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除def delete_data(self, data):if self.is_empty():print("delete_data error")returncurrent = self.headwhile current.next:if current.next.data == data:current.next = current.next.nextelse:current = current.next# 7.判断单向链表是否为空 1代表空 0代表非空def is_empty(self):return self.head.next is None# 8.修改指定位置的数据 post 被修改的位置 data修改成的数据def change_data(self, position, data):# 容错判断if self.is_empty() or position < 0 or position >= self.length():print("change_data error")returncurrent = self.headfor _ in range(position + 1):current = current.nextcurrent.data = data# 9.查找指定数据出现的位置 data被查找的数据 //search 查找def search_data(self, data):if self.is_empty():print("search_data error")returncurrent = self.headposition = 0while current.next:current = current.nextif current.data == data:return positionposition += 1return -1# 10.转置链表def reverse(self):# 断开前，保存头节点的下一个节点的地址current = self.head.next# 断开链表self.head.next = None# 遍历无头单向链表，把无头单向链表的节点头插到有头空链表中while current:# 提前将current的下一个节点保存起来next_node = current.next# 先连后面，再连前面, 将无头表的节点插入头结点的下一个位置current.next = self.head.nextself.head.next = current# 将current移动，指向下一个节点current = next_node# 11.清空单向链表def clear(self):pass# endifif __name__ == '__main__':link_list = LinkedList()link_list.insert(0, 999)link_list.insert(1, 888)link_list.insert(2, 888)link_list.show()link_list.insert(0, 666)link_list.show()link_list.insert(1, 777)link_list.show()link_list.reverse()link_list.show()link_list.delete_position(0)link_list.show()link_list.insert(0, 666)link_list.show()link_list.delete_data(666)link_list.show()link_list.change_data(1,666)link_list.show()print(link_list.search_data(777))
单向循环链表
class Node:"""创建单链表节点"""def __init__(self, data=None):self.data = dataself.next = Nonedef Josepy(self):all_num = 6 # 猴子总数start_num = 1 # 从几号猴子开始数kill_num = 5 # 数到几杀死猴head = Node(1)p_tail = head # 尾指针指向当前的第一个结点for i in range(2, all_num + 1):new_node = Node(i) # 实例化新结点且装上数据p_tail.next = new_node # 链接到链表的尾p_tail = new_node # 尾指针继续指向当前链表的尾p_tail.next = head # 形成单向循环链表# 开始杀猴子# 将头指针移动到开始猴子的号码处for i in range(0, start_num - 1):head = head.next# 循环进行杀猴子while head != head.next:for i in range(0, kill_num - 2):head = head.nextp_del = head.next# 跨过要删除的节点head.next = p_del.nextprint("kill is -------------=", p_del.data)# 杀死猴子后，从下一个节点开始继续开始数, 将头指针移动到开始数的地方head = head.nextprint("king is=================== ", head.data)if __name__ == '__main__':linklist = Node()linklist.Josepy()
双向链表
class Node:def __init__(self, data=None):self.data = data # 数据域self.prior = None # 指向前一个节点的指针self.next = None # 指向下一个节点的指针class DoubleLinkedList:def __init__(self):self.head = Node() # 头节点，作为哑节点（不存储实际数据）self.tail = self.head # 尾指针初始时指向头节点self.len = 0 # 当前链表的长度def insert(self, position, data):# 容错判断if position < 0 or position > self.len:print("插入位置无效！")return -1# 创建一个新的节点new_node = Node(data)# 将节点链接到链表中if position == self.len: # 插入到链表尾部self.tail.next = new_nodenew_node.prior = self.tailself.tail = new_node # 更新尾指针else: # 插入到链表中间或头部if position < self.len // 2: # 插入位置在前半部分，从头向后遍历current = self.headfor _ in range(position + 1):current = current.nextelse: # 插入位置在后半部分，从尾向前遍历current = self.tailfor _ in range(self.len - position - 1):current = current.prior# 进行插入操作（先连前面，再连后面）new_node.prior = current.priorcurrent.prior.next = new_nodenew_node.next = currentcurrent.prior = new_nodeself.len += 1 # 链表长度加1return 0# 删除双向链表指定位置的数据
def delete(self, position):# 容错处理if position < 0 or position >= self.len:print("删除位置无效！")return -1# 2.对删除位置进行分析，分为两种情况# 如果删除的是链表最后一个节点if position == self.len - 1:# 将尾指针向前移动一个位置self.tail = self.tail.priorself.tail.next = None else:# 找到要删除的节点的前一个节点和后一个节点if position < self.len // 2: # 如果位置在前半部分，从头向后遍历current = self.headfor _ in range(position + 1):current = current.nextelse: # 如果位置在后半部分，从尾向前遍历current = self.tailfor _ in range(self.len - position - 1):current = current.prior# 断开链接并进行删除操作（在Python中，这会导致被删除节点被垃圾回收）current.prior.next = current.nextcurrent.next.prior = current.prior# 双向链表的长度减1self.len -= 1return 0# 判断双向链表是否为空def is_empty(self):return self.len == 0# 求双向链表的长度def length(self):return self.len# 测试代码
if __name__ == "__main__":dll = DoubleLinkedList()dll.insert(0, 10) # 在位置0插入数据10dll.insert(1, 20) # 在位置1插入数据20dll.insert(1, 15) # 在位置1插入数据15（应该在20之前）dll.insert(3, 30) # 在位置3插入数据30# 打印链表内容（从头节点后的第一个节点开始，直到尾节点前的最后一个节点）current = dll.head.nextwhile current != dll.tail.next:print(current.data, end=" -> ")current = current.nextprint("None") # 用None表示链表末尾
双向循环链表
class Node:def __init__(self, data):self.data = data # 节点数据self.prior = None # 指向前一个节点的指针self.next = None # 指向下一个节点的指针class DoubleLinkedList:def __init__(self):self.head = None # 链表头指针self.tail = None # 链表尾指针def append(self, data):# 在链表末尾添加新节点new_node = Node(data)if not self.head:# 如果链表为空，则新节点既是头节点也是尾节点self.head = self.tail = new_nodeelse:# 否则，将新节点添加到链表末尾self.tail.next = new_nodenew_node.prior = self.tailself.tail = new_nodedef make_circular(self):# 使链表形成循环if self.head and self.tail:self.tail.next = self.headself.head.prior = self.taildef josephus_problem(self, all_num, start_num, kill_num):# 解决约瑟夫问题# 填充循环双向链表for i in range(1, all_num + 1):self.append(i)self.make_circular()# 移动到起始位置current = self.headfor _ in range(start_num - 1):current = current.next# 解决约瑟夫问题while current.next != current: # 当链表中不止一个节点时# 移动到要删除的节点for _ in range(kill_num - 1):current = current.next# 删除当前节点print(f"杀死的是 ------- {current.data}")if current.prior:current.prior.next = current.nextif current.next:current.next.prior = current.prior# 移动到删除节点后的下一个节点current = current.next# 打印最后剩下的节点（猴王）print(f"猴王是 {current.data}")# 主函数
if __name__ == "__main__":dll = DoubleLinkedList() # 创建双向链表实例all_num = int(input("请您输入猴子的总数: ")) # 输入猴子总数start_num = int(input("从几号猴子开始数: ")) # 输入开始数数的猴子号码kill_num = int(input("数到几杀死猴子: ")) # 输入数到几杀死猴子的号码dll.josephus_problem(all_num, start_num, kill_num) # 解决约瑟夫问题
3.栈
顺序栈
class Stack:max_len = 32 # 保存栈的最大长度# 始终代表当前栈内最后一个有效元素的下标，称为栈顶指针top = -1data = [0] * max_len # 顺序栈的存储空间# 1、判断是否为满, 满返回True,未满返回Falsedef is_full(self):return self.top + 1 == self.max_len# 2. 入栈def push(self, data: int): # data代表入栈的数据if self.is_full():print("push error")returnself.top += 1self.data[self.top] = data# 3.判断栈是否为空def is_empty(self):return self.top == -1# 4.出栈def pop(self):if self.is_empty():print("pop error")returnself.top -= 1return self.data[self.top + 1]# 5. 清空栈def clear(self):self.top = -1# 6.获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)def get_top(self):if self.is_empty():print("get_top error")returnreturn self.data[self.top]# 7. 求栈的有限长度def get_length(self):return self.top + 1if __name__ == '__main__':seq_stack = Stack()for i in range(6):seq_stack.push(i)print("top_data",seq_stack.get_top())print("stack_len",seq_stack.get_length())for _ in range(6):print(seq_stack.pop())
链式栈
class Node:"""链式栈节点类"""def __init__(self, data):self.data = dataself.next = Noneclass LinkStack:def __init__(self):self.top = None# 2.入栈,data是入栈的数据def push(self, data):new_node = Node(data)new_node.next = self.topself.top = new_node# 3.判断栈是否为空def is_empty(self):return self.top is None# 4.出栈def pop(self):if self.is_empty():print("pop error")returndata = self.top.dataself.top = self.top.nextreturn data# 5.清空栈def clear(self):self.top = None# 6.求栈的长度def length(self):current = self.toplength = 0while current:length += 1current = current.nextreturn length# 7.获取栈顶数据,不是出栈,不需要移动topdef get_top(self):if self.is_empty():print("get_top error")returnreturn self.top.dataif __name__ == '__main__':link_stack = LinkStack()for i in range(6):link_stack.push(i)print("top_data",link_stack.get_top())print("stack_length",link_stack.length())for _ in range(6):print("data", link_stack.pop())
4.队列
顺序队列（循环队列）
class SeqQueue:def __init__(self, max_len=5):self.max_len = max_len # 队列的最大长度self.rear = 0 # 入队端self.front = 0 # 出队端self.data = [0] * max_len # 队列的存储空间# 2.入列 data代表入列的数据def enqueue(self, data):if self.is_full():print("enqueue error")returnself.data[self.rear] = dataself.rear = (self.rear + 1) % self.max_len# 3.判断队列是否为满def is_full(self):return (self.rear + 1) % self.max_len == self.front# 4.判断队列是否为空def is_empty(self):return self.rear == self.front# 5.出列def dequeue(self):if self.is_empty():print("dequeue error")returndata = self.data[self.front]self.front = (self.front + 1) % self.max_lenreturn data# 6.求队列有效的长度def length(self):if self.rear >= self.front:return self.rear - self.frontelse:return self.rear - self.front + self.max_len# 7.清空队列函数def clear(self):self.front = self.rear = 0if __name__ == '__main__':seq_queue = SeqQueue()for i in range(4):seq_queue.enqueue(i)print("queue_len",seq_queue.length())for i in range(4):print("queue_data:%s" % seq_queue.dequeue())
链式队列
# 1、定义链式队列节点
class Node:def __init__(self, value):self.data = value # 数据域self.next = None # 指针域# 定义队列函数
class LinkQueue:# 队列初始化def __init__(self):self.front = Node(None) # 相当于队列的头指针self.rear = self.front # 相当于队列的尾指针# 2、判断队列是否为空def is_empty(self):return self.front.next is None# 3、元素入队def InLinkQueue(self, data):new_node = Node(data)# 将新节点连接到队尾self.rear.next = new_node# 队尾指针指向新的队尾节点self.rear = new_node# 4、队列元素出队def OutLinkQueue(self):if self.is_empty():# print("OutLinkQueue error")return "error"'''# 方法一：头节点不动，剩最后一个节点时需将尾结点回到队头，以防下一次入队且正常出队del_queue = self.front.nextif self.front.next == self.rear:self.rear = self.front# 跨越删除self.front.next = del_queue.nextreturn del_queue.data'''# 方法二：data = self.front.next.dataself.front = self.front.nextreturn data# 5、获取队首元素def Get_top(self):if self.is_empty():return "Get_top error"return self.front.next.data# 6、遍历队列def display(self):if self.is_empty():print("display error")returncurrent = self.frontwhile current.next:current = current.nextprint(current.data)# 7、清空队列def ClearLinkQueue(self):while not self.is_empty():self.OutLinkQueue()# 8、返回队列长度def LengthLinkQueue(self):current = self.frontlength = 0while current.next:current = current.nextlength += 1return lengthif __name__ == '__main__':link_queue = LinkQueue()for i in range(6):link_queue.InLinkQueue(i)print("queue_topdata=",link_queue.Get_top())print("queue_len=",link_queue.LengthLinkQueue())for _ in range(6):print("queue_data", link_queue.OutLinkQueue())
5.树
二叉树
class TreeNode:def __init__(self, data=None, left=None, right=None):self.data = dataself.left = leftself.right = rightdef create_bitree(n, i): # n = 3root = TreeNode(i)if 2 * i <= n:root.left = create_bitree(n, 2 * i)else:root.left = Noneif 2 * i + 1 <= n:root.right = create_bitree(n, 2 * i + 1)else:root.right = Nonereturn rootdef pre_order(r):if r is None:return# 根print(r.data, end='')# 左pre_order(r.left)# 右pre_order(r.right)returndef in_order(r):if r is None:return# 左in_order(r.left)# 根print(r.data, end='')# 右in_order(r.right)def post_order(r):if r is None:return# 左post_order(r.left)# 右post_order(r.right)# 根print(r.data, end='')n = 3 # 树的节点(编号从1号开始)root = create_bitree(n, 1)
print("前序遍历:")
pre_order(root)
print("\n中序遍历:")
in_order(root)
print("\n后序遍历:")
post_order(root)
层序遍历（往后为了解）
class TreeNode:"""树节点定义"""def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef level_order_with_queue(root):"""基于队列思想实现二叉树的层序遍历"""if not root:return []# 初始化队列并加入根节点queue = [root]result = []# 队列不为空时持续处理while queue:# 当前层的节点数量level_size = len(queue)current_level = []# 处理当前层的所有节点for _ in range(level_size):# 出队操作（取队列头部元素）node = queue.pop(0) # 队列特性：先进先出current_level.append(node.val)# 将子节点入队（为下一层做准备）if node.left:queue.append(node.left) # 左子节点先入队if node.right:queue.append(node.right) # 右子节点后入队result.append(current_level)return result# 测试代码
if __name__ == "__main__":# 构建示例二叉树# 1# / \# 2 3# / \ \# 4 5 6root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.right.right = TreeNode(6)# 执行层序遍历traversal = level_order_with_queue(root)print("层序遍历结果:", traversal) # 输出: [[1], [2, 3], [4, 5, 6]]
import que
import qqqclass TreeNode:def __init__(self, data=None, left=None, right=None):self.data = dataself.left = leftself.right = rightdef create_bitree(n, i):root = TreeNode(i)if 2 * i <= n:root.left = create_bitree(n, 2 * i)else:root.left = Noneif 2 * i + 1 <= n:root.right = create_bitree(n, 2 * i + 1)else:root.right = Nonereturn root# 创建实例对象
link_queue = que.LinkQueue()
def Link_struct_order(root):link_queue.InLinkQueue(root)while not link_queue.is_empty():q = link_queue.OutLinkQueue()print(q.data,end=' ')if q.left:link_queue.InLinkQueue(q.left)if q.right:link_queue.InLinkQueue(q.right)# seq_queue = qqq.SeqQueue()
# # def Seq_struct_order(root):
# # seq_queue.enqueue(root)
# # while not seq_queue.is_empty():
# # q = seq_queue.dequeue()
# # print(q.data,end=' ')
# # if q.left:
# # seq_queue.enqueue(q.left)
# # if q.right:
# # seq_queue.enqueue(q.right)r = create_bitree(6, 1)
Link_struct_order(r)
print()
# Seq_struct_order(r)
6.排序算法
冒泡排序
def bubble_sort(arr):N = len(arr)for i in range(N - 1):for j in range(N - 1 - i):if arr[j] > arr[j + 1]:# 交换元素temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = tempdef main():N = 7a = [0] * N # 初始化数组为0print("Please input array (int a[7]): ")# 从标准输入读取7个整数a = list(map(int, input().split()))[:N] # 确保只获取前7个输入# 调用冒泡排序函数bubble_sort(a)# 打印排序后的数组for i in range(N):print(f"{a[i]:\t}", end="")print() # 换行if __name__ == "__main__":main()C语言：
#include<stdio.h>
#define N 10
int main(int argc, const char *argv[])
{int st[N],i,j,temp;for(i = 0; i < N; i++){scanf("%d",&st[i]);}for(i = 0; i < N - 1; i++){for(j = 0; j < N - 1 - i; j++){if(st[j] > st[j + 1]) {temp = st[j];st[j] = st[j + 1];st[j + 1] = temp;}}}for(i = 0; i < N; i++){printf("%d\n",st[i]);}return 0;
}
选择排序
def exchange(arr, i, k):# 交换数组arr中索引为i和k的元素arr[i], arr[k] = arr[k], arr[i]def selection_sort(arr):N = len(arr)for i in range(N - 1):# 假设当前元素i是最小的k = i# 在剩余未排序部分中寻找最小值for j in range(i + 1, N):if arr[j] < arr[k]:k = j# 如果找到的最小值不是当前元素i，则交换它们if i != k:exchange(arr, i, k)def main():# 初始化一个长度为7的数组，这里使用随机数填充import randoma = [random.randint(0, 100) for _ in range(7)]print("原始数组:")print(a)# 调用选择排序函数selection_sort(a)print("排序后的数组:")print(a)if __name__ == "__main__":main()C语言：
#include<stdio.h>
#define N 5
int main(int argc, const char *argv[])
{int st[N] = {0};int i,j,temp,k;for(i = 0; i < N; i++){scanf("%d",&st[i]);}for(i = 0; i < N - 1; i++){ k = i;//开始的时候假设最小的元素的下标为i，对第一趟，开始假设的最小元素为第一个元素.for(j = i+1; j < N; j++){if(st[k] > st[j])//从一组数据里面找最小的，方法：先假设一个最小的k = j;}if(k != i){temp = st[i];st[i] = st[k];st[k] = temp;}}for(i = 0; i < N; i++){printf("%d\n",st[i]);}return 0;
}
插值排序
python：
def insertion_sort(arr):# 遍历从1开始的所有元素for i in range(1, len(arr)):key = arr[i] # 当前要插入的元素j = i - 1 # 已排序部分的最后一个元素索引# 将大于key的元素向后移动while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1# 插入key到正确位置arr[j + 1] = keyreturn arr# 测试示例
if __name__ == "__main__":test_array = [12, 11, 13, 5, 6]print("排序前的数组:", test_array)sorted_array = insertion_sort(test_array)print("排序后的数组:", sorted_array)
c语言：
#include <stdio.h>// 插入排序函数
void insertionSort(int arr[], int n) {int i, key, j;// 遍历从1开始的所有元素for (i = 1; i < n; i++) {key = arr[i]; // 当前要插入的元素j = i - 1; // 已排序部分的最后一个元素索引// 将大于key的元素向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}// 插入key到正确位置arr[j + 1] = key;}
}// 打印数组函数
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数测试
int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组: ");printArray(arr, n);insertionSort(arr, n);printf("排序后的数组: ");printArray(arr, n);return 0;
}
快速排序
def get_pivot(arr, low, high):pivot = arr[low] # 选择第一个元素作为枢轴left = lowright = highwhile left <= right:# 从右向左扫描while arr[right] >= pivot and left <= right:right -= 1if left <= right:arr[left] = arr[right] # 将小于枢轴的元素移动到左边left += 1# 从左向右扫描while arr[left] <= pivot and left <= right:left += 1if left <= right:arr[right] = arr[left] # 将大于枢轴的元素移动到右边right -= 1# 将枢轴放置到正确的位置arr[left] = pivotreturn left # 返回枢轴的位置def show_array(arr):print(" ".join(map(str, arr)))print()def quick_sort(arr, low, high):if low < high:pivot_index = get_pivot(arr, low, high)quick_sort(arr, low, pivot_index - 1) # 递归排序枢轴左侧quick_sort(arr, pivot_index + 1, high) # 递归排序枢轴右侧def main():# 初始化数组arr = [32, 2, 54, 6, 78, 23, 17, 76]print("快速排序之前:")show_array(arr)quick_sort(arr, 0, len(arr) - 1)print("快速排序之后:")show_array(arr)if __name__ == "__main__":main()
