第6章有向图上机练习答案

应用离散数学有向图PAGE杭电－周丽、方景龙第六章PAGE3第6章有向图上机练习编写下列程序并计算至少1个算例1．给定一个有向图的邻接矩阵，编程求它的可达矩阵并判断：它是否弱连通的？是否是单向连通的？是否是强连通的？若不连通，求出相应的连通分图个数。（1）程序代码fromcollectionsimportdequedefwarshall(adj_matrix):"""Warshall算法计算有向图的传递闭包（长度≥1的路径可达性）"""n=len(adj_matrix)reach=[row.copy()forrowinadj_matrix]forkinrange(n):foriinrange(n):forjinrange(n):reach[i][j]=reach[i][j]or(reach[i][k]andreach[k][j])returnreachdefget_strong_reachability(adj_matrix):"""生成有向图的强可达矩阵（自反传递闭包，自身到自身视为可达）"""n=len(adj_matrix)reach=warshall(adj_matrix)#对角线置1：顶点自身可达foriinrange(n):reach[i][i]=1returnreachdefcheck_strong_connectivity(reach_matrix):"""判断强连通性并统计强连通分支数返回：(是否强连通,强连通分支个数)"""n=len(reach_matrix)#判定是否强连通：所有元素均为1is_strong=all(all(row)forrowinreach_matrix)#统计强连通分支：互相可达的顶点属于同一分支visited=[False]*ncomponent_count=0foriinrange(n):ifnotvisited[i]:component_count+=1#标记所有与i互相可达的顶点forjinrange(n):ifreach_matrix[i][j]andreach_matrix[j][i]:visited[j]=Truereturnis_strong,component_countdefto_undirected_adj(adj_matrix):"""将有向邻接矩阵转换为无向邻接矩阵（忽略边的方向）"""n=len(adj_matrix)undir_adj=[[0]*nfor_inrange(n)]foriinrange(n):forjinrange(n):ifadj_matrix[i][j]==1:undir_adj[i][j]=1undir_adj[j][i]=1returnundir_adjdefcheck_undirected_connectivity(undir_adj):"""无向图连通性判定与连通分支统计（BFS实现）返回：(是否连通,连通分支个数)"""n=len(undir_adj)ifn==0:returnTrue,0visited=[False]*ncomponent_count=0forstartinrange(n):ifnotvisited[start]:component_count+=1q=deque([start])visited[start]=Truewhileq:u=q.popleft()forvinrange(n):ifundir_adj[u][v]==1andnotvisited[v]:visited[v]=Trueq.append(v)is_connected=(component_count==1)returnis_connected,component_countdefis_unilaterally_connected(reach_matrix):"""判断有向图是否为单向连通"""n=len(reach_matrix)foriinrange(n):forjinrange(n):#存在两个顶点互相都不可达，则不是单向连通ifnotreach_matrix[i][j]andnotreach_matrix[j][i]:returnFalsereturnTruedefanalyze_digraph_connectivity(adj_matrix):"""完整分析有向图的连通性：输出可达矩阵+三类连通性判定+对应分支数"""n=len(adj_matrix)print("输入有向邻接矩阵：")forrowinadj_matrix:print(f"{row}")print()#1.计算强可达矩阵reach=get_strong_reachability(adj_matrix)print("可达矩阵（强可达）：")forrowinreach:print(f"{row}")print()#2.强连通性判定is_strong,strong_comp=check_strong_connectivity(reach)print(f"强连通性：{'是'ifis_strongelse'否'}")print(f"强连通分支个数：{strong_comp}")#3.单向连通性判定is_unilateral=is_unilaterally_connected(reach)print(f"单向连通性：{'是'ifis_unilateralelse'否'}")#4.弱连通性判定undir_adj=to_undirected_adj(adj_matrix)is_weak,weak_comp=check_undirected_connectivity(undir_adj)print(f"弱连通性：{'是'ifis_weakelse'否'}")print(f"弱连通分支个数：{weak_comp}")#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,adj_matrix):print(f"====={test_name}=====")analyze_digraph_connectivity(adj_matrix)print("-"*55)print()#测试1：3顶点有向环（强连通图）adj1=[[0,1,0],[0,0,1],[1,0,0]]run_test("测试1：3顶点强连通有向环",adj1)#测试2：3顶点有向链（单向连通，非强连通）adj2=[[0,1,1],[0,0,1],[0,0,0]]run_test("测试2：3顶点单向连通有向链",adj2)#测试3：弱连通但非单向连通adj3=[[0,1,0],[0,0,0],[0,1,0]]run_test("测试3：弱连通、非单向连通",adj3)#测试4：非弱连通图（两个独立分量）adj4=[[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]run_test("测试4：非弱连通图（双分量）",adj4)（2）测试算例=====测试1：3顶点强连通有向环=====输入有向邻接矩阵：[0,1,0][0,0,1][1,0,0]可达矩阵（强可达）：[1,1,1][1,1,1][1,1,1]强连通性：是强连通分支个数：1单向连通性：是弱连通性：是弱连通分支个数：1=====测试2：3顶点单向连通有向链=====输入有向邻接矩阵：[0,1,1][0,0,1][0,0,0]可达矩阵（强可达）：[1,1,1][0,1,1][0,0,1]强连通性：否强连通分支个数：3单向连通性：是弱连通性：是弱连通分支个数：1=====测试3：弱连通、非单向连通=====输入有向邻接矩阵：[0,1,0][0,0,0][0,1,0]可达矩阵（强可达）：[1,1,0][0,1,0][0,1,1]强连通性：否强连通分支个数：3单向连通性：否弱连通性：是弱连通分支个数：1=====测试4：非弱连通图（双分量）=====输入有向邻接矩阵：[0,1,0,0][1,0,0,0][0,0,0,1][0,0,1,0]可达矩阵（强可达）：[1,1,0,0][1,1,0,0][0,0,1,1][0,0,1,1]强连通性：否强连通分支个数：2单向连通性：否弱连通性：否弱连通分支个数：22．编写一个程序，接受一个根树和树上的一个顶点。（1）找出的父结点 （2）找出的祖先结点（3）找出的子结点 （4）找出的后代结点（5）找出的兄弟结点 （6）确定是否为叶结点（1）程序代码classRootedTree:def__init__(self,edges,root):"""初始化根树:paramedges:边列表，每个元素为(父结点,子结点)的二元组:paramroot:根结点"""self.root=rootself.children={}#键：结点，值：该结点的子结点列表self.parent={}#键：结点，值：该结点的父结点self._build_tree(edges)def_build_tree(self,edges):"""根据边列表构建树结构"""#收集所有结点all_nodes=set()foru,vinedges:all_nodes.add(u)all_nodes.add(v)#初始化子结点列表fornodeinall_nodes:self.children[node]=[]#填充父子关系forparent,childinedges:self.children[parent].append(child)self.parent[child]=parent#根结点无父结点self.parent[self.root]=Nonedef_check_node_exist(self,v):"""校验结点是否存在于树中"""ifvnotinself.children:raiseValueError(f"结点{v}不存在于当前根树中")defget_parent(self,v):"""查询v的父结点，根结点返回None"""self._check_node_exist(v)returnself.parent[v]defget_ancestors(self,v):"""查询v的所有祖先结点（按从近到远顺序：父→祖父→...→根）"""self._check_node_exist(v)ancestors=[]current=self.parent[v]whilecurrentisnotNone:ancestors.append(current)current=self.parent[current]returnancestorsdefget_children(self,v):"""查询v的所有直接子结点"""self._check_node_exist(v)returnself.children[v].copy()defget_descendants(self,v):"""查询v的所有后代结点（BFS广度优先遍历，不含v自身）"""self._check_node_exist(v)descendants=[]queue=self.children[v].copy()whilequeue:node=queue.pop(0)descendants.append(node)queue.extend(self.children[node])returndescendantsdefget_siblings(self,v):"""查询v的兄弟结点（同父结点的其他子结点）"""self._check_node_exist(v)parent=self.parent[v]ifparentisNone:#根结点无兄弟return[]siblings=self.children[parent].copy()siblings.remove(v)returnsiblingsdefis_leaf(self,v):"""判断v是否为叶结点（无子结点）"""self._check_node_exist(v)returnlen(self.children[v])==0#==========测试算例与运行入口==========if__name__=="__main__":deftest_node(tree,node):print(f"=====查询结点：{node}=====")print(f"父结点：{tree.get_parent(node)}")print(f"祖先结点：{tree.get_ancestors(node)}")print(f"子结点：{tree.get_children(node)}")print(f"后代结点：{tree.get_descendants(node)}")print(f"兄弟结点：{tree.get_siblings(node)}")print(f"是否为叶结点：{'是'iftree.is_leaf(node)else'否'}")print("-"*45)print()#构建测试根树：#0#/\#12#/\\#345edges=[(0,1),(0,2),(1,3),(1,4),(2,5)]tree=RootedTree(edges,root=0)print("测试根树结构：")print("0")print("/\\")print("12")print("/\\\\")print("345")print("="*45)print()#测试1：根结点（0号）test_node(tree,0)#测试2：中间结点（1号）test_node(tree,1)#测试3：叶结点（3号）test_node(tree,3)#测试4：独生子叶结点（5号）test_node(tree,5)（2）测试算例测试根树结构：0/\12/\\345==================================================查询结点：0=====父结点：None祖先结点：[]子结点：[1,2]后代结点：[1,2,3,4,5]兄弟结点：[]是否为叶结点：否=====查询结点：1=====父结点：0祖先结点：[0]子结点：[3,4]后代结点：[3,4]兄弟结点：[2]是否为叶结点：否=====查询结点：3=====父结点：1祖先结点：[1,0]子结点：[]后代结点：[]兄弟结点：[4]是否为叶结点：是=====查询结点：5=====父结点：2祖先结点：[2,0]子结点：[]后代结点：[]兄弟结点：[]是否为叶结点：是3．编写一个程序来产生所有有个顶点的二叉树。（1）程序代码fromcollectionsimportdequeclassTreeNode:"""二叉树节点类"""def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefgenerate_all_binary_trees(n):"""生成所有n个顶点的不同结构二叉树参数:n:int，顶点个数返回:list[TreeNode]，所有二叉树的根节点列表"""ifn<=0:return[]defbuild_trees(start,end):"""递归生成值范围为[start,end]的所有二叉树"""trees=[]#空树边界ifstart>end:trees.append(None)returntrees#枚举根节点的值forroot_valinrange(start,end+1):#递归生成所有左子树（值小于根）left_trees=build_trees(start,root_val-1)#递归生成所有右子树（值大于根）right_trees=build_trees(root_val+1,end)#左右子树两两组合forleftinleft_trees:forrightinright_trees:root=TreeNode(root_val)root.left=leftroot.right=righttrees.append(root)returntreesreturnbuild_trees(1,n)deftree_to_level_order(root):"""辅助函数：将二叉树转换为层序遍历列表（含None表示空节点），便于直观查看结构"""ifnotroot:return[]result=[]q=deque([root])whileq:node=q.popleft()ifnode:result.append(node.val)q.append(node.left)q.append(node.right)else:result.append(None)#移除末尾多余的空节点，简化输出whileresultandresult[-1]isNone:result.pop()returnresult#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(n):print(f"=====测试：{n}个顶点的二叉树=====")all_trees=generate_all_binary_trees(n)total=len(all_trees)print(f"总数：{total}棵（对应第{n}个卡特兰数）")print("各树结构（层序遍历，None表示空节点）：")foridx,treeinenumerate(all_trees,1):print(f"第{idx}棵：{tree_to_level_order(tree)}")print("-"*55)print()#测试1：1个顶点run_test(1)#测试2：2个顶点run_test(2)#测试3：3个顶点run_test(3)#测试4：4个顶点（仅输出总数，验证卡特兰数）n4=4print(f"=====测试：{n4}个顶点的二叉树=====")print(f"总数：{len(generate_all_binary_trees(n4))}棵（对应第{n4}个卡特兰数）")（2）测试算例=====测试：1个顶点的二叉树=====总数：1棵（对应第1个卡特兰数）各树结构（层序遍历，None表示空节点）：第1棵：[1]=====测试：2个顶点的二叉树=====总数：2棵（对应第2个卡特兰数）各树结构（层序遍历，None表示空节点）：第1棵：[1,None,2]第2棵：[1,2,None]=====测试：3个顶点的二叉树=====总数：5棵（对应第3个卡特兰数）各树结构（层序遍历，None表示空节点）：第1棵：[1,None,2,None,3]第2棵：[1,None,3,2,None]第3棵：[2,1,3]第4棵：[3,2,None,1,None]第5棵：[3,1,None,None,2]=====测试：4个顶点的二叉树=====总数：14棵（对应第4个卡特兰数）4．编写一个程序，接受字符串并将它们放到一个二叉搜索树上，而且要求这个二叉树的高度最低。（1）程序代码classTreeNode:"""二叉树节点类"""def__init__(self,val="",left=None,right=None):self.val=valself.left=leftself.right=rightdefbuild_min_height_bst(strings):"""输入字符串列表，构造高度最低的二叉搜索树参数:strings:list[str]，输入的字符串列表返回:TreeNode，构造完成的二叉搜索树根节点"""#1.去重+按字典序排序，得到BST的中序序列sorted_unique=sorted(list(set(strings)))n=len(sorted_unique)ifn==0:returnNone#2.分治递归构造平衡BSTdefbuild(left,right):ifleft>right:returnNone#取中间位置作为根，保证左右子树节点数均衡mid=(left+right)//2root=TreeNode(sorted_unique[mid])root.left=build(left,mid-1)root.right=build(mid+1,right)returnrootreturnbuild(0,n-1)defget_tree_height(root):"""计算二叉树的高度（边数定义：根到最远叶子的路径边数；空树高度为-1，单节点高度为0）"""ifnotroot:return-1left_h=get_tree_height(root.left)right_h=get_tree_height(root.right)returnmax(left_h,right_h)+1definorder_traversal(root):"""中序遍历，验证二叉搜索树的有序性"""result=[]defdfs(node):ifnotnode:returndfs(node.left)result.append(node.val)dfs(node.right)dfs(root)returnresultdeflevel_order_traversal(root):"""层序遍历，直观展示树的层级结构，None表示空节点"""ifnotroot:return[]fromcollectionsimportdequeresult=[]q=deque([root])whileq:level_size=len(q)current_level=[]for_inrange(level_size):node=q.popleft()ifnode:current_level.append(node.val)q.append(node.left)q.append(node.right)else:current_level.append(None)#全空层不输出ifall(xisNoneforxincurrent_level):breakresult.append(current_level)returnresult#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,strings):print(f"====={test_name}=====")print(f"输入字符串：{strings}")root=build_min_height_bst(strings)height=get_tree_height(root)inorder=inorder_traversal(root)level_order=level_order_traversal(root)print(f"去重后节点总数：{len(inorder)}")print(f"树的高度（边数）：{height}")print(f"中序遍历（验证BST有序性）：{inorder}")print("层序结构（逐层输出）：")fori,levelinenumerate(level_order):print(f"第{i}层：{level}")print("-"*60)print()#测试1：7个字符串（完美平衡，满二叉树）test1=["banana","apple","cherry","date","grape","fig","elderberry"]run_test("测试1：7个字符串（完美平衡）",test1)#测试2：4个字符串（非满二叉树，最小高度）test2=["dog","cat","bird","ant"]run_test("测试2：4个字符串（均衡分布）",test2)#测试3：含重复字符串test3=["hello","world","hello","python","world"]run_test("测试3：含重复字符串",test3)#测试4：单个字符串test4=["only"]run_test("测试4：单个字符串",test4)#测试5：空输入test5=[]run_test("测试5：空输入",test5)（2）测试算例=====测试1：7个字符串（完美平衡）=====输入字符串：['banana','apple','cherry','date','grape','fig','elderberry']去重后节点总数：7树的高度（边数）：2中序遍历（验证BST有序性）：['apple','banana','cherry','date','elderberry','fig','grape']层序结构（逐层输出）：第0层：['date']第1层：['banana','fig']第2层：['apple','cherry','elderberry','grape']=====测试2：4个字符串（均衡分布）=====输入字符串：['dog','cat','bird','ant']去重后节点总数：4树的高度（边数）：2中序遍历（验证BST有序性）：['ant','bird','cat','dog']层序结构（逐层输出）：第0层：['bird']第1层：['ant','cat']第2层：[None,None,None,'dog']=====测试3：含重复字符串=====输入字符串：['hello','world','hello','python','world']去重后节点总数：3树的高度（边数）：1中序遍历（验证BST有序性）：['hello','python','world']层序结构（逐层输出）：第0层：['python']第1层：['hello','world']=====测试4：单个字符串=====输入字符串：['only']去重后节点总数：1树的高度（边数）：0中序遍历（验证BST有序性）：['only']层序结构（逐层输出）：第0层：['only']=====测试5：空输入=====输入字符串：[]去重后节点总数：0树的高度（边数）：-1中序遍历（验证BST有序性）：[]层序结构（逐层输出）：5．将赫夫曼算法实现为程序，并根据字母的频率表，构造一个最佳前缀码。（1）程序代码importheapqclassHuffmanNode:"""哈夫曼树结点类"""def__init__(self,char=None,freq=0,left=None,right=None):self.char=char#叶子结点存储字符，内部结点为Noneself.freq=freq#结点权值（频率）self.left=leftself.right=rightdef__lt__(self,other):"""重载小于号，支持最小堆按频率排序"""returnself.freq<other.freqdefbuild_huffman_tree(freq_dict):"""根据字符频率表构造哈夫曼树参数:freq_dict:dict，键为字符，值为对应频率（权值）返回:HuffmanNode，哈夫曼树根结点"""heap=[]#1.所有字符叶子结点入最小堆forchar,freqinfreq_dict.items():heapq.heappush(heap,HuffmanNode(char=char,freq=freq))#特殊情况：只有一个字符iflen(heap)==1:returnheap[0]#2.反复合并两个最小权值结点，直到只剩根结点whilelen(heap)>1:#取出频率最小的两个结点left_node=heapq.heappop(heap)right_node=heapq.heappop(heap)#合并为父结点parent=HuffmanNode(freq=left_node.freq+right_node.freq,left=left_node,right=right_node)heapq.heappush(heap,parent)returnheap[0]defgenerate_huffman_codes(root):"""遍历哈夫曼树，生成每个字符的最佳前缀码返回:dict，字符到编码的映射"""codes={}defdfs(node,current_code):ifnotnode:return#叶子结点：记录最终编码ifnode.charisnotNone:#单个字符特殊处理，约定编码为0codes[node.char]=current_codeifcurrent_codeelse'0'return#左子树路径加0，右子树路径加1dfs(node.left,current_code+'0')dfs(node.right,current_code+'1')dfs(root,'')returncodesdefcalculate_metrics(freq_dict,codes):"""计算带权路径长度WPL和平均码长返回:(总WPL,平均码长)"""total_freq=sum(freq_dict.values())wpl=0forchar,freqinfreq_dict.items():wpl+=freq*len(codes[char])avg_length=wpl/total_freqreturnwpl,avg_length#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,freq_dict):print(f"====={test_name}=====")print("字符频率表：")forchar,freqinsorted(freq_dict.items()):print(f"{char}:{freq}")#构造哈夫曼树+生成编码root=build_huffman_tree(freq_dict)codes=generate_huffman_codes(root)wpl,avg_len=calculate_metrics(freq_dict,codes)print("\n生成的最佳前缀码：")forchar,codeinsorted(codes.items()):print(f"{char}:{code}(码长：{len(code)})")print(f"\n带权路径长度（WPL）：{wpl}")print(f"平均码长：{avg_len:.2f}")print("-"*55)print()#测试1：教材经典6字符算例（总频率100）freq1={'a':45,'b':13,'c':12,'d':16,'e':9,'f':5}run_test("测试1：经典6字符频率表",freq1)#测试2：3字符简单场景freq2={'a':2,'b':3,'c':5}run_test("测试2：3字符简单场景",freq2)#测试3：2字符场景freq3={'x':7,'y':3}run_test("测试3：2字符场景",freq3)#测试4：单个字符边界场景freq4={'z':10}run_test("测试4：单字符边界场景",freq4)#测试5：英文字母频率样例freq5={'A':8,'B':3,'C':5,'D':7,'E':12,'F':2}run_test("测试5：6字母频率样例",freq5)（2）测试算例=====测试1：经典6字符频率表=====字符频率表：a:45b:13c:12d:16e:9f:5生成的最佳前缀码：a:0(码长：1)b:101(码长：3)c:100(码长：3)d:111(码长：3)e:1101(码长：4)f:1100(码长：4)带权路径长度（WPL）：224平均码长：2.24=====测试2：3字符简单场景=====字符频率表：a:2b:3c:5生成的最佳前缀码：a:00(码长：2)b:01(码长：2)c:1(码长：1)带权路径长度（WPL）：15平均码长：1.50=====测试3：2字符场景=====字符频率表：x:7y:3生成的最佳前缀码：x:0(码长：1)y:1(码长：1)带权路径长度（WPL）：10平均码长：1.00=====测试4：单字符边界场景=====字符频率表：z:10生成的最佳前缀码：z:0(码长：1)带权路径长度（WPL）：10平均码长：1.00=====测试5：6字母频率样例=====字符频率表：A:8B:3C:5D:7E:12F:2生成的最佳前缀码：A:10(码长：2)B:010(码长：3)C:011(码长：3)D:110(码长：3)E:111(码长：3)F:00(码长：2)带权路径长度（WPL）：85平均码长：2.506．随机输入500～1000个英文小写字母，保存为文本文件（ASCII文件），然后设计和实现以下两个程序（1）压缩程序：用赫夫曼编码压缩文本文件成为二进制文件。（2）解压缩程序：对压缩后的文件进行解压缩，还原原始文件。（1）程序代码importrandomimportheapqimportstructimportos#=====================赫夫曼树核心模块=====================classHuffmanNode:"""赫夫曼树结点"""def__init__(self,char=None,freq=0,left=None,right=None):self.char=charself.freq=freqself.left=leftself.right=rightdef__lt__(self,other):returnself.freq<other.freqdefbuild_huffman_tree(freq_dict):"""根据频率字典构建赫夫曼树"""heap=[]forchar,freqinfreq_dict.items():heapq.heappush(heap,HuffmanNode(char=char,freq=freq))iflen(heap)==1:returnheap[0]whilelen(heap)>1:left=heapq.heappop(heap)right=heapq.heappop(heap)parent=HuffmanNode(freq=left.freq+right.freq,left=left,right=right)heapq.heappush(heap,parent)returnheap[0]defgenerate_code_map(root):"""生成字符→赫夫曼编码的映射字典"""code_map={}defdfs(node,current_code):ifnotnode:returnifnode.charisnotNone:code_map[node.char]=current_codeifcurrent_codeelse'0'returndfs(node.left,current_code+'0')dfs(node.right,current_code+'1')dfs(root,'')returncode_map#=====================二进制位处理辅助函数=====================defbitstring_to_bytes(bit_str):"""01字符串转换为字节数组，末尾不足8位补0"""padding_len=(8-len(bit_str)%8)%8bit_str+='0'*padding_lenbyte_arr=bytearray()foriinrange(0,len(bit_str),8):byte_val=int(bit_str[i:i+8],2)byte_arr.append(byte_val)returnbytes(byte_arr)defbytes_to_bitstring(byte_data):"""字节数组转换为01字符串"""bit_str=''forbinbyte_data:bit_str+=f'{b:08b}'returnbit_str#=====================1.随机文本生成程序=====================defgenerate_random_text(output_path,min_len=500,max_len=1000):"""生成随机小写英文字母文本，保存为ASCII文件"""length=random.randint(min_len,max_len)text=''.join(random.choice('abcdefghijklmnopqrstuvwxyz')for_inrange(length))withopen(output_path,'w',encoding='ascii')asf:f.write(text)returnlength#=====================2.压缩程序=====================defcompress_file(input_txt_path,output_bin_path):"""赫夫曼编码压缩文本文件为二进制文件:paraminput_txt_path:原始文本文件路径:paramoutput_bin_path:压缩后二进制文件路径"""#1.读取原始文本withopen(input_txt_path,'r',encoding='ascii')asf:text=f.read()ifnottext:raiseValueError("文本文件为空，无法压缩")#2.统计字符频率freq_dict={}forcintext:freq_dict[c]=freq_dict.get(c,0)+1#3.构建赫夫曼树，生成编码映射huff_root=build_huffman_tree(freq_dict)code_map=generate_code_map(huff_root)#4.将文本转换为二进制位串bit_str=''.join(code_map[c]forcintext)#5.转换为字节数据compressed_data=bitstring_to_bytes(bit_str)#6.写入二进制文件（先写文件头，再写压缩数据）withopen(output_bin_path,'wb')asf:#写入字符种类数（1字节）char_count=len(freq_dict)f.write(struct.pack('B',char_count))#写入每个字符的ASCII码和频率forchar,freqinfreq_dict.items():f.write(struct.pack('B',ord(char)))f.write(struct.pack('I',freq))#写入原始文本总长度f.write(struct.pack('I',len(text)))#写入压缩数据f.write(compressed_data)#输出压缩统计original_size=os.path.getsize(input_txt_path)compressed_size=os.path.getsize(output_bin_path)print(f"压缩完成！")print(f"原始文件大小：{original_size}字节")print(f"压缩后大小：{compressed_size}字节")print(f"压缩率：{(1-compressed_size/original_size)*100:.2f}%")#=====================3.解压缩程序=====================defdecompress_file(input_bin_path,output_txt_path):"""解压缩赫夫曼编码的二进制文件，还原原始文本:paraminput_bin_path:压缩二进制文件路径:paramoutput_txt_path:还原后的文本文件路径"""withopen(input_bin_path,'rb')asf:#1.读取文件头：字符种类数char_count=struct.unpack('B',f.read(1))[0]#2.读取所有字符的频率freq_dict={}for_inrange(char_count):char_ascii=struct.unpack('B',f.read(1))[0]freq=struct.unpack('I',f.read(4))[0]freq_dict[chr(char_ascii)]=freq#3.读取原始文本总长度original_len=struct.unpack('I',f.read(4))[0]#4.读取剩余所有压缩数据compressed_data=f.read()#5.重建赫夫曼树huff_root=build_huffman_tree(freq_dict)#6.字节转二进制位串bit_str=bytes_to_bitstring(compressed_data)#7.遍历赫夫曼树还原字符result=[]current_node=huff_rootidx=0whilelen(result)<original_lenandidx<len(bit_str):bit=bit_str[idx]ifbit=='0':current_node=current_node.leftelse:current_node=current_node.right#到达叶子结点，记录字符，回到根结点ifcurrent_node.charisnotNone:result.append(current_node.char)current_node=huff_rootidx+=1#8.写入还原后的文本文件restored_text=''.join(result)withopen(output_txt_path,'w',encoding='ascii')asf:f.write(restored_text)print(f"解压缩完成！")print(f"还原字符数：{len(restored_text)}，与原始长度一致：{len(restored_text)==original_len}")#=====================测试与运行入口=====================if__name__=="__main__":#文件路径定义original_txt="original.txt"#原始随机文本compressed_bin="compressed.bin"#压缩后的二进制文件restored_txt="restored.txt"#解压还原的文本print("="*55)print("步骤1：生成随机英文小写字母文本文件")text_len=generate_random_text(original_txt)print(f"生成文本长度：{text_len}个字符，保存为{original_txt}")print()print("步骤2：执行赫夫曼编码压缩")compress_file(original_txt,compressed_bin)print()print("步骤3：执行解压缩还原")decompress_file(compressed_bin,restored_txt)print()#验证正确性：对比原始文件与还原文件print("步骤4：正确性验证")withopen(original_txt,'r')asf1,open(restored_txt,'r')asf2:iff1.read()==f2.read():print("✅验证通过：解压后的文件与原始文件完全一致")else:print("❌验证失败：解压后的文件与原始文件不一致")print("="*55)（2）测试算例=======================================================步骤1：生成随机英文小写字母文本文件生成文本长度：762个字符，保存为original.txt步骤2：执行赫夫曼编码压缩压缩完成！原始文件大小：762字节压缩后大小：451字节压缩率：40.81%步骤3：执行解压缩还原解压缩完成！还原字符数：762，与原始长度一致：True步骤4：正确性验证✅验证通过：解压后的文件与原始文件完全一致=======================================================7．编写一个程序，接受带有给定流的有向网络作为输入，输出所有可能的从源点到收点的路径，使流可以在路径上面增加。（1）程序代码defbuild_residual_network(capacity,flow):"""根据容量矩阵和当前流矩阵，构建残余网络邻接矩阵参数:capacity:list[list[int]]，有向图容量矩阵，无边则为0flow:list[list[int]]，当前流矩阵，对应边的流量返回:residual:list[list[int]]，残余网络邻接矩阵"""n=len(capacity)residual=[[0]*nfor_inrange(n)]foruinrange(n):forvinrange(n):ifcapacity[u][v]>0:#正向残余：还能增加的流量residual[u][v]+=capacity[u][v]-flow[u][v]#反向残余：可以退回的流量（退流）residual[v][u]+=flow[u][v]returnresidualdeffind_all_augmenting_paths(capacity,flow,source,sink):"""找出流网络中所有从源点到汇点的可增广路径参数:capacity:容量矩阵flow:当前流矩阵source:源点编号sink:汇点编号返回:list[tuple]，每个元素为(路径顶点列表,该路径最大可增流量)"""n=len(capacity)#校验顶点合法性ifsource<0orsource>=norsink<0orsink>=n:raiseValueError("源点或汇点编号超出范围")#1.构建残余网络residual=build_residual_network(capacity,flow)result=[]visited=[False]*n#2.DFS回溯找所有简单路径defdfs(current,path,min_cap):ifcurrent==sink:result.append((path.copy(),min_cap))returnfornext_vinrange(n):ifresidual[current][next_v]>0andnotvisited[next_v]:visited[next_v]=Truepath.append(next_v)#更新路径上的最小残余容量new_min=min(min_cap,residual[current][next_v])dfs(next_v,path,new_min)#回溯path.pop()visited[next_v]=False#从源点开始搜索visited[source]=Truedfs(source,[source],float('inf'))returnresult#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,capacity,flow,source,sink):print