C++教程:鏈表節(jié)點的插入和刪除

2020-05-23 14:26:47

字體：大中小

供稿：網(wǎng)友

插入結(jié)點

數(shù)組在內(nèi)存中是順序存儲的，要在數(shù)組中插入一個數(shù)據(jù)就變得頗為麻煩。這就像是在一排麻將中插入一個牌，必須把后面的牌全部依次順移。然而，鏈表中各結(jié)點的關(guān)系是由指針決定的，所以在鏈表中插入結(jié)點要顯得方便一些。這就像是把一條鏈子先一分為二，然后用一個環(huán)節(jié)再把它們連接起來。如下圖9.6.2所示。

下面我們先對插入結(jié)點這個功能具體分析一下：

我們必須知道對哪個鏈表進行操作，所以表頭指針head是必須知道的。
為了確定插入位置，插入位置前的結(jié)點指針pGuard是必須是知道的。
用一個newnode指針來接受新建的結(jié)點。
如果要插入的位置是表頭，由于操作的是表頭指針而不是一個結(jié)點，所以要特殊處理。
在插入結(jié)點的過程中，始終要保持所有的結(jié)點都在我們的控制范圍內(nèi)，保證鏈表的完整性。為了達到這一點，我們采用先連后斷的方式：先把新結(jié)點和它的后繼結(jié)點連接，再把插入位置之前的結(jié)點與后繼結(jié)點斷開，并與新結(jié)點連接。如下圖9.6.3所示。

做完了分析，我們可以開始編寫插入函數(shù)了。為了簡單起見，我們規(guī)定新結(jié)點插入位置為數(shù)據(jù)是關(guān)鍵字的結(jié)點之后，這樣就可以使用剛才編寫好的search函數(shù)了。如果該結(jié)點不存在，則插入在表頭。則插入函數(shù)如下：（程序9.6.3）
void insert(node * &head,char keyWord,char newdata)//keyWord是查找關(guān)鍵字符
{
node *newnode=new node;//新建結(jié)點
newnode->data=newdata;//newdata是新結(jié)點的數(shù)據(jù)
node *pGuard=search(head,keyWord);//pGuard是插入位置前的結(jié)點指針
if (head==NULL || pGuard==NULL)//如果鏈表沒有結(jié)點或找不到關(guān)鍵字結(jié)點
{//則插入表頭位置
newnode->next=head;//先連
head=newnode;//后斷
}
else//否則
{//插入在pGuard之后
newnode->next=pGuard->next;//先連
pGuard->next=newnode;//后斷
}
}

刪除結(jié)點

與插入數(shù)據(jù)類似，數(shù)組為了保持其順序存儲的特性，在刪除某個數(shù)據(jù)時，其后的數(shù)據(jù)都要依次前移。而鏈表中結(jié)點的刪除仍然只要對結(jié)點周圍小范圍的操作就可以了，不必去修改其他的結(jié)點。
仍然我們先要來具體分析刪除結(jié)點這個功能：

我們必須知道對哪個鏈表進行操作，所以表頭指針head是必須知道的。
一般來說，待刪除的結(jié)點是由結(jié)點的數(shù)據(jù)確定的。然而我們還要操作待刪除結(jié)點之前的結(jié)點（或指針），以連接前后兩段鏈表。之前所寫的search函數(shù)只能找到待刪除的結(jié)點，卻無法找到這個結(jié)點的前趨結(jié)點。所以，我們只好放棄search函數(shù)，另起爐灶。
令pGuard指針為待刪除結(jié)點的前趨結(jié)點指針。
由于要對待刪除結(jié)點作內(nèi)存釋放，需要有一個指針p指向待刪除結(jié)點。
如果待刪除結(jié)點為頭結(jié)點，則我們要操作表頭head，作為特殊情況處理。
在刪除結(jié)點的過程中，仍然要始終保持所有的結(jié)點都在我們的控制范圍內(nèi)，保證鏈表的完整性。為了達到這一點，我們還是采用先連后斷的方式：先把待刪除結(jié)點的前趨結(jié)點和它的后繼結(jié)點連接，再把待刪除結(jié)點與它的后繼結(jié)點斷開，并釋放其空間。如下圖9.6.4所示。
如果鏈表沒有結(jié)點或找不到待刪除結(jié)點，則給出提示信息。

由于delete是C++中的保留字，我們無法用它作為函數(shù)名，所以只好用Delete代替（C++是大小寫敏感的，Delete和delete是不同的）。都準備好了，我們就可以開始寫函數(shù)了：（程序9.6.4）
void Delete(node * &head,char keyWord)//可能要操作表頭指針，所以head是引用
{
if (head!=NULL)//如果鏈表沒有結(jié)點，就直接輸出提示
{
node *p;
node *pGuard=head;//初始化pGuard指針
if (head->data==keyWord)//如果頭結(jié)點數(shù)據(jù)符合關(guān)鍵字
{
p=head;//頭結(jié)點是待刪除結(jié)點
head=head->next;//先連
delete p;//后斷
cout <<"The deleted node is " <<keyWord <<endl;
return;//結(jié)束函數(shù)運行
}
else//否則
{
while (pGuard->next!=NULL)//當pGuard沒有達到表尾
{
if (pGuard->next->data==keyWord)//如果pGuard后繼結(jié)點數(shù)據(jù)符合關(guān)鍵字
{
p=pGuard->next;//pGuard后繼結(jié)點是待刪除結(jié)點
pGuard->next=p->next;//先連
delete p;//后斷
cout <<"The deleted node is " <<keyWord <<endl;
return;//結(jié)束函數(shù)運行
}
pGuard=pGuard->next;//pGuard指針向后移動
}
}
}
cout <<"The keyword node is not found or the link list is empty!" <<endl;//輸出提示信息
}

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

下一篇：C++教程:鏈表的查詢