我现在正努力学习C++，因为我必须学习一门来自Java的课程。我目前正在阅读《跳到C++》一书并完成练习。在阅读了关于链表的部分之后，它告诉我创建自己的链表，并使用一个方法来移除元素（在练习中使用指针）。
到目前为止，我已经能够向我的链表添加值，并显示我的链表。在执行了remove元素方法，并让我的程序明确地告诉我它已经删除了特定内存地址的值之后，我再次显示列表，发现我的值仍然以某种方式出现在应该被删除的内存地址。
这是我的removeElement方法：
// remove an element from the linked list
void removeElement(int remValue) {
// to remove an element, we go through the list, find the value given
// if we find it, stop
// to remove, disconnect the link
// relink the two values now (ie. value 1->2->3->NULL, 2 is removed, 1->3->NULL )
LinkedList* current = head;
LinkedList* next = current;
while(current != NULL) {
if(current->value == remValue) { // if match
break; // break out of while
}
else {
cout << "Value " << current->value << " does not match " << remValue << ".n";
next = current; // save in case
current = current->pNextValue; // go to next value
}
} // end while
if(current == NULL) { // if we reached end of list
cout << "Can't remove value: no match found.n"; // no match, cant remove
} else { // found match
cout << "Deleting: " << current << "n";
delete current;
current = next->pNextValue; // current is updated
}
}
以下是我的链接列表的全部代码（包括一些测试，以查看内容的进展）：
http://pastebin.com/cHZr4cBa
我意识到我的大多数代码对于现实的链表来说都是不高效和不正常的，我只是试图找出指针，以及如何在最基本的级别上在链表中使用它们。
您实际上并没有取消链接您删除的节点。
您需要跟踪上一个节点，并使其next指针指向当前节点next节点。还要考虑要删除的节点是第一个节点时的特殊情况。
@Joachim Pileborg是对的，您需要记录上一个节点，而不是next。
试试这个代码：
// remove an element from the linked list
void removeElement(int remValue) {
LinkedList* prev = head; // empty header
LinkedList* current = head->pNextValue; // the first valid node
while(current != NULL) {
if(current->value == remValue) {
break;
}
else {
cout << "Value " << current->value << " does not match " << remValue << ".n";
prev = current;
current = current->pNextValue; // go to next value
}
}
if(current == NULL) { // if we reached end of list or the list is empty
cout << "Can't remove value: no match found.n";
} else {
cout << "Deleting: " << current << "n";
prev->pNextValue = current->pNextValue; // unlink the node you remove
delete current; // delete the node
}
}
您需要更新列表中的链接以删除已删除的节点。
请注意，使用delete运算符不会更改内存中的任何值。它只是简单地告诉操作系统您不再使用内存中的该位置，它可以将其回收用于其他用途。
#include <iostream>
#include <cstdlib>
using namespace std;
class Node
{
public:
Node* next;
int data;
Node();
~Node();
void print();
};
class LinkedList
{
public:
int length;
Node* head;
LinkedList();
~LinkedList();
void add(int data);
void remove(int data);
Node* search(int data);
void print();
void size();
};
Node::Node(){
//set default values;
}
Node::~Node(){
cout << "NODE DELETED" <<endl;
}
void Node::print(){
Node* node = this;
if(node != NULL){
cout << "===============================" << endl;
cout << this->data << endl;
cout << "===============================" << endl;
}
}
LinkedList::LinkedList(){
this->length = 0;
this->head = NULL;
}
LinkedList::~LinkedList(){
cout << "LIST DELETED" <<endl;
}
void LinkedList::add(int data){
Node* node = new Node();
node->data = data;
node->next = this->head;
this->head = node;
this->length++;
}
void LinkedList::remove(int data){
if(this->length == 0){
cout << "The list is empty" << endl;
}else if(this->head->data == data){
Node* current = head;
this->head = this->head->next;
delete current;
this->length--;
}else{
Node* previous = this->head;
Node* current = head->next;
while(current != NULL) {
if(current->data == data) {
break;
}
else {
previous = current;
current = current->next;
}
}
if(current == NULL) {
cout << "Can't remove value: no match found.n";
} else {
previous->next = current->next;
delete current;
this->length--;
}
}
}
Node* LinkedList::search(int data) {
Node* head = this->head;
while(head){
if(head->data == data){
return head;
}else{
head = head->next;
}
}
cout << "No match found.n";
return NULL;
}
void LinkedList::print(){
if(this->length == 0){
cout << "The list is empty" << endl;
}else{
Node* head = this->head;
int i = 1;
cout << "===============================" << endl;
while(head){
cout << i << ": " << head->data << endl;
head = head->next;
i++;
}
cout << "===============================" << endl;
}
}
void LinkedList::size(){
cout << "List Length: " << this->length << endl;
}
int main(int argc, char const *argv[])
{
LinkedList* list = new LinkedList();
for (int i = 0; i < 5; ++i)
{
if(i == 3){
list->add(105);
list->add(106);
}
list->add(rand() % 100);
}
list->print();
list->size();
list->remove(105);
list->print();
list->size();
Node* node = list->search(106);
node->print();
delete list;
return 0;
}
基于@某个程序员兄弟的答案编写的代码。
void removeElement(int remValue) {
LinkedList * current, next, previous;
current = *&head;
while(current != NULL){
// `next` node
next = current->next;
// if match
if(current->value == remValue){
// if `previous` and `next` has a node, link the `previous` node to `next` node
if(previous != NULL && next != NULL) previous->next = next;
// if `current` is the last node, link `previous` node to `NULL`
else if(previous != NULL && next == NULL) previous->next = NULL;
// if `current` node is the first node, set the header node to `next` node
else if(previous == NULL && next != NULL) *&head = next;
// if `current` node is the only item, empty the list
else *&head = NULL;
cout << "Deleting: " << current->value << "n";
// delete node
delete current;
// exit the function
return;
// if not match
} else cout << "Value " << current->value << " does not match " << remValue << ".n";
// Variables for next loop
previous = current;
current = current->next;
}
// No Match
cout << "Can't remove value: no match found.n";
}
// C++ program to delete a node in
// singly linked list recursively
#include <bits/stdc++.h>
using namespace std;
struct node {
int info;
node* link = NULL;
node() {}
node(int a)
: info(a)
{
}
};
/*
Deletes the node containing 'info' part as val and
alter the head of the linked list (recursive method)
*/
void deleteNode(node*& head, int val)
{
// Check if list is empty or we
// reach at the end of the
// list.
if (head == NULL) {
cout << "Element not present in the listn";
return;
}
// If current node is the node to be deleted
if (head->info == val) {
node* t = head;
head = head->link; // If it's start of the node head
// node points to second node
delete (t); // Else changes previous node's link to
// current node's link
return;
}
deleteNode(head->link, val);
}
// Utility function to add a
// node in the linked list
// Here we are passing head by
// reference thus no need to
// return it to the main function
void push(node*& head, int data)
{
node* newNode = new node(data);
newNode->link = head;
head = newNode;
}
// Utility function to print
// the linked list (recursive
// method)
void print(node* head)
{
// cout<<endl gets implicitly
// typecasted to bool value
// 'true'
if (head == NULL and cout << endl)
return;
cout << head->info << ' ';
print(head->link);
}
int main()
{
// Starting with an empty linked list
node* head = NULL;