软件技术基础上机作业

软件技术基础上机作业内容摘要：

实验十、统计二叉树的结点 问题的提出 采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。 13 算法分析 Step1：先统计结点总数，利用结点的遍历使其结点数加 1 的方法即可； Step2：再统计叶子结点总数，分别统计左、右子树中叶子结点个数，相加即得出叶子结点总数 leaf。 问题的程序代码 //统计结点总数 int countleaf(bitree *p) { static int n=0。 //n 为结点个数 if(p!=NULL) {n++。 //每遍历一个结点， n 加 1 countnode(plchild)。 countnode(prchild)。 } //遍历根结点及子树的左、右子树 return n。 } //统计叶子结点总数 static int leaf =0。 if(p!=NULL) { leaf = countleaf( plchild )。 //统计左子树中叶子结点个数 if ((plchild==NULL)amp。 amp。 (prchild==NULL)) leaf=leaf+1。 leaf=countleaf(prchild)。 //统计右子树中叶子结点个数 } return leaf。 } 运行结果 存在的问题 统计结点总数时 要确定遍历完全部的结点，并且 统计叶子结点总数要确定左右叶子个子树的完全统计。 14 实验十一、无向图邻接矩阵 问题的提出 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。 算法分析 Step1：确定出发点为 iv ，开始进行深度优 先搜索； Step2：当被访问过时，利用 visited[i]=1 进行标记； Step3：并从未被访问的邻接点 jv 出发进行深度优先搜索遍历即可。 问题的程序代码 //添加深度优先搜索遍历算法 void dfsa(int i) {int j。 printf(出发点 %c\n,gvexs[i])。 //从出发点为 iv 开始进行深度优先搜索 visited[i]=1。 //标记 iv 已被访问 for(j=0。 jn。 j++) if((garcs[i][j]==1)amp。 amp。 (visited[j]==0)) dfsa(j)。 }//从未被访问的邻接点 jv 出发进行深度优先搜索遍历 15 运行结果 存在的问题 注意确定开始进行深度优先搜索的出发点为 iv ，并且标记 iv 已被访问和从未被访问的邻接点 jv 的确定。 实验十二、希尔排序 问题的提出 采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序的结果。 16 算法分析 Step1：先设置 T 个监视哨，并且每一趟增加相应的常量； Step2：通过 Step1 设置不同的常量，可得出输出一趟的排序结果，结束。 问题的程序代码 //希尔排序 void shellsort(rectype r[],int d[]) { int i,j,k,h。 rectype temp。 int maxint=32767。 for(i=0。 iD1。 i++) r[i].key=maxint。 //设置 T 个监视哨 k=0。 do{ h=d[k]。 //取一趟的增量 for(i=h+D1。 iN+D1。 i++) { temp=r[i]。 j=ih。 while(r[j].key) { r[j+h]=r[j]。 j=jh。 } r[j+h]=temp。 }//组内直接插入法排序 print(r,N)。 //输出一趟的排序结果 k++。 }while(h!=1)。 } 运行结果 17 存在的问题 希尔排序要注意设置适当的增加的常量，从而减少时间的复杂度。 实验十三、双向起泡排序 问题的提出 编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序的结果。 算法分析 Step1：先设置交换标志为假，进行 n1 趟的排序将最大的量进行“下沉”； Step2：再后移一个数，重复 Step1，直到得到的结果为从小到大排好序的结果，结束。 问题的 程序代码 //双向起泡排序 void dbubblesort(sequenlist r[],int n) { int i=1,j,noswap=1。 sequenlist temp。 while(noswap){ noswap=0。 //交换标志设为假 for(j=ni+1。 j=i+1。 j)//最多进行 n1 趟的排序 if(r[j].keyr[j1].key) { noswap=1。 temp=r[j]。 r[j]=r[j1]。 r[j1]=temp。 }//将最大的量进行“下沉” for(j=i+1。 j=ni。 j++)//最多进行 n2i+1 趟的排序 if(r[j].keyr[j+1].key) { noswap=1。 temp=r[j]。 r[j]=r[j+1]。 r[j+1]=temp。 }//将最大的量进行“下沉” for(int k=1。 k=n。 k++) printf(%5d,r[k].key)。 printf(\n)。 18 i++。 }//输出排序后的结果 } 运行结果 存在的问题 一次扫描可以将最重的“气泡”进行“下沉”，而当进行上浮时比较简单时应利用上浮进行排序，这比较难以判定。 实验十四、分块查找 问题的提出 18 个记录的关键字为 2 1 1 3 4 4 3 2 460、 5 7 4 8 53，编写分块查找的算法进行查找。 算法分析 Step1：在索引表较大时，应先利用折半查找的方法确定关键字所在的块； Step2：再利用顺序查找的方法即可查 找出关键字所在的确定位置即可。 问题的程序代码 //分块查找 int blksearch(record r[],index idx[],keytype k,int n) { int i,low=0,high=n1,mid,bh,find=0。 //折半查找索引表 while(low=highamp。 amp。 !find) { mid=(low+high)/2。 if(kidx[mid].key)high=mid1。 else if(kidx[mid].key)low=mid+1。 else { high=mid1。 19 find=1。 } } if(lown) { i=idx[low].low。 //块的起始地址 bh=idx[low].high。 //块的终止地址 } //块内顺序查找 while(ibhamp。 amp。 r[i].key!=k)i++。 if(r[i].key!=k)i=1。 return i。 } 运行结果 存在的问题 在索引表较大，分块查找先利用折半查找方法可大大的简化步骤 ，之后利用顺序查找即可得出，分块查找结合了折半查找和顺序查找的优点，有较广泛的应用。 实验十五、判断二叉排序树 问题的提出 编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，结点的数据域只存放正整数。 20 算法分析 Step1：先判断二叉树的左子树的值是否均小于相应的根结点的值，否，不是二叉排序树，是，转 Step2； St。