C++教程:链表节点的插入和删除

2020-05-23 14:26:47

字体：大中小

来源：转载

供稿：网友

插入结点

数组在内存中是顺序存储的，要在数组中插入一个数据就变得颇为麻烦。这就像是在一排麻将中插入一个牌，必须把后面的牌全部依次顺移。然而，链表中各结点的关系是由指针决定的，所以在链表中插入结点要显得方便一些。这就像是把一条链子先一分为二，然后用一个环节再把它们连接起来。如下图9.6.2所示。

下面我们先对插入结点这个功能具体分析一下：

我们必须知道对哪个链表进行操作，所以表头指针head是必须知道的。
为了确定插入位置，插入位置前的结点指针pGuard是必须是知道的。
用一个newnode指针来接受新建的结点。
如果要插入的位置是表头，由于操作的是表头指针而不是一个结点，所以要特殊处理。
在插入结点的过程中，始终要保持所有的结点都在我们的控制范围内，保证链表的完整性。为了达到这一点，我们采用先连后断的方式：先把新结点和它的后继结点连接，再把插入位置之前的结点与后继结点断开，并与新结点连接。如下图9.6.3所示。

做完了分析，我们可以开始编写插入函数了。为了简单起见，我们规定新结点插入位置为数据是关键字的结点之后，这样就可以使用刚才编写好的search函数了。如果该结点不存在，则插入在表头。则插入函数如下：（程序9.6.3）
void insert(node * &head,char keyWord,char newdata)//keyWord是查找关键字符
{
node *newnode=new node;//新建结点
newnode->data=newdata;//newdata是新结点的数据
node *pGuard=search(head,keyWord);//pGuard是插入位置前的结点指针
if (head==NULL || pGuard==NULL)//如果链表没有结点或找不到关键字结点
{//则插入表头位置
newnode->next=head;//先连
head=newnode;//后断
}
else//否则
{//插入在pGuard之后
newnode->next=pGuard->next;//先连
pGuard->next=newnode;//后断
}
}

删除结点

与插入数据类似，数组为了保持其顺序存储的特性，在删除某个数据时，其后的数据都要依次前移。而链表中结点的删除仍然只要对结点周围小范围的操作就可以了，不必去修改其他的结点。
仍然我们先要来具体分析删除结点这个功能：

我们必须知道对哪个链表进行操作，所以表头指针head是必须知道的。
一般来说，待删除的结点是由结点的数据确定的。然而我们还要操作待删除结点之前的结点（或指针），以连接前后两段链表。之前所写的search函数只能找到待删除的结点，却无法找到这个结点的前趋结点。所以，我们只好放弃search函数，另起炉灶。
令pGuard指针为待删除结点的前趋结点指针。
由于要对待删除结点作内存释放，需要有一个指针p指向待删除结点。
如果待删除结点为头结点，则我们要操作表头head，作为特殊情况处理。
在删除结点的过程中，仍然要始终保持所有的结点都在我们的控制范围内，保证链表的完整性。为了达到这一点，我们还是采用先连后断的方式：先把待删除结点的前趋结点和它的后继结点连接，再把待删除结点与它的后继结点断开，并释放其空间。如下图9.6.4所示。
如果链表没有结点或找不到待删除结点，则给出提示信息。

由于delete是C++中的保留字，我们无法用它作为函数名，所以只好用Delete代替（C++是大小写敏感的，Delete和delete是不同的）。都准备好了，我们就可以开始写函数了：（程序9.6.4）
void Delete(node * &head,char keyWord)//可能要操作表头指针，所以head是引用
{
if (head!=NULL)//如果链表没有结点，就直接输出提示
{
node *p;
node *pGuard=head;//初始化pGuard指针
if (head->data==keyWord)//如果头结点数据符合关键字
{
p=head;//头结点是待删除结点
head=head->next;//先连
delete p;//后断
cout <<"The deleted node is " <<keyWord <<endl;
return;//结束函数运行
}
else//否则
{
while (pGuard->next!=NULL)//当pGuard没有达到表尾
{
if (pGuard->next->data==keyWord)//如果pGuard后继结点数据符合关键字
{
p=pGuard->next;//pGuard后继结点是待删除结点
pGuard->next=p->next;//先连
delete p;//后断
cout <<"The deleted node is " <<keyWord <<endl;
return;//结束函数运行
}
pGuard=pGuard->next;//pGuard指针向后移动
}
}
}
cout <<"The keyword node is not found or the link list is empty!" <<endl;//输出提示信息
}

上一篇：C++教程:清除链表

下一篇：C++教程:链表的查询