WedX - журнал о программировании и компьютерных науках

Linkedlist и ошибка сегментации

Это мой код.

#include<stdio.h>
#include<stdlib.h>
struct prefix {
   unsigned int IP ;
   unsigned char len ;
  struct prefix *next ;
 };
typedef struct prefix Prefix ;
int cal(int d){
   int i , sum ;
   sum = 2 ;
   for( i = 0 ; i < d-1 ; i++)
     sum = sum * 2 ;
      return sum+1 ; }


Prefix *insert_a_node(Prefix *head,Prefix *node ){
    Prefix *cur ;
      cur = head ;
    if(head == NULL)
        return node ;
    if( node == NULL )
       return head ;
    if( node->IP < head->IP)
      { node->next = head ;
          return node ;  }
    while( cur->next != NULL && cur->next->IP <= node->IP)
        cur = cur->next ;
       node->next = cur->next ;
       cur->next = node ;
      return head ;
                       }

void insert_prefix(Prefix *group_head,Prefix *node){
  int i = 0;
  Prefix *t;

  if(node == NULL) return;
  if(group_head->next == NULL)
        {
         group_head->next=node;

         return ;
        }
  if(node->IP <= group_head->next->IP)
        {
        node->next = group_head->next ;
        group_head->next=node;

        return ;
        }
  t = group_head->next ;
 if(t->next==NULL)
   {  t->next=node;

      return;}
  while(t->next!=NULL && t->next->IP < node->IP)
        t=t->next;
 if(t->next==NULL)
     { t->next=node;

       return;}
   else{
    node->next=t->next;
    t->next=node;

    return;}
}
Prefix *build_list_no_order(Prefix *head,Prefix *node){

     if (head == NULL)
         return node ;
     if (node == NULL)
        return head ;
   Prefix *cur ;
     cur = head ;
   while ( cur->next != NULL)
    cur = cur->next ;
    cur->next = node ;
  return head ;

 }

Prefix *build_routing_table(){
    int a[5],i ;
   int ip = 0 ;
  Prefix *head ;
      head =  NULL ;
 FILE *ofp ;
 ofp = fopen("routing_table","r") ;
 while( fscanf(ofp,"%d.%d.%d.%d/%d",&a[0],&a[1],&a[2],&a[3],&a[4]) != EOF){
       Prefix *node = (Prefix*)malloc(sizeof(Prefix)) ;
   for ( i =0 ; i < 4 ; i++)
   {  ip = ip + a[i] ;
    if ( i != 3 )
      ip = ip<<8 ;  }
        node->IP = ip ;
        ip = 0 ;
        node->len=a[4];
      head = build_list_no_order(head,node);  }
 fclose(ofp);
    return head ;

    }

void segment(int d,Prefix *rout ,Prefix group[],int each_seg_num[]){
   int index=0,i;
 if(rout->len < d)
      index = cal(d)-1;
 else{
   for(i=31 ; i>31-d ; i--){
    if( ( rout->IP & 1<<i ) && ( i!=32-d))
        {index++;
        index=index<<1;}
    if( (rout->IP & 1<<i) && i==32-d)
        index++;
    if( !(rout->IP & 1<<i) && i!=32-d)
        index=index<<1;
                           }
      }
   each_seg_num[index]++;
   insert_prefix(&group[index],rout);
    return ;
   }
int main ( int argc , char *argv[]){
  Prefix *routing_head;
  Prefix *trace_head;
  Prefix *node;
  int d = 5 , i ; //need use argc finally
  int group_num;
  group_num = cal(d);
  Prefix group[group_num] ;
  int each_seg_num[group_num];
 for( i = 0 ; i < group_num ; i++)
  each_seg_num[i] = 0;
  routing_head = build_routing_table();
 int count = 1200 ;
 while(routing_head != NULL &&count>=0){
   node = routing_head ;
   routing_head = routing_head->next ;
   node->next = NULL ;
   segment(d,node,group,each_seg_num);
    count--;
     }
 for( i = 0 ; i < group_num ; i++)
   printf("%d\n",each_seg_num[i]);

     return 0 ;
}

Позвольте мне объяснить, что я делал сейчас.

Сначала я читаю 80000 данных из routing_table (все данные имеют аналогичный формат, например 2.10.120.20/8, и я сохраняю их в IP-адресе префикса (unsigned int), вы можете называть его длиной IP / префикса).
Затем мне нужен сегмент эти данные в другую группу (каждая группа представляет собой один связанный список), число определяется int d, предположим, что d = 2, поэтому у меня есть 2 ^ 2 + 1 группа. По первому биту "d" каждого данных мы можем определить, в какую группу должны быть отправлены данные.
Пример: IP (в двоичном формате): 01000011 ...... он должен попасть в группу [1]
IP: 1000001 ..... должен попасть в группу [2]
и если префикс len ‹d, например IP: 1 ******** (* означает, что это не важно), он должен попасть в специальную группу, группу [4].
В-третьих, каждый связанный список должен быть в порядке (от маленького к большему)

Проблема: я думаю, что я уже почти закончил код, но когда я выполняю свою программу, у нее возникает ошибка сегментации. Но больше всего меня удивляет то, что когда я использую int count для ограничения количества данных, передаваемых в segment (), программа может работать !!
Код может работать меньше, чем передать около 1000 данных. Я хочу знать, как решить мою проблему, спасибо, что прочитали мой вопрос.

..... Наконец, мой английский, возможно, недостаточно хорош, чтобы точно объяснить вопрос ..... пожалуйста, простите меня ^^

c
06.01.2018


Ответы:


1

Ваш сбой происходит в insert_prefix, когда вы вставляете узел в список групп, сохраняя при этом список отсортированным.

Во-первых, при определении групп возникает концептуальная ошибка. Есть group_num групп, и каждая группа представляет собой связанный список, поэтому вам нужен массив указателей для префиксов узлов вместо массива узлов:

Prefix *group[group_num];

Вы также должны инициализировать каждый указатель на NULL. И вы должны настроить аргумент group на функции segment и insert_prefix.

В вашей реализации неупорядоченного связного списка вы возвращаете новый головной узел. Здесь вы также должны найти средства для обновления головы, если это необходимо. В C я считаю полезным передавать указатель на указатель головного узла.

Вы можете использовать этот указатель на указатель узла для итерации по списку: когда вы вызываете функцию, этот указатель является адресом головного узла. После этого это адрес указателя next предыдущего узла.

С помощью этой техники ваша функция становится:

void insert_prefix(Prefix **head, Prefix *node)
{
    if (node == NULL) return;

    while (*head && (*head)->IP < node->IP) {
        head = &(*head)->next;
    }

    node->next = *head;
    *head = node;
}

Посмотрите, как этот метод итераций учитывает все особые случаи. Нет необходимости различать пустой и полный список.

Другие изменения в вашей программе, которые вы должны сделать, - это изменить здесь аргумент group:

void segment(int d, Prefix * rout, Prefix *group[], int each_seg_num[])
{
    ....
}

и изменить определение и инициализацию в main:

group_num = cal(d);
Prefix *group[group_num];
int each_seg_num[group_num];

for (i = 0; i < group_num; i++) {
    group[i] = NULL;
    each_seg_num[i] = 0;
}

Вам, вероятно, также следует ввести код для уничтожения ваших списков в конце программы.

06.01.2018
  • Ваш код в insert_prefix - это для меня совершенно новая идея о связанном списке, большое спасибо. Но у меня все еще есть два вопроса по вашему ответу. Во-первых, код в вашем insert_prefix: head = & (* head) - ›next; я думаю (* голова) - ›следующий адрес принадлежит * следующему в префиксе, почему вы добавили '&'? Во-вторых, вы сказали, что мой код разбился в insert_prefix, потому что я вставляю узел в список групп, сохраняя при этом список отсортированным. Я не могу понять, почему они делают это одновременно. Спасибо за чтение 07.01.2018
  • Я не сказал, что сбой произошел из-за того, что вы вставили узел в orrer, просто это произошло там. Я просто поместил ваш код в отладчик, создал несколько примеров данных и обнаружил, где произошел сбой. Как только я увидел настоящую проблему (а именно, что указатели на заголовки не были указателями), я не стал выяснять, что именно произошло. Я думаю, что стоит изучить технику указателя на указатель узла, поэтому я просто переписываю insert_index с нуля, вместо того, чтобы пытаться адаптировать вашу функцию. 07.01.2018
  • Унарный оператор & принимает адрес переменной и тем самым создает на нее указатель. В этом подходе адресом является адрес указателя, который указывает на текущий узел, который находится &head в начале и &prev->next, когда вы перемещаетесь по списку. Вы можете получить доступ к этим указателям и обновить их через ´ * head. Because both cases are represented by just ´*head, вам не нужно выделять эти случаи. 07.01.2018
  • Новые материалы

    Как создать диаграмму градиентной кисти с помощью D3.js
    Резюме: Из этого туториала Вы узнаете, как добавить градиентную кисть к диаграмме с областями в D3.js. Мы добавим градиент к значениям SVG и применим градиент в качестве заливки к диаграмме с..

    Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что это выглядит сложно…
    Просто начните и учитесь самостоятельно Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что он кажется мне сложным, и я бросил его. Это в основном инструмент..

    Лицензии с открытым исходным кодом: руководство для разработчиков и создателей
    В динамичном мире разработки программного обеспечения открытый исходный код стал мощной парадигмой, способствующей сотрудничеству, инновациям и прогрессу, движимому сообществом. В основе..

    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..

    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..

    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..


    Для любых предложений по сайту: [email protected]