c - 在C中反转双向链表
问题描述
我目前正在尝试反转一个双向链表并在 C 中打印出来。不幸的是，我的代码只打印一个项目，我不知道为什么。我在 Stack Overflow 和在线查看了多种解决方案
基本上，我传递了一个看起来像这样的 txt 文件。
Name 100
John 40
这是完整的代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct person{
char* firstName;
char* age;
struct person* previous;
struct person* next;
}Person;
void print(Person*);
void reverseList(Person*);
Person* add (Person*, char*, char*);
void print (Person* list) {
while(list != NULL) {
printf("%s %s\n",list->firstName,list->age);
list = list->next;
}
}
void reverseList (Person* list) {
Person *current = list;
Person* last = current;
while(current != NULL) {
Person *temp = NULL;
temp = current->previous;
current->previous = current->next;
current->next = temp;
last = current;
current = current->previous;
}
list = last;
while(list != NULL) {
printf("%s %s\n",list->firstName,list->age);
list = list->next;
}
}
Person* add (Person *list, char *firstName, char *age) {
// allocate node
Person* node = (Person*)malloc(sizeof(Person));
// if node is empty
if(node != NULL) {
node->firstName=(char *)malloc(sizeof(char)*strlen(firstName)+1);
// insert name
strcpy(node->firstName, firstName);
// allocate age & insert
node->age = (char*)malloc(sizeof(char)*strlen(age)+1);
strcpy(node->age, age);
node->next = NULL;
if(list == NULL) list = node;
else {
Person *curr = list;
Person *pre = NULL;
while(curr != NULL) {
if(strcmp(curr->firstName, firstName) > 0) {
if(pre == NULL) {
node->next = list;
list = node;
} else {
pre->next = node;
node->next = curr;
}
return list;
}
pre = curr;
curr = curr->next;
}
pre->next = node;
}
return list;
}
return list;
}
int main (int argc, char **argv) {
FILE *in = fopen(argv[1], "r");
char name[20];
char num[20];
Person *list=NULL;
while(fscanf(in, "%s %s",name, num)==2) {
list = add(list,name, num);
}
printf ("Original List\n***\n");
print (list);
printf ("Printing Reversed List\n***\n");
reverseList(list);
return 0;
}
目标是，如果我通过如下列表：
John 10
Mary 5
它会打印
Mary 5
John 10
知道这里发生了什么吗？不知道我在误解什么
解决方案
正如我在评论中指出的那样，您的问题不在您的reverseList()函数中（尽管它需要帮助），您的问题在于您的add()函数没有设置任何previous节点指针。因此，当您到达列表末尾并尝试反向打印列表时，您打印的只是当前节点，并且您的打印循环将退出，因为->next节点（原始->previous节点）是NULL.
要解决此问题，您需要连接->previous指针。
（编辑 add()重写以解决原始角落案例的排序错误）
Person *add (Person *list, char *firstName, char *age)
{
size_t len;
Person *node = malloc (sizeof *node), /* allocate node, use dereference ptr for size */
*iter = list,
*prev = NULL;
if (!node) { /* validate EVERY allocation */
perror ("malloc-node");
return list;
}
node->next = node->previous = NULL; /* initialize next and previous NULL */
len = strlen (firstName); /* get length of firstName */
if (!(node->firstName = malloc (len + 1))) { /* allocate/validate */
perror ("malloc-node->firstName");
free (node); /* free node before return */
return list;
}
memcpy (node->firstName, firstName, len + 1); /* copy firstName to node */
len = strlen (age); /* get length of age */
if (!(node->age = malloc (len + 1))) { /* allocate/validate */
perror ("malloc-node->age");
free (node->firstName); /* free node->firstName, and */
free (node); /* free node before return */
return list;
}
memcpy (node->age, age, len + 1); /* copy age to node */
if (!list) /* if list empty */
return node; /* return node */
/* iterate until iter->firstName sorts before firstName */
while (iter && strcmp (firstName, iter->firstName) <= 0) {
prev = iter;
iter = iter->next;
}
if (!iter) { /* if new end node */
prev->next = node;
node->previous = prev;
}
else { /* insert between nodes */
node->next = iter->next;
node->previous = iter;
if (iter->next) /* protect when new next to last */
iter->next->previous = node;
iter->next = node;
}
/* if new first node, return iter, otherwise return list */
return strcmp (list->firstName, firstName) >= 0 ? node : list;
}
你reverseList()实际上不能“扭转”任何事情。它所能做的就是迭代到列表中的最后一个节点，然后使用->previous指针以相反的顺序打印列表。因此，您不必要地交换指针。只需迭代到最后，转身并使用->previous指针迭代回到开头反向打印列表，例如
void reverseList (Person *list) {
if (!list) { /* validate list not empty */
puts ("(list empty)");
return;
}
while (list->next != NULL) /* iterte to last node */
list = list->next;
while (list) { /* print in reverse using ->previous pointers */
printf ("%s %s\n", list->firstName, list->age);
list = list->previous;
}
}
不幸的是，您无法更改函数原型。要在函数中实际反转行列列表void，您必须传递列表指针的地址，以便可以使用新的第一个节点更新该地址处的节点。如果您确实想实际反转列表，您可以执行以下操作：
void reverseList (Person **list) {
Person *current = *list;
Person *last = current;
if (!current || !current->next)
return;
do {
Person *temp = current->previous;
current->previous = current->next;
current->next = temp;
last = current;
} while ((current = current->previous));
*list = last;
}
您可以将上述内容称为：reverseList(&list);. 然后你只需print (list);再次调用以反向打印列表......
此外，如果您可以更改原型并将列表指针的地址传递给您的add()函数，您将无需跟踪preand curr，您可以简单地使用当前节点的地址和指向当前节点的指针进行迭代. 请参阅Linus 了解指针
最后，不要忘记释放您分配的内存。您必须在释放节点之前释放和firstName。age一个简单的删除列表函数，用于删除与列表关联的所有当前分配的内存，可以写成：
/** delete all nodes in list */
void del_list (Person *list)
{
while (list) {
Person *victim = list;
list = list->next;
free (victim->firstName);
free (victim->age);
free (victim);
}
}
如果您还有其他问题，请告诉我。
完整示例
由于我在评论中提供的示例代码链接只能使用一个月，因此我将在此处包含示例以供后人使用。例子是：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct person{
char* firstName;
char* age;
struct person* previous;
struct person* next;
}Person;
void print(Person*);
// void reverseList(Person*);
Person* add (Person*, char*, char*);
void print (Person* list) {
while(list != NULL) {
printf("%s %s\n",list->firstName,list->age);
list = list->next;
}
}
void prnptrs (Person *list) {
while (list) {
printf ("%p %p %p\n", (void*)list->previous, (void*)list, (void*)list->next);
list = list->next;
}
}
#ifndef PASSPTR2PTR
void reverseList (Person *list) {
if (!list) { /* validate list not empty */
puts ("(list empty)");
return;
}
while (list->next != NULL) /* iterte to last node */
list = list->next;
while (list) { /* print in reverse using ->previous pointers */
printf ("%s %s\n", list->firstName, list->age);
list = list->previous;
}
}
#else
void reverseList (Person **list) {
Person *current = *list;
Person *last = current;
if (!current || !current->next)
return;
do {
Person *temp = current->previous;
current->previous = current->next;
current->next = temp;
last = current;
} while ((current = current->previous));
*list = last;
}
#endif
Person *add (Person *list, char *firstName, char *age)
{
size_t len;
Person *node = malloc (sizeof *node), /* allocate node, use dereference ptr for size */
*iter = list,
*prev = NULL;
if (!node) { /* validate EVERY allocation */
perror ("malloc-node");
return list;
}
node->next = node->previous = NULL; /* initialize next and previous NULL */
len = strlen (firstName); /* get length of firstName */
if (!(node->firstName = malloc (len + 1))) { /* allocate/validate */
perror ("malloc-node->firstName");
free (node); /* free node before return */
return list;
}
memcpy (node->firstName, firstName, len + 1); /* copy firstName to node */
len = strlen (age); /* get length of age */
if (!(node->age = malloc (len + 1))) { /* allocate/validate */
perror ("malloc-node->age");
free (node->firstName); /* free node->firstName, and */
free (node); /* free node before return */
return list;
}
memcpy (node->age, age, len + 1); /* copy age to node */
if (!list) /* if list empty */
return node; /* return node */
/* iterate until iter->firstName sorts before firstName */
while (iter && strcmp (firstName, iter->firstName) <= 0) {
prev = iter;
iter = iter->next;
}
if (!iter) { /* if new end node */
prev->next = node;
node->previous = prev;
}
else { /* insert between nodes */
node->next = iter->next;
node->previous = iter;
if (iter->next) /* protect when new next to last */
iter->next->previous = node;
iter->next = node;
}
/* if new first node, return iter, otherwise return list */
return strcmp (list->firstName, firstName) >= 0 ? node : list;
}
/** delete all nodes in list */
void del_list (Person *list)
{
while (list) {
Person *victim = list;
list = list->next;
free (victim->firstName);
free (victim->age);
free (victim);
}
}
int main (int argc, char **argv) {
FILE *in = argc > 1 ? fopen(argv[1], "r") : stdin;
char name[20];
char num[20];
Person *list=NULL;
while(fscanf(in, "%s %s",name, num)==2) {
list = add(list,name, num);
}
fclose (in);
printf ("Original List\n***\n");
print (list);
puts ("\nPointers\n***");
prnptrs (list);
printf ("\nPrinting Reversed List\n***\n");
#ifndef PASSPTR2PTR
reverseList(list);
#else
reverseList(&list);
print (list);
#endif
del_list (list);
return 0;
}
(1) 反向打印列表和 (2) 实际反转列表的两个版本都有条件地包含在PASSPTR2PTR. 如果未定义，它将简单地传递一个指向列表的指针，反向打印列表，如果PASSPTR2PTR已定义，它将传递列表指针的地址并执行实际的列表反转。
您在 pastebin 上发布的测试数据文件是：
$ cat dat/ypzgttvk.txt
John 12345
Sam 54321
Lion 43222
在这两种情况下，输出将是：
$ ./bin/lld_reverse_add dat/ypzgttvk.txt
Original List
***
John 12345
Lion 43222
Sam 54321
Pointers
***
(nil) 0xb014a0 0xb01580
0xb014a0 0xb01580 0xb01510
0xb01580 0xb01510 (nil)
Printing Reversed List
***
Sam 54321
Lion 43222
John 12345
其中显示了原始列表，列表previous current next中每个节点的所有节点的地址，最后将列表的输出反转。
如果您还有其他问题，请告诉我。
推荐阅读
- java - 如何将 io.micronaut.http.HttpRequest 转换为 CompletableFuture
- mongodb - MongoDB - 计算包含数组元素的数组中的值的总和
- c# - 如果该页面上有空间，有什么方法可以在同一页面上显示水晶报表的字段？
- go - 一对多关联
- python-3.x - Python串行失败
- json - Flutter - 对同一个 JSON 的多个 HTTP 请求
- json - Jenkins - 使用环境变量定义 json
- node.js - 套接字 IO 允许来自 curl 的 CORS 请求，但不允许来自客户端应用程序
- google-apps-script - How to print the result of a script on the current sheet
- javascript - 如何在本地保存使用带节点的 html2pdf 生成的 pdf？