鏈接列表執行

Question

任何人都可以檢查並查看鏈接列表實現是否存在錯誤？嘗試迭代鏈表時，我不斷收到seg錯誤。

我想通過「process_command」中的「root」迭代鏈接列表，但是當我嘗試訪問root-> child時，會出現seg fault錯誤。

實現，我使用來標記一個字符串，並把它們放到一個鏈表節點

typedef struct _node { 
    struct _node *child; 
    char *command; 
} Command_list; 

兩個功能。

Command_list *process_command(char command_line[256]) 
{ 
    printf("Command: %s", command_line); 

    //allocate space for root & child 
    Command_list *root = (Command_list*)malloc(sizeof (Command_list)); 
    Command_list *child = (Command_list*)malloc(sizeof (Command_list)); 

    char *token; 
    char *saveptr; 
    //get the first part of the string 
    token = strtok_r(command_line, " ", &saveptr); 

    //if the first word in the string is student 
    if(!strcmp(token, "student")) 
    { 
     //set the first word to the be root 
     root = insert_command(token, root); 
     printf("Current root command: %s \n", root->command); 
     child = root; 

     //get the next word from the string 
     token = strtok_r(NULL, " ", &saveptr); 

     //keep getting words from the list and store them in a linked-list 
     while(token != NULL) 
     { 
      child = insert_command(token, child); 
      token = strtok_r(NULL, " ", &saveptr); 
     } 
    } 
    return root; 
} 

Command_list *insert_command(char *value, Command_list *root) 
{ 
    printf("previous value: %s \n", root->command); 

    Command_list *child_node = (Command_list*)malloc(sizeof (Command_list)); 

    //if the node being passed in is empty, store the value in itself 
    if(root->command == NULL){ 
     root->command = value; 
     root->child = 0; 
     printf("Inserting value to root: %s \n", root->command); 
     return root; 
    } 
    //otherwise store the value in a child node 
    else 
    { 
     child_node->command = value; 
     child_node->child = 0; 
     printf("Inserting value to child node: %s \n", child_node->command); 
     return child_node; 
    } 
} 

編輯： 迭代代碼

{ 
    .... 
    Command_list *temp = (Command_list*)malloc(sizeof (Command_list)); 
    temp = root; 
    while(temp != NULL){ 
    printf("Command: %s\n", temp->command); 
    temp = temp->child; 
    .... 
} 

補充說我使用迭代碼。 該代碼似乎在代碼塊中正常工作，但它在終端中的第一個輸出之後停止迭代。

Answer 1

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

struct node 
{ 
node *next; 
char *command; 
}; 

void addNode(node **listHead, char *newData) 
{ 
    node *newNode; 

    if (*listHead == NULL) 
    { 
     *listHead = (node*)malloc(sizeof(node)); 
     newNode = *listHead; 
    } 
    else 
    { 
     newNode = *listHead; 
     while (newNode->next != NULL) 
      newNode = newNode->next; 
     newNode->next = (node*)malloc(sizeof(node)); 
     newNode = newNode->next; 
    } 
    newNode->next = NULL; 
    newNode->command = strdup(newData); 
} 

node *makeLinkedListOfWords(char *inputString) 
{ 
    char *token; 
    char *cmdClone; 
    char *delims = " "; 
    node *result = NULL; 

    cmdClone = strdup(inputString); 
    token = strtok(cmdClone, delims); 
    while (token != NULL) 
    { 
     addNode(&result, token); 
     token = strtok(NULL, delims); 
    } 
    free(cmdClone);  // EDIT: forgot to give back the duplicate string's memory 
    return result; 
} 


void printList(node *list) 
{ 
    int i = 0; 
    while (list != NULL) 
    { 
     printf("%d. '%s'\n", ++i, list->command); 
     list = list->next; 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    node *list1 = makeLinkedListOfWords("this is a test"); 
    node *list2 = makeLinkedListOfWords("so is this"); 
    node *list3 = makeLinkedListOfWords("and this is another"); 
    printList(list1); 
    printList(list2); 
    printList(list3); 
    return 0; 
} 

[編輯：所以是把這個輸出爲有序的列表中，編號爲1-11：哎呀：）

輸出：

1. 'this' 
2. 'is' 
3. 'a' 
4. 'test' 
1. 'so' 
2. 'is' 
3. 'this' 
1. 'and' 
2. 'this' 
3. 'is' 
4. 'another' 

Answer 2

當您分配Command_list，你不不初始化其成員。那麼測試(root->command == NULL)在insert_command將嚴格地說有未定義的結果。很有可能，這個測試會失敗，您將繼續創建一個子節點。稍後調用insert_command將添加到以此子節點爲根的列表。

您的迭代代碼將從root開始，其中未初始化command和child。如果打印command沒有失敗，則移動到子元素並幾乎可以肯定會打印它。

解決這個問題應該可以解決您的seg故障。你也有可能被整理了一些內存泄漏：

• 的結構在insert_command在root->command == NULL
• 的Command_list在迭代代碼
分配的情況下，分配給 child附近的 process_command
• child_node頂部

Answer 3

template<class T> 
ostream& operator<<(ostream& os, LinkedList<T>& ll) { 
    if(!(ll.isEmpty())) 
    { 
     //os<<temp->data; 
     int size=ll.size(); 
     int count=0; 
     while(count<size) 
     { 
      os<<ll.get(count); 
      if(count+1<size) 
       os<<","; 
      count++; 
     } 
    } 
    else 
    { 
     os<<"[]"; 
    } 

} 

template<class T>  
LinkedList<T>::LinkedList(){ 
    head=NULL; 
} 

template<class T> 
LinkedList<T>::LinkedList(const LinkedList<T>& other){ 
    this->head=0; 
    Node<T>* tempHead=other.getLeader(); 
    while(tempHead!=0) 
    { 
     Node<T> *temp = new Node<T>(tempHead->data); 
     temp->next = 0; 
     Node<T>* curr = this->getLeader(); 
     if (curr != 0) 
     { 
      while (curr->next != 0) 
      { 
      curr = curr->next; 
      } 
      curr->next = temp; 
     } 
     else 
     { 
      this->head = temp; 
     } 
     tempHead=tempHead->next; 
    } 
} 

template<class T> 
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& other){ 
    if(&other != this) 
    { 
     this->head=0; 
     Node<T>* tempHead=other.head; 
     while(tempHead!=0) 
     { 
      Node<T>* temp = new Node<T>(tempHead->data); 
      temp->next = 0; 
      Node<T>* curr = this->head; 
      if (curr != 0) 
      { 
       while (curr->next != 0) 
       { 
       curr = curr->next; 
       } 
       curr->next = temp; 
      } 
      else 
      { 
       this->head = temp; 
      } 
      tempHead=tempHead->next; 
     } 
    } 
    return *this; 


template<class T> 
LinkedList<T>* LinkedList<T>::clone() { 

    LinkedList<T>* list=new LinkedList<T>(*this); 
    return list; 

} 

template<class T> 
LinkedList<T>::~LinkedList(){ 

    Node<T>*temp; 
    while (head != NULL) 
    { 
    temp = head->next; 
    delete head; 
    head = temp; 
    } 
} 

template<class T> 
void LinkedList<T>::insert(int index, T data){ 

    Node<T> *n= new Node<T>(data); 
    if((0 <= index) &&(index<= size())) 
    { 
     if(index==0) 
     { 
      if(isEmpty()) 
      { 
       head=n; 
      } 
      else 
      { 
       Node<T>*skip=head; 
       head=n; 
       head->next=skip; 
      } 
     } 
     else 
     { 
      Node<T> *temp =head; 
      int count =1; 
      while(count!=index) 
      { 
       temp=temp->next; 
       count++; 
      } 
      n->next=temp->next; 
      temp->next=n; 
     } 
    } 
    else 
    { 
     throw ("invalid index"); 
    } 
    return ; 
} 

template<class T> 
T LinkedList<T>::remove(int index){ 
     T pet; 
    if(0 <= index && index<= size()-1) 
    { 
     if(!isEmpty()) 
     { 
      Node<T> *ret=getLeader(); 
      Node<T>* skip=NULL; 
      if(index!=0) 
      { 
      int i=1; 
      while(i!=(index)) 
      { 
       ret=ret->next; 
       i++; 
      } 
      skip=ret; 
      pet=get(index); 
      ret=ret->next; 
      if(ret->next==NULL) 
      { 
       delete ret; 
       skip->next=NULL; 
       ret=NULL; 
      } 
      else 
      { 
       skip->next=ret->next; 
       delete ret; 
       ret=NULL; 
      } 
     } 
     else 
     { 
       Node<T> *tmp = head->next; 
       pet=get(index); 
       delete head; 
       head = tmp; 
     } 
     return pet; 
     } 
     else 
     { 
      throw ("empty list"); 
     } 

    } 
    else 
    { 
     throw ("invalid index"); 
    }} 


template<class T> 
T LinkedList<T>::get(int index) const { 
    if(head!=NULL) 
    { 
     if(0 <= index && index<= size()-1) 
     { 
      int count=0; 
      Node<T>* place =head; 
      while(place!=NULL) 
      { 
       if(count==index) 
       { 
        return place->data; 
       } 
       count++; 
       place=place->next; 
      } 
    } 
     else 
     { 
      throw ("invalid index"); 
     } 
    } 
    else 
    { 
     throw("empty list"); 
    } 
} 

template<class T> 
bool LinkedList<T>::isEmpty(){ 
    if(head==0) 
    { 
     return true ; 
    } 
    else 
    { 
     return false; 
    } 
} 

template<class T> 
void LinkedList<T>::clear(){ 
    Node<T>*temp=head; 
    while(head!=NULL) 
    { 
     head=head->next; 
     delete temp; 
     temp=head; 
    } 
} 

template<class T> 
Node<T>* LinkedList<T>::getLeader() const{ 
    return head; 
} 

template<class T> 
ostream& LinkedList<T>::print(ostream& os){ 
    os<<*this; 
} 

template<class T> 
int LinkedList<T>::size() const { 
    int count=0; 
    Node<T> *temp =getLeader(); 
    while(temp!=NULL) 
    { 
     temp=temp->next; 
     count++; 
    } 
    return count; 
} 

template<class T> 
T LinkedList<T>::operator[](int index){ 
    return get(index); 
} 

template<class T> 
LinkedList<T>& LinkedList<T>::operator+(const LinkedList<T>& other){ 
    LinkedList<T>* ting=new LinkedList<T>(*this); 
    Node<T>* UGE=other.getLeader(); 
    int count=ting->size(); 
    int pos=0; 
    while(UGE!=NULL) 
    { 
     ting->insert(count,other.get(pos)); 
     UGE=UGE->next; 
     pos++; 
     count++; 
    } 
    return *ting; 
}