链表(删除节点)

Question

我的问题是，如果用户输入一个姓氏，并且链表中有多个相同的姓氏，其中一个姓氏在head节点中。如何在不删除头节点的情况下删除其他姓氏呢?我尝试了一些我能想到的方法，但所需的节点被删除(这很好)，包括头节点(这不是我想要的…)

void NumberList::deleteCertainRecord()
{
string lname = "";
ListNode *ptr;
ptr = head;
string answer;
cout << "Please enter last name: "<<endl;
cin>>answer;
int num = 0;
char confirm;
while (ptr!= NULL){
    lname = ptr -> data.person.getLastName();
    if(lname == answer){
        num++;
        cout << "Person found : ";
        cout << ptr->data.person.getTitle()<<" " << ptr -> data.person.getFirstName() << " " << ptr -> data.person.getLastName() << endl << endl;
        cout << "Do you want to delete his/her record? [Y/N]" << endl;
        do{
            cin >> confirm;
            if(confirm=='Y'||confirm=='y'){
                    ListNode *previousNode;
                    if(isEmpty()){
                        return;
                    }
                    else if(head->data.person.getLastName() == answer){
                        ptr = head->next;
                        delete head; 
                        head = ptr;
                    }
                    else{
                        ptr = head;
                        while(ptr!=NULL && ptr->data.person.getLastName() != answer){
                            previousNode = ptr;
                            ptr = ptr->next;
                        }
                        if(ptr==NULL){
                            cout<< "Node not found!" << endl;
                            return;
                        }
                        else{
                            previousNode->next = ptr->next;
                            delete ptr; 
                        }
                    }
                    cout << endl << "Deleting..."<<endl;
                    cout << "Done!!" <<endl;
                    cout << "Exiting delete function... "<<endl;
                    return;
            }
            else if(confirm=='N'||confirm=='n'){
                break;
            }
            else{
                cout << "invalid input, please enter again!!" << endl;
            }
        }while(confirm!='Y'&&confirm!='y'&&confirm!='n'&& confirm!='N');
        cout << endl;
    }
    ptr = ptr -> next;
}
if (num == 0){
    cout << "nNo person with the last name ("<< answer << ") was found!" << endl;
    cout << "Exiting delete function... "<<endl;
    return;
}
}

Answer 1

你这样做的代码的绝对数量是模糊的实际意图。

• 你有一个人的链表。
• 给定一个姓，您想枚举查找匹配的列表。
• 在发现匹配时，您希望提示用户进行删除确认
• 如果确认删除，则提取发现的节点，否则保持列表完整，并删除。
• 如果没有确认，跳到下一个节点，寻找更多的匹配

如果节点实际上是头节点，则删除部分显然有问题。对于刚接触链表的人来说，特殊情况的头节点逻辑总是很棘手。幸运的是，如果你使用正确的算法，它可以完全被规避。假设列表以NULL结束，如果列表为空， 包括NULL头指针，这样的算法如下:

ListNode ** pp = &head;
while (*pp)
{
    if ((*pp)->data.person.getLastName() == answer &&
         confirmDelete((*pp)->data.person)) // <== TODO: write this function
    {
        ListNode *victim = *pp;
        *pp = victim->next;
        delete victim;
    }
    else
    {   // just advance to next person
        pp = &(*pp)->next;
    }
}

这将正确地删除用户，即使他们是列表中的第一个节点和正确地为您推进头部指针。它也适用于具有和不具有匹配条件的单节点列表，甚至head为NULL的空列表。该技术使用列表中的指针作为枚举列表的机制;不仅仅是它们的值，实际的指针。

最后，如果您保持列表的排序，这可以大大提高效率，但我把它留给您。