如何在C中使用for循环将数据插入双向链表

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

所以，在这里我制作了一个双向链表，但我不想手动分配值（10、20、30），而是想制作一个 for 循环并以这种方式放置数据以使其高效。 我在单链表中做到了这一点，但这里没有发生同样的情况，只有backward_traversing函数起作用。 在这里给出代码。

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

typedef struct Node
{
    int value;
    struct Node *next_link;
    struct Node *prev_link;
} Node;

Node *create_node(int value)
{
    Node *new_node = malloc(sizeof(Node));
    new_node->value = value;
    new_node->next_link = NULL;
    new_node->prev_link = NULL;

    return new_node;
}

void forward_traversing(Node *head)
{
    Node *temp = head;

    while (temp != NULL)
    {
        printf("%d ", temp -> value);
        temp = temp->next_link;
    }
    printf("\n");
}

void backward_traversing(Node *tail)
{
    Node *temp = tail;

    while (temp != NULL)
    {
        printf("%d ", temp->value);
        temp = temp->prev_link;
    }
    printf("\n");
}

void show_first(Node *head)
{
    printf("%d \n", head->value);
}

void show_last(Node *tail)
{
    printf("%d \n", tail->value);
}

int main()
{
    Node *head, *temp, *tail;

    for (int i = 0; i <= 25; i++){
        temp = create_node(i);
        temp -> next_link = head;
        head = temp;
    }
    
    forward_traversing(head);
    backward_traversing(tail);
    show_first(head);
    show_last(tail);
    
    return 0;
}
c loops for-loop data-structures doubly-linked-list
1个回答
0
投票

定义一个类型来保存列表的头指针和尾指针非常有用，因为某些函数可能需要更新头指针和尾指针。

基本操作包括：

  • 初始化列表
  • 向列表添加元素的各种方式，例如：
    • 将其添加到列表的开头
    • 将其附加到列表末尾
    • 将其插入列表中已有的其他元素之前
    • （将其插入到其他元素之后可以通过将其插入到下一个元素（如果存在）之前，或者将其追加到列表中来实现）
  • 从列表中删除元素的各种方法，例如：
    • 删除第一个元素
    • 删除最后一个元素
    • 删除已知在列表中的元素

可以编写函数来执行这些操作，如以下基于 OP 原始代码的示例所示（OP 的函数采用头指针或尾指针已更改为采用指向列表控制结构的指针）：

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

typedef struct Node
{
    int value;
    struct Node *next_link;
    struct Node *prev_link;
} Node;

typedef struct List
{
    struct Node *head;
    struct Node *tail;
} List;

Node *create_node(int value)
{
    Node *new_node = malloc(sizeof(Node));
    new_node->value = value;
    new_node->next_link = NULL;
    new_node->prev_link = NULL;

    return new_node;
}

Node *node_next(Node *node)
{
    return node->next_link;
}

Node *node_prev(Node *node)
{
    return node->prev_link;
}

void free_node(Node *node)
{
    free(node);
}

void list_init(List *list)
{
    list->head = NULL;
    list->tail = NULL;
}

Node *list_first(List *list)
{
    return list->head;
}

Node *list_last(List *list)
{
    return list->tail;
}

/* Note: existingnode assumed to be on the list if non-null */
/* Note: if existingnode is null, newnode will be prepended to the list */
void list_insert_before(List *list, Node * restrict existingnode,
                        Node * restrict newnode)
{
    if (newnode)
    {
        Node *prev;

        if (existingnode == NULL)
        {
            /* newnode will be prepended before head (if it exists) */
            existingnode = list->head;
        }
        if (existingnode)
        {
            prev = existingnode->prev_link;
            existingnode->prev_link = newnode;
        }
        else
        {
            /* list is empty */
            prev = NULL;
            list->tail = newnode;
        }
        newnode->prev_link = prev;
        newnode->next_link = existingnode;
        if (prev)
        {
            prev->next_link = newnode;
        }
        else
        {
            /* newnode being prepended to the list */
            list->head = newnode;
        }
    }
}

void list_prepend(List *list, Node *node)
{
    /* Note: list->head may be null */
    list_insert_before(list, list->head, node);
}

void list_append(List *list, Node *node)
{
    if (node)
    {
        node->next_link = NULL;
        node->prev_link = list->tail;
        if (list->tail)
        {
            list->tail->next_link = node;
        }
        else
        {
            /* list is empty */
            list->head = node;
        }
        list->tail = node;
    }
}

/* Note: existingnode assumed to be on the list if non-null */
/* Note: if existingnode is null, newnode will be appended to the list */
void list_insert_after(List *list, Node * restrict existingnode,
                       Node * restrict newnode)
{
    if (existingnode == NULL || existingnode == list->tail)
    {
        list_append(list, newnode);
    }
    else
    {
        list_insert_before(list, existingnode->next_link, newnode);
    }
}

/* Note: node assumed to be on the list if non-null */
void list_remove_node(List *list, Node *node)
{
    if (node)
    {
        Node *next = node->next_link;
        Node *prev = node->prev_link;

        if (next)
        {
            next->prev_link = prev;
        }
        else
        {
            list->tail = prev;
        }
        if (prev)
        {
            prev->next_link = next;
        }
        else
        {
            list->head = next;
        }
    }
}

Node *list_remove_first(List *list)
{
    Node *node = list_first(list);

    list_remove_node(list, node);
    return node;
}

Node *list_remove_last(List *list)
{
    Node *node = list_last(list);

    list_remove_node(list, node);
    return node;
}

void free_list_nodes(List *list)
{
    Node *temp;

    while ((temp = list_remove_first(list)) != NULL)
    {
        free_node(temp);
    }
}

void forward_traversing(List *list)
{
    Node *temp = list_first(list);

    while (temp != NULL)
    {
        printf("%d ", temp->value);
        temp = temp->next_link;
    }
    printf("\n");
}

void backward_traversing(List *list)
{
    Node *temp = list_last(list);

    while (temp != NULL)
    {
        printf("%d ", temp->value);
        temp = temp->prev_link;
    }
    printf("\n");
}

void show_first(List *list)
{
    Node *head = list_first(list);

    if (head)
    {
        printf("%d \n", head->value);
    }
    else
    {
        printf("(empty)\n");
    }
}

void show_last(List *list)
{
    Node *tail = list_last(list);

    if (tail)
    {
        printf("%d \n", tail->value);
    }
    else
    {
        printf("(empty)\n");
    }
}

int main()
{
    List list;
    Node *node;
    int i;

    list_init(&list);
    for (i = 10; i < 50; i += 10)
    {
        node = create_node(i);

        if (node)
        {
            list_append(&list, node);
        }
    }

    printf("Initial list\n");
    forward_traversing(&list);
    backward_traversing(&list);

    printf("Remove first node\n");
    node = list_remove_first(&list);    /* (10), 20, 30, 40 */
    forward_traversing(&list);
    backward_traversing(&list);

    printf("Prepend removed node to start of list\n");
    list_prepend(&list, node);          /* 10, 20, 30, 40 */
    forward_traversing(&list);
    backward_traversing(&list);

    printf("Remove last node\n");
    node = list_remove_last(&list);     /* 10, 20, 30, (40) */
    forward_traversing(&list);
    backward_traversing(&list);
    printf("Append removed node to end of list\n");
    list_append(&list, node);           /* 10, 20, 30, 40 */
    forward_traversing(&list);
    backward_traversing(&list);

    printf("Remove third node\n");
    node = node_next(node_next(list_first(&list))); /* (30) */
    list_remove_node(&list, node);      /* 10, 20, 40 */
    forward_traversing(&list);
    backward_traversing(&list);
    printf("Insert removed node after second node\n");
    list_insert_after(&list, node_next(list_first(&list)), node);
                                        /* 10, 20, 30, 40 */
    forward_traversing(&list);
    backward_traversing(&list);
    printf("Remove previous (third) node again\n");
    list_remove_node(&list, node);      /* 10, 20, 40 */
    forward_traversing(&list);
    backward_traversing(&list);
    printf("Insert removed node before third (original fourth) node\n");
    list_insert_before(&list, node_next(node_next(list_first(&list))),
                       node);           /* 10, 20, 30, 40 */
    forward_traversing(&list);
    backward_traversing(&list);

    printf("First node\n");
    show_first(&list);
    printf("Last node\n");
    show_last(&list);

    free_list_nodes(&list);
    return 0;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.