???477
2017-01-22 04:19
采纳率: 100%
浏览 1.1k
已采纳

c语言小白求解一道算法题,能编写运行出结果立即采纳给分

这是一道C语言算法测试题,题目有点长,但看着图片和例子,耐心多读一下就能很容易理解,同学都说题目不难,但本人实在是小白,特此求助,能编写运行出正确结果则采纳给分,拜托了。同学说这道题要用 动态数组malloc创建。

一个网络由M个城市和M-1条连接它们的道路组成的。城市在 [0 …(M-1) ]范围内用不同的整数标记。

如下图,道路以这样的方式连接城市,每对不同的城市通过道路组成的路径连接。只有一种方法可以从任何城市到达任何其它城市。必须经过的“直接道路”的数量被称为这两个城市之间的距离。

例如,考虑以下由十个城市和九条道路组成的网络:

图片说明

城市2和4直接相连,因此它们之间的距离是1.城市4和7通过由“直接道路” 4-0, 0-9和 9-7组成的路径连接; 因此它们之间的距离为3。

其中一个城市是首都,此题目标是计算在距离首都 1,2,3,...,M-1的每个距离处的城市的数量。

如图,如果数字1是首都,那么离首都不同距离的城市将如下:

9处于距离1;
0,3,7处于距离2;
8,4在距离3;
2,5,6距离为4。

假设给出以下声明:

struct Results {

int * A;
int N.
};
(A代表需要返回的数组,N代表数组的大小)
要求写一个函数

struct Results solution(int T [ ],int M),

给定由M个整数组成的非空的零索引数组T(描述M个城市和M-1条道路组成的网络),返回由M-1个整数组成的数组(表示距离首都1,2,…,M-1的每个距离处的城市数目)。

数组T描述了一个城市网络,如下所示:

如果T [P] = Q且P = Q,则P是首都;
如果T [P] = Q且 P不等于Q,则P和Q之间存在“直接道路”

例如,给定以下由十个元素组成的数组T; (请详细看此例)

T [0] = 9 T [1] = 1 T [2] = 4
T [3] = 9 T [4] = 0 T [5] = 4
T [6] = 8 T [7] = 9 T [8] = 0
T [9] = 1

因为 T [1] = 1且1=1,则此时1为首都,
则该函数应返回[1,3,2,3,0,0,0,0,0],如上所述。

假设:
M是在范围[1 ... 100,000]内的整数;
数组T的每个元素是在范围[0 ... M-1]内的整数;
在任何两个不同的城市之间只有一个(可能是间接的)连接。

复杂度:

预期最坏情况时间复杂度为O(M);
预期的最坏情况空间复杂度为O(M),超出输入存储(不计算输入参数所需的存储)。

输入数组的元素可以修改。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

7条回答 默认 最新

  • Kolamu 2017-01-22 06:19
    已采纳

    我看是对的!

    struct Results solution(int T[],int M)
    {
        int cap = 0;
        int* res = (int*)malloc((M-1)*sizeof(int));
        for(int i=0;i<M-1;i++)
        {
            res[i] = 0;
        }
        for(int i=0;i<M;i++)
        {
            int v = T[i];
            int n = i;
    
            int index = 0;
            if(n == v)
            {
                continue;
            }
            while(v != n)
            {
                index++;
                n = v;
                v = T[v];
            }
    
            res[index-1]++;
        }
    
        Results* rs = (Results *)malloc(sizeof(Results));
        rs->A = res;
        rs->N = M-1;
    
        return *rs;
    }
    
    点赞 打赏 评论
  • wild84 2017-01-22 05:00

    mark,同是小白,等着看答案。我想用java实现是不是简单点。

    点赞 打赏 评论
  • 奔跑的小鱼儿 2017-01-22 05:09

    你又来了,我又来了,搞不懂你

    点赞 打赏 评论
  • Kolamu 2017-01-22 05:20

    A和N分别表示啥呀?

    点赞 打赏 评论
  • 奔跑的小鱼儿 2017-01-22 05:23

    你要是在做算法题,刷题库之类的直接找个学长要答案不就好了吗

    点赞 打赏 评论
  • How_about_yes 2017-01-22 05:35

    很久没有写C程序了,结构体还有函数调用这些都忘了,不过还是有一些思路,这里给朋友分享一下。
    主要思路:
    1、求得每点到首都的距离
    2、对距离进行统计

    我把第1点的关键代码贴出来,看看能不能给楼主一点启发

     #include "stdafx.h"
    #include "stdio.h"
    
    int main(int argc, char* argv[])
    {
    
        int T[10] = {9,1,4,9,0,4,8,9,0,1};
        int D[10] = {0};
    
        int i , p;
        //遍历每点
        for(i = 0; i<10; i++)
        {   
            //求点到首都的距离
            for(p = i; p != T[p]; p = T[p])
            {
                D[i] = D[i]++;
            }
        }
    
        //输出0--10到首都的距离
        //for(i = 0; i<10; i++){
        //  printf("%d\n" , D[i]);
        //}
    
        return 0;
    }
    
    点赞 打赏 评论
  • 小傅傅阿明 2017-01-22 09:39

    #include
    #include
    struct Results {
    int* A;
    int N;
    };
    struct Results solution(int T[], int M) {
    //创建result并初始化。
    struct Results result = { (int*)malloc((M - 1) * sizeof(int)), (M - 1) };
    //定义一个temp数组,尺寸和传进来的那个T一样。
    //temp数组是用来储存城市和首都的距离。比如temp[0]的值为2表示城市0和首都距离为2。
    int* temp = (int*)malloc(M * sizeof(int));
    int i, j;
    //将temp数组初始化。
    for (i = 0; i < M; i++) {
    temp[i] = 0;
    }
    //将result的成员A数组初始化。
    for (i = 0; i < result.N; i++) {
    result.A[i] = 0;
    }
    //开始填充temp数组。这里的循环中i代表城市标号。
    for (i = 0; i < M; i++) {
    j = i;
    //如果城市标号j和T[j]不一致,那么就朝首都前进一个单位。
    while (j != T[j]) {
    //每前进一个单位就要记录一次。
    temp[i]++;
    j = T[j];
    }
    }
    //统计距离。存入result的成员A数组里面。
    for (i = 0; i < M; i++) {
    if (temp[i]) {
    result.A[--temp[i]]++;
    }

    }
    return result;
    }
    //测试
    int main() {
    int T[10] = { 9, 1, 4, 9, 0, 4, 8, 9, 0, 1 };
    struct Results results = solution(T, 10);
    for (int i = 0; i < results.N; i++) {
    printf("%d ", results.A[i]);
    }
    return 0;
    }

    点赞 打赏 评论

相关推荐 更多相似问题