假设我已经有一些链接列表已经可用,我想将每个列表的第一个节点存储到另一个列表中,以便我可以回想一下这个列表来显示原始列表。 我认为我们必须使用两种不同的结构。 我已经成功保留原始列表并使用单个列表的第一个节点的数组显示它们但我想创建一个单独列表的链接列表来实现它。 它有预期的输出,但正如我所说,我想使用链表而不是节点数组。
现在这就是我试图解决问题的方法,将链接列表数组替换为第一个节点的链表,每当我尝试调试代码时,我都会崩溃。 请帮我。
#include #include struct node{ int number; struct node*next; }; typedef struct node Node; Node* insertValue(Node * list, int value); void display(Node*); struct list_of_nodes { Node *list; struct list_of_nodes *next; }; typedef struct list_of_nodes ListNode; ListNode* insertNode(ListNode* head,Node* node); int main() { ListNode *head=NULL; Node *globalList = NULL, *lists[100]; int nbrOfLists, listNo, nbrOfVal, valNo, val,i=0,k; CHECKER: printf("nn Enter the number of lists (1 to 100):"); scanf("%d", &nbrOfLists); if(nbrOfLists 100) //handling exceptional cases { printf("n n Number of Lists should be between 1 to 100"); // since array of node pointers contains 100 elements goto CHECKER; } for(listNo = 0; listNo < nbrOfLists; listNo++) { printf("nn Enter the number of inputs to the list %d: n ",listNo+1); scanf("%d", &nbrOfVal); lists[listNo] = NULL; for(valNo = 0; valNo < nbrOfVal; valNo++) // to enter values in each individual list { printf("Enter node value %d:", valNo+1); scanf("%d", &val); // Here we insert the value in both lists lists[listNo]= insertValue(lists[listNo], val); // original list has to be retained so storing in array lists globalList = insertValue(globalList, val); // inserting node in combined list. This prevents an extra loop and merges the list elements into one. } head=insertNode(head,lists[listNo]); // CRASHING HERE printf("n The list %d is: ",listNo+1); display(lists[listNo]); // display each list after input } printf("nnn THE FINAL LIST IS: "); display(globalList); //display combined list printf("nn THE LISTS WERE: "); while(ilist=node; if(newNode == NULL) { newNode->next=NULL; // inserting first node return newNode; } m = head; while(m->next) // checking for right position in ordered list for new node { m = m->next; } newNode->next = m->next; // inserting new node m->next = newNode; return head; } Node* insertValue(Node * list, int value) // function to insert node in ordered manner into list { Node *newNode, *m; newNode = malloc(sizeof(Node)); newNode->number=value; if(list == NULL) { newNode->next=NULL; // inserting first node return newNode; } if(value number) { newNode->next = list; // inserting in end return newNode; } m = list; while(m->next) // checking for right position in ordered list for new node { if(value next->number) break; m = m->next; } newNode->next = m->next; // inserting new node m->next = newNode; return list; } void display(Node*nodex){ // display node values in list printf("%d ->",nodex->number); nodex=nodex->next; if(nodex) return display(nodex); else return 0; }
以下是显示预期结果但使用节点数组的代码:
#include #include #include struct node{ int number; struct node*next; }; typedef struct node Node; Node* insertValue(Node *list, int value); void display(Node*); int main() { Node *globalList = NULL, *lists[100]; int nbrOfLists, listNo, nbrOfVal, valNo, val, i = 0, k; CHECKER: printf("nn Enter the number of lists (1 to 100):"); scanf("%d", &nbrOfLists); if(nbrOfLists 100) //handling exceptional cases { printf("n n Number of Lists should be between 1 to 100"); // since array of node pointers contains 100 elements goto CHECKER; } for(listNo = 0; listNo < nbrOfLists; listNo++) { printf("nn Enter the number of inputs to the list %d: n ", listNo + 1); scanf("%d", &nbrOfVal); lists[listNo] = NULL; for(valNo = 0; valNo < nbrOfVal; valNo++) // to enter values in each individual list { printf("Enter node value %d:", valNo + 1); scanf("%d", &val); // Here we insert the value in both lists lists[listNo] = insertValue(lists[listNo], val); // original list has to be retained so storing in array lists globalList = insertValue(globalList, val); // inserting node in combined list. This prevents an extra loop and merges the list elements into one. } printf("n The list %d is: ", listNo + 1); display(lists[listNo]); // display each list after input } printf("nnn THE FINAL LIST IS: "); display(globalList); //display combined list printf("nn THE LISTS WERE: "); while(i number = value; if(list == NULL) { newNode->next = NULL; // inserting first node return newNode; } if(value number) { newNode->next = list; // inserting in end return newNode; } m = list; while(m->next) // checking for right position in ordered list for new node { if(value next->number) break; m = m->next; } newNode->next = m->next; // inserting new node m->next = newNode; return list; } void display(Node *nodex){ // display node values in list printf("%d ->", nodex->number); nodex = nodex->next; if(nodex) return display(nodex); else return 0; }
如果你不明白这个问题,请告诉我。
在聊天中进行了大量讨论后,我最终使用了与问题中最后一个版本密切相关的代码:
#include #include struct node { int number; struct node *next; }; typedef struct node Node; Node *insertValue(Node *list, int value); void display(Node *); struct list_of_nodes { Node *list; struct list_of_nodes *next; }; typedef struct list_of_nodes ListNode; ListNode *insertNode(ListNode *head, Node *node); int main(void) { ListNode *head = NULL; Node *globalList = NULL, *lists[100]; int nbrOfLists, listNo, nbrOfVal, valNo, val, i = 0, k; CHECKER: printf("nn Enter the number of lists (1 to 100):"); scanf("%d", &nbrOfLists); if (nbrOfLists <= 0 || nbrOfLists > 100) { printf("n n Number of Lists should be between 1 to 100"); goto CHECKER; } for (listNo = 0; listNo < nbrOfLists; listNo++) { printf("nn Enter the number of inputs to the list %d: n ", listNo + 1); scanf("%d", &nbrOfVal); lists[listNo] = NULL; for (valNo = 0; valNo < nbrOfVal; valNo++) { printf("Enter node value %d:", valNo + 1); scanf("%d", &val); lists[listNo] = insertValue(lists[listNo], val); globalList = insertValue(globalList, val); } head = insertNode(head, lists[listNo]); printf("n The list %d is: ", listNo + 1); display(lists[listNo]); } printf("nnn THE FINAL LIST IS: "); display(globalList); printf("nn THE LISTS WERE: "); while (i < nbrOfLists) { k = i + 1; printf("nn The list %d is: ", k); display(lists[i]); i++; } printf("nn"); return 0; } ListNode *insertNode(ListNode *head, Node *node) { ListNode *newNode, *m; newNode = malloc(sizeof(ListNode)); newNode->list = node; newNode->next = NULL; if (newNode == NULL) { fprintf(stderr, "Out of memory in %sn", __func__); exit(1); } if (head == NULL) return newNode; m = head; while (m->next) { m = m->next; } newNode->next = m->next; m->next = newNode; return head; } Node *insertValue(Node *list, int value) { Node *newNode, *m; newNode = malloc(sizeof(Node)); newNode->number = value; newNode->next = NULL; if (list == NULL) return newNode; if (value < list->number) { newNode->next = list; return newNode; } m = list; while (m->next) { if (value < m->next->number) break; m = m->next; } newNode->next = m->next; m->next = newNode; return list; } void display(Node *nodex) { printf("%d ->", nodex->number); nodex = nodex->next; if (nodex) display(nodex); }
使用示例数据文件( ll7.data
):
3 6 26 22 83 96 89 69 10 87 33 5 36 85 34 0 25 57 99 5 49 44 27 75 82
我使用以下编译ll7.c
:
$ gcc -O3 -g -std=c11 -Wall -Wextra -Werror ll7.c -o ll7 $
并在valgrind
下运行它,注意到代码泄漏就像一个筛子(因为看不到自由),但另外给它一个干净的健康状况。
$ valgrind --suppressions=suppressions ./ll7 < ll7.data ==7696== Memcheck, a memory error detector ==7696== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. ==7696== Using Valgrind-3.11.0.SVN and LibVEX; rerun with -h for copyright info ==7696== Command: ./ll7 ==7696== --7696-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option --7696-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 2 times) --7696-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 4 times) Enter the number of lists (1 to 100): Enter the number of inputs to the list 1: Enter node value 1:Enter node value 2:Enter node value 3:Enter node value 4:Enter node value 5:Enter node value 6: The list 1 is: 22 ->26 ->69 ->83 ->89 ->96 -> Enter the number of inputs to the list 2: Enter node value 1:Enter node value 2:Enter node value 3:Enter node value 4:Enter node value 5:Enter node value 6:Enter node value 7:Enter node value 8:Enter node value 9:Enter node value 10: The list 2 is: 0 ->5 ->25 ->33 ->34 ->36 ->57 ->85 ->87 ->99 -> Enter the number of inputs to the list 3: Enter node value 1:Enter node value 2:Enter node value 3:Enter node value 4:Enter node value 5: The list 3 is: 27 ->44 ->49 ->75 ->82 -> THE FINAL LIST IS: 0 ->5 ->22 ->25 ->26 ->27 ->33 ->34 ->36 ->44 ->49 ->57 ->69 ->75 ->82 ->83 ->85 ->87 ->89 ->96 ->99 -> THE LISTS WERE: The list 1 is: 22 ->26 ->69 ->83 ->89 ->96 -> The list 2 is: 0 ->5 ->25 ->33 ->34 ->36 ->57 ->85 ->87 ->99 -> The list 3 is: 27 ->44 ->49 ->75 ->82 -> ==7696== ==7696== HEAP SUMMARY: ==7696== in use at exit: 43,752 bytes in 471 blocks ==7696== total heap usage: 551 allocs, 80 frees, 49,880 bytes allocated ==7696== ==7696== LEAK SUMMARY: ==7696== definitely lost: 32 bytes in 2 blocks ==7696== indirectly lost: 688 bytes in 43 blocks ==7696== possibly lost: 0 bytes in 0 blocks ==7696== still reachable: 29,998 bytes in 310 blocks ==7696== suppressed: 13,034 bytes in 116 blocks ==7696== Rerun with --leak-check=full to see details of leaked memory ==7696== ==7696== For counts of detected and suppressed errors, rerun with: -v ==7696== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) $
当输入来自文件时,并不真正想要提示输出,这就是为什么数字也看不到的原因。 当您在终端上键入时,终端驱动程序会回显您在屏幕上键入的内容。 当数据来自文件时,您在阅读时看不到字符。
抑制文件列出并抑制来自Mac OS X 10.10.3 Yosemite运行时系统的各种泄漏。 这就是为什么使用这么多内存的原因; 运行时系统使用大量内存。
如果是我的所有代码,就会有很多不同的方式。 应该添加许多错误检查和可以/应该完成的重构(特别是“提取函数”),但是这些更改并不是为了保留与问题中发布的代码相似的一些外观。
更新:在我完成此操作前大约5分钟,发布了一个新版本的代码,似乎按照我的建议进行,但新function并不完全正确。
这是一个问题:
ListNode* insertNode(ListNode* head, Node* node){ // ... other code here ... m = head; while(m->next)
第一次insertNode
, head
是一个空指针(它应该是,因为列表列表在那时仍然是空的)。 所以这将m
设置为空指针,然后尝试访问m->next
… oops!
我看到这个评论:
// checking for right position in ordered list for new node
为什么? 什么是“正确的位置”? 似乎“正确的位置”是列表清单的末尾; 但是一开始有什么问题?
如果绝对必须按照输入列表的顺序排列列表,那么更简单,更有效的设计是在列表列表的开头插入每个新列表,并在完成所有操作后,反转列表列表。
但是你也可以稍微调整一下insertValue
的代码。 比较insertValue
这段代码:
newNode = malloc(sizeof(Node)); newNode->number=value; if(list == NULL)
这个insertNode
代码:
newNode = malloc(sizeof(ListNode)); newNode->list=node; if(newNode == NULL)
你看得到差别吗? 在insertValue
, if
测试传递给函数的指针; 在insertNode
, if
测试刚刚由newNode = malloc(sizeof(ListNode))
指定的指针。 当然, if(newNode == NULL)
将永远不会执行if
的主体(除非某些事情已经严重错误)。 你需要的是测试if(head == NULL)
以便你能正确处理这种情况。
其余部分涉及问题的旧版本。
除了其他可能没有做到他们应该做的事情之外,这段代码有许多严重的缺陷:
if(valNo==0){ // FOR EVERY FIRST NODE IN INDIVIDUAL LIST, I AM TRYING TO INSERT IT INTO LIST OF FIRST NODES head->list=malloc(sizeof(Nodex)); head->list=lists[listNo]; head=head->next; }
好的,第一个主要缺陷,您正在尝试在列表完成之前将新列表添加到列表列表中。 在列表完成之前,您不知道哪个节点最终会位于该列表的开头。 您插入列表的第一个节点可能会在完成列表中的任何位置结束。 这不是您想要列入列表的内容。 因此,您应该在代码中更改的一件事是将这些行(我复制的行)移出现在的内部for
循环; 改为在循环结束后放置它们(当然删除if(valNo==0)
;这些行应无条件执行)。
接下来,您从未为head
对点分配Nodex
,因此head->list
将始终是访问错误。
接下来, head->list=lists[listNo]
用head->list=malloc(sizeof(Nodex))
覆盖你刚刚设置的指针; 您使用malloc(sizeof(Nodex))
分配的内存会立即泄露。 (无论如何,它是使用错误类型的大小分配的,因为list
应该指向Node
而不是Nodex
,尽管Nodex
可能至少足够大,所以你可以逃脱这个错误。)
最后: head=head->next;
??? 由于head
是你在main()
函数开始时声明的唯一Nodex*
,如果你的列表中有一个合法的Nodex
,在head=head->next
,就没有任何东西指向那个Nodex
了,你在程序中找不到任何东西。 因此,如果您成功地将任何内容放入列表列表中,那么该步骤将基本上将其丢弃(它将成为内存泄漏)。
为了您的理智,您可能应该做的是编写一个函数Nodex* insertList(Nodex* list_list, Node* value_list)
,它将列表的头指针value_list
插入到列表列表中,类似于Node* insertValue(Node * list, int value)
的方式Node* insertValue(Node * list, int value)
在列表中插入一个数字,除了你可能不需要使insertList
保持其列表“已排序”,因此insertValue
应该比insertValue
简单得多。 (实际上它会如此简单,以至于你可能只想在你的main
函数中内联编写该函数的代码。我建议你抵制诱惑;在第一次尝试时编写内联代码并不适合你甚至非常简单的function来做好定义的事情是一种很好的做法。)
以上就是c/c++开发分享在链接列表的末尾插入节点而不是值相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/549334.html