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++教程:鏈表的查詢