删除单链表中特定数字范围之外的节点

Question

我正在研究这个程序，它读取文本文件并从文本文件中抓取数据并将其插入链表的节点中。

我有整个程序运行和工作良好，除了节点删除。我是从文本文件过滤的数据，所以我只需要打印出有一定范围内的值的数据。我可以用if()语句做到这一点，它工作得很好，但这不是我想要的结果。

我想删除超出指定范围的节点，并释放它们正在使用的内存。我写了几行代码来尝试这样做，但它最终只是删除了整个列表。所以如果有人能给我指出正确的方向，告诉我我做错了什么，那就太好了!

#include <fstream>
#include <iostream>
using namespace std;
struct Employee
{
    string firstN;
    string lastN;
    float salary;
    float bonus;
    float deduction;
    Employee *link;
};
typedef Employee* EmployPtr;
void insertAtHead( EmployPtr&, string, string, float, float,float );
void insert( EmployPtr&, string, string, float, float,float );
float netSalary( EmployPtr& );
int main()
{
//Open file
fstream in( "payroll.txt", ios::in );
//Read lines
string first, last;
float salary, bonus, deduction;
EmployPtr head = new Employee;
//Inserts all the data into a new node in the linked list, creating a new node each time the loop executes.
while( in >> first >> last >> salary >> bonus >> deduction)
    insertAtHead (head, first, last, salary, bonus, deduction);
//Close file
in.close();
cout << "-Salary in the range of ($45,000 - $60,000)-n" << "Printed in format: First Name, Last Name, Salary, Bonus, Deduction, Net Salary.n";
EmployPtr iter, temp;
for(iter = head; iter!= NULL; iter = iter->link)
{
    temp = head;
    //Deletes nodes outside of range.
    while(netSalary(iter)<45000 || netSalary(iter)>60000)
    {
        EmployPtr nodeToDelete = temp;
        temp = temp->link;
        delete nodeToDelete;
    }
    cout << iter->firstN << ", " << iter->lastN << ", " << iter->salary << ", " << iter->bonus << ", " << iter->deduction << ", " << netSalary(iter) <<endl;
}
    return 0;
}
    //Based off of the input values, this function will create a new node and insert it at the beginning of the linked list. This function ONLY allows insertion at the beginning of the list and no where else.
 void insertAtHead(EmployPtr& head, string firstValue, string lastValue,
            float salaryValue, float bonusValue,float deductionValue)
{
    EmployPtr tempPtr= new Employee;
    tempPtr->firstN = firstValue;
    tempPtr->lastN = lastValue;
    tempPtr->salary = salaryValue;
    tempPtr->bonus = bonusValue;
    tempPtr->deduction = deductionValue;
    tempPtr->link = head;
    head = tempPtr;
}
//Based off of the input values, this function creates a new node and inserts it AFTER the node provided in the argument.
void insert(EmployPtr& afterNode, string firstValue, string lastValue,
        float salaryValue, float bonusValue,float deductionValue)
{
    EmployPtr tempPtr= new Employee;

    tempPtr->firstN = firstValue;
    tempPtr->lastN = lastValue;
    tempPtr->salary = salaryValue;
    tempPtr->bonus = bonusValue;
    tempPtr->deduction = deductionValue;
    tempPtr->link = afterNode->link;
    afterNode->link = tempPtr;
}
//This function calculates a net salary based off of the salary, bonus, and deduction variables of the input node.
float netSalary(EmployPtr& node)
{
    float netSalary, newDeduction;
    newDeduction = ((node->salary) + (node->bonus)) * (node->deduction);
    netSalary = (node->salary + node->bonus) - newDeduction;
    return netSalary;
}

编辑:更改&&返回到||仍然有问题。

EDIT #2: Solution

while(netSalary(iter)<45000 || netSalary(iter)>60000)
        {
            EmployPtr nodeToDelete = new Employee;
            nodeToDelete = iter;
            iter = iter->link;
            delete nodeToDelete;
        }

Answer 1

这一行:

while(netSalary(iter)<45000 && netSalary(iter)>60000)

我认为你的条件应该是OR(||)。一个值同时小于45000和大于60000是没有意义的。

给定一个值25000，它将小于45000，但不大于60000，因此不会删除任何内容。

编辑:也许你可以试试这样做:

for (iter = head; iter != NULL; iter = iter->link) 
{
    cout << iter->salary; // so you can see what node it's looking at
    if (netSalary(iter) < 45000 || netSalary(iter) > 60000)
    {
        EmployPtr nodeToDelete = iter;
        iter = iter->link; // difference here is that you're explicitly moving the iter forward
        delete nodeToDelete;
    } 
}

Answer 2

我想你希望条件是

while(netSalary(iter) >= 45000  &&  netSalary(iter) <= 60000)

我说think是因为我没有看到你真正想要过滤掉的语句

Answer 3

您应该首先更改while条件。'&&'应该是'||'，因为'<45000’，同时大于60000。另外，如果节点不满足这些条件，为什么不完全跳过向列表中添加节点呢?换句话说，在创建列表时，检查这些条件，如果不满足就不要添加到列表中。这样你就不会创建一个列表，然后马上回来修改它。

编辑:

好的，问题，我认为，是与while循环使用'iter'。一旦迭代器匹配了while循环中的条件，在此之后不需要再移动迭代器(因为您没有回到for循环)，因此可以删除while循环内列表的其余部分。试着把while改成if，看看你得到了什么。

Answer 4

最新的解决方案应该解决了主要问题(删除整个列表，因为循环以head而不是iter开始)，但您可能仍然会遇到另一个问题。如果最后一个元素被删除，下一次检查循环条件时，将在空指针上调用netSalary(因为iter一旦进入iter->link将为空)。此外，试图修改该循环以考虑空指针可能会导致外部for循环试图访问空指针的link成员。

我建议的最简单的解决方案是修改代码，只使用一个while循环和条件，如下面的代码所示:

EmployPtr iter = head, temp;
while(iter!= NULL)
{
    if(netSalary(iter)<45000 || netSalary(iter)>60000)
    {
        // bad node, delete and advance
        EmployPtr nodeToDelete = iter; 
        iter = iter->link;
        delete nodeToDelete;
    } 
    else 
    {
        // good node, write and advance
        cout << iter->firstN << ", " << iter->lastN << ", " << iter->salary << ", " << iter->bonus << ", " << iter->deduction << ", " << netSalary(iter) <<endl;
        iter = iter->link;
    }
}