C++按姓名字母序插入的单链表makeMatch函数异常排查

功能要求 #

若待添加的全名（名+姓）与链表中现有任意全名都不重复，则将其插入链表并返回true。元素需先按姓的字母序排序插入，姓相同的元素按名的字母序排序插入。若全名已存在，则不对链表做任何修改，返回false（表示姓名已在链表中）。

现有实现代码 #

//this function add nodes to the list
//return true if fullname isn't in the list. Else return false if fullname is in the list.
//should be added according to last name.
bool OnlineDating::makeMatch(const std::string& firstName, const std::string& lastName, const OnlineType& value)
{
    Node* p = head;
    //are these nodes already set to firstName and lastName in this function
    Node first;
    Node last;
    Node* temp = nullptr;
    //if the list is empty just insert the fullname and value to the list
    if (p == nullptr) {
        //add values to the empty list
        insertToRear(firstName, lastName, value);
        return true;
    }
    else {
        // so this loop is to check if fullname is in the list but first sort in alphebetial order
        //sure its added in alphebetical order
        //traverse the list after knowing where head is
        while (p != nullptr) {

            //checking to make sure theres at least another node in the list
            if (p->next != nullptr) {
                //its not going through ig loop?
                //these are used to check and alphebetically selected names
                if (p->last > p->next->last) {
                    insertToRear(p->first, p->last, p->value);
                    p->next = temp;

                    return true;
                }
                else if (p->next->last > p->last) {
                    insertToRear(p->first, p->last, p->value);
                    p->next = temp;

                    return true;
                }
                //check if full name is already in the list
                if (p->last == p->next->last) {
                    insertToRear(p->first, p->last, p->value);
                    p->next = temp;

                    return true;
                }
                else if (p->first > p->next->first) {
                    insertToRear(p->first, p->last, p->value);
                    p->next = temp;

                    return true;
                }
                else {
                    //returns false if it passes through these  checks
                    return false;
                }
            }
            p = p->next;
        }
    }
}

测试代码（main.cpp） #

int main()
{

    OnlineDating clippersGonnaClip;
    clippersGonnaClip.makeMatch("Kawhi", "Leonard", 2);
    clippersGonnaClip.makeMatch("Paul", "George", 13);
    clippersGonnaClip.makeMatch("Ivica", "Zubac", 40);
    clippersGonnaClip.makeMatch("Reggie", "Jackson", 1);
    clippersGonnaClip.makeMatch("Patrick", "Beverley", 21);
    for (int n = 0; n < clippersGonnaClip.howManyMatches(); n++) {
        string first;
        string last;
        int val;
        clippersGonnaClip.confirmMatch(n, first, last, val);
        cout << first << " " << last << " " << val << endl;
    }

    return 0;
}

问题描述 #

原本的实现思路是创建指针遍历每一个节点，只要节点不为空就做判断，将链表按字母序排序，最后用temp指针完成节点关联。但现在每次运行编译都会得到负数，程序中其他函数均可正常运行，仅makeMatch函数存在异常。

错误原因 #

• 核心逻辑完全偏离需求：现有代码全程没有比对待插入的firstName、lastName参数和链表中已有节点的姓名，反而一直在比对相邻节点的姓名字段，完全没有实现姓名去重、按指定规则排序插入的功能。
• 链表结构被破坏：代码中temp指针始终为nullptr，所有判断分支执行时都会将p->next赋值为temp，直接截断链表，后续遍历会出现野指针、内存越界问题，这就是输出负数的根本原因。
• 插入逻辑错误：所有分支都调用insertToRear将节点插在链表尾部，完全没有实现按字母序插入到对应位置的要求。
• 遍历逻辑不成立：只要链表长度≥2，第一个节点就会命中p->next != nullptr的判断，直接执行return终止函数，根本不会遍历整个链表。
• 冗余无效代码：定义的Node first、Node last两个变量全程没有被使用，属于无效代码。

修正逻辑 #

1. 首先遍历整个链表，校验待插入的全名是否已经存在，存在则直接返回false。
2. 遍历过程中同时定位插入位置：找到第一个比待插入姓名排序更靠后的节点，将新节点插入到该节点之前；如果所有节点排序都更靠前，就插入到链表尾部。
3. 插入时仅修改新节点和相邻节点的next指针，不要随意修改已有节点的指向，避免破坏链表结构。

内容的提问来源于stack exchange，提问作者Emi Anyakpor