Это мой код.
#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 данных. Я хочу знать, как решить мою проблему, спасибо, что прочитали мой вопрос.
..... Наконец, мой английский, возможно, недостаточно хорош, чтобы точно объяснить вопрос ..... пожалуйста, простите меня ^^
insert_index
с нуля, вместо того, чтобы пытаться адаптировать вашу функцию. 07.01.2018&
принимает адрес переменной и тем самым создает на нее указатель. В этом подходе адресом является адрес указателя, который указывает на текущий узел, который находится&head
в начале и&prev->next
, когда вы перемещаетесь по списку. Вы можете получить доступ к этим указателям и обновить их через ´ * head. Because both cases are represented by just ´*head
, вам не нужно выделять эти случаи. 07.01.2018