c - 具有 2 个结构的双向数字链表

Question

我正在尝试弄清楚如何使用双向链表编写以下代码。

用户将被要求输入一个数字。如果是负数则在开头添加，如果是正数则在末尾添加。当用户输入 0 时程序将停止。

我必须使用以下预定义的结构。

由于使用“typedef struct Node* NodePtr;”，我有点困惑然后是两个结构中的 NodePtr。有人可以向我解释一下什么是正确的思维方式吗？

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

typedef struct Node* NodePtr; /* Pointer to a node */

typedef struct Node     /* Node contains a read number */
{
    int n;          /* Stored number */
    NodePtr prev;
    NodePtr next; 
} Knoten;

typedef struct
{ /* Structure for double linked lists: start + end */
    NodePtr start;      /* Pointer to the beginning of the doubly linked list */
    NodePtr end;        /* Pointer to the end of the doubly linked list */
} DVListe;

<小时/>

这是我到目前为止所拥有的。当然有很多错误和段错误:)

我仍然不明白在哪里定义开始和结束，以及我应该将它们分配给谁，newNode 还是 NodePtr 或者与此完全不同的东西？ :/

 // continue
    DVList *h = NULL;
    Knoten *newNode;

    void negative_start(int n)
    {
        if (newNode == NULL)
        {
            newNode = malloc(sizeof(Knoten));
            if (newNode == NULL)
            {
                printf("ERROR! Could not allocate memory");
                exit(EXIT_FAILURE);
            }
            newNode->n = n;
            newNode->prev = NULL;
            newNode->next = NULL;

            newNode = h->start;
            h->start = h->end;
        }
        else
        {
            newNode = malloc (sizeof(Knoten));
            if (newNode == NULL)
                {
                    printf("ERROR! Could not allocate memory");
                    exit(EXIT_FAILURE);
                }
            newNode->n = n;
            newNode->next = h->start;
            newNode->prev = NULL;
            h->start = newNode;
        }
    }
    void positive_end(int n)
    {
        // I didn't write it because it will be wrong like the negative_start function.
    }

    int main ()
    {
        int x;
        newNode = NULL;
        printf("\n Enter a number ");
        scanf("%d", &x);
        while ( x != 0)
        {
            if ( x < 0 ){ negative_start(x); 
                        }
            else{ positive_end(x); 
                }
            scanf("%d", &x);
        }
        return 0;
    }

<小时/>

我尝试使用 @ChrisTurner 结构从 new 编写代码。

它仅适用于负数。如果我只输入任何正数，它们将被丢弃。有人可以帮我解决这个问题吗？

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

typedef struct Node Knoten;
typedef struct DVListe_s DVList;

struct Node
{
    int n;
    Knoten *next;
    Knoten *prev;
};

struct DVListe_s
{
    Knoten *start;
    Knoten *end;
};

DVList *construct()
{
    DVList *list;
    list = malloc (sizeof(DVList));
    list->start = NULL;
    list->end = NULL;
    
    return list;
}



void add_negative_start (DVList *list, int n)
{
    if (list->start != NULL)
    {
        Knoten *newNode = malloc(sizeof(Knoten));
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->n = n;
        
        newNode->next = list->start;
        list->start = newNode;
    }
     else
    {
        Knoten *newNode = malloc(sizeof(Knoten));
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->n = n;
        
        list->start = newNode;
        list->end = list->start;
    }
}

void add_positive_end(DVList *list, int n)
{
    if (list->end != NULL)
    {
        Knoten *newNode = malloc(sizeof(Knoten));
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->n = n;
        
        newNode->prev = list->end;
        list->end = newNode;
    }
    else
    {
        Knoten *newNode = malloc(sizeof(Knoten));
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->n = n;
        
        list->end = newNode;
        list->start = list->end;
    }
}

void print(DVList *list)
{
    Knoten *temp = list->start;
    printf ("Entered Numbers\n");
    while (temp != NULL)
    {
        printf("%d\n", temp->n);
        temp = temp->next;
    }
}

int main()
{
    DVList *list = construct();
    
    int x = 1;
    printf("Enter a number\n");
    
    while (x)
    {
        scanf ("%d", &x);
        if (x < 0)
        {
            add_negative_start(list, x);
        }
        else
        {
            add_positive_end(list, x);
        }
          
    }
    print(list);
    
    return 0;
}
 R

Answer 1

typedef 创建可以被视为 NodePtr 和 struct Node * 之间的别名的内容，以便每当您放置 NodePtr 编译器知道你实际上指的是 struct Node *。

你不能在struct NodePtr内部使用struct NodePtr，因为此时它不知道struct NodePtr有多大，所以无论您是否使用 typedef，此时您都需要使用指针。

在您的 DVListe 中，由于您的列表将从空开始，因此您在此处使用指针，以便可以将 start 和 end 设置为 NULL 表示或者如果您有一个节点，则它们可以都指向同一位置。

就我个人而言，我认为创建一个指向某物的指针并不是一个好主意，尽管您至少清楚地表明它是一个带有名称的指针。您可能会丢失 typedef 并也这样做。

typedef struct Node Knoten;
typedef struct DVListe_s DVListe;

struct Node     /* Node contains a read number */
{
    int n;          /* Stored number */
    Node *prev;
    Node *next; 
};

struct DVListe_s
{ /* Structure for double linked lists: start + end */
    Node *start;      /* Pointer to the beginning of the doubly linked list */
    Node *end;        /* Pointer to the end of the doubly linked list */
};