我正在尝试做的是交换单链列表的第一个和最后一个元素。到目前为止,我有以下代码,在其中创建列表并向其中添加一些数字。我的问题是在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
这是一个演示
这显然是错误的:
*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] 删除。
我来说两句