当前位置： 首页 > news >正文

小杰数据结构（five day）——知人者智，自知者明。

news 2025/8/5 6:19:14

1.树

（1）链式存储

链式存储此二叉树，从根结点开始，将各个结点以及其左右子的地址使用链表进行存储。

其左子的结点编号为2*i，

右子编号为2*i+1

设完全二叉树的结点数为n，某结点的编号为i。

当i>1时(不是根结点时)，有父节点，其编号为i//2。

当2*i <= n时，有左子，其编号为2*i，否则没有左子，没左子一定没右子，其本身为叶节点。

当2*i+1 <= n时，有右子，其编号为2*i+1，否则就没有右子。

整体代码：

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 root# 先序遍历——根左右
def pre_order(r):if r is None:return# 根print(r.data, end='')# 左pre_order(r.left)# 右pre_order(r.right)return# 中序遍历——左根右
def 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)
输出：
前序遍历:
123
中序遍历:
213
后序遍历:
231
Process finished with exit code 0

（2）层序遍历（后边都是了解扩展）

队列思想

2.链表

（1）双向链表

概念

  1. 逻辑结构：线性结构
  2. 物理结构：链式存储结构

步骤：

  1. 判错
  2. 创新
  3. 尾插
  4. 中间插
    1. 中间插前半段
    2. 中间插后半段
    3. 无论前半段还是后半段，伪指针指向插入位置post结点后，其插入代码都是一样的

①插入

②打印

遍历双向链表

  1. 从前往后
  2. 从后往前

③删除

整体代码

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 = Noneelse:# 找到要删除的节点的前一个节点和后一个节点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表示链表末尾

（2）双向循环链表

思想和单向循环一样，只需要将双向链表尾的next和头的prior双向链接

解决约瑟夫问题

整体代码：

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.排序算法

（1）冒泡排序

（1）比较第一个数与第二个数，若为逆序a[0]>a[1]，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止——第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上

（2）对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置

（3）重复上述过程，共经过n-1趟冒泡排序后，排序结束

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;
}

（2）选择排序

（1）首先通过n-1次比较，从n个数中找出最小的， 将它与第一个数交换—第一趟选择排序，结果最小的数被安置在第一个元素位置上

（2）再通过n-2次比较，从剩余的n-1个数中找出次小的记录，将它与第二个数交换—第二趟选择排序

（3）重复上述过程，共经过n-1趟排序后，排序结束

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;
}

（3）插值排序

def interpolation_search(arr, target):low = 0high = len(arr) - 1while low <= high and arr[low] <= target <= arr[high]:# 计算插值位置（核心公式）# 类似于根据比例估算位置pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])# 检查找到的位置if arr[pos] == target:return pos# 如果目标值更大，在右半部分查找elif arr[pos] < target:low = pos + 1# 如果目标值更小，在左半部分查找else:high = pos - 1# 特殊情况：检查low位置是否为目标（当数组中只有一个元素时）if low <= high and arr[low] == target:return low# 未找到目标return -1# 测试
if __name__ == "__main__":# 插值查找要求数组是有序的arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]target = 18result = interpolation_search(arr, target)if result != -1:print(f"元素 {target} 找到，索引位置为 {result}")else:print(f"元素 {target} 未在数组中找到")

（4）快速排序

其实就是逐个找到单个数据的位置

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()

http://www.lryc.cn/news/609497.html

相关文章：

  • WPF 按钮背景色渐变
  • 飞算 JavaAI：给需求分析装上 “智能大脑“
  • VPS云服务器Linux性能分析与瓶颈解决方案设计
  • 机器学习 决策树案例电信用户流失
  • 豆包新模型+PromptPilot深度评测：提示词工程的智能化突破
  • Chrontel 【CH7104B-BF】CH7104B HDMI to HDTV/VGA Converter
  • SJW-app-1
  • 力扣热题100——双指针
  • Android GPU测试
  • 豹女篇章-人形态技能加攻速
  • 数据离不开哈希
  • 【Linux | 网络】网络层（IP协议、NAT技术和ICMP协议）
  • 【前端:Html】--1.3.基础语法
  • 【人工智能99问】什么是Post-Training，包含哪些内容？(19/99)
  • 3.JVM，JRE和JDK的关系是什么
  • Linux 系统重置用户密码指南
  • 【09】C++实战篇——C++ 生成静态库.lib 及 C++调用lib，及实际项目中的使用技巧
  • vue3指定设置了dom元素的ref但是为null问题
  • 大模型 与 自驾 具身 3D世界模型等相关知识
  • 华为OD机考2025C卷 - 最小矩阵宽度（Java Python JS C++ C ）
  • vim 组件 使用pysocket进行sock连接
  • 408数据结构排序部分知识的复盘：从原理到辨析的系统化梳理
  • 抗辐照DCDC与MCU在核环境监测设备中的集成应用
  • 远程测控终端RTU:工业物联的“神经末梢”与远程操控核心
  • CVPR论文解析：告别Janus问题，text-to-3D更一致！
  • 5G专网与SD-WAN技术融合：某饮料智能工厂网络架构深度解析
  • Planner 5D v2.29.0 安卓高级解锁版，手机3D家装，全套家具免费
  • 【基于WAF的Web安全测试：绕过Cloudflare/Aliyun防护策略】
  • iOS混淆工具有哪些？功能测试与质量保障兼顾的混淆策略
  • SpringBoot3.x入门到精通系列：3.2 整合 RabbitMQ 详解