creat函數用于建立一個(gè)有n個(gè)結點(diǎn)的鏈表，它是一個(gè)指針函數，它返回的指針指向stu結構。在creat函數內定義了三個(gè)stu結構的指針變量。head為頭指針，pf 為指向兩相鄰結點(diǎn)的前一結點(diǎn)的指針變量。pb為后一結點(diǎn)的指針變量。在for語(yǔ)句內，用malloc函數建立長(cháng)度與stu長(cháng)度相等的空間作為一結點(diǎn)，首地址賦予pb。然后輸入結點(diǎn)數據。如果當前結點(diǎn)為第一結點(diǎn)(i==0)，則把pb值 (該結點(diǎn)指針)賦予head和pf。如非第一結點(diǎn)，則把pb值賦予pf 所指結點(diǎn)的指針域成員next。而pb所指結點(diǎn)為當前的最后結點(diǎn)，其指針域賦NULL。 再把pb值賦予pf以作下一次循環(huán)準備。
creat函數的形參n，表示所建鏈表的結點(diǎn)數，作為for語(yǔ)句的循環(huán)次數。圖7.4表示了creat函數的執行過(guò)程。
[例7.11]寫(xiě)一個(gè)函數，在鏈表中按學(xué)號查找該結點(diǎn)。
TYPE * search (TYPE *head,int n)
{
TYPE *p;
int i;
p=head;
while (p->num!=n && p->next!=NULL)
p=p->next; /* 不是要找的結點(diǎn)后移一步*/
if (p->num==n) return (p);
if (p->num!=n&& p->next==NULL)
printf ("Node %d has not been found!\n",n
}
本函數中使用的符號常量TYPE與例7.10的宏定義相同，等于struct stu。函數有兩個(gè)形參，head是指向鏈表的指針變量，n為要查找的學(xué)號。進(jìn)入while語(yǔ)句，逐個(gè)檢查結點(diǎn)的num成員是否等于n，如果不等于n且指針域不等于NULL(不是最后結點(diǎn))則后移一個(gè)結點(diǎn)，繼續循環(huán)。如找到該結點(diǎn)則返回結點(diǎn)指針。 如循環(huán)結束仍未找到該結點(diǎn)則輸出“未找到”的提示信息。
[例7.12]寫(xiě)一個(gè)函數，刪除鏈表中的指定結點(diǎn)。刪除一個(gè)結點(diǎn)有兩種情況：
1. 被刪除結點(diǎn)是第一個(gè)結點(diǎn)。這種情況只需使head指向第二個(gè)結點(diǎn)即可。即head=pb->next。其過(guò)程如圖7.5所示。
2. 被刪結點(diǎn)不是第一個(gè)結點(diǎn)，這種情況使被刪結點(diǎn)的前一結點(diǎn)指向被刪結點(diǎn)的后一結點(diǎn)即可。即pf->next=pb->next。其過(guò)程如圖7.6所示。
函數編程如下：
TYPE * delete(TYPE * head,int num)
{
TYPE *pf,*pb;
if(head==NULL) /*如為空表， 輸出提示信息*/
{ printf("\nempty list!\n");
goto end;}
pb=head;
while (pb->num!=num && pb->next!=NULL)
/*當不是要刪除的結點(diǎn)，而且也不是最后一個(gè)結點(diǎn)時(shí)，繼續循環(huán)*/
{pf=pb;pb=pb->next;}/*pf指向當前結點(diǎn)，pb指向下一結點(diǎn)*/
if(pb->num==num)
{if(pb==head) head=pb->next;
/*如找到被刪結點(diǎn)，且為第一結點(diǎn)，則使head指向第二個(gè)結點(diǎn)，
否則使pf所指結點(diǎn)的指針指向下一結點(diǎn)*/
else pf->next=pb->next;
free(pb);
printf("The node is deleted\n");}
else
printf("The node not been foud!\n");
end:
return head;
}
函數有兩個(gè)形參，head為指向鏈表第一結點(diǎn)的指針變量，num刪結點(diǎn)的學(xué)號。 首先判斷鏈表是否為空，為空則不可能有被刪結點(diǎn)。若不為空，則使pb指針指向鏈表的第一個(gè)結點(diǎn)。進(jìn)入while語(yǔ)句后逐個(gè)查找被刪結點(diǎn)。找到被刪結點(diǎn)之后再看是否為第一結點(diǎn)，若是則使head指向第二結點(diǎn)(即把第一結點(diǎn)從鏈中刪去)，否則使被刪結點(diǎn)的前一結點(diǎn)(pf所指)指向被刪結點(diǎn)的后一結點(diǎn)(被刪結點(diǎn)的指針域所指)。如若循環(huán)結束未找到要刪的結點(diǎn)， 則輸出“末找到”的提示信息。最后返回head值。
[例7.13]寫(xiě)一個(gè)函數，在鏈表中指定位置插入一個(gè)結點(diǎn)。在一個(gè)鏈表的指定位置插入結點(diǎn)， 要求鏈表本身必須是已按某種規律排好序的。例如，在學(xué)生數據鏈表中， 要求學(xué)號順序插入一個(gè)結點(diǎn)。設被插結點(diǎn)的指針為pi。 可在三種不同情況下插入。
1. 原表是空表，只需使head指向被插結點(diǎn)即可。見(jiàn)圖7.7(a)
2. 被插結點(diǎn)值最小，應插入第一結點(diǎn)之前。這種情況下使head指向被插結點(diǎn)，被插結點(diǎn)的指針域指向原來(lái)的第一結點(diǎn)則可。即：pi->next=pb;
head=pi; 見(jiàn)圖7.7(b)
3. 在其它位置插入，見(jiàn)圖7.7(c)。這種情況下，使插入位置的前一結點(diǎn)的指針域指向被插結點(diǎn)，使被插結點(diǎn)的指針域指向插入位置的后一結點(diǎn)。即為：pi->next=pb;pf->next=pi；
4. 在表末插入，見(jiàn)圖7.7(d)。這種情況下使原表末結點(diǎn)指針域指向被插結點(diǎn)，被插結點(diǎn)指針域置為NULL。即：
pb->next=pi;
pi->next=NULL； TYPE * insert(TYPE * head,TYPE *pi)
{
TYPE *pf,*pb;
pb=head;
if(head==NULL) /*空表插入*/
(head=pi;
pi->next=NULL;}
else
{
while((pi->num>pb->num)&&(pb->next!=NULL))
{pf=pb;
pb=pb->next; }/*找插入位置*/
if(pi->num<=pb->num)
{if(head==pb)head=pi;/*在第一結點(diǎn)之前插入*/
else pf->next=pi;/*在其它位置插入*/
pi->next=pb; }
else
{pb->next=pi;
pi->next=NULL;} /*在表末插入*/
}
return head;}
本函數有兩個(gè)形參均為指針變量，head指向鏈表，pi 指向被插結點(diǎn)。函數中首先判斷鏈表是否為空，為空則使head指向被插結點(diǎn)。表若不空，則用while語(yǔ)句循環(huán)查找插入位置。找到之后再判斷是否在第一結點(diǎn)之前插入，若是則使head 指向被插結點(diǎn)被插結點(diǎn)指針域指向原第一結點(diǎn)，否則在其它位置插入， 若插入的結點(diǎn)大于表中所有結點(diǎn)，則在表末插入。本函數返回一個(gè)指針， 是鏈表的頭指針。 當插入的位置在第一個(gè)結點(diǎn)之前時(shí)， 插入的新結點(diǎn)成為鏈表的第一個(gè)結點(diǎn)，因此head的值也有了改變， 故需要把這個(gè)指針?lè )祷刂髡{函數。
