1

このプログラムで分割リストが常に空なのはなぜですか? (これは、Linked Lists のウィキペディアページのコードから派生したものです。)

/* 
    Example program from wikipedia linked list article
    Modified to find nth node and to split the list
*/

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

typedef struct ns
{
    int data;
    struct ns *next; /* pointer to next element in list */
} node;

node *list_add(node **p, int i)
{
    node *n = (node *)malloc(sizeof(node));
    if (n == NULL)
        return NULL;

    n->next = *p; //* the previous element (*p) now becomes the "next" element */
    *p = n;       //* add new empty element to the front (head) of the list */
    n->data = i;

    return *p;
}

void list_print(node *n)
{
    int i=0;
    if (n == NULL)
    {
        printf("list is empty\n");
    }
    while (n != NULL)
    {
        printf("Value at node #%d = %d\n", i, n->data);
        n = n->next;
        i++;
    }
}

node *list_nth(node *head, int index) {
    node *current = head;
    node *temp=NULL;
    int count = 0; // the index of the node we're currently looking at
    while (current != NULL) {
        if (count == index)
            temp = current;
        count++;
        current = current->next;
    }
    return temp;
}
/* 
This function is to split a linked list:
Return a list with nodes starting from index 'int ind' and
step the index by 'int step' until the end of list.
*/
node *list_split(node *head, int ind, int step) {
    node *current = head;
    node *temp=NULL;
    int count = ind; // the index of the node we're currently looking at
    temp = list_nth(current, ind);
    while (current != NULL) {
        count = count+step;
        temp->next = list_nth(head, count);
        current = current->next;
    }

    return temp; /* return the final stepped list */
}

int main(void)
{
    node *n = NULL, *list1=NULL, *list2=NULL, *list3=NULL, *list4=NULL;
    int i;
    /* List with 30 nodes */
    for(i=0;i<=30;i++){
        list_add(&n, i);
    }
    list_print(n);

    /* Get 1th, 5th, 9th, 13th, 18th ... nodes of n etc */ 

    list1 = list_split(n, 1, 4);

    list_print(list1);

    list2 = list_split(n, 2, 4); /* 2, 6, 10, 14 etc */   
    list_print(list2);

    list3 = list_split(n, 3, 4); /* 3, 7, 11, 15 etc */   
    list_print(list3);

    list3 = list_split(n, 4, 4); /* 4, 8, 12, 16 etc */   
    list_print(list4);

    getch();
    return 0;
}
4

4 に答える 4

5 
 temp = list_nth(current, ind);

 while (current != NULL) {
        count = count+step;
        temp->next = list_nth(head, count);
        current = current->next;
    }

分割を開始する正しいアイテムを見つけていますが、それ以降の temp に何が起こるかを見てください... temp->next にのみ割り当てます。

分割リストの先頭と、新しい項目を挿入する末尾の両方を追跡する必要があります。

于 2008-11-27T18:03:43.500 に答える
0

list_split が何を返すかについての説明は非常に明確ですが、元のリストに何が起こるかは明確ではありません。変更されるべきではないと仮定すると、次のようになります。

node *list_split(node *head, int ind, int step) {
    node *current = head;
    node *newlist=NULL;
    node **end = &newlist;
    node *temp = list_nth(current, ind);

    while (temp != NULL) {
        *end = (node *)malloc(sizeof(node));
        if (*end == NULL) return NULL;
        (*end)->data = temp->data;
        end = &((*end)->next);
        temp = list_nth(temp, step);
    }

    return newlist; /* return the final stepped list */
}

(おそらく、指定された場所に新しいノードを挿入する list_insert ルーチンを除外する必要があります。list_add は、常にリストの先頭に追加されるため、あまり役に立ちません。)

于 2008-11-27T18:20:54.353 に答える
0

list_nthを計算しているときに、リストの最初のレコードをスキップしているようにも見えます。C は通常ゼロからカウントを開始することを思い出してください。

リンク リスト図を作成し、ロジックに従います。

[0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->...->[10]->[NULL]
于 2008-11-27T19:28:08.273 に答える
0

実際、プログラムには複数の問題があります。

  • インデックスは、リンクされたリストのコンテンツに対処するためのネイティブな方法ではありません。通常、ノードまたはイテレーター (ノードへの偽装ポインター) へのポインターが使用されます。インデックスを使用すると、ノードへのアクセスO(n)は定数ではなく線形の複雑さ ( ) になりO(1)ます。

  • list_nthコピーではなく、リスト内の「ライブ」ノードへのポインターを返すことに注意してください。temp->nextinに代入することでlist_split、新しいリストを作成するのではなく、元のリストを再配線しています (ただし、意図的なものでしょうか?)

  • 内list_splitでtempは は決して進められないため、ループはテールではなくヘッドにノードをアタッチし続けます。

  • list_nthリスト全体を最初から反復してノードを見つけるために を使用しているため、線形時間ではなくlist_split二次時間 ( ) が含まれています。. O(n**2)_ list_nthまたは、次のように書くこともできますcurrent = list_nth(current, step)。

  • 【追記】言い忘れました。元のリストを再配線しているため、書き込みlist_nth(head, count)は正しくありません。変更されていないリストではなく、「ショートサーキット」リストを移動します。

于 2008-11-27T18:18:51.253 に答える