2015-04-05 149 views
0

試圖編寫一個函數,要求用戶輸入一個整數,然後按升序將其插入到鏈接列表中。插入已排序的鏈接列表

typedef struct _listnode{ 
    int item; 
    struct _listnode *next; 
} ListNode;   

typedef struct _linkedlist{ 
    int size; 
    ListNode *head; 
} LinkedList;   

void insertSortedLinkedList(LinkedList *l) 
{ 
    ListNode *cur; 
    int x; 
    printf("please input an integer you want to add to the linked list:"); 
    scanf("%d", &x); 

    if (l->head == NULL) // linkedlist is empty, inserting as first element 
    { 
     l->head = malloc(sizeof(ListNode)); 
     l->head->item = x; 
     l->head->next = NULL; 
    } 
    else 
    { 
     cur = l->head; 
     if (x < cur->item) // data is smaller than first element, we will insert at first element and update head. 
     { 
      cur->next->item = cur->item; // store current element as next element. 
      cur->item = x; 
      cur->next = cur->next->next; 
     } 
    } 
    l->size++; 
} 

函數尚未完成,但爲什麼我的代碼不工作,如果數據比第一個元素小?

+0

請注意,以下劃線開頭的名字基本上是爲'實現'使用的(它稍微比這更微妙,但只是稍微有點)。避免使用這些名字。 – 2015-04-05 05:47:25

回答

1

首先,你需要爲新元素創建節點,就像這樣:

ListNode* newNode = malloc(sizeof(ListNode)); 
newNode ->item = x; 

現在改變你的代碼:

if (x < l->head->item) // data is smaller than first element, we will insert at first element and update head. 
    { 
     newNode->next = l->head; 
     l->head = newNode; 
    } 
} 

像你說的代碼是不完整的肯定和循環經列表直到找到插入新節點的正確位置。

可以編寫1個代碼來處理所有情況。 處理這些情況的一種常見方式是這樣做,即讓節點位於鏈接列表的頭部。

1

插入函數的else分支假定cur->next不是NULL(因爲您將值設置爲cur->next->item)。現在設想插入兩個數字(第二個小於第一個)。在第一次插入中,l->head->next設置爲NULL。因此,在第二次插入時,程序在嘗試將cur->next->item設置爲某個值時會崩潰。您應創建節點(即通過malloc()分配內存),根據需要初始化節點以包含字段,然後將其設置爲cur->next