链表插入排序在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 completen");
  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]=='';
    r=insertlist(&head,buffer);
   }
fclose(fp);
 }
for(p=head;p!=NULL;p=p->next)
  printf("%d  %s  %fnn",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

您的排序问题是操作符优先级之一

<和>具有比=更高的优先级，这意味着它将首先求值，然后进行赋值。

你的字符串在这两个地方比较:

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

head是一个指针，所以为了在函数中改变它，你需要传递一个指针给它。指向指针的指针

这样声明:

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

这样写:

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

然后在函数中更改所有引用它的地方以取消对指针的引用

Answer 3

首先，修复这个:

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

这是一个相等比较;不是任务。我相信你是想在缓冲区的末尾丢掉换行符。如果是这种情况，您可能想要确保具有的换行符以抛出(例如，输入文件的最后一行不能以换行符结尾)。无论如何，这仍然是坏的，需要修复。

接下来，排序循环有问题。我在下面附上了一个，希望更容易阅读，因此也更容易理解，删除了逻辑缺陷(以及相当多的其他课外活动):

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 completen");
        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

我强烈建议您在尝试修复这些问题时在调试器中单步检查代码，和当您想了解代码是如何工作的时候。

最后，不要再往伤口上撒盐了，你永远不会释放你的清单。也就是说，它在程序退出时泄漏内存，在"坏"级别中，这仅次于在执行期间泄漏内存。遍历列表，释放记忆。这是一个很好的习惯。

---

EDIT OP请求释放链表:

现在，在main()语句的末尾return语句之前就足够了。有时候你应该考虑写一个函数来完成这个任务:

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