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

2020-05-23 14:26:47

字體：大中小

供稿：網(wǎng)友

插入結(jié)點(diǎn)

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

下面我們先對(duì)插入結(jié)點(diǎn)這個(gè)功能具體分析一下：

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

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

刪除結(jié)點(diǎn)

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

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

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

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

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