3

LinkedListにchar*を追加して、linkedListが常にアルファベット順にソートされるようにするメソッドを作成しようとしています。LinkedItem構造体を定義するコードが与えられました：

// Define our list item as 'struct ListItem', and also 
// typedef it under the same name.
typedef struct ListItem {
  char *s;
  struct ListItem *p_next;
} ListItem;

リストの先頭にアイテムを追加する方法もあります。

// Adds a new item to the beginning of a list, returning the new
// item (ie the head of the new list *)
ListItem* add_item(ListItem *p_head, char *s) {  
    // Allocate some memory for the size of our structure.
    ListItem *p_new_item = malloc(sizeof(ListItem));
    p_new_item->p_next = p_head;       // We are the new tail.
    p_new_item->s = s;     // Set data pointer. 
    return p_new_item;
}

これが私のコードです。後で詳しく説明します。

ListItem* addSortedItem(ListItem *p_head, char *s){         
    if(p_head==NULL)//if the list is empty, we add to the beginning
        return add_item(p_head,s);
    ListItem* p_new_item = malloc(sizeof(ListItem));
    ListItem *p_current_item = p_head; //makes a pointer to the head of the list


    while (p_current_item) {    // Loop while the current pointer is not NULL
        printf("entering while loop with current=%s\n",p_current_item->s);
        // now we want to look at the value contained and compare it to the value input     
        if(aThenB(s,p_current_item->s)!=TRUE){
            // if A goes after B, we want to go on to look at the next element
            p_current_item=p_current_item->p_next;
        } else if (aThenB(s,p_current_item->s)==TRUE) {printf("entered elseif\n");      
            p_head=add_item(p_current_item,s);
            return p_head;          
        } else {printf("WHY DID WE EVER REACH THE ELSE!?"); return p_head;}
    }
}

ここで、aThenB（StringA、StringB）は、AとBの正しい並べ替え順序がA、次にBの場合はTRUEを返し、それ以外の場合はfalseを返します。 -）

私のテストデータ（つまり"sheep i"、0から10までのi）で起こっていることは、順序の入力に応じて、1つの要素のみを返すか、要素をランダムにスキップすることです。より多くのコードを含めることができますが、少し面倒です。

私の問題は、ポインタとその動作を完全に理解していないことに起因していると思います。p_currentがリストを移動している間、p_headが常にヘッドを指していることを確認したいと思います。しかし、p_currentが最後の要素に到達すると、セグメンテーション違反も発生するため、どこが間違っているのかわかりません。

私のコードを正しく返す方法について助けてくれてありがとう:-)

編集：addSortedItem（）は、メインメソッドの次のブロックで呼び出されます。

    // The empty list is represented by a pointer to NULL.
    ListItem *p_head = NULL;
    ListItem *p_head2=NULL;
    // Now add some items onto the beginning of the list.
    int i;
    for (i=0; i<NO_ITEMS; i++) {

    // Allocate some memory for our string, and use snprintf to
    // create a formatted string (see GNU API docs) much like printf
    // but instead writing to memory rather than the screen.
    char* s = malloc(MAX_DATA_CHARS);
    snprintf(s, (size_t) MAX_DATA_CHARS, "sheep %d", i);
    p_head = addSortedItem(p_head, s);
    }
4

3 に答える 3

1

リンクされたリストの途中または最後に新しい要素を追加する際にエラーが発生しました。関数でaddStoredItemは、newItem から currentItem へのポインターを作成しますが、前の要素から newItem へのリンクを考慮していません。

呼び出す前の最初の連結リストaddStoredItem

item1-->item2-->item4-->item5

item3addStoredItemを追加するための呼び出し後のリンクされたリスト

item1-->item2-->item4-->item5
                ^
                |
                item3

ご覧のとおり、 item4から始まるサブ リンク リストの先頭に新しいアイテムを追加しましたが、item2 から item3へのリンクを作成していないため 、リンクを完了するために前のアイテムへのポインタを保持する必要があります。 .

頭にadd_item()アイテムを追加できる関数

リンクされたリストの最後にアイテムを追加しようとすると同じこと

item1-->item2-->item4-->item5    NULL
                                 ^
                                 |
                                 item6

item6は別のヘッドとして追加され、item5 (前) から item6 (新規) へのリンクはありません

あなたのaddStoredItem()機能はこのように修正することができます

ListItem* addSortedItem(ListItem *p_head, char *s){         
    if(p_head==NULL)//if the list is empty, we add to the beginning
        return add_item(p_head,s);
    struct ListItem* p_new_item = malloc(sizeof(ListItem));
    ListItem *p_current_item = p_head; //makes a pointer to the head of the list
    ListItem *p_prev_item = NULL; //FIXED

    while (p_current_item) {    // Loop while the current pointer is not NULL
        printf("entering while loop with current=%s\n",p_current_item->s);
        // now we want to look at the value contained and compare it to the value input     
        if(aThenB(s,p_current_item->s)!=TRUE){
            // if A goes after B, we want to go on to look at the next element
            p_prev_item = p_current_item; //FIXED
            p_current_item=p_current_item->p_next;
        } else if (aThenB(s,p_current_item->s)==TRUE) {printf("entered elseif\n");      
            break;        
        } else {printf("WHY DID WE EVER REACH THE ELSE!?"); return p_head;}
    }

    if (p_prev_item!=NULL) //FIXED
        p_prev_item->p_next=add_item(p_current_item,s); //FIXED
    else //FIXED
        p_head=add_item(p_current_item,s);//FIXED
    return p_head; //FIXED
}

固定回線は で示されます//FIXED

于 2012-10-10T16:42:44.580 に答える
0

サポート内容:

#define FALSE 0
#define TRUE 1
#define aThenB(a,b) (strcmp(a,b) <=0 ? TRUE : FALSE)

ポインターへのポインターを受け入れるように関数のシグネチャを変更することで、すべての特殊なケースを回避できます。

void addSortedItem(ListItem **pp_head, char *s){         
    ListItem *p_new_item ;

    for (       ;*pp_head; pp_head = &(*pp_head)->p_next) {    
        if (aThenB(s,(*pp_head)->s)==FALSE) break;
    }

    p_new_item = malloc(sizeof *p_new_item);
    p_new_item->s = s;

    p_new_item->p_next = *pp_head;
    *pp_head = p_new_item;
}

呼び出し元は次のことを行う必要があります。

ListItem *root = NULL;
addSortedItem( &root, "sheep#0");
于 2012-10-10T17:14:33.040 に答える
0

最初p_headは isNULLであるため、addSortedItem関数を入力すると、リストが作成され、最初の文字列が追加されます。それは大丈夫だ。
しかし、2 番目の項目 (この場合は「羊 1」) を追加すると、while (p_current_item)ループに入ります。への呼び出しがaThenB返さFALSEれ、次の要素に移動します.. NULL! 実際、現時点では、p_head次のようになります。

p_head {
s = "sheep 0",
p_next = NULL
}

while条件が真ではなく、関数を終了すると、何も追加されませんでした。次のような
条件を最初に追加できます。if

if (p_current_item->next == NULL)
  p_current_item->next = addSortedItem(NULL, s);
else
  p_current_item = p_current_item->next;

また、その言い方p_head=add_item(p_current_item,s);は間違っています。リストが次のようなものであるとします。

"sheep 1" -> "sheep 2" -> "sheep 4" -> "sheep 5"

"sheep 3" を追加すると、次のようになります。

"sheep 1" -> "sheep 2" -> "sheep 3" -> "sheep 4" -> "sheep 5"
                          ^
                          |
                          p_head

「羊 0」を追加することはできなくなります。addSortedItemの戻り値をnew として返さないp_head

于 2012-10-10T15:46:47.377 に答える