排序链接列表中的名称
问题描述:
我想按链接列表中的字母顺序排列名称,但得到运行时错误。我在这里做错了什么?排序链接列表中的名称
#include <iostream>
#include <string>
using namespace std;
struct node{
string name;
node *next;
};
node *A;
void addnode(node *&listpointer,string newname){
node *temp;
temp = new node;
if (listpointer == NULL){
temp->name = newname;
temp->next = listpointer;
listpointer = temp;
}else{
node *add;
add = new node;
while (true){
if(listpointer->name > newname){
add->name = newname;
add->next = listpointer->next;
break;
}
listpointer = listpointer->next;
}
}
}
int main(){
A = NULL;
string name1 = "bob";
string name2 = "tod";
string name3 = "thomas";
string name4 = "kate";
string name5 = "alex";
string name6 = "jimmy";
addnode(A,name1);
addnode(A,name2);
addnode(A,name3);
addnode(A,name4);
addnode(A,name5);
addnode(A,name6);
while(true){
if(A == NULL){break;}
cout<< "name is: " << A->name << endl;
A = A->next;
}
return 0;
}
答
我认为错误是,你认为:
if (listpointer == NULL){
temp->name = newname;
temp->next = listpointer;
listpointer = temp;
}
保证listpointer永远不会为NULL后。然而,这是不是这样的,例如:
void addnode(node *&listpointer,string newname){
node *temp;
temp = new node;
if (listpointer == NULL){
temp->name = newname;
temp->next = listpointer;
listpointer = temp;
}else{
node *add;
add = new node;
while (true){
if((listpointer) == NULL){
std:cout << "oops (listpointer) == NULL)";
}
if(listpointer->name > newname){
add->name = newname;
add->next = listpointer->next;
break;
}
listpointer = listpointer->next;
}
}
}
会打印出“糟糕”则作为段错误是lispointer NULL和使用 - >对NULL会导致段错误。这是因为在while(true)循环中,列表指针最终到达最后并被设置为NULL。你然后得到段错误。
我想一个更好的想法是做类似:
bool has_inserted;
while (listpointer != NULL){
if(listpointer->name > newname){
add->name = newname;
add->next = listpointer->next;
has_inserted = true;
break;
}
listpointer = listpointer->next;
}
if(has_inserted == false){
//insert at end of list
}
而且这个代码泄漏内存,你不删除你创建新的东西。你可能想用valgrind运行这个(和其他代码)来看看我的意思。从你的代码删除临时从内存泄漏防止 -
1:
答
您试图取消引用addnode
中的空指针。在listpointer->name > newname
从不为真的情况下,listpointer
最终将被设置为NULL,然后在接下来的listpointer->name > newname
比较中尝试再次解除引用。
...代码中的其他可能的逻辑错误,也就是说。
答
我做你的代码进行一些修改。
2 - 您必须保持列表的第一个元素的指针。如果你失去了它,你将无法再添加更多的项目或打印列表内容。
3 - 代码必须分析是否必须将新项目插入列表的顶部,中间或末尾。如果在顶部,则列表指针必须更改为它。
所以我修复了这个bug,你的代码现在已经很好了。
请记住,您的main()应该调整为在打印其项目时不更改列表指针(A)。如果是这样,打印后您将失去对列表的控制权,并且无法再访问或删除其节点。如果你在这个测试中不关心它,就忘记它。
void addnode(node *&listpointer,string newname){
node *add,
*last,
*current;
add = new node;
add->name = newname;
if (listpointer == NULL){
add->next = listpointer;
listpointer = add;
}else{
current = listpointer;
last = listpointer;
while (current && current->name < newname){
last = current;
current = current->next;
}
if (current == listpointer){
/* Insert before 1st node */
add->next = listpointer;
listpointer = add;
}
else{
/* Insert between last and current
or at the end of the list */
last->next = add;
add->next = current;
}
}
}
为什么你的代码中没有一个而是两个*无限循环? – 2010-05-31 04:35:58
你也有一个很好的内存泄漏,在'listpointer'不为NULL的情况下'temp'被创建,但未被使用(并且因此不可能被释放)在'addnode'中。 – 2010-05-31 04:38:07