鏈接列表段錯誤。 c

Question

我必須編寫這個代碼來創建一個鏈表。以下代碼如下。問題在於我在代碼中的某個地方進行了segfa，並且我無法弄清楚在哪裏。如果任何人都可以幫助我找到並理解（這是最重要的部分）段錯誤來自哪裏，將不勝感激。

#include "linkedlist.h" 
#include <stdio.h> 
#include <stdlib.h> 


/* Alloc a new node with given data. */ 
struct ListNode* createNode(int data) { 
    struct ListNode *new_node = (struct ListNode *)malloc(sizeof(struct ListNode)); 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
} 

/* Insert data at appropriate place in a sorted list, return new list head. */ 
struct ListNode* insertSorted(struct ListNode* head, int inputData) 
{ 

    struct ListNode * nextIS = NULL; 
    struct ListNode * newNodeIS = NULL; 
    struct ListNode * currIS = head; 
    struct ListNode * listHeadIS = currIS; 
    if (currIS == NULL) 
    { 
     listHeadIS = createNode(inputData); 
     return listHeadIS; 
    } 
    while (currIS->next != NULL) 
    { 
     nextIS = currIS->next; 

     if (currIS->data < inputData) 
     { 
      if (nextIS->data >= inputData) 
      { 

       nextIS->next = createNode(inputData); 
       newNodeIS = nextIS->next; 
       if (newNodeIS->data > listHeadIS->data) 
       { 
        listHeadIS = newNodeIS; 
       } 
      } 
     } 
     currIS = currIS->next; 
    } 

    return listHeadIS; 
} 
/* Remove data from list pointed to by headRef, changing head if necessary. 
* Make no assumptions as to whether the list is sorted. 
* Memory for removed node should be freed. 
* Return 1 if data was present, 0 if not found. */ 
int removeItem(struct ListNode** headRef, int data) 
{ 
    while (*headRef && (*headRef)->data != data) 
     headRef = &(*headRef)->next; 

    if (*headRef) 
    { 
     struct ListNode *tmp = *headRef; 
     free(tmp); 
     *headRef = tmp->next; 

     return 1; 
    } 
    return 0; 
} 

/* Insert data at head of list, return new list head. */ 
struct ListNode* pushStack(struct ListNode* head, int data) 
{ 
    int dataPush = data; 

    struct ListNode * tempPush = (struct ListNode*)malloc(sizeof(struct ListNode)); 
    tempPush->data = dataPush; 
    tempPush->next = head; 
    *head = *tempPush; 
    return tempPush; 
} 

/* Remove and return data from head of non-empty list, changing head. 
* Memory for removed node should be freed. */ 
int popStack(struct ListNode** headRef) 
{ 
    struct ListNode * tempPop = *headRef; 
    int tempData; 

    free(tempPop); 
    tempData = tempPop->data; 
    tempPop = tempPop->next; 

    return tempData; 
} 

/* Return length of the list. */ 
    int listLength(struct ListNode* head) 

{ 
    int count = 0; 
    struct ListNode* current = head; 
    while (current != NULL) { 
    count++; 
    current=current->next; 
    } 
    return(count); 
} 

/* Print list data on single line, separated with spaces and ending 
* with newline. */ 
void printList(struct ListNode* head) 
{ 

    if (head != NULL) 
    { 

     while (head->next != NULL) 
     { 

      printf("%d\n", head->data); 
      head = head->next; 
     } 
    } 
} 
/* Free memory used by the list. */ 
void freeList(struct ListNode* head) 
{ 
    struct ListNode* tmp; 

    while (head != NULL) 
    { 
     tmp = head; 
     head = head->next; 
     free(tmp); 
    } 
} 

/* Reverse order of elements in the list */ 
void reverseList(struct ListNode** headRef) 
{ 
    struct ListNode * origRL = *headRef; 
    struct ListNode * nextRL = NULL; 
    struct ListNode * prevRL = NULL; 
    while (origRL->next != NULL); 
    { 
     nextRL = origRL->next; 
     prevRL = origRL; 
     origRL = nextRL; 
     origRL->next = prevRL; 
    } 

} 

用於測試它的文件（linkedlist.c）包含在此評論下面。

#include <stdio.h> 
#include <stdlib.h> 
#include "linkedlist.h" 

int main(int argc, char** argv) 
{ 
    int i, n; 
    struct ListNode* head = NULL; 
    struct ListNode* stack = NULL; 

    printf("empty list: "); 
    printList(head); 

    for(i = 0; i < 23; ++i) 
    { 
    n = (i*17+11) % 23; 
    head = insertSorted(head, n); 
    stack = pushStack(stack, n); 
    } 

    printf("filled list: "); 
    printList(head); 
    printf("list length = %d\n", listLength(head)); 

    printf("filled stack: "); 
    printList(stack); 
    printf("stack size = %d\n", listLength(stack)); 

    for(i = -4; i < 25; i+=4) 
    { 
    n = removeItem(&head, i); 
    if(!n) printf("remove did not find %d\n", i); 
    } 

    printf("list after removes: "); 
    printList(head); 
    printf("list length = %d\n", listLength(head)); 

    for(i = 0; i < 5; ++i) 
    { 
    printf("pop: %d\n", popStack(&stack)); 
    } 

    printf("stack after pops: "); 
    printList(stack); 
    printf("stack size = %d\n", listLength(stack)); 

    reverseList(&head); 
    printf("list after reverse: "); 
    printList(head); 

    freeList(head); 
    head = NULL; 

    freeList(stack); 
    stack = NULL; 

    return 0; 
} 

預期輸出是

empty list: 
filled list: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
list length = 23 
filled stack: 17 0 6 12 18 1 7 13 19 2 8 14 20 3 9 15 21 4 10 16 22 5 11 
stack size = 23 
remove did not find -4 
remove did not find 24 
list after removes: 1 2 3 5 6 7 9 10 11 13 14 15 17 18 19 21 22 
list length = 17 
pop: 17 
pop: 0 
pop: 6 
pop: 12 
pop: 18 
stack after pops: 1 7 13 19 2 8 14 20 3 9 15 21 4 10 16 22 5 11 
stack size = 18 
list after reverse: 22 21 19 18 17 15 14 13 11 10 9 7 6 5 3 2 1 

Answer 1

你的段錯誤在pushStack()功能發生。行*head = *tempPush在這裏沒有意義。當您傳遞指針head時，會嘗試解除引用它，導致段錯誤。您可以刪除此行，並刪除不必要的變量dataPush。此外，there is no reason to cast the result of malloc()，並且最好使用您分配的指針作爲sizeof()的參數。如果稍後更改類型，則避免在sizeof()中使用顯式類型意味着更少要記住更新。這意味着，新pushStack()功能是：

struct ListNode * pushStack(struct ListNode *head, int data) 
{ 
    struct ListNode *tempPush = malloc(sizeof(*tempPush)); 
    tempPush->data = data; 
    tempPush->next = head; 

    return tempPush; 
} 

你insertSorted()功能包含一個錯誤。我不確定這是在哪裏;你的功能比較複雜，所以我只爲你寫了一個新功能。同樣，您的printList()功能可以簡化。我還修改了printList()功能，以配合您所提供的預期輸出例如：

struct ListNode * insertSorted(struct ListNode *head, int inputData) 
{ 
    struct ListNode *prev = NULL; 
    struct ListNode *curr = head; 
    struct ListNode *new_node = createNode(inputData); 

    while (curr) { 
     if (inputData < curr->data) { 
      new_node->next = curr; 
      if (prev) 
       prev->next = new_node; 
      return (prev ? head : new_node); 
     } 
     prev = curr; 
     curr = curr->next; 
    } 
    if (head) { 
     new_node->next = NULL; 
     prev->next = new_node; 
    } else { 
     head = new_node; 
    } 

    return head; 
} 

void printList(struct ListNode *head) 
{ 
    struct ListNode *curr = head; 

    while (curr) { 
     printf("%d ", curr->data); 
     curr = curr->next; 
    } 
    putchar('\n'); 
} 

有了這些變化時，輸出開始將自己的預期。您的listLength()功能存在問題，並且popStack()功能存在問題。可能還有其他問題。我會讓你解決這些問題;我的建議應該讓你開始。如果你仍然有問題，請給我評論，我會盡力幫助你。