SLL 的双指针在内存中是如何存储的？

问题描述 投票：0回答：1

在@4386427提出建议后，我将我的问题更改如下。 在尝试合并两个列表时，我使用双指针来存储最终列表，并使用单指针来指向头节点。

  1. 为什么我不能直接用
    trav->next
    代替
    &((*trav)->next)
    ？
  2. 在第一次迭代中 mergedList 如何指向 &((*trav)>next) ？
  3. 它实际上是如何存储在内存中以及如何遍历的。请帮助我理解这里的概念。 此页面没有帮助。
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
}Node;

Node *createNode(int data) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    if(!newNode) {
        printf("mem-alloc failed for data: %d\n", data);
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

Node *mergeTwoSortedLists(Node *head1, Node *head2) {
    Node *mergedList = NULL;
    Node **trav = &mergedList;

    if(!head1 && !head2) {
        printf("Both the heads are NULL, cant merge\n");
        return NULL;
    }

    while (head1 && head2) {
        if(head1->data <= head2->data) {
            *trav = createNode(head1->data);
            printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %d ", (void*)&trav, (void*)trav, (void*)*trav, (**trav).data, (void*)&mergedList, (void*)mergedList, (*mergedList).data);
            printf("&((*trav)->next): %p, mergedList->next: %p\n", &((*trav)->next), mergedList->next);
            head1 = head1->next;
        }
        else {
            *trav = createNode(head2->data);
            printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %d ", (void*)&trav, (void*)trav, (void*)*trav, (**trav).data, (void*)&mergedList, (void*)mergedList, (*mergedList).data);
            printf("&((*trav)->next): %p, mergedList->next: %p\n", &((*trav)->next), mergedList->next);
            head2 = head2->next;
        }
        trav = &((*trav)->next);
    }

    /* insertion of the remaining list to the trav 
       or insert the list that is not null. */
    while (head1) {
        *trav = createNode(head1->data);
        printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %d ", (void*)&trav, (void*)trav, (void*)*trav, (**trav).data, (void*)&mergedList, (void*)mergedList, (*mergedList).data);
        printf("&((*trav)->next): %p, mergedList->next: %p\n", &((*trav)->next), mergedList->next);
        head1 = head1->next;
        trav = &((*trav)->next);
    }

    while (head2) {
        *trav = createNode(head2->data);
        printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %d ", (void*)&trav, (void*)trav, (void*)*trav, (**trav).data, (void*)&mergedList, (void*)mergedList, (*mergedList).data);
        printf("&((*trav)->next): %p, mergedList->next: %p\n", &((*trav)->next), mergedList->next);
        head2 = head2->next;
        trav = &((*trav)->next);
    }

    return mergedList;
}

void createSortedList(Node **head, int data) {
    Node *trav = NULL;
    Node *newNode = (Node *) malloc(sizeof(Node));

    if(!newNode) {
        printf("Memalloc failed - No memory allocated for data: %d\n", data);
        return;
    }

    newNode->data = data;

    if(!(*head) || (*head)->data >= data) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    trav = *head;

    while((trav->next) && (trav->next->data < data)) {
        trav = trav->next;
    }

    newNode->next = trav->next;
    trav->next = newNode;

    return;
}

void printList(Node *head) {
    if(!head) {
        printf("Node is empty\n");
        return;
    }
    while(head) {
        printf("%d\t", head->data);
        head = head->next;
    }
    printf("\n");
    return;
}

int main() {
    Node *head = NULL;
    Node *head2 = NULL;
    Node *head3 = NULL;
    createSortedList(&head, 3);
    createSortedList(&head, 5);
    createSortedList(&head, 7);
    createSortedList(&head, 3);
    createSortedList(&head, 4);
    createSortedList(&head, 9);
    printList(head);
    createSortedList(&head2, 10);
    createSortedList(&head2, 5);
    createSortedList(&head2, 9);
    createSortedList(&head2, 4);
    printList(head2);
    head3 = mergeTwoSortedLists(head, head2);
    printList(head3);
    return 0;
}

输出：

PS C:\Users\preet\OneDrive\Desktop\preethiC\VSCode> gcc -Wall .\FirstProg.c
PS C:\Users\preet\OneDrive\Desktop\preethiC\VSCode> .\a.exe
3       3       4       5       7       9
4       5       9       10
&trav: 0061FEE8 trav: 0061FEEC, *trav: 007417C8, **trav: 3, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 007417CC, mergedList->next: 00000000
&trav: 0061FEE8 trav: 007417CC, *trav: 007417D8, **trav: 3, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 007417DC, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 007417DC, *trav: 007417E8, **trav: 4, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 007417EC, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 007417EC, *trav: 007417F8, **trav: 4, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 007417FC, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 007417FC, *trav: 00741808, **trav: 5, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 0074180C, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 0074180C, *trav: 00741818, **trav: 5, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 0074181C, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 0074181C, *trav: 00741828, **trav: 7, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 0074182C, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 0074182C, *trav: 00741838, **trav: 9, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 0074183C, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 0074183C, *trav: 007469F0, **trav: 9, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 007469F4, mergedList->next: 007417D8
&trav: 0061FEE8 trav: 007469F4, *trav: 00746A80, **trav: 10, &mergedList: 0061FEEC, mergedList: 007417C8, *mergedList: 3 &((*trav)->next): 00746A84, mergedList->next: 007417D8
3       3       4       4       5       5       7       9       9       10
PS C:\Users\preet\OneDrive\Desktop\preethiC\VSCode>
c malloc heap-memory
1个回答
0
投票

您的打印声明是错误的。

如果您没有从编译器收到任何警告，则需要提高警告级别。例如，对于 

gcc
使用选项：
-Wall -Wextra -Werror -pedantic

打印指针时（即

%p
），您需要将指针强制转换为空指针。喜欢：

int x;
int* p = &x;
printf("p equals %p\n", (void*)p);
                        ^^^^^^^
                        cast to void*

更糟糕的是 

**trav
属于 
Node
类型，但您使用 
%d
打印它。您可能想打印 
(**trav).data
。

和 

*mergedList
类似。再次是 
Node
，但这次您使用 
%p
打印它。也许您想要 
%d
和 
(*mergedList).data
。

所有这些都意味着你的程序有未定义的行为。例如，请注意打印 

&mergedList: 00000000
。这都是错误的。局部变量的地址不能是 
00000000
。

请尝试：

printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %d\n", (void*)&trav, (void*)trav, (void*)*trav, (**trav).data, (void*)&mergedList, (void*)mergedList, (*mergedList).data);

也就是说，我建议您避免这么长的 

printf
声明。将其分解为许多更简单的语句。喜欢：

printf("&trav: %p, ", (void*)&trav);
printf("trav: %p, ", (void*)trav);
printf("*trav: %p, ", (void*)*trav);
printf("(**trav).data: %d, ", (**trav).data);
printf("&mergedList: %p, ", (void*)&mergedList);
printf("mergedList: %p, ", (void*)mergedList);
printf("(*mergedList).data: %d\n", (*mergedList).data);

更容易阅读。更容易确保事情正确。

由于您执行了 4 次相同的打印，因此您可以考虑使用宏来避免多次输入相同的内容。

#define DUMP_VALUES                                        \
    printf("&trav: %p, ", (void*)&trav);                   \
    printf("trav: %p, ", (void*)trav);                     \
    printf("*trav: %p, ", (void*)*trav);                   \
    printf("(**trav).data: %d, ", (**trav).data);          \
    printf("&mergedList: %p, ", (void*)&mergedList);       \
    printf("mergedList: %p, ", (void*)mergedList);         \
    printf("(*mergedList).data: %d\n", (*mergedList).data)

然后要打印，只需写：

DUMP_VALUES;

完成这些更改后，我的系统打印：

3   3   4   5   7   9   
4   5   9   10  
&trav: 0x7ffea69fcb20, trav: 0x7ffea69fcb28, *trav: 0x2134160, (**trav).data: 3, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134168, *trav: 0x2134180, (**trav).data: 3, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134188, *trav: 0x21341a0, (**trav).data: 4, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x21341a8, *trav: 0x21341c0, (**trav).data: 4, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x21341c8, *trav: 0x21341e0, (**trav).data: 5, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x21341e8, *trav: 0x2134200, (**trav).data: 5, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134208, *trav: 0x2134220, (**trav).data: 7, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134228, *trav: 0x2134240, (**trav).data: 9, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134248, *trav: 0x2134260, (**trav).data: 9, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134268, *trav: 0x2134280, (**trav).data: 10, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
3   3   4   4   5   5   7   9   9   10

这比 OP 的结果更有意义。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.