C - リンクされたリストのノードを移動する

Question

私はリンクされたリストを扱っています。リストのノードをある場所から別の場所に移動したいと思います。

リンクリストの構造体は次のとおりです。

struct Frame 
{ 
    char* name; // Name and path are just pointers to strings 
    unsigned int duration; 
    char* path; 
}; 

typedef struct Frame frame_t; 

そして：

struct Link 
{ 
    frame_t *frame; 
    struct Link *next; 
}; 

今、私は必要なもの

（それは私が、ではない私の選択にそれを行うために要求された方法です）リンクリストと文字列（ノードの1つの名前）と整数を受け取り、その名前のノードをその位置（受け取った整数）に移動する関数です。最初の位置は0ではなく1です。何リストには、ノードが含まれている場合 ：

例えばので

）要求された[PIC1、PIC2、PIC3、PI4] とPOS 3に「PIC1」を移動するために要求されたユーザーが、その後、新たなリストは次のようになります。

私はいくつかのバージョンを試しましたが、常に80％しか働いていませんでした（リストを切り捨てたり、正しい場所に移動していない）。何か案は？

相続人は、私が試した機能：

void changePos(link_t** anchor_link, char* name1, int pos) 
{ 
    link_t* currLink = *anchor_link; 
    link_t* temp = NULL; 
    link_t* temp2 = NULL; 
    int i; 

    if (strcmp(name1, currLink->frame->name) == 0 && currLink->next) 
    { 
     *anchor_link = (*anchor_link)->next; 
     temp = currLink; 
    } 
    else 
    { 
     while (strcmp(name1, currLink->next->frame->name) != 0 && currLink->next) 
     { 
      currLink = currLink->next; 
     } 

     temp = currLink->next; 
    } 

    currLink = *anchor_link; 

    for (i = 1; i < pos - 1; i++) // Go up until the node before the pos (meaning if pos is 4 then node 3) 
    { 
      currLink = currLink->next; 
    } 

    // Now we insert the temp node at the pos 

    temp2 = currLink->next->next; 
    currLink->next->next = temp; 
    temp->next = temp2; 
} 

Answer 1

これは私が思い付いたコードです - changePos()の機能と正しいコードを作成したテストコードです。

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

struct Frame 
{ 
    char *name; 
    unsigned int duration; // Effectively unused 
// char *path;    // Actually unused 
}; 

typedef struct Frame Frame; 

struct Link 
{ 
    Frame *frame; 
    struct Link *next; 
}; 

typedef struct Link Link; 

static void print_list(Link *root); 

static void changePos(Link **anchor_link, const char *name, int pos) 
{ 
    assert(anchor_link != 0 && name != 0 && pos >= 0); 
    Link *root = *anchor_link; 
    Link *link = root; 
    Link *prev = 0; 
    int count = 0; 
    while (link != 0 && strcmp(link->frame->name, name) != 0) 
    { 
     prev = link; 
     link = link->next; 
     count++; 
    } 
    if (link == 0)  // Name not found - no swap! 
     return; 
    if (count == pos) // Already in target position - no swap 
     return; 
    if (count == 0)  // Moving first item; update root 
    { 
     assert(link == root); 
     *anchor_link = root->next; 
     root = *anchor_link; 
    } 
    else 
    { 
     assert(prev != 0); 
     prev->next = link->next; 
    } 
    // link is detached; now where does it go? 
    if (pos == 0)  // Move to start; update root 
    { 
     link->next = root; 
     *anchor_link = link; 
     return; 
    } 
    Link *node = root; 
    for (int i = 0; i < pos - 1 && node->next != 0; i++) 
     node = node->next; 
    link->next = node->next; 
    node->next = link; 
} 

static void print_list(Link *root) 
{ 
    const char *pad = ""; 
    while (root != 0) 
    { 
     printf("%s[%s]", pad, root->frame->name); 
     root = root->next; 
     pad = "->"; 
    } 
} 

static void free_frame(Frame *frame) 
{ 
    if (frame != 0) 
    { 
     free(frame->name); 
     free(frame); 
    } 
} 

static void free_link(Link *link) 
{ 
    while (link != 0) 
    { 
     Link *next = link->next; 
     free_frame(link->frame); 
     free(link); 
     link = next; 
    } 
} 

static Frame *make_frame(const char *name, unsigned int number) 
{ 
    Frame *frame = malloc(sizeof(*frame)); 
    if (frame != 0) 
    { 
     frame->name = strdup(name); 
     frame->duration = number; 
    } 
    return frame; 
} 

static Link *make_link(const char *name, unsigned int number) 
{ 
    Link *link = malloc(sizeof(*link)); 
    if (link != 0) 
    { 
     link->frame = make_frame(name, number); 
     link->next = 0; 
    } 
    return link; 
} 

static Link *make_list(int num, Frame *frames) 
{ 
    Link *head = 0; 
    Link *tail = 0; 
    for (int k = 0; k < num; k++) 
    { 
     Link *link = make_link(frames[k].name, frames[k].duration); 
     assert(link != 0 && link->frame != 0); // Lazy! 
     if (head == 0) 
      head = link; 
     if (tail != 0) 
      tail->next = link; 
     tail = link; 
    } 
    return head; 
} 

int main(void) 
{ 
    Frame frames[] = 
    { 
     { "pic0", 0 }, 
     { "pic1", 1 }, 
     { "pic2", 2 }, 
     { "pic3", 3 }, 
     { "pic4", 4 },  // Never in the list, but searched for 
    }; 
    enum { NUM_FRAMES = sizeof(frames)/sizeof(frames[0]) }; 

    for (int i = 0; i < NUM_FRAMES; i++) 
    { 
     for (int j = 0; j < NUM_FRAMES; j++) 
     { 
      Link *head = make_list(NUM_FRAMES - 1, frames); 
      print_list(head); 
      printf(" == %s to %u == ", frames[i].name, j); 
      changePos(&head, frames[i].name, j); 
      print_list(head); 
      putchar('\n'); 
      free_link(head); 
     } 
    } 

    return 0; 
} 

私はchangePos()のコードが少しまだ合理化することが可能と思われるが、私はどのように、まだ発見されていません。数値の位置とリストとの間には醜いインターフェースがあります。ノードをどこに移動するかを識別するために別の名前を使用するのが自然です。数字のポジションでは、リストの代わりに配列を使用したくなるでしょう。

サンプル出力： - PIC3にPIC0順番に、常に同じ

[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 0 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 1 == [pic1]->[pic0]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 2 == [pic1]->[pic2]->[pic0]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 3 == [pic1]->[pic2]->[pic3]->[pic0] 
[pic0]->[pic1]->[pic2]->[pic3] == pic0 to 4 == [pic1]->[pic2]->[pic3]->[pic0] 
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 0 == [pic1]->[pic0]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 1 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 2 == [pic0]->[pic2]->[pic1]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 3 == [pic0]->[pic2]->[pic3]->[pic1] 
[pic0]->[pic1]->[pic2]->[pic3] == pic1 to 4 == [pic0]->[pic2]->[pic3]->[pic1] 
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 0 == [pic2]->[pic0]->[pic1]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 1 == [pic0]->[pic2]->[pic1]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 2 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 3 == [pic0]->[pic1]->[pic3]->[pic2] 
[pic0]->[pic1]->[pic2]->[pic3] == pic2 to 4 == [pic0]->[pic1]->[pic3]->[pic2] 
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 0 == [pic3]->[pic0]->[pic1]->[pic2] 
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 1 == [pic0]->[pic3]->[pic1]->[pic2] 
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 2 == [pic0]->[pic1]->[pic3]->[pic2] 
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 3 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic3 to 4 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 0 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 1 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 2 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 3 == [pic0]->[pic1]->[pic2]->[pic3] 
[pic0]->[pic1]->[pic2]->[pic3] == pic4 to 4 == [pic0]->[pic1]->[pic2]->[pic3] 

出力のLHSは、前のリストです。出力のRHSは、changePosを呼び出した後のリストです。位置n = 0..3の場合、 'picn'が0から3に順に移行しています。 pic4という名前は決してリストには挿入されないので、探しても何も変わらない。また、存在しない位置に名前のいずれかを移動しようとすると、リストの最後の位置に移動されます。 0より小さい位置は無効であるとアサートされます。

コードにはカジュアルなエラーチェックがあります。これは、メモリ割り当ての問題や他のいくつかの問題（0より小さい位置など）を回避する方法を主張します。

changePos()に何か値を書き込む前に、ダミーの何もないバージョンのchangePos()でハーネスをきれいに走らせました。

コードをコンパイルし、GCC 6.1.0を搭載したMac OS X 10.11.5とValgrindの3.12.0.SVNにきれいに動作します、私の習慣的なコンパイラの警告オプションを使用して：

$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \ 
>  -Wold-style-definition -Werror so.3807-9550.c -o so.3807-9550 
$ 

Answer 2

は、私はあなたの一般的なアプローチは大丈夫だと思う。そして、指定された位置に挿入し直し、リストから削除し、ターゲット・ノードを検索します。しかし、コードにはいくつかの問題があります。

まず、このwhile()ループの条件を検討：あなたはcurrLink->nextがNULLである（そして、あなたがする必要があります）かどうかわからない場合、あなたは逆参照前にnullをチェックを実行する必要があり

while (strcmp(name1, currLink->next->frame->name) != 0 && currLink->next) 

をそれは式currLink->next->frame->nameで行います。つまり、指定された名前を見つけずにリストの最後に到達すると、コードは未定義の動作を示します。

第2に、変数の名前付けが少し望ましいです。 tempとはなんですか？ temp2とはなんですか？ name2が見つからないとすれば、1はname1の意味は何ですか？変数を目的を明確に伝えるように名前を付けることで、コードを記述し分析するのに役立ちます。 "target_node"の何が問題なの？

第三に、あなたの挿入コードが間違っている：

temp2 = currLink->next->next; 
currLink->next->next = temp; 
temp->next = temp2; 

あなたが*currLinkと*currLink->next間*tempを挿入しようとするが、実際にあなたが*currLink->next後にそれをを配置し、2つの要素を閉じますループ。また、私はtemp2の使用がこのコードを混乱させていると思われます。私はこれを記述します。

temp->next = currLink->next->next; 
currLink->next = temp; 

第四に、あなたはあなたのリストの位置1に挿入するための規定を持っていません。あなたがそれをやっているやり方は、そのための特別なケースが必要です。