鏈接列表插入排序在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); 
}