链接列表插入排序在c

Question

程序应该为节点做插入升序排序，首先它应该检查名称，如果名称相同，它应该排序的ID，我不知道是什么问题，不正确排序。

# include <stdio.h> 
# include <string.h> 
# include <stdlib.h> 

typedef struct nd{ 
int id; 
char name[20]; 
float gpa; 
struct nd *next; 
}node; 


typedef node *list; 

//--------------------------------------------------------------- 

int insertlist(list *head,char *buffer) 
{ 
list p,q,n; 
int m,num,k,sc; 
p=(list)malloc(sizeof(node)); 
num=sscanf(buffer,"%d %s %f",&(p->id),(p->name),(&p->gpa)); 
if(num!=3) 
{ 
    printf("info not complete\n"); 
    free(p); 
    return 1; 
} 
else 
{ 

    if(!*head) 
    { 
    *head=p; 
    p->next = NULL; 
    } 
//******** sorting tthe names and ids for equal names 
    else if(sc=strcmp((*head)->name,p->name)> 0 || ((sc == 0) && ((*head)->id > p->id))) 
     {//head is modified 
     p->next=*head; 
     *head=p; 
     } 

    else{ 
     n=*head; 
     q=n->next; 
     while(q && ((sc=strcmp(q->name,p->name)<0) || ((sc == 0) && (q->id < p->id)))) 
      { 
      n=q; 
      q=q->next; 
      } 
     n->next=p; 
     p->next=q; 
     } 
} 

return 0; 
} 

//------------------------------------------------------ 

int main() 
{ 
int id,r; 
list head,p; 
FILE *fp; 
char c,buffer[100],filename[10]; 
if ((fp=fopen("student.txt","r"))==NULL) 
{ 
    printf("error opening %s",filename); 
    exit(1); 
} 
else 
{ 
head=NULL; 

while(fgets(buffer,100,fp)!=NULL) 
    { 
    buffer[strlen(buffer)-1]=='\0'; 
    r=insertlist(&head,buffer); 
    } 
fclose(fp); 
} 

for(p=head;p!=NULL;p=p->next) 
    printf("%d %s %f\n\n",p->id,p->name,p->gpa); 
} 

的student.txt内容的一个例子：

121513 ala 45.00 
121510 wang 21.00 
145852 frank 26.00 
151515 ala 25.00 

Answer 1

你的排序问题是operator precedence

<之一，>具有更高的优先级比=，这意味着它会首先评估，那么分配将发生。

所以你的字符串比较在这两个地方：

else if(sc=strcmp((*head)->name,p->name)> 0 || ((sc == 0) && ((*head)->id > p->id))) 
... 
while(q && ((sc=strcmp(q->name,p->name)<0) || ((sc == 0) && (q->id < p->id)))) 

是错误的。 sc分别获得的strcmp((*head)->name,p->name)> 0和strcmp(q->name,p->name)<0值（注意：这将永远是1或0，从未-1）

如果你简单地调整你的代码，例如：

else if((sc=strcmp((*head)->name,p->name))> 0 || ((sc == 0) && ((*head)->id > p->id))) 
... 
while(q && (((sc=strcmp(q->name,p->name))<0) || ((sc == 0) && (q->id < p->id)))) 

你会看到它加工。故事的道德：不要试图对你的支撑物或支架吝啬，它不会花费任何费用，它使代码更清晰，并且可以节省您调试类似此类问题的麻烦。

Answer 2

头是一个指针，以改变它的功能，你需要一个指针传递给它。指向指针的指针。

声明是这样的：

int insertlist(list **head,char *buffer) 

这样称呼它：

r=insertlist(&(&head),buffer); 

然后在功能变化无处不在，你引用它去参考指针。

Answer 3

首先，解决这个问题：

buffer[strlen(buffer)-1]=='\0'; 

这是一个平等的比较;不是任务。我相信你会试图在缓冲区的末尾丢掉换行符。如果是这种情况，你可能想确保它有一个换行符开始（输入文件的最后一行，例如可能不会结束于一个。无论如何，这仍然是坏的，需要

接下来，你的排序循环有问题，我在下面包括一个，希望更容易阅读，因此理解，删除了逻辑缺陷（以及相当多的其他课外活动）：

int insertlist(list *head, char *buffer) 
{ 
    list p=NULL, q=NULL; 
    int sc=0; 

    /* allocate new node */ 
    p = calloc(1, sizeof(*p)); 
    if(3 != sscanf(buffer,"%d %s %f",&(p->id),(p->name),(&p->gpa))) 
    { 
     printf("info not complete\n"); 
     free(p); 
     return 1; 
    } 

    /* initially wire p->next to our list head. then, walk list, 
     advancing p->next. break on first "less" condition */ 
    p->next = *head; 
    while (p->next) 
    { 
     /* broken out here for clarity; break on first "less" */ 
     sc = strcmp(p->name, p->next->name); 
     if (sc < 0 || (sc == 0 && p->id < p->next->id)) 
      break; 
     q = p->next; 
     p->next = q->next; 
    } 

    /* non-null means we wire q->next to p */ 
    if (q) 
     q->next = p; 

    /* else p is the new head; what head was prior is already in p->next */ 
    else 
     *head = p; 

    return 0; 
} 

具有以下输入文件测试：

0001 Brook 3.50 
0002 James 3.51 
0003 Katie 3.52 
0004 James 3.87 
0005 Brook 2.70 

个

结果：

1 Brook 3.500000 

5 Brook 2.700000 

2 James 3.510000 

4 James 3.870000 

3 Katie 3.520000 

我强烈想，当你想看看代码是如何工作来解决这些问题和时，建议你通过在调试器的单步执行代码。

最后，不要添加侮辱伤害，你永远不会释放你的名单。即它在程序退出时泄漏内存，仅次于在执行期间内存“”的内存泄漏。走这个列表并释放内存。这是一个很好的习惯。

---

编辑 OP请求释放链表：

现在，在main()的return语句之前结束就足够了。在某些时候你应该考虑编写一个函数来为你做这个：

while (head) 
{ 
    list p=head; 
    head=head->next; 
    free(p); 
}