计算机软件技术基础上机编程

1 计算机软件技术基础上机编程计算机软件技术基础上机编程 上机题一 线性表上机题一 线性表 1 建立单向链表 表长任意 2 可交互输出单链表中的内容 3 编写算法计算出自己所建单链表的长度并输出 4 输出自己所建立单链表中的第 K 个结点 并将剩余结点输出 5 将单链表倒排并输出结果 include include typedef int datatype typedef struct node datatype data struct node next linklist linklist Creatlist 建立链表建立链表 int x linklist h s h NULL printf n please input the date end with 0 n printf n Input data scanf d while x 0 s malloc sizeof linklist s data x s next h h s printf n Input data scanf d return h void Putlist linklist h 输出单链表中的内容输出单链表中的内容 linklist s s h while s NULL printf 4d s data s s next int Long linklist h 计算链表的长度计算链表的长度 int i 0 linklist s s h while s NULL i 2 s s next return i void Delete linklist h int k 删除链表中第删除链表中第 k 个结点个结点 int i 0 linklist p1 p2 p1 h if k 1 h h next free p1 else while inext p2 next p1 next free p1 linklist Nixu linklist h 逆序输出链表逆序输出链表 linklist r q p r h p r next q p next if h NULL printf the linklist is empty n 空表空表 while q NULL r p p q q q next h next NULL p next r return p 返回根结点返回根结点 main int k x linklist h do 输出菜单输出菜单 printf nqing shu ru ming ling n printf 1 jian li lian biao n printf 2 shu chu lian biao zhong de nei rong n printf 3 shu chu lian biao de chang du n printf 4 shan chu di K ge jie dian n printf 5 jiang lian biao dao xu bing shu chu n printf 6 tui chu cheng xu n 3 printf qing shu ru 1 6 de shu zi n scanf d if x6 printf error n else switch x case 1 h Creatlist break case 2 Putlist h break case 3 printf lian biao de chang du shi d Long h break case 4 printf Input the node you want to delete n scanf d Delete h k Putlist h break case 5 h Nixu h Putlist h break case 6 exit 0 break 退出程序退出程序 while 1 退出程序 4 上机题二 二叉树上机题二 二叉树 1 动态交互建立二叉树 结点个数任意 2 分别用 DLR LDR LRD 三种方式对二叉树进行遍历并输出结果 3 计算二叉树中结点个数并输出 4 计算二叉树深度并输出 源程序 include stdio h 5 include malloc h struct TreeNode int data struct TreeNode Lchild struct TreeNode Rchild struct TreeNode create 用于建立二叉树的子函数用于建立二叉树的子函数 struct TreeNode T int a scanf d if a 0 return NULL else 动态建立二叉树动态建立二叉树 T struct TreeNode malloc sizeof struct TreeNode T data a 建立根结点建立根结点 T Lchild create 递归建立左子树递归建立左子树 T Rchild create 递归建立右子树递归建立右子树 return T void Pre struct TreeNode T 用于进行先序遍历的子函数用于进行先序遍历的子函数 if T NULL printf 5d T data 访问根结点访问根结点 Pre T Lchild 递归访问左子树递归访问左子树 Pre T Rchild 递归访问右子树递归访问右子树 void Mid struct TreeNode T 用于进行中序遍历的子函数用于进行中序遍历的子函数 if T NULL Mid T Lchild 递归访问左子树递归访问左子树 printf 5d T data 访问根结点访问根结点 6 Mid T Rchild 递归访问右子树递归访问右子树 void Post struct TreeNode T 用于进行后序遍历的子函数用于进行后序遍历的子函数 if T NULL Post T Lchild 递归访问左子树递归访问左子树 Post T Rchild 递归访问右子树递归访问右子树 printf 5d T data void visit struct TreeNode T 用于访问二叉树的子函数用于访问二叉树的子函数 printf the result of DLR Pre T printf n printf the result of LDR Mid T printf n printf the result of LRD Post T printf n int leaf struct TreeNode T 用于计算叶子结点的子函数用于计算叶子结点的子函数 int a b if T NULL return 0 else if T Lchild NULL else a leaf T Lchild 递归计算左子树上叶子数递归计算左子树上叶子数 b leaf T Rchild 递归计算右子树上叶子数递归计算右子树上叶子数 return a b 1 int max int x int y 用于取两数的较大值的子函数用于取两数的较大值的子函数 if x y return x else return y 7 int deep struct TreeNode T 用于计算二叉树深度的子函数用于计算二叉树深度的子函数 int k 0 if T NULL return 0 else if T Lchild NULL else return 1 max deep T Lchild deep T Rchild 递归求取树的深递归求取树的深 度度 main int m n p struct TreeNode T printf create a tree n T create 建立二叉树建立二叉树 printf 1 visit the tree n 打印菜单打印菜单 printf 2 putout the total number of node n printf 3 putout the depth of the tree n printf 4 exit n while 1 printf nplease input 1 4 完成菜单的相应功能完成菜单的相应功能 scanf d if m 1 visit T if m 2 n leaf T printf the total number of leaves in the tree is d n n if m 3 if m 3 p deep T printf the depth of the tree is d n p if m 4 break 调试结果 create a tree 1 0 2 5 0 4 0 6 8 96 0 0 0 56 85 0 0 69 0 0 0 2 5 0 0 0 1 visit the tree 8 2 putout the total number of node 3 putout the depth of the tree 4 exit please input 1 4 the total number of leaves in the tree is 10 please input 1 4 please input 1 4 please input 1 4 please input 1 4 please input 1 4 1 the result of DLR 1 2 5 4 6 8 96 56 85 69 the result of LDR 1 5 4 96 8 6 85 56 69 2 the result of LRD 96 8 85 69 56 6 4 5 2 1 please input 1 4 2 the total number of leaves in the tree is 10 please input 1 4 3 9 the depth of the tree is 7 please input 1 4 4 Press any key to continue 上机题三上机题三 图图 在交互方式下完成下列任务 1 根据教材上算法 完成图的深度和广度优先遍历 要求任意给定起始点 输出结果 2 根据教材上算法 完成图的单源最短路径的算法 要求任意给定源点 输出结果 程序 include include define M 1000 define VNum 6 struct GLink int No int Right struct GLink Relat int G VNum VNum 1 对图对图 进行初始化进行初始化 1 31 11 M 41 M M 0 15 50 10 M 13 M 0 15 M M M 13 M 0 17 M M M M 26 0 M M M M 3 M 0 struct GLink GL VNum int Visited VNum void CreateGLink int G VNum VNum 建建 立邻接表立邻接表 int i j struct GLink p q for i 0 i VNum i GL i q NULL for j 0 j 0 将该点加将该点加 入邻接表入邻接表 p Right G i j if GL i NULL GL i p else q Relat p q p void DFS int A VNum VNum int V 用于进行深度优先遍历的子函数 用于进行深度优先遍历的子函数 V 是起点是起点 int i printf d V Visited V 1 将其标记将其标记 为已访问为已访问 for i 0 i 0 访问该点访问该点 for i 0 i VNum i if Visited i 1 DFS A i 仍有未必访问过的点 仍有未必访问过的点 访问该点访问该点 void BFS int A VNum VNum int V 用于广度优先遍历用于广度优先遍历 的子函数的子函数 int CQ VNum int a 0 b c int i k 1 for i 0 i VNum i CQ i M Visited V 1 标志为访问过标志为访问过 CQ 0 V printf d V 将该结点放将该结点放 入队列入队列 while k 6 11 for c 0 c VNum c 依次将队列中以结点为首的邻接表中的结点依次将队列中以结点为首的邻接表中的结点 插入队列插入队列 if Visited c 0 CQ k c 未被访问过 将其插未被访问过 将其插 入到队列中入到队列中 Visited c 1 标志为访问过标志为访问过 a for i 0 i VNum i if Visited i 0 BFS A i void Short int A VNum VNum int V 用于计算最短路径的子函数 用于计算最短路径的子函数 V 是起点是起点 int Dist VNum Path VNum int S 0 int i k int wm u for i 0 i VNum i Dist i A V i 默认这两点之间即为默认这两点之间即为 最短路径最短路径 if Dist i M Path i V 存储该存储该 路径路径 S S 1 V for k 0 k VNum k wm M u V for i 0 i VNum i if S wm Dist i S S 1 u for i 0 i VNum i if S 找到新的找到新的 最短路径最短路径 Path i u 更新路更新路 径长度径长度 for i 0 i VNum i 输出该源结点到其他各点的输出该源结点到其他各点的 最短路径最短路径 if S while k V printf d k k Path k printf d V printf d n Dist i else printf No Path d i main int i j a b CreateGLink G printf 1 search the graph deep first n 打印打印 菜单菜单 printf 2 search the graph broad first n printf 3 find the shortest path n printf 4 exit n while 1 完成菜单功能完成菜单功能 printf n please input a num from 1 to 4 scanf d if a 1 for i 0 i VNum i Visited i 0 printf please input the first node scanf d printf n The Result of DFS is DFS G j printf n if a 2 for i 0 i VNum i Visited i 0 printf please input the first node scanf d printf n The Result of BFS is BFS G j printf n if a 3 printf please input the source node scanf d printf n The Result of Shortest path is n Short G b if a 4 break 13 结果调试截图 结果调试截图 上机题四上机题四 检索和排序 在交互方式下完成下列任务 1 任意给定无序序列 用对半检索法 交互检索任意给定的关键字 KEY 2 任意给定无序序列 用快速排序法对进行排序 并统计交换次数 3 任意给定无序序列 用冒泡排序法对进行排序 并统计交换次数和排序的趟数 程序 程序 include define M 100 struct RedType int key int other int a int Search struct RedType ST int n int key 用用 于进行对半查找的子函数于进行对半查找的子函数 14 int low high mid low 0 high n 1 while low high 未未 检索完毕检索完毕 mid low high 2 指向中间值指向中间值 if ST mid key key return mid 1 检索成功检索成功 else if key high 待排序队列空 结束待排序队列空 结束 return 0 i low j high temp L i while i temp key if i j L i L j t 交换 交换 同时交换次数加同时交换次数加 1 while L i key i 从前向后找出第从前向后找出第 一个大于关键值的数据一个大于关键值的数据 i if i j L j L i t 交换 同交换 同 时交换次数加时交换次数加 1 L i temp printf n nThe QukSort Loop d is i for j 0 j a j 15 printf d L j key return t QuickSort L low i 1 QuickSort L i 1 high 对前对前 后块分别进行快速排序后块分别进行快速排序 void bubsort struct RedType L int n 用于冒泡排序的子函数用于冒泡排序的子函数 int i j 0 m fag 1 t 0 struct RedType x while j 0 fag 0 标志有无交换标志有无交换 for i 0 i n 1 i if L i 1 key L i key 满足交换条件满足交换条件 fag 标记发生交换标记发生交换 x L i 将相将相 邻数据交换邻数据交换 L i L i 1 L i 1 x t 交换次数加交换次数加 1 if fag 输出交换过程输出交换过程 j 排序次数加排序次数加 1 for m 0 m n m printf 5d L m key printf n n printf the sorted array is 输出排序完之后的数据输出排序完之后的数据 for m 0 m n m printf 5d L m key printf n printf nthe times of sort is d j 给出排序次数给出排序次数 printf nthe total times of exchange is d n t 给出交换次数给出交换次数 16 main int b m n i j struct RedType S M T M printf input the length of the data 预先给定数据的个数预先给定数据的个数 scanf d printf please input the data n for i 0 i a i scanf d printf n1 quick sort n 打印菜单打印菜单 printf 2 bub sort n printf 3 search the data you want to see n printf 4 exit