c++ - 删除链表中的特定节点
问题描述
我有一个这样的链接列表
struct product {
string ID;
double quantity;
product* next = NULL;
};
我想删除所有数量小于数字的产品。如果至少删除一个产品,此函数返回 true,否则返回 false。这是我的代码
bool deleteProducts(product*& pHead, double quantity) {
static int flag = 0;
product* pTemp = pHead;
product* prev = pHead;
if (pTemp != NULL && pTemp->quantity <= quantity) pHead = pTemp->next;
while (pTemp != NULL && pTemp->quantity > quantity) {
prev = pTemp;
pTemp = pTemp->next;
}
if (pTemp == NULL) return flag;
flag = 1;
prev->next = pTemp->next;
deleteProducts(prev->next, quantity);
}
但是当我有一个这样的列表(仅限数量)时:
7 -> 7.5 -> 2 -> 5 -> 6
我运行数量 = 10 的函数,它返回:
7.5 -> 5
这不是真的,谁能给我解释一下。提前致谢!
解决方案
你的方法有几个问题。
- 您正在使用静态
flag
. (请参阅其他评论以了解它为什么不好。) - 您正在使用递归。由于您使用的是静态标志,因此它会破坏递归。
- 您可以在迭代自身时删除元素,然后运行时间将是 O(n)。
- 您可以使用双向链表来避免
pPrev
在循环中使用。
这是我想出的正确解决方案。
#include <iostream>
#include <string>
using namespace std;
typedef struct product {
string ID;
double quantity;
product* next = NULL;
} product;
product* deleteProducts(product*& pHead, double quantity) {
product* pTemp = pHead;
product* pPrev = pHead;
while (pTemp != NULL) {
if ( pTemp->quantity > quantity ){
if ( pTemp == pHead ){
cout << "Deleteing Current Head " << pTemp->quantity << endl;
product* pTmp = pHead;
pTemp = pTemp->next;
pHead = pPrev = pTemp;
delete pTmp;
}
else{
cout << "Deleteing Node" << pTemp->quantity << endl;
product* pNext = pTemp->next;
delete pTemp;
pTemp = pNext;
pPrev->next = pTemp;
}
}
else{
pPrev = pTemp;
pTemp = pTemp->next;
}
}
return pHead;
}
bool printProducts(product*& pHead) {
product* pTemp = pHead;
while (pTemp != NULL) {
cout << pTemp->quantity << " ";
pTemp = pTemp->next;
}
cout << endl;
}
int main()
{
product* p1 = new product{"1", 7};
product* p2 = new product{"2", 7.5};
product* p3 = new product{"3", 2};
product* p4 = new product{"4", 5};
product* p5 = new product{"5", 6};
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p5;
if ( deleteProducts(p1, 10) ){
cout << "Done" << endl;
}
printProducts(p1);
return 0;
}
推荐阅读
- c# - 为什么在反序列化期间尝试解析派生类型时会出错?(Newtonsoft.Json)
- javascript - 如何在 Chrome 中为某些字段禁用用户名自动填充?
- scala - 在 Scala 2.13 中发布一个暴露库的 SBT 插件
- python - Python - 字符串转换为列表
- encryption - ISAP 轻量级加密算法
- sql-server - 将表数据类型从 SQL Server 转换为 Oracle 并将动态 SQL 数据插入到表数据类型
- python - 如何根据同一个类的另一个属性的值来访问一个类的属性?
- typescript - 如何使用 TypeScript 中预定义的可接受值正确声明自定义类型?
- ruby - docker-compose 选择了错误的 ruby 版本
- python-3.x - 使用单个命令运行测试并收集覆盖率报告