Python数据结构与算法全解：双向链表、六大排序算法与图遍历实现

发布于：2025-03-20 ⋅ 阅读:(26) ⋅ 点赞:(0)

目录

前言

书接上文

深入解析二叉树：从存储结构到遍历算法的Python实现全解-CSDN博客文章浏览阅读1.1k次，点赞22次，收藏13次。本文系统讲解二叉树的逻辑与物理结构，详解完全二叉树与满二叉树的数学特性，对比顺序存储与链式存储的实现差异，提供基于递归的完全二叉树生成算法及前序、中序、后序遍历的Python代码实现，通过n=3的实例演示树结构构建与遍历过程，揭示二叉树在数据组织与算法设计中的核心应用价值。 https://blog.csdn.net/qq_58364361/article/details/146334348?fromshare=blogdetail&sharetype=blogdetail&sharerId=146334348&sharerefer=PC&sharesource=qq_58364361&sharefrom=from_link

一、双向链表

单向链表

有头

无头

单向循环链表

链式栈 （无头单向链表）

链式队列（有头单向链表）

以上链表均只能从头往后找。即结点只有数据域和一个指向后继结点的指针域next。

双向链表即可以从前往后或者从后往前找，这就意味着链表的结点就不能只有一个指针域next了，还需要一个指向前驱结点的指针域prior。

1.1 概念

逻辑结构：线性结构

物理结构：链式存储结构

class Node:
    def __init__(self):
        self.prior = None  # 指向前一个节点的指针
        self.next = None  # 指向下一个节点的指针
        self.data = None  # 数据域（在这个空链表的例子中，数据域未被使用）
 
class DoubleLinkedList:
    def __init__(self):
        self.head = Node()  # 头节点，初始化时不存储实际数据
        self.tail = self.head  # 尾指针初始时指向头节点，因为链表为空
        self.len = 0  # 当前链表的长度

1.2 插入

					new_node
					  |
        post前驱====新结点====post结点
		   |				    |
	  current->prior		   	  current

中间插口诀

先前再后

current->prior按兵不动

或

先新再旧

current->prior按兵不动

步骤：

1.判错

2.创新

3.尾插

4.中间插

        a.中间插前半段

        b.中间插后半段

        c.无论前半段还是后半段，伪指针指向插入位置post结点后，其插入代码都是一样的

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_node
            new_node.prior = self.tail
            self.tail = new_node  # 更新尾指针
        else:  # 插入到链表中间或头部
            if position < self.len // 2:  # 插入位置在前半部分，从头向后遍历
                current = self.head
                for _ in range(position + 1):
                    current = current.next
            else:  # 插入位置在后半部分，从尾向前遍历
                current = self.tail
                for _ in range(self.len - position - 1):
                    current = current.prior

            # 进行插入操作（先连前面，再连后面）
            new_node.prior = current.prior
            current.prior.next = new_node
            new_node.next = current
            current.prior = new_node

        self.len += 1  # 链表长度加1
        return 0


# 测试代码
if __name__ == "__main__":
    dll = DoubleLinkedList()
    dll.insert(0, 10)  # 在位置0插入数据10
    dll.insert(1, 20)  # 在位置1插入数据20
    dll.insert(1, 15)  # 在位置1插入数据15（应该在20之前）
    dll.insert(3, 30)  # 在位置3插入数据30

    # 打印链表内容（从头节点后的第一个节点开始，直到尾节点前的最后一个节点）
    current = dll.head.next
    while current != dll.tail.next:
        print(current.data, end=" -> ")
        current = current.next
    print("None")  # 用None表示链表末尾

1.3 打印

遍历双向链表

从前往后

从后往前

  # 打印链表内容（从头节点后的第一个节点开始，直到尾节点前的最后一个节点）
    current = dll.head.next
    while current != dll.tail.next:
        print(current.data, end=" -> ")
        current = current.next
    print("None")  # 用None表示链表末尾

1.4 删除 

# 删除双向链表指定位置的数据
def delete(self, position):
    # 容错处理
    if position < 0 or position >= self.len:
        print("删除位置无效！")
        return -1
    # 2.对删除位置进行分析，分为两种情况
    # 如果删除的是链表最后一个节点
        if position == self.len - 1:
            # 将尾指针向前移动一个位置
            self.tail = self.tail.prior
            self.tail.next = None        
        else:
            # 找到要删除的节点的前一个节点和后一个节点
            if position < self.len // 2:  # 如果位置在前半部分，从头向后遍历
                current = self.head
                for _ in range(position + 1):
                    current = current.next
            else:  # 如果位置在后半部分，从尾向前遍历
                current = self.tail
                for _ in range(self.len - position - 1):
                    current = current.prior

            # 断开链接并进行删除操作（在Python中，这会导致被删除节点被垃圾回收）
            current.prior.next = current.next
            current.next.prior = current.prior
 # 双向链表的长度减1
        self.len -= 1
        return 0

    # 判断双向链表是否为空
    def is_empty(self):
        return self.len == 0

    # 求双向链表的长度
    def length(self):
        return self.len

二、双向循环列表

思想和单向循环一样，只需要将双向链表尾的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_node
        else:
            # 否则，将新节点添加到链表末尾
            self.tail.next = new_node
            new_node.prior = self.tail
            self.tail = new_node

    def make_circular(self):
        # 使链表形成循环
        if self.head and self.tail:
            self.tail.next = self.head
            self.head.prior = self.tail

    def 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.head
        for _ 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.next
            if 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 冒泡排序

冒泡排序动画演示_哔哩哔哩_bilibili

从终端输入7个数排序好输出

（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] = temp

def main():
    N = 7
    a = [0] * N  # 初始化数组为0
    print("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;
}

3.2 选择排序

选择排序动画演示_哔哩哔哩_bilibili经典排序算法选择排序动画演示视频制作工具 https://github.com/3b1b/manim制作视频的代码你可以在这个仓库里面找到 https://github.com/jimowushuang/manim, 视频播放量 38264、弹幕量 52、点赞数 495、投硬币枚数 157、收藏人数 613、转发人数 357, 视频作者 季末梧霜, 作者简介 ，相关视频：插入排序动画演示，冒泡排序动画演示，快速排序动画演示，冒泡排序动画演示，灰常基础，灰常简单，两分钟认识插入排序，堆排序动画演示，三分钟搞定选择排序（图解+动画演示），算法讲解004【入门】选择、冒泡、插入排序，五分钟认识堆排序，秒懂算法4-选择排序https://www.bilibili.com/video/BV1qS4y1w7jM?share_source=copy_web

从终端输入7个数排序好输出

（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 random
    a = [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.3 差值操作

3.3.1 计数排序（Counting Sort）

核心思想：通过计算元素的最大值与最小值的差值，确定元素的范围，构建一个“计数数组”来统计每个元素出现的次数，最终实现线性时间复杂度的排序。

def counting_sort(arr):
    if not arr:
        return []
    
    # 计算最大值和最小值，确定范围（差值）
    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1
    
    # 初始化计数数组
    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1  # 差值操作：将元素映射到计数数组的索引
    
    # 生成排序后的结果
    sorted_arr = []
    for i in range(range_size):
        sorted_arr.extend([i + min_val] * count[i])
    
    return sorted_arr

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))  # 输出: [1, 2, 2, 3, 3, 4, 8]

差值操作的作用：

  • 将元素 num 减去最小值 min_val，确保负数或范围较大的元素也能映射到计数数组的有效索引位置。
  • 通过差值操作压缩数据范围，节省内存空间。

3.3.2 桶排序（Bucket Sort）

核心思想：将元素按范围（差值）分配到不同的“桶”中，每个桶单独排序，最后合并结果。适用于元素均匀分布的场景。

def bucket_sort(arr, bucket_size=5):
    if not arr:
        return []
    
    min_val = min(arr)
    max_val = max(arr)
    
    # 计算需要的桶数量（根据差值分配）
    num_buckets = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(num_buckets)]
    
    # 将元素分配到桶中
    for num in arr:
        index = (num - min_val) // bucket_size  # 差值操作：确定桶的索引
        buckets[index].append(num)
    
    # 对每个桶排序并合并
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))  # 使用 Python 内置排序
    
    return sorted_arr

# 示例
arr = [0.42, 0.32, 0.99, 0.12, 0.55, 0.73]
print(bucket_sort(arr))  # 输出: [0.12, 0.32, 0.42, 0.55, 0.73, 0.99]

差值操作的作用：

  • 通过 (num - min_val) // bucket_size 将元素按范围分配到不同的桶中。

3.3.3 基数排序（Radix Sort）

核心思想：按元素的“位”或“字符”的差值逐位排序（如个位、十位、百位），通过多次分配和收集完成排序。

def radix_sort(arr):
    max_val = max(arr)
    exp = 1  # 从个位开始
    
    while max_val // exp > 0:
        # 初始化 10 个桶（0-9）
        buckets = [[] for _ in range(10)]
        
        # 按当前位分配到桶中
        for num in arr:
            digit = (num // exp) % 10  # 差值操作：提取当前位的值
            buckets[digit].append(num)
        
        # 合并桶中的元素
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
        
        exp *= 10  # 处理更高位
    
    return arr

# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(arr))  # 输出: [2, 24, 45, 66, 75, 90, 170, 802]

差值操作的作用：

  • 通过 (num // exp) % 10 提取当前位的值，实现按位排序。

3.3.4 快速排序

四、图

4.1 概念

图（Graph）是一种非线性数据结构。

4.2 术语

有向图和无向图

网: 弧边上有权值，带权值得图成为网

顶点的度

路径：路径上边的条数定义为该路径的长度

4.3 特征

任意的两个元素都可能相关，即图中任一元素可以有若干个直接前驱和直接后继，属于网状结构类型。

4.4 存储结构

4.4.1 邻接矩阵(数组)

#include <stdio.h>
#include <string.h>

#define N 5

typedef struct
{
	int V[N];
	int R[N][N];
}adjmatrix_t;

int main(int argc, const char *argv[])
{
	adjmatrix_t graph;
	int i,j;
	// 1.初始顶点集合
	for(i = 0; i < N; i++)
		graph.V[i] = i;
	
	// 2.将关系集合清空置0，然后输入顶点之间的关系
	bzero(graph.R,sizeof(graph.R));
	
	printf("请您输入顶点关系:\n");
	while(scanf("(V%d,V%d) ",&i,&j) == 2)//scanf函数，如果输入i j两个值成功，返回值为 2代表输入成功有两个，如果不成功为EOF
	{
		graph.R[i][j] = 1;//vi --> vj
		graph.R[j][i] = 1;//vj --> vi 如何将此行代码注销，可用表示有向图
	}
	
	// 3.打印图
	for(i = 0; i < N; i++)
	{
		printf("V%d:",graph.V[i]);
		for(j = 0; j < N; j++)
		{
			if(graph.R[i][j] == 1)// == 1说明vi ---> vj
			{
				printf("V%d ",graph.V[j]);//将Vi 所有能到达的顶点Vj打印
			}
		}
		printf("\n");
	}

	return 0;
}

 4.4.2 邻接表(链表)

int u;
//这段代码实现将v顶点所有能到达顶点全部找一遍
u = firstAdj(g,v); //u此时为第一个邻接点
while(u != -1)
{
	u = nextAdj(g,v,u);//每循环一次，就向下再继续找下一个邻接点
	//知道u == -1 说明已经没有v能到达的点了
}

4.5 遍历 

4.5.1 深度优先搜索

// 深度搜索 visited 拜访，访问 v 代表的是从哪个顶点开始深度搜索
//visited是一个指向整型数组的指针，用来标记这个顶点是否被访问
void DFS(adjmatrix_t *g, int v, int *visited)
{//visited[v] == 0代表没被访问， 1代表被访问

	int u;//用来保存邻接点
	if(visited[v] == 0)//说明该顶点没有被访问
	{
		printf("V%d ",g->V[v]);//相当于已经被访问了
		visited[v] = 1;//将标志位置1，变为已经被访问,已经被打印输出
	}
	//获取v的第一个邻接点
	u = firstAdj(g,v);
	while(u != -1)//如果u == -1代表,没有邻接点
	{
		if(visited[u] == 0)//没有被访问
		{
			DFS(g,u,visited);
		}
		u = nextAdj(g,v,u);//获取下一个邻接点
	}
}

4.5.2 广度优先搜索 

// 广度搜索
void BFS(adjmatrix_t *g, int v, int *visited)
{
	int u;
	//创建一个队列
	linkqueue_t *p = createEmptyLinkQueue();
	inLinkQueue(p,v);
	while(!isEmptyLinkQueue(p))
	{
		v = outLinkQueue(p);
		if(visited[v] == 0)//说明v未被访问
		{
			printf("V%d ",g->V[v]);
			visited[v] = 1;//打印之后标记为已经访问
		}
		//开始遍历v所有能达到的顶点
		u = firstAdj(g,v);
		while(u != -1)
		{
			if(visited[u] == 0)//v到达的顶点没有被访问
			{
				inLinkQueue(p,u);
			}
			u = nextAdj(g,v,u);//在上面入列的u基础上，在找到下一个邻接点返回
		}
	}
}
from collections import deque

class Graph:
    def __init__(self, n_vertices):
        self.n = n_vertices
        self.adj_matrix = [[0] * n_vertices for _ in range(n_vertices)]
    
    def add_edge(self, i, j):
        """ 添加无向边 """
        self.adj_matrix[i][j] = 1
        self.adj_matrix[j][i] = 1
    
    def first_adj(self, v):
        """ 获取第一个邻接点 """
        for j in range(self.n):
            if self.adj_matrix[v][j] == 1:
                return j
        return -1
    
    def next_adj(self, v, u):
        """ 获取下一个邻接点 """
        for j in range(u+1, self.n):
            if self.adj_matrix[v][j] == 1:
                return j
        return -1

def create_graph():
    """ 创建图并输入边 """
    n = int(input("请输入顶点数量: "))
    g = Graph(n)
    edges = input("请输入边（格式如 (0,1) (1,2): ").strip().split()
    for edge in edges:
        i, j = map(int, edge.strip('()').split(','))
        g.add_edge(i, j)
    return g

def dfs(g, v, visited):
    """ 深度优先搜索 """
    if visited[v] == 0:
        print(f"V{v}", end=' ')
        visited[v] = 1
    u = g.first_adj(v)
    while u != -1:
        if visited[u] == 0:
            dfs(g, u, visited)
        u = g.next_adj(v, u)

def bfs(g, v, visited):
    """ 广度优先搜索 """
    queue = deque([v])
    while queue:
        v = queue.popleft()
        if visited[v] == 0:
            print(f"V{v}", end=' ')
            visited[v] = 1
        u = g.first_adj(v)
        while u != -1:
            if visited[u] == 0:
                queue.append(u)
            u = g.next_adj(v, u)

# 运行示例
if __name__ == "__main__":
    g = create_graph()
    
    # DFS示例
    print("DFS遍历:")
    visited = [0] * g.n
    dfs(g, 0, visited)
    
    # BFS示例
    print("\n\nBFS遍历:")
    visited = [0] * g.n
    bfs(g, 0, visited)

总结

        本文系统梳理了Python实现的核心数据结构与算法，重点解析双向链表的高效操作方法，详细对比冒泡排序、选择排序、计数排序、桶排序、基数排序和快速排序六大经典算法的实现原理与性能差异，并深入讲解图的邻接矩阵存储方式及其深度优先遍历（DFS）、广度优先遍历（BFS）实现技巧。在双向链表部分，通过前驱/后继指针的智能链接策略，实现了O(1)时间复杂度的首尾插入和O(n/2)平均复杂度的随机访问；排序算法模块揭示比较排序与非比较排序的本质区别，展示计数排序在小范围整型数据处理、桶排序在均匀分布数据场景的独特优势；图论章节则通过邻接矩阵的动态映射，结合递归栈与双端队列分别实现DFS的纵向探索和BFS的横向扩展，为网络分析与路径优化提供核心解决方案。所有代码实现均遵循Pythonic风格，融入类型注解和算法优化技巧，可作为工程级开发的标准化模板。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布