C++链表Insert_Nth()节点插入位置错误问题求解

问题背景 #

补全给定缺失月份的利润数据，将缺失月份添加至对应位置后输出完整列表，同时计算所有月份利润值的总和与平均值。

当前存在的问题：

• 预期通过Insert_Nth()函数将May节点插入到March节点之后，实际运行时该节点被输出在January节点之后，结果不符合预期，不清楚问题成因和实现逻辑。
• 猜测需要使用if条件语句配合for循环精确定位链表中的目标插入位置后再执行插入操作，但不知道具体实现方法。

问题根因 #

你当前调用Insert_Nth(head)时，传入的参数是链表头节点（对应January）。而现有Insert_Nth()函数的逻辑是固定将新节点插入到传入的previous节点后方，所以May节点自然会被放到January节点之后，本质是传入的前置节点参数错误，没有先定位到目标插入位置的前置节点就执行了插入。

另外补充：按月份时间顺序，May（5月）应该放在April（4月）之后，如果插在March（3月）之后会出现月份顺序错乱的问题，你可以根据实际需求调整目标位置。

实现方案 #

方案1：最小改动，先定位前置节点再插入 #

不需要修改现有Insert_Nth()函数，只需要在调用前先遍历找到目标前置节点，替换main函数中原来的Insert_Nth(head);代码即可：

// 从表头开始遍历定位目标节点
node* prev_node = head;
while (prev_node != NULL) {
    // 如果要插在March后就判断March，插在April后就把字符串改成"April 2022: $"
    if (prev_node->month == "March 2022: $") {
        break;
    }
    prev_node = prev_node->next;
}
// 定位完成后执行插入
Insert_Nth(prev_node);

注意：上述代码需要在front(&head)调用前执行，避免表头新增节点后遍历逻辑异常。

方案2：改造插入函数，支持按索引位置插入 #

按照你猜想的思路，用循环定位位置，改造Insert_Nth()函数，直接传入目标插入位置即可，不需要手动找前置节点：

// 参数改为链表头指针的指针、目标插入位置（从0开始计数）
void Insert_Nth(node** head, int pos) {
    // 非法位置判断
    if (pos < 0) {
        cout << "\n插入位置不能为负数" << endl;
        return;
    }

    // 初始化May节点
    node* May = new node();
    May->month = "May 2022: $";
    May->value = n.may;

    // 插入到表头的情况
    if (pos == 0) {
        May->next = *head;
        *head = May;
        return;
    }

    // 循环遍历到插入位置的前一个节点
    node* prev = *head;
    for (int i = 0; i < pos - 1; i++) {
        prev = prev->next;
        if (prev == NULL) {
            cout << "\n插入位置超出链表长度" << endl;
            return;
        }
    }

    // 执行节点插入
    May->next = prev->next;
    prev->next = May;
}

函数改造完成后，main函数中调用方式改为：

• 如果要插在March（索引为2，0对应January、1对应February、2对应March）之后，传入位置3：Insert_Nth(&head, 3);
• 如果要符合时间顺序插在April（索引为3）之后，传入位置4：Insert_Nth(&head, 4);

现有问题代码 #

#include <iostream>
#include <stdio.h>
#include <iomanip> //library needed for setprecision 

using namespace std;

class node {
public:
    int value = 0;
    string month;
    node* next;
};

struct NewValues {
    long int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, may = 0;
} n;

void front(node* *head)
{
    node* Dec = new node();
    node* Nov = new node();
    node* Oct = new node();
    
    Dec->value = n.c;
    Dec->month = "December 2021: $";
    Dec->next = *head;
    *head = Dec;

    Nov->value = n.b;
    Nov->month = "November 2021: $";
    Nov->next = Dec;
    *head = Nov;

    Oct->value = n.a;
    Oct->month = "October 2021: $";
    Oct->next = Nov;
    *head = Oct;
}

void end(node* *head)
{
    node* June = new node();
    node* July = new node();        
    node* Aug = new node();
        
        //find the last node
            node* last = *head;
                while (last->next != NULL) {
                    last = last->next;
                }

    Aug->value = n.f;
    Aug->month = "August 2022: $";
    Aug->next = NULL;
    last->next = Aug;
    
    July->value = n.e;
    July->month = "July 2022: $";
    July->next = Aug;
    last->next = July;
    
    June->value = n.d;
    June->month = "June 2022: $";
    June->next = July;
    last->next = June;
}

void Insert_Nth(node* previous)
{
    //1: check if previous node is null
        if(previous == NULL) {
        cout << "\nPrevious cannot be null" << endl;
        return;
        }
    
    //2: prepare a newnode assign value
    node* May = new node();
    May->month = "May 2022: $";
    May->value = n.may;
    
    //3: insert newnode after previous
    May->next = previous->next;
    previous->next = May;
}

void sumOfNodes(node* head, long double* sum)
{
    // if head = NULL
    if (!head)
        return;

    // recursively traverse the remaining nodes
    sumOfNodes(head->next, sum);

    // accumulate sum
    *sum = *sum + head->value;
}

int sumOfNodesUtil(node* head)
{
    long double sum = 0;

    // find the sum of  nodes
    sumOfNodes(head, &sum);

    // required sum
    return sum;
}

void printList(node* n)
{
    cout << "\nList of earnings from October 2021 - August 2022\n" << endl;
    
    while (n != NULL) {
        cout << n->month << n->value << endl;
        n = n->next;
    }
}

void deleteList(node* *head_ref)
{
    /* deref head_ref to get the real head */
    node* current = *head_ref;
    node* next = NULL;
  
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
  
    /* deref head_ref to affect the real head back
        in the caller. */
    *head_ref = NULL;
}

int main()
{
    cout << "Hello, This program takes in input for unaccounted months from your";
    cout << " salary over the months and prints them out, \nalong with the total and average." << endl;
    cout << "\nThere are a total There are 11 months and 7 months unaccounted for..." << endl;
    cout << "please enter in the data for the missing months when prompted" << endl;
    
    cout << "\n------------------------" << endl;
    
    cout << "October 2021: $";
    cin >> n.a;

    cout << "November 2021: $";
    cin >> n.b;

    cout << "December 2021: $";
    cin >> n.c;

    cout << "May 2022: $";
    cin >> n.may;
    
    cout << "June 2022: $";
    cin >> n.d;

    cout << "July 2022: $";
    cin >> n.e;

    cout << "August 2022: $";
    cin >> n.f;
    
    cout << "------------------------" << endl;
    
    node* head = new node();
    node* second = new node();
    node* third = new node();
    node* fourth = new node();

    head->value = 500;
    head->month = "January 2022: $";
    head->next = second;

    second->value = 125;
    second->month = "Febuary 2022: $";
    second->next = third;

    third->value = 200;
    third->month = "March 2022: $";
    third->next = fourth;

    fourth->value = 300;
    fourth->month = "April 2022: $";
    fourth->next = NULL;

    Insert_Nth(head);
    front(&head);
    end(&head);
    printList(head);
    
    long double avg = sumOfNodesUtil(head) / 11;

    cout << "\n\n------------------------" << endl;

    cout << "Total earnings: $" << setprecision(6) << sumOfNodesUtil(head) << endl;
    cout << "Average: $" << setprecision(6) << avg << endl;
    
    cout << "------------------------" << endl;

    cout << "\nDeleting Linked List..." << endl;
    
    deleteList(&head);
    
    cout << "\nLinked List Deleted\n\n\tProgram Terminated..." << endl;
}

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