【趣学C语言和数据结构100例】

问题描述

91.堆排序算法

92.归并排序

93.设计一个完整的 C 语言程序。要求完成以下功能:从低值开始取出长整型变量 s中偶数位上的数，依次构成一个新数放在t中。例如，当s中的数为 7654321 时，得到结果为 642.

94.实现计算:有 80 工人，每个工人包括的信息有:工号，名字，三个月的收入以及平均收入。用函数(1)完成工人信息的输入，并计算其平均收入。(2)用冒泡排序法排序工人平均收入。(3)完成工人信息的输出。

95.试设计一个算法，判断一个无向图 G是否为一棵树。若是一棵树，则算法返回 true,否则返回 false。

代码分析

==86.堆排序==
算法步骤：
1.建堆: 将输入数组构建成最大堆。这可以通过从数组的最后一个非叶子节点开始，自底向上地进行“向下调整”（heapify）操作来实现。向下调整操作确保每个节点都满足最大堆性质。
2.排序: 重复执行以下步骤，直到堆为空：
将堆顶元素（最大元素）与堆的最后一个元素交换。
将堆的大小减 1（因为最大元素已在正确的位置）。
对新的堆顶元素进行向下调整，以维护最大堆性质。

==87.归并排序==
归并排序是一种基于分治策略的排序算法。其基本思想是：
分治 (Divide): 将待排序的数组递归地分成两个子数组，直到每个子数组只包含一个元素（此时子数组已排序）。
合并 (Conquer): 将两个已排序的子数组合并成一个更大的已排序数组。 合并操作的关键在于比较两个子数组的第一个元素，将较小的元素放入新的数组中，然后继续比较下一个元素，直到所有元素都被合并到新的数组中。
递归 (Recurse): 重复步骤 1 和 2，直到所有子数组都被合并成一个完整的已排序数组。

==88.从低值开始取出长整型变量 s中偶数位上的数==
使用了一个 while 循环来迭代处理 s 中的每一位数字。 它通过取模运算 (% 10) 获取最后一位数字，然后通过除法运算 (/ 10) 去除最后一位数字。 它使用一个 multiplier 变量来正确地构建新数 t。 if 语句确保只处理偶数位数字。 temp 变量用于避免修改原始的 s 值。 代码还添加了对只有一位数和奇数位数情况的处理。

==89.冒泡排序==

==90.无向图 G是否为一棵树==
分析：
1.判断有没有环
2.广度优先搜索 从任意一个顶点开始BFS遍历图。 记录访问过的顶点数量Vnum和经过的边的数量Enum。 如果BFS遍历结束后，访问过的顶点数量等于图中顶点的总数，并且经过的边的数量等于顶点总数减一（因为树是一个没有环的连通图，边的数量总是顶点数减一），则图是一棵树。

代码实现

#include<stdio.h>
#define N 80
typedef struct worker{
   
    char num[10];
    char name[10];
    float money[3];
    float avg;
}worker;
worker wk[N];
void fun1(worker wk[]){
   
    float sum=0;
    for(int i=0;i<N;i++){
   
        scanf("%s %s %f %f %f",&wk[i].num,&wk[i].name,&wk[i].money[0],&wk[i].money[1],&wk[i].money[2]);
        wk[i].avg= (wk[i].money[0]+wk[i].money[1]+wk[i].money[2])/3.0;
        sum=0;
    }    
}

void fun2(worker wk[]){
   
    for(int i=0;i<N-1;i++){
   
        bool flag=false;
        for(int j=N-1;i<j;j--){
   
            if(wk[j].avg<wk[j-1].avg){
   
                int temp=wk[j].avg;
                wk[j].avg=wk[j-1].avg;
                wk[j-1].avg=wk[j].avg;
                flag=true;
            }
            if(flag==false){
   
                return;
            }
        }
    }    
}

void fun3(worker wk[]){
   
    for(int i=0;i<N;i++){
   
        printf("%s %s %f %f %f",wk[i].num,wk[i].name,wk[i].money[0],wk[i].money[1],wk[i].money[2],wk[i].avg);
    }    
}

int main(){
   
//    91.堆排序算法   完全二叉树  k  2k  2k+1 
void HeadAjust(int a[],int k,int len){
   
    a[0]=a[k];
    for(int i=2*k;i<len;i){
   
        if(a[i]<a[i+1] && i<len){
   
            i++;
        }
        if(a[0]>a[i]){
   
            break;
        }else{
   
            a[k]=a[i];
            k=i;
        }
    }
    a[k]=a[0];
}
void BridMaxheap(ElemType[],int len){
   
    for(int i=len/2;i>0;i--){
   
        HeadAjust(A,i,len)
    }
}

//    92.归并排序
void merge(int A,int low,int mid,int high){
   
    int *b=(int *)malloc((high-low+1)*sizeof(int));
    for(int k=low;k<=high;k++){
   
        b[k]=a[k];
    }
    for(int i=low,i=mid+1,k=low;i<=mid && j<=high;){
   
        if(b[i]<=b[j]){
   
            a[k++]=b[i++];
        }else{
   
            a[k++]=b[j++];
        }
    }
    while(i<=mid){
   
        a[k++]=b[i++];
    }
    while(j<=high){
   
        a[k++]=b[j++];
    }
}

//    93.设计一个完整的 C 语言程序。要求完成以下功能:从低值开始取出长整型变量 s中偶数位上的数，依次构成一个新数放在t中。例如，当s中的数为 7654321 时，得到结果为 642.
void fun(long s,long *t){
   
    s=s/10;
    *t=s%100;
    long s1=10； 
    while(s>=100){
   
        s=s/100;
        *t=s%10*s1+*t;
        s1=s1*10;
    }    
}

//    实现计算:94.有 80 工人，每个工人包括的信息有:工号，名字，三个月的收入以及平均收入。用函数(1)完成工人信息的输入，并计算其平均收入。(2)用冒泡排序法排序工人平均收入。(3)完成工人信息的输出。
fun1();
fun2();
fun3();

//    95.试设计一个算法，判断一个无向图 G是否为一棵树。若是一棵树，则算法返回 true,否则返回 false。
//1.判断有没有环
//2.广度优先搜索 从任意一个顶点开始BFS遍历图。 记录访问过的顶点数量Vnum和经过的边的数量Enum。  如果BFS遍历结束后，访问过的顶点数量等于图中顶点的总数，并且经过的边的数量等于顶点总数减一（因为树是一个没有环的连通图，边的数量总是顶点数减一），则图是一棵树。
bool istree(Graph G){
   
    bool visited[G.vexunm];
    for(int i=0;i<G.vexnum;i++){
   
        visited[i]=false;
    }
    int Vnum=0,Vnum=0;
    BFS(G,0,visited,Vnum,Enum);
    if(Vnum=G.vexnum && Enum=G.vexnum-1){
   
        return true;
    }else{
   
        return false;
    }
} 
BFS(Graph G,int u,bool visited,int &Vnum,int &Enum){
   
    Vnum++;
    visited[u]=true;
    Inqueue(Q);
    ENqueue(Q,u);
    while(!isEmpty(Q)){
   
        DeQueue(Q,u);
        for(int w=FirstNeihbor(Q,u);w>=0){
   
            w=NextNeihbor;
            if(!visited[w]){
   
                Vnum++;
                Enum++;
                visited[w]=true;
                Enqueue(Q,w);
            }
        }
    }
}

    return 0;
}

总结

本文介绍了几个经典的算法问题及其C语言实现，包括堆排序、归并排序、特定数字处理、工人信息排序和无向图是否为树的判断。这些问题覆盖了排序、数据处理和图论等多个领域，展示了算法和数据结构在解决实际问题中的应用。

堆排序是一种高效的比较类排序算法，其核心在于构建最大堆并进行反复的调整。通过将堆顶的最大元素与堆尾元素交换并缩小堆大小，可以实现高效的排序。堆排序的时间复杂度为O(nlogn)，在处理大数据量时表现良好。

归并排序是一种分治算法，通过递归地将数组分成更小的子数组，然后合并这些子数组来实现排序。归并排序的时间复杂度同样为O(nlogn)，且由于其稳定的排序特性，在实际应用中非常有效。

在处理特定数字的问题中，我们通过迭代和条件判断，从长整型变量中提取出偶数位上的数构成新数。这个问题虽然简单，但涉及到了位操作和循环控制，是基础算法训练的好例子。

工人信息排序问题涉及到结构体的使用和冒泡排序的实现。通过结构体存储工人信息，并使用冒泡排序算法根据平均收入对工人进行排序，展示了C语言在数据处理方面的能力。冒泡排序虽然时间复杂度为O(n^2)，在数据量较大时效率不高，但其实现简单，适合教学和理解排序算法的基本概念。

最后，无向图是否为树的判断问题涉及到图论的基本概念。通过广度优先搜索（BFS）遍历图，并记录访问过的顶点数量和边的数量，可以判断图是否为一棵树。这个问题展示了图论算法在判断图结构方面的应用。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对算法和数据结构的理解。通过这些问题的解决，我们可以更好地理解算法的工作原理和适用场景，为解决更复杂的问题打下坚实的基础。这些算法的实现和分析，不仅提升了我们的问题解决能力，也让我们更加欣赏算法之美。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。