0

谁能检查我的链表实现是否有错误?尝试遍历链表时,我不断遇到段错误。

我正在尝试从“process_command”中的“root”遍历链表,但是当我尝试访问 root->child 时,我会收到 seg 错误错误。

节点的实现

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;
    .... 
}

添加了我正在使用的迭代代码。该代码似乎在代码块中运行良好,但在终端中的第一个输出后停止迭代。

4

3 回答 3

0
#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 :grrr: )

输出:

1. 'this'
2. 'is'
3. 'a'
4. 'test'
1. 'so'
2. 'is'
3. 'this'
1. 'and'
2. 'this'
3. 'is'
4. 'another'
于 2012-09-30T07:14:31.447 回答
0

当你 allocate 时Command_list,你不会初始化它的成员。(root->command == NULL)严格来说,测试insert_command将有未定义的结果。然后,此测试很可能会失败,您将继续创建子节点。稍后调用insert_command将添加到以该子节点为根的列表中。

您的迭代代码将从未root初始化的command和开始child。如果打印command没有失败,移动到子元素并打印它几乎肯定会失败。

解决此问题应该可以解决您的段错误。您还有一些内存泄漏,可以清理:

  • 分配给child靠近顶部的结构process_command
  • child_nodeinsert_command这种情况下root->command == NULL
  • 在您的Command_list迭代代码中分配
于 2012-09-30T07:21:28.260 回答
-1
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;
}
于 2016-11-16T18:39:13.337 回答