如何在C / C++中正确实现链接列表而不会使程序崩溃

Question

我正在尝试实现链表。在此示例程序中，用户输入一个整数值(要存储在列表中的字符串数(，然后逐个字符串...但是在几个输入(可能是 4 或 5(后，程序崩溃，就像这里的图像一样......

甚至，我不能一次调用任何包含 malloc(( 的函数超过 3 次。 我不知道为什么会出现这个问题。帮我解决问题....

#include <bits/stdc++.h>
using namespace std;
typedef struct Linked_List NODE;
struct Linked_List
{
string data;
NODE* next;
};
//Function prototypes
NODE *traverse(NODE *temp);
NODE* createNode(string data);
void preAppend(NODE* ln_list, string x);
NODE* find_data(NODE* ln_list, string data);
int main()
{
NODE* x=createNode("");
int t;
cin >>t;
string z;
while(t--)
{
cin >> z;
preAppend(x, z);
}
traverse(x);
return 0;
}
NODE *traverse(NODE *temp)
{
cout << temp->data << endl;
if(temp->next==NULL) return temp;
traverse(temp->next);
}
NODE* createNode(string data)
{
NODE* node = (NODE*)malloc(sizeof(NODE));
if(node==NULL)
{
printf("Error creating node (Error! Allocating Memory)n");
exit(1);
}
node->data = data;
node->next = NULL;
}
void preAppend(NODE* ln_list, string x)
{
NODE* new_node = (NODE*)malloc(sizeof(NODE));
if(new_node==NULL)
{
printf("Error! Appending (Error Allocating Memory)n");
exit(1);
}
new_node->data = x;
new_node->next = ln_list->next;
ln_list->next = new_node;
}
NODE* find_data(NODE* ln_list, string data)
{
NODE* current_node;
current_node = ln_list;
while(current_node->next!=NULL)
{
if(current_node->data == data)
{
return current_node;
}
current_node  = current_node -> next ;
}
return NULL;
}

Answer 1

代码中存在几个问题：

使用malloc而不是new

对包含 c++ 对象的对象(如string(使用malloc不会调用构造函数，因此对非构造对象的任何操作都将失败。

如果您的程序在没有return语句的情况下工作，那是因为未定义的行为

溶液：

取代

NODE* new_node = (NODE*)malloc(sizeof(NODE));

跟

NODE* new_node = new NODE;

非空函数中没有return语句

NODE *traverse(NODE *temp)
{
cout << temp->data << endl;
if (temp->next == NULL) return temp;
return traverse(temp->next);  // return statement is needed here
}
NODE* createNode(string data)
{
NODE* node = new NODE;
if (node == NULL)
{
printf("Error creating node (Error! Allocating Memory)n");
exit(1);
}
node->data = data;
node->next = NULL;
return node;    // return statement needed here
}

滥用递归

在traverse中使用递归可能会导致长列表的堆栈溢出。

应使用迭代方法。但是你已经发现了那个。

Answer 2

我一次上传了整个代码。此方法应该可以不间断地工作 虽然如果你想完全了解每个部分，我会建议你阅读我在我的网站上写的这篇文章。 https://www.thebytewise.com/post/data-structure-and-algorithm-using-c-linear-linked-list-thebytewise

#include<stdio.h>
#include<stdlib.h>
void createList();
void traverseList();
struct node{
int data;
struct node *next;
}*header;

int main(){
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
createList(n);
printf("nData in the list:n");
traverseList(n);
return 0;
}
void createList(int n){
struct node *newNode, *temp;
int data, i;
newNode = (struct node *) malloc(sizeof(struct node));
if(newNode == NULL){
printf("ERROR: Memory Overflow");
}
else{
printf("Enter element 1: ");
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
header = newNode;
temp = newNode;
for(i=2;i<=n;++i){
newNode = (struct node *) malloc(sizeof(struct node));
if(newNode == NULL){
printf("ERROR: Memory Overflow");
}
else{
printf("Enter element %d: ",i);
scanf("%d",&data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
}
}
void traverseList(int n){
struct node *temp;
int i;
if(header == NULL){
printf("ERROR: Memory Underflow");
}
else{
temp = header;
for(i=0;i<n;++i){
printf("ndata %d= %d",i+1, temp->data);
temp = temp->next;
}
}
}