鏈表的刪除操作是指在鏈表中根據要求刪除其中的某個結點。與插入操作類似,鏈表的刪除操作也分為四種情況來考慮:
(1)如果待刪除的鏈表是一張空表,則直接返回。
(2)如果非空表,但找不到要刪除的結點,則輸出未找到信息,並直接返回。
(3)如果待刪除的結點是第一個結點,則將頭指針的值改為:head=head->next;。
(4)如果待刪除的結點是鏈表中間或最後一個結點,假設待刪除的結點為p1,其前一個結點為p0,則使p0的指針域指向p1的下一個結點的地址,即p0->next=p1->next;。
下麵通過一個例子說明如何在鏈表中完成刪除操作。
[例119]編寫一個delist函數,完成在學生鏈表中將指定學號的結點刪除。
structstu*delist(structstu*head,intnum)
{
structstu*p0,*p1;
p1=head;
if(head==NULL)/*如為空表,則輸出提示信息*/
{
printf("\nemptylist!\n");
}
else
if(p1->num==num)
head=p1->next;
else
{
while(p1->num!=num&&p1->next!=NULL)
/*當p1所指的結點不是要刪除的結點,也不是最後一個結點時,繼續循環*/
{
p0=p1;
p1=p1->next;
}/*p0指向當前結點,p1指向下一結點*/
if(p1->num==num)
{
p0->next=p1->next;
/*如找到被刪結點,則使p0所指結點的指針域指向p1的下一結點*/
printf("Thenodeisdeleted\n");
}
else
printf("Thenodecannotbeenfoud!\n");
}
returnhead;
}
本函數有兩個形參,head為指向鏈表第一個結點的指針變量,num為待刪除結點的學號。首先判斷鏈表是否為空,為空則不可能有被刪結點。若不為空,則使p1指針指向鏈表的第一個結點,判斷被刪結點是否為第一結點,若是則使head指向第二結點,否則進入while語句逐個查找被刪結點,如找出則使被刪結點的前一結點指向被刪結點的後一結點。如果循環結束後未找到要刪的結點,則輸出未找到的提示信息,最後返回head值。