所以我一直在搜索论坛，但我对语言和链接列表仍然很陌生，所以我几乎无法破译结果。
基本上我为我的链表做了一个删除功能。我目前可以创建列表，遍历列表，排序列表，搜索列表，并在链表中的任何节点之前插入。我从插入中回收了一些代码，以找到列表中可以删除的点。我的主要困惑是如何将以前的点链接到我要删除的节点之后的节点。
问问题
92183 次
5 回答
7
我不会编写一个全新的链表实现，但我可以为您指出代码中的一些问题。
诀窍是在要删除的节点之前保持一个节点。
为了清楚起见，我已重命名entry为current
nodetype *current , *first, *next;
int akey;
// With this line your search will start from the second element.
// current =start->ptr;
// Should be
current = start;
// this is not needed. I am assuming the last node has NULL value for '->ptr'
// last=start;
next = current->ptr;
cout<<"Input Data You Would Like To Delete"<<endl;
cin>>akey;
// Check if the first node contains the data
// Assuming the list will have at least one element. i.e. current is not NULL
while (current->adata == akey)
{
// Delete it.
delete current;
// Update current for the while loop
current = next;
// update next too.
next = current->ptr;
}
// Now we know the first element doesn't contain the data.
// Update the pointer to the begging of the new list if anything is removed from the top.
first = current;
// This has unnecessary checks.
// ****Specifically (akey!=current->adata) will
// prevent you from entering the loop if it is false.
// while((akey!=current->adata)&&(current->ptr !=NULL))
while(next != NULL) // This should be enough
{
if(next->adata == akey)
{
// make the current node (before the 'deletion point')
// lined to the one after the 'deletion point (next of the next)
current->ptr = next->ptr;
// delete the node.
delete next;
// Make the next pointer point to the new next.
next = current->ptr
}
// Otherwise advance both current and next.
else {
current = next;
next = next->ptr;
}
}
// Use this to test it.
current = first;
while(current){
cout<<current->adata<<", ";
current = current->ptr;
}
这不是最干净的方法。但是，它与您的实现类似，因此您可以看到哪里出错了。
于 2013-03-24T20:24:04.073 回答
4
#include <iostream>
#include <string>
// blank line(s) after includes
using namespace std; // some people will say to avoid this
// but I use it in examples for brevity
// blank line(s) around class def
class nodetype
{ // bracket on its own line
public: // non indented visibility specifier
nodetype(int value, nodetype *p) // constructor first declared in class
{
adata = value; // level of indentation for fn body
ptr = p; // spaces around operators like =
}
// blank line(s) between fns and vars
int adata;
nodetype *ptr;
};
// blank line(s) between class and fn
void LinkedListDelete(nodetype **start, int akey)
{
nodetype *current, **previous; // pointer *s are connected to vars
// blank line between section
previous = start;
current = *start;
// blank line between section
// I use blank lines a lot, they help
// me to organize my thoughts
while((current != NULL) && (akey != current->adata))
{ // indentation inside nested scope
previous = ¤t->ptr; // no space for unary operators like &
current = current->ptr; // assignments justified to same level
}
if (current != NULL)
{
*previous = current->ptr; // no space for unary *, space for =
delete current;
}
// more blank lines between sections
return;
}
void LinkedListPrint(nodetype *list) // no space for unary *
{ // brackets on their own lines
while (list != NULL) // space around !=
{
cout << "(Node: " << list->adata << ") ";
list = list->ptr; // spaces around <<
}
cout << endl;
}
int main()
{
nodetype *node = new nodetype(5, new nodetype(10, // justified stuff
new nodetype(7, new nodetype(14,
new nodetype(23, NULL)))));
// blank lines
cout << "Build linked list: ";
LinkedListPrint(node);
cout << "Removed node 7: ";
LinkedListDelete(&node, 7);
LinkedListPrint(node);
return 0;
}
我根据您提供的代码制作了此代码。不完全一样，我改变了一些东西，但它会做你想要的。我不得不猜测 nodetype 的结构是什么，为了方便我添加了一个构造函数。我添加了一些评论，指出我的风格的各个方面。
请注意，它比您最初提供的代码更容易阅读。风格很重要。人们会告诉你必须使用 X 或 Y 风格，但真正重要的是你选择你喜欢的任何风格并始终如一地坚持下去；它将使您更容易快速阅读和理解自己的代码。
相信我，当您编写了大量代码时，您将无法一次记住所有代码，并且能够快速弄清楚您在做什么是必不可少的。
于 2013-03-24T20:18:22.410 回答
0
考虑下面给出的结构，
struct info
{
int data;
struct info *next;
};
如果您使用上述结构将记录存储在链表中，则可以使用以下代码从链表中删除元素，
void delitem()
{
info *curr,*prev;
int tdata;
if(head==NULL)
{
cout<<"\nNo Records to Delete!!!";
}
cout<<"\nEnter the Data to be deleted: ";
cin>>tdata;
prev=curr=head;
while((curr!=NULL)&&(curr->data!=tdata))
{
prev=curr;
curr=curr->next;
}
if(curr==NULL)
{
cout<<"\nRecord not Found!!!";
return;
}
if(curr==head)
{
head=head->next;
cout<<"\nData deleted: "<<tdata;
}
else
{
prev->next=curr->next;
if(curr->next==NULL)
{
temp=prev;
}
cout<<"\nData deleted: "<<tdata;
}
delete(curr);
}
于 2013-03-24T19:48:46.113 回答
0
我认为删除一个节点或在链表中插入 ine 过于简单易行，但需要准确了解其机制。这个例子展示了如何添加和删除节点，但它不是一个完整的程序，但它揭示了添加和删除以及移动链表的机制：
#include <iostream>
using namespace std;
//class Data to store ages. in a real program this class can be any other
//class for example a student class or customer...
class Data
{
public:
Data(int age):itsAge(age){}
~Data(){}
void SetAge(int age){itsAge=age;}
int getAge()const{return itsAge;}
private:
int itsAge;
};
//the most important part of the program is the linked0list
class Node
{
public:
//we just make itsPtrHead when created points to Null even if we pass a pointer to Data that is not NULL
Node(Data* pData): itsPtrData(pData),itsPtrHead(NULL),itsCount(0){}
Data* getPdata()const;
Node* getPnext()const;
int getCount()const{return itsCount;}
void insertNode(Data*);//import bcause it shoes the mechanism of linked-list
void deleteNode(int);//most significant in this program
Data* findData(int&,int);
void print()const;
private:
Data* itsPtrData;
Node* itsPtrHead;
int itsCount;
};
Data* Node::getPdata()const
{
if(itsPtrData)
return itsPtrData;
else
return NULL;
}
Node* Node::getPnext()const
{
return itsPtrHead;
}
void Node::insertNode(Data* pData)
{
Node* pNode=new Node(pData);//create a node
Node* pCurrent=itsPtrHead;//current node which points first to the first node that is the "head bode"
Node* pNext=NULL;//the next node
int NewAge=pData->getAge();//the new age that is past to insertNode function
int NextAge=0;//next age
itsCount++;//incrementing the number of nodes
//first we check wether the head node "itsPtrHead" points NULL or not
//so if it is null then we assign it the new node "pNode" and return from insert function
if(!itsPtrHead)
{
itsPtrHead=pNode;
return;
}
//if the condition above fails (head is not null) then check its value and
//compare it with new age and if the new one is smaller than the head
//make this new one the head and then the original node that head points to it make it its next node to the head
if(itsPtrHead->getPdata()->getAge() > NewAge)
{
pNode->itsPtrHead=itsPtrHead;
itsPtrHead=pNode;
//exit the function
return;
}
//if the condition above fails than we move to the next node and so on
for(;;)
{
//if the next node to the current node is null the we set it with this new node(pNode) and exit
if(!pCurrent->itsPtrHead)
{
pCurrent->itsPtrHead=pNode;
return;
}
//else if it not null(next node to current node)
//then we compare the next node and new node
pNext=pCurrent->itsPtrHead;
NextAge=pNext->getPdata()->getAge();
//if next node's age is greater than new then we want new node
//to be the next node to current node then make the original next to current to be the next to its next
if(NextAge > NewAge)
{
pCurrent->itsPtrHead=pNode;
pNode->itsPtrHead=pNext;
//exitting
return;
}
//if no condition succeeds above then move to next node and continue until last node
pCurrent=pNext;
}
}
// delete a node is a bit different from inserting a node
void Node::deleteNode(int age)
{
//deleting a node is much like adding one the differecne is a bit trickier
Node* pTmp=itsPtrHead;
Node* pCurrent=itsPtrHead;
Node* pNext=NULL;
//1 checking for wether age (node contains age) to be deleted does exist
for(;pTmp;pTmp=pTmp->itsPtrHead)
{
if(pTmp->getPdata()->getAge() == age)
break;
}
//if age to be deleted doesn't exist pop up a message and return
if(!pTmp)
{
cout<<age<<": Can't be found!\n";
return;
}
int NextAge=0;
for(;;)
{
//if age to be deleted is on the head node
if(itsPtrHead->getPdata()->getAge() == age)
{
//store the next to head node
pTmp=itsPtrHead->itsPtrHead;
//delete head node
delete itsPtrHead;
//assign the head new node (node after the original head)
itsPtrHead=pTmp;
//decrement the count of nodes
itsCount--;
//exiting gracefully
return;
}
//moving to next node
pNext=pCurrent->itsPtrHead;
NextAge=pNext->getPdata()->getAge();
//checking next node age with age to be deleted. if they
//match delete the next node
if(NextAge == age)
{
//next node holds the target age so we want its NEXT node
//and store it in pTmp;
pTmp=pNext->itsPtrHead;//Next node of the target node
//pCurrent doesn't yet hold the target age but it is the
//previous node to target node
//change the next node of pCurrent so that it doesn't
//point to the target node but instead to the node right
//after it
pCurrent->itsPtrHead=pTmp;
//delete the target node (holds the target age)
delete pNext;
//decrement number of nodes
itsCount--;
//exit
return;
}
//if pNext doesn't point to target node move to the next node
//by making pCurrent points to the next node in the list
pCurrent=pNext;
}
}
void Node::print()const
{
Node* pTmp=itsPtrHead;
while(pTmp)
{
cout<<"age: "<<pTmp->getPdata()->getAge()<<endl;
pTmp=pTmp->itsPtrHead;
}
}
int main()
{
//note this is not a real proram just we show how things works
Data* pData=new Data(6);
Node theNode(pData);
theNode.print();
pData=new Data(19);
theNode.insertNode(pData);
pData=new Data(20);
theNode.insertNode(pData);
pData=new Data(23);
theNode.insertNode(pData);
pData=new Data(25);
theNode.insertNode(pData);
pData=new Data(30);
theNode.insertNode(pData);
pData=new Data(27);
theNode.insertNode(pData);
pData=new Data(33);
theNode.insertNode(pData);
pData=new Data(18);
theNode.insertNode(pData);
theNode.print();
cout<<endl<<endl;
//int age;
//int index;
//cout<<"Age to finde: ";
//cin>>age;
//cout<<endl;
//theNode.Find(index,age);
//cout<<age<<" : Found on index: "<<index<<endl;
//theNode.modify(age);
//theNode.print();
int age;
cout<<"age to delete: ";
cin>>age;
cout<<endl;
theNode.deleteNode(age);
theNode.print();
cout<<endl<<endl<<endl;
return 0;
}
//modify and other member functions are not the purpose of this program
于 2015-01-03T21:26:02.960 回答
0
void Delete()
{
int num;
cout<<"enter node to delete"<<endl;
cin>>num;
node *nodeptr=head;
node *prev;
if(head==0)
{
cout<<"list is empty"<<endl;
}
else if(head->data==num)
{
node *t=head;
head=head->next;
delete t;
}
else
{
nodeptr=head;
prev=head;
while(nodeptr!=NULL)
{
if(nodeptr->data==num)
{
prev->next=nodeptr->next;
node *tem=nodeptr->next;
delete tem;
}
prev=nodeptr;
nodeptr=nodeptr->next;
}
}
}
于 2020-11-09T12:51:48.210 回答