将链接列表按字母顺序排序

Question

从排序的链接列表中删除节点时遇到问题。我从.txt文件读入了73个必须按字母顺序排序的不同名称。我有一个switch语句应该能够对链表执行5个单独的事情。目前我已经拿到1号和2号的工作，但不是三号。 ＃3希望我能够从链接列表中删除名称。在我输入要删除的名称后，我的代码不会显示任何内容。因此我假设我遇到了deleteAfter函数的问题。任何人都可以给我一个暗示，为什么这可能是？

#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <fstream> 
using namespace std; 

struct node{ 
    string name; 
    node *next; 
}; 

node *A = NULL; 

void addnode(string newname){ 
    node *add, 
     *last, 
     *current; 

    add = new node; 
    add->name = newname; 

    if (A == NULL){ 
     add->next = A; 
     A = add; 
    }else{ 
     current = A; 
     last = A; 
     while (current && current->name < newname){ 
      last = current; 
      current = current->next; 
     } 

     if (current == A){ 
      /* Insert before 1st node */ 
      add->next = A; 
      A = add; 
     } 
     else{ 
      /* Insert between last and current 
       or at the end of the list */ 
      last->next = add; 
      add->next = current; 
     } 
    } 
} 
void deleteName(string name) 
{ 
    node *curr; 
    node *nextNode; 
    curr = A; 
    nextNode = curr; 
    while(curr){ 
     if(curr -> next -> name == name){ 
      nextNode = curr -> next; 
      curr -> next = nextNode -> next; 
     } 

    } 


} 



void display() 
{ 
    node *curr; 
    curr = A; 
    while(curr){ 
     if(A == NULL){break;} 
     cout << A->name << endl; 
     A = A->next; 
    } 

} 

int main(){ 


    int input, count; 
    count = 0; 
    ifstream dataFile; 
    dataFile.open("Data.txt"); 
    string item; 
    string name; 
    while(dataFile) 
    { 
     dataFile >> item; 
     addnode(item); 
     count++; 
    } 




    cout << "1. Display the linked list\n"; 
    cout << "2. Display the length of the list\n"; 
    cout << "3. Delete name from the list\n"; 
    cout << "4. display the length of a section of the list\n"; 
    cout << "5. Print out section of list\n"; 
    cin >> input; 

    switch (input) 
    { 
    case 1: 
     display(); 
     break; 
    case 2: 
     cout << "There are " << count - 1 << " names in the list\n"; 
     break; 
    case 3: 
     cout << "Type in the name that you want to be deleted: "; 
     cin >> name; 
     deleteName(name); 
     display(); 
     break; 
    case 4: 
     break; 
    case 5: 
     break; 
    } 


    system("PAUSE"); 
    return 0; 

} 

这是我到目前为止的代码。你会注意到，在我的主函数中，我从一个名为“Data.txt”的文件读取输入。

joe 
bob 
harry 
mary 
brian 
tom 
jerry 
bullwinkle 
pam 
ellis 
dale 
bill 
barrack 
george 
gertrude 
zack 
zeus 
apollo 
gemini 
greg 
larry 
meriam 
webster 
thomas 
stewart 
dianna 
theresa 
billyjoe 
carl 
karl 
charles 
karla 
donna 
tena 
kerry 
howard 
johnson 
ulyssess 
paul 
peter 
issaac 
marvin 
dudz 
chuck 
ellie 
anny 
judy 
matt 
ross 
dan 
robert 
kim 
eric 
junkun 
ghassan 
cris 
raymond 
avery 
roy 
halley 
mitzee 
ziggy 
rocky 
twirly 
max 
huey 
dewy 
hongkongfooey 
clarence 
lala 
sammy 
fred 
francis 

这就是txt文件由^^组成的内容。任何建议将不胜感激。谢谢！

Answer 1

您正在访问下一个，但未检查它是否为空，而且您没有遍历该列表。另外，你应该在找到它之后再打破它（除非你想删除所有的实例，并且你应该删除这个节点，因为你会泄漏内存，而且你也不能删除第一个元素，因为你永远不会检查它。因为你需要处理不断变化的根节点你可以在它的特殊检查添加。

if (A != nullptr && A->name == name) 
{ 
    node *toBeDeleted = A; 
    A = A->next; 
    delete toBeDeleted; 
    return; 
} 

while(curr && curr->next){ 
    if(curr->next->name == name){ 
     nextNode = curr->next; 
     curr->next = nextNode->next; 
     delete nextNode; 
     break; 
    } 
    curr = curr->next; 
} 

当然，如果你想删除的名称的所有实例，您需要删除的回报和休息声明

你的显示功能也将清空列表您需要设置CURR，没有A：

void display() 
{ 
    node *curr; 
    curr = A; 
    while(curr){ 
     cout << curr->name << endl; 
     curr = curr->next; 
    } 
} 

Answer 2

while (current && strcmp(current->name , newname) <=0){ 
    last = current; 
    current = current->next; 
} 

试试这个。

Answer 3

您正在使用链接列表数据结构。我发现奇怪的是你使用了一个循环。最后一个节点的下一个元素再次指向开头。

这里是deleteName我根据自己的知识和风格（即我相信看到）的级建议：

void deleteName(string name) { 

    node *current = A; 
    node *previous; 

    while (current) { 
     if (current->name == name) { 
      previous->next = current->next; 
      delete current; 
      break; 
     } else { 
      previous = current; 
      current = current->next; 
     } 
    } 
}