注释行上的分段故障：

Question

我想解决一个关于Codechef的问题。我以前发过这篇文章，但现在完全不同了。

http://www.codechef.com/problems/STEPUP#

问题的思想是确定在给定的测试案例中是否出现了所希望的情况。一个理想的情况是，当每个顶点的间接方向比连接到它的顶点更高时。即。如果a->b，F(b)应该是> F(a)。如果在给定的设置中这是不可能的，输出是不可能的。如果没有，则输出具有最大间接方向的顶点X的最小值F(x)，使其对所有其他顶点都成立。我还没有试着打印可能的案例的输出。

输入格式：

第一行输入包含一个数字t，测试用例的数量。

每个测试用例包含两个分隔的整数N和M，分别表示图中的顶点数和边数。

以下每条M行包含两个分隔的整数a、b，表示从顶点a到顶点b的边缘。

在两个顶点a和b之间可以有多个边。

2

2 2

1 2

2 1

3 2

1 2

1 3

产出应是：

不可能

2

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node{
 int val;
 struct Node* next;
};

int indirection[10001];//indirection[a] holds count. What vertex it holds count OF is     given by list[a].val;

int main()
{
 int testcases, num_vertices, num_edges, a,b,c,d,e;
 scanf("%d", &testcases);
 while(testcases--)
    {
        scanf("%d %d",&num_vertices, &num_edges);
        struct Node *list[num_vertices];//array of pointers to node
        int h;
        struct Node * ptr;
        for(h=1;h<=num_vertices;h++)
           {
            list[h]=(struct Node *)malloc(sizeof(struct Node));
            list[h]->val=0;
           }
        memset(indirection,0,10001);
        for(e=0;e<10001;e++)
            printf("Indirection[e]=%d \n",indirection[e]);

        a=1;
        while(a<=num_edges)
        {
            printf("messge printing for the %dth time\n",a);
             scanf("%d %d",&b,&c);
             printf("Message recd %d \n",indirection[c]);
             if(indirection[c]==0)   
                { 
                    printf("entered case1\n");
                     list[a]->val=c;
                     printf("S\n");
                       //Segfaults here
                    list[a]->next->val=b;
                     printf("SS\n");
                     indirection[a]=1;
                     ptr=list[a]->next;
                     printf("SSS \n");
                     printf("case1\n");
                }
             else
                 {  printf("entered case2\n");
                    indirection[c]++;
                     //segfaults here if i comment out the previous one
                     ptr->next->val=b;
                     printf("case2\n");
                     ptr=ptr->next;

                }
            a++;
         }

         int tra,i;
         struct Node *ptr1,*ptrnext;
         for(i=1;i<=num_edges;i++)
         {
            ptr1=list[i];
            ptrnext=list[i]->next;
            {
                if (indirection[ptr1->val]<indirection[ptrnext->val])
                     {   printf("IMPOSSIBLE");
                         break;
                      }

               else
                    {   
                        ptr1=ptrnext;
                        ptrnext=ptrnext->next;
                    }


            }

          }
          free(list);
    }
}

我在注释中提到分段错误的2条语句就在(我认为)有问题的语句之前。如果我删除第一个，在第二个分段故障。如果我把这两样都去掉，不管怎么说，都是段错。

我还在努力解决这个问题，这样我就可以继续下一个问题了。谢谢!

Answer 1

num_vertices被当作是基于1的而不是0的

    struct Node *list[num_vertices];//array of pointers to node
    int h;
    struct Node * ptr;

    // for(h=1;h<=num_vertices;h++)
    for(h=0;h<num_vertices;h++)

       {
        list[h]=(struct Node *)malloc(sizeof(struct Node));
        list[h]->val=0;
       }

next字段不像Daniel所回答的那样初始化

       {
        list[h]=(struct Node *)malloc(sizeof(struct Node));
        list[h]->val = 0;
        list[h]->next = something_maybe_NULL();
       }

建议更简单的malloc()风格

        list[h] = malloc(sizeof *(list[h]));

Answer 2

您的代码分段错误是因为您创建了一个struct Node*数组并为它们分配了内存，但是您从不设置每个Node的next指针。因此，当您尝试访问每个Node的next指针时，它只是指向内存中的任意位置和分段错误。

我觉得你的设计是错的。如果您试图创建一个节点链接列表(如下一个指针的存在所建议的那样)，则根本不需要创建一个数组来保存这些节点。

Answer 3

我分析了您所有的代码，并在其中发现了几个问题，这些问题主要表明您不理解指针

1. 数组是基于0-index的 /*如果声明，结构列表大小；*索引从0 ti szie -1 */ for (h =1；h <= num_vertices；h++) {
2. 您从不初始化node->next指针 /*，您应该将下一个节点初始化为null。*/ listh->next = NULL；
3. 你的memset错了，sizeof(int) != 1 /* memset(间接，0,10001)；错误*/ memset(间接，0,10001 * sizeof(int))；
4. 访问indirection数组时不检查溢出 /*这是非常不安全的，您不检查c */ printf("Message %d \n"，间接)；
5. 取消引用node->next而不检查NULL 如果没有检查，/*不会取消引用列表->next。* lista-> next ->val (错误) */ next= lista->next；if (next != NULL) next->val = b；
6. free list，它是一个数组而不是指针，因此不能在其上调用free，但是，您应该对其元素进行free，因为它们是指向有效malloced内存的指针。 for (i =0；i< num_vertices；i++)空闲(Listi)；

这里是您的代码版本，这个问题已经解决了，我不知道您的算法是否有效，但是代码至少少了6个错误。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/* no need for typedef, since you declare as struct Node */
struct Node
{
    int          val;
    struct Node* next;
};

int indirection[10001];//indirection[a] holds count. What vertex it holds count OF is     given by list[a].val;

int main()
{
    int testcases, num_vertices, num_edges, a, b, c;

    printf("input testcase: ");
    scanf("%d", &testcases);
    while (testcases--)
    {
        printf("input testcase num_vertices and num_edges: ");
        scanf("%d %d",&num_vertices, &num_edges);

        int          h;
        struct Node *list[num_vertices]; // array of pointers to node
        struct Node *ptr;

        /* struct list[size];
            * index goes from 0 ti szie - 1
            */
        for (h = 0 ; h < num_vertices ; h++)
        {
            /* If this is plain C you don't need the cast (struct Node *) */
            list[h]      = malloc(sizeof(struct Node));
            list[h]->val = 0;
            /* You should initialize the next node to null. */
            list[h]->next = NULL;
        }
        /* memset(indirection, 0, 10001); wrong */
        memset(indirection, 0, 10001 * sizeof(int));

        /* What, you dont believe all values are 0? */
        /* for(e = 0 ; e < 10001 ; e++)
            printf("Indirection[e] = %d\n",indirection[e]); */

        /* arrays go from 0 ti size - 1 */
        a = 0;
        while (a < num_edges)
        {
            printf("messge printing for the %dth time\n", a);

            printf("input b and c: ");
            scanf("%d %d", &b, &c);

            if (c < 10001)
            {
                /* this is very unsafe, you don't check c */
                printf("Message recd %d \n", indirection[c]);
                if (indirection[c]==0)
                {
                    struct Node *next;
                    printf("entered case1\n");

                    list[a]->val = c;
                    printf("S\n");

                    // Segfaults here
                    /* don't dereference list[a]->next without checking . */
                    next = list[a]->next;
                    if (next != NULL)
                        next->val = b;
                    printf("SS\n");

                    indirection[a] = 1;
                    ptr            = list[a]->next;

                    printf("SSS \n");
                    printf("case1\n");
                }
                else
                {
                    printf("entered case2\n");
                    indirection[c]++;

                    //segfaults here if i comment out the previous one
                    ptr->next->val=b;

                    printf("case2\n");
                    ptr=ptr->next;
                }
                a++;
            }
        }

        int          i;
        struct Node *ptr1, *ptrnext;

        for(i = 0 ; i < num_edges ; i++) /* arrays go from 0 ti size - 1 */
        {
            ptr1 = list[i];
            if (ptr1 != NULL)
                ptrnext = ptr1->next;
            if ((ptr1 != NULL) && (ptrnext != NULL))
            {
                if (indirection[ptr1->val] < indirection[ptrnext->val])
                {
                    printf("IMPOSSIBLE");
                    break;
                }
                else
                {
                    ptr1    = ptrnext;
                    ptrnext = ptrnext->next;
                }

            }
        }

        for (i = 0 ; i < num_vertices ; i++)
            free(list[i]);
    }
    return 0;
}