c - リンクリストの実装

Question

リンクリストの実装にエラーがあるかどうか、誰でも確認できますか? リンクされたリストを繰り返し処理しようとすると、セグフォールトが発生し続けます。

"process_command" の "root" からリンクリストを繰り返し処理しようとしていますが、root->child にアクセスしようとすると、seg fault エラーが発生します。

ノードの実装

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

文字列をトークン化し、それらをリンクリストに入れるために使用している2つの関数。

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

私が使用している反復コードを追加しました。コードはコードブロックで正常に動作しているように見えますが、ターミナルでの最初の出力後に反復が停止します。

score 0 · Accepted Answer

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

[編集: SO は、この出力を 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'

score 0 · Accepted Answer

を割り当てるときCommand_list、そのメンバーを初期化しません。のテスト(root->command == NULL)はinsert_command、厳密に言えば未定義の結果になります。おそらく、このテストは失敗し、子ノードの作成に進みます。後でを呼び出すとinsert_command、この子ノードをルートとして持つリストに追加されます。

反復コードは、root初期化されていないcommandとchild. 印刷commandが失敗しない場合は、子要素に移動して印刷するとほぼ確実に失敗します。

これを修正すると、セグフォールトが修正されます。また、整理できるメモリリークがいくつかあります。

childの上部近くに割り当てられた構造体process_command
child_nodeinsert_command場合にはroot->command == NULL
Command_list反復コードで割り当てられた

score -1 · Accepted Answer

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

c - リンクリストの実装

3 に答える 3

Related

Reference