この2Dリンクリストをどのように反復しますか？

Question

どのようにこの2次元リンクリストを反復処理するのでしょうか？

typedef struct _NODE 
{ 
    char   *pszName; 
    unsigned long ulIntVal; 
    char   *pszString; 
    struct _NODE *pNext; 
    struct _NODE *pDown; 
} NODE; 

私はこのような何かを行うことができます。..

NODE *pHEad; 

while (pHead != NULL) { 
    printf("%s", pHead->pDown->pszName); 
    pHead = pHead->pNext; 
} 

を..しかし、それだけですべての次のノードの下に私に一つのノードを与えるだろう。もう1つのノードが再びその下にある場合はどうなりますか？そしてもう一度その下で？またはpDownに添付pNextがある場合は？最も単純なケースで

Answer 1

、次の再帰関数のようなものを使用することができます

void processNode(NODE *current) { 
    if (current != NULL) { 
     printf("%s", current->pszName); 

     processNode(current->pNext); 
     processNode(current->pDown); 
    } 
} 

int main(void) { 
    NODE *pHead; 
    /* ... Do something to fill your list ... */ 
    processNode(pHead); 
    /* ... */ 
} 

はまた、これはあなたの処理されたリストに応じて、関数呼び出しの深いネストを引き起こす可能性があることに注意してください。だから、限られたスタックサイズと組み込みシステム上にあるか、あなたは巨大なリストを処理している場合は、スタックが不足する可能性がある場合。その場合、処理のための別のアプローチを見つける必要があります。これは最初pNextリストを処理し、最後のノードのPDOWNリストの最初のノードの処理で開始すること

注。だから、（右にpNextで、下向きPDOWNである）以下の構造を仮定：

pHead -> p1 -------> p2 
     |- p1_1  |- p2_1 -> p2_1_1 
     \- p1_2  |- p2_2 
        \- p2_3 -> p2_3_1 

それは次の順序でノードを印刷する必要があります：この答えで

pHead, p1, p2, p2_1, p2_1_1, p2_2, p2_3, p2_3_1, p1_1, p1_2 

Answer 2

ルック。コードの量に圧倒されないでください。あなたの手助けをするのに十分なコメントを追加しました。

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

typedef struct Node{ 
    char data[100]; // Assume that this linked list will contain only 100 chars of data 
    struct Node* next; 
} NODE; 

// Global Variables are bad, but oh well. 
NODE* head = NULL; 

// Function to create a node 
NODE* createNode(char* str) 
{ 
    // First allocate memory for struct 
    NODE* newNode = malloc(sizeof(NODE)); 
    if(newNode == NULL) 
    { 
     printf("Unable to create a new node."); 
    } 
    else 
    { 

     // Use strcpy or strncpy or memcpy instead of doing something like newNode -> data = str, which changes the pointer, but doesn't copy the contents 
     // That is do not do newNode -> data = "hello" or something 
     strncpy(newNode -> data, str, strlen(str)); 
     newNode -> next = NULL; 
    } 
    return newNode; 
} 

void addNode(char* str) 
{ 
    // Returns a node which contains str, but points to NULL 
    NODE* newNode = createNode(str); 

    // If the linked list is empty, then we make this node itself as the first node(or head) 
    if(head == NULL) 
    { 
     head = newNode; 
    } 
    // Else if the linked list is not empty, then we add this node at the start of the linked list 
    else 
    { 
     newNode -> next = head; 
     head = newNode; 
    } 
} 

int main() 
{ 
    // Example Linked List Generated(say you already have it in some form) 
    addNode("This"); 
    addNode("Is"); 
    addNode("Linked List"); 

    // Now let's print the linked list 
    // Temporary NODE pointer ptr is used in order to not mess with the original NODE pointer head. 
    NODE* ptr = head; 

    // Traverse through the linked list starting from head and at the same time printing the corresponding data, until ptr is null 
    // This ptr != NULL check is exactly what you are looking for. This is your way of stopping the traversal of Linked List once you 
    // are at the end of it. You don't have to know the number of nodes to stop the traversal this way. 
    while(ptr != NULL) 
    { 
     printf("%s ", ptr -> data); 
     ptr = ptr -> next; 
    } 
} 

ただし、出力が逆順で印刷されることに注意してください。このリンクリストの実装では、背中に物事を追加しているためです。ただ、プログラムを実行しようとするとmain関数から始まるプログラムを読み始めます。私はコードを分かりやすくするためにコードを別々の関数にしました。最初にコードを実行するだけで、何が起きているのか把握できます。

Answer 3

スタックオーバーフローの可能性を回避する場合は、キューを追加することで反復の代わりに繰り返しを使用することができます。—これは少しヒープメモリを使用しますが、実行する可能性があります大きなリストを持っている場合や、メモリが制約されているシステムで実行している場合は、ヒープメモリを使用してください。重要な部分は最後にprint_list関数です。他のものは、私が提供してきましたちょうど（主に）自己管理キューの実装です：

typedef struct node_queue NodeQueue; 
struct node_queue { 
    NODE *n; 
    NodeQueue *next; 
}; 

/* 
* Add an item to the end of the queue. 
* 
* If the item could not be added, 0 is returned. 
* Otherwise, a nonzero value is returned. 
*/ 
int enqueue(NodeQueue **headp, NodeQueue **endp, NODE *n) 
{ 
    NodeQueue *old_end = *endp; 
    NodeQueue *new_end; 

    new_end = malloc(sizeof *new_end); 
    if (new_end == NULL) { 
     return 0; 
    } 
    new_end->n = n; 
    new_end->next = NULL; 

    if (old_end != NULL) { 
     old_end->next = new_end; 
    } 
    if (*headp == NULL) { 
     *headp = new_end; 
    } 
    *endp = new_end; 
    return 1; 
} 

/* 
* Remove an item from the head of the queue, 
* storing it in the object that "nret" points to. 
* 
* If no item is in the queue, 0 is returned. 
* Otherwise, a nonzero value is returned. 
*/ 
int dequeue(NodeQueue **headp, NodeQueue **endp, NODE **nret) 
{ 
    NodeQueue *old_head = *headp; 
    NodeQueue *new_head; 
    if (old_head == NULL) { 
     return 0; 
    } 
    if (nret != NULL) { 
     *nret = old_head->n; 
    } 
    new_head = old_head->next; 
    free(old_head); 
    if (new_head == NULL) { 
     *endp = NULL; 
    } 
    *headp = new_head; 
    return 1; 
} 

void print_list(NODE *start) 
{ 
    NodeQueue *head = NULL; 
    NodeQueue *end = NULL; 
    NODE *current; 

    current = start; 

    /* Iterate all `pNext` nodes, then pop each `pDown` node and repeat. */ 
    for (;;) { 
     /* Add the "down" node to the node queue. */ 
     if (current->pDown != NULL) { 
      if (!enqueue(&head, &end, current->pDown)) { 
       perror("warning: could not add node to queue"); 
      } 
     } 

     printf("%s", current->pszNode); 

     /* 
     * Move to the "next" node. 
     * If there is no next node, get the first "down" node from the queue. 
     * If there is no "down" node, break the loop to end processing. 
     */ 
     current = current->pNext; 
     if (current == NULL) { 
      if (!dequeue(&head, &end, &current)) { 
       break; 
      } 
     } 
    } 
} 

これはpDown項目に移動する前に、すべてのpNextの項目を反復処理します。次の2-DリストはA B C D E F G H I J K L M N O P Qとして印刷される。

A 
| 
B--C 
| 
D--E-----------F 
    |   | 
    G-----H  I-----J 
    |  |  |  | 
    K--L M--N O  P 
     | 
     Q 

あなたはその内部pNextとpDownを交換することにより、print_list関数でpDown/pNextの優先順位を逆にすることができ、そうpNextアイテムをキューとpDownに追加されます項目がリストの構造を変更しない限り、アイテムがA B D C E G K F I O H M Q L J P Nに印刷される順序が変更される、疲れまで反復されます。

上記のコードと上記の最初の2-Dリンクリストの例をhttps://repl.it/NjyV/1で見ることができますが、NODEの定義を変更して、フィールドを少し単純にするようにしています。