C-交换单链列表中的第一个和最后一个元素

用户名

我正在尝试做的是交换单链列表的第一个和最后一个元素。到目前为止,我有以下代码,在其中创建列表并向其中添加一些数字。我的问题是在swapElements1函数。

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

struct node
{
    int number;
    struct node *next;
};

void addNodeSingle(struct node **head, int num, int thesi) //Function to insert new node at the beginning or the end of the list, depending on the value of "thesi"
{
    if (*head == NULL)
    {
        struct node *current;
        current = (struct node*) malloc (1*sizeof(struct node));
        current -> number = num;
        current -> next = NULL;
        *head = current;
    }

    else
    {
        if (thesi == 0)
        {
            struct node *current;
            current = (struct node*) malloc (1*sizeof(struct node));
            current -> number = num;
            current -> next = *head;
            *head = current;
        }

        else
        {
            struct node *current, *temp;
            current = (struct node*) malloc (1*sizeof(struct node));
            current -> number = num;
            temp = *head;
            while (temp -> next != NULL)
                temp = temp -> next;

            temp -> next = current;
            current -> next = NULL;
        }
    }
}

void displayList(struct node **head) //Function to display the list
{
    struct node *current;
    if(*head == NULL)
        printf("I lista einai adeia!\n");

    else
    {
    current= *head ;
        while(current != NULL)
        {
            printf("%d ",current -> number);
            current = current -> next;
        }
    }
}

void swapElements1(struct node **head) //(not working)Function to swap first and last element of the list
{
    struct node *current, *temp;
    current = temp = *head;

    while(current != NULL)
    {
        temp = current;
        current = current -> next;
    }

    *head = (*head)->next;
    *head = temp;
    current = NULL;
}

int main()
{
    struct node *head;
    head = NULL;

    addNodeSingle(&head,5,1);
    addNodeSingle(&head,6,1);
    addNodeSingle(&head,2,0);
    addNodeSingle(&head,7,0);
    addNodeSingle(&head,8,0);

    printf("List is: ");
    displayList(&head);
    swapElements1(&head);
    printf("\nNew list is: ");
    displayList(&head);
}

我得到的输出是:

清单是:8 7 2 5 6

新列表是:6

我需要的是:

清单是:8 7 2 5 6

新列表是:6 7 2 5 8

这是一个演示

WhozCraig

这显然是错误的:

*head = (*head)->next;
*head = temp;

只是用的值覆盖了先前的值temp第一条语句甚至也可能不存在。

从根本上讲,您需要两次交换(技术上是一次交换,再加上分配和终止)

  • 指向两个节点的指针
  • 两个节点的next指针

后者的这些在技术上并不需要,而是直接分配需要,新的尾部都需要有它的next设置为空,终止新的列表。

下面显示了一个完整的示例,对其进行了自由评论,以期希望揭示出正在发生的事情的算法。

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

struct node
{
    int data;
    struct node *next;
};

void swapFirstAndLast(struct node **head)
{
    // don't bother unless we have a list of at least two nodes
    if (!*head || !(*head)->next)
        return;

    // start with the head's next pointer (the second node in the list)
    struct node **pp = &(*head)->next;

    // walk the pointer-to-pointer down the list, each time grasping
    //  the next node's "next" pointer address until we reach a node
    //  whose 'next' is NULL. When that happens, `pp` will hold the
    //  address of the pointer pointing to the last node in the list
    while (*pp && (*pp)->next)
        pp = &(*pp)->next;

    // swap the pointer held in *head with *pp
    struct node *tmp = *head;
    *head = *pp;
    *pp = tmp;

    // save new head's next pointer to be the old head's next
    (*head)->next = (*pp)->next;

    // and finally, terminate the list.
    (*pp)->next = NULL;
}

void print_list(const struct node *head)
{
    while (head)
    {
        printf("%d ", head->data);
        head = head->next;
    }
    fputc('\n', stdout);
}

int main()
{
    struct node *head = NULL, **pp = &head;
    for (int i=1; i<=5; ++i)
    {
        *pp = malloc(sizeof **pp);
        (*pp)->data = i;
        pp = &(*pp)->next;
    }
    *pp = NULL;

    print_list(head);

    swapFirstAndLast(&head);

    print_list(head);
}

输出

1 2 3 4 5 
5 2 3 4 1 

我已经为您保留了列表清理功能(毫无疑问,您已经编码了这样的算法)。问题的关键是如何使用指向指针的指针来操作链表的指针。不只是一堆临时指针。我强烈建议您在调试器中单步执行交换功能,观察过程中每一步的情况。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

在c中使用结构的地址和指针访问结构的第一个元素

为什么将\ 0定义为C中char数组的第一个元素?

c ++-如果用作map中的键,如何获取对的第一个和第二个元素?

读取第一个和最后一个字母后,解析C#中的字符串

如何在C#中删除字符串的第一个和最后一个字符?

基于列表C#中项目的第一个和最后一个字符进行区分

指向C中数组的第一个元素

在对C#中的第一个和/或最后一个元素进行特殊处理时,如何评估IEnumerable <T>?

将一个列表与一个或多个列表进行比较:如何指定它们在第一个列表中的索引位置?在C#中

C ++:我有两个数组,其中第一个元素和最后一个元素具有相同的内存地址

交换C数组时交换最后一个元素的问题

从.txt文件创建一个单链列表,并反转C中每行的奇数

第一个C程序中的异常行为

如何在C ++中交换队列的第一个和最后一个元素?

如何从输入短语中获取单词,然后使用C按字母顺序获取第一个单词和最后一个单词?

c中按字母顺序排列的第一个和最后一个单词

尝试引用char *中的第一个元素时,C中出现分段错误

如何检查数组c ++中的第一个元素和最后一个元素

C:使用列表的数组的最后一个元素

C struct指针从第一个元素到最后一个元素的步骤

C#如何交换字符串中的第一个字符与最后一个字符

Elasticsearch,仅索引第一个和最后一个字母,'abc'=>'a''c'

如何在C#中使用EF从MySQL表中获取第一个和最后一个日期?

使用 C# 获取列表中每个元素的第一个索引的平均值

listBox c#的第一个元素

将一个列表中的 8 个元素拆分为另一个 C# 的第一个元素

名称数组和 C 中数组的第一个元素有什么区别?

元组列表到元组 C# 列表中的第一个元素列表

如何从C中的行中获取第一个和最后一个单词?