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），超出输入存储（不计算输入参数所需的存储）。

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

答

我看是对的！

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;
}

答

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

答

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

答

A和N分别表示啥呀？

答

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

答

很久没有写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;
}

答

#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;
}

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

相关推荐