前兩個成員項組成數據域，后一個成員項next構成指針域，它是一個指向stu類型結構的指針變量。鏈表的基本操作對鏈表的主要操作有以下幾種：

　　1.建立鏈表;

　　2.結構的查找與輸出;

　　3.插入一個結點;

　　4.刪除一個結點;

　　下面通過例題來說明這些操作。

　　[例7.10]建立一個三個結點的鏈表，存放學生數據。為簡單起見，我們假定學生數據結構中只有學號和年齡兩項。

　　可編寫一個建立鏈表的函數creat。程序如下：

　　#define NULL 0

　　#define TYPE struct stu

　　#define LEN sizeof (struct stu)

　　struct stu

　　{

　　int num;

　　int age;

　　struct stu *next;

　　};

　　TYPE *creat(int n)

　　{

　　struct stu *head,*pf,*pb;

　　int i;

　　for(i=0;i

　　{

　　pb=(TYPE*) malloc(LEN);

　　printf("input Number and Age\n");

　　scanf("%d%d",&pb->num,&pb->age);

　　if(i==0)

　　pf=head=pb;

　　else pf->next=pb;

　　pb->next=NULL;

　　pf=pb;

　　}

　　return(head);

　　}

　　在函數外首先用宏定義對三個符號常量作了定義。這里用TYPE表示struct stu，用LEN表示sizeof(struct stu)主要的目的是為了在以下程序內減少書寫并使閱讀更加方便。結構stu定義為外部類型，程序中的各個函數均可使用該定義。

　　creat函數用于建立一個有n個結點的鏈表，它是一個指針函數，它返回的指針指向stu結構。在creat函數內定義了三個stu結構的指針變量。head為頭指針，pf 為指向兩相鄰結點的前一結點的指針變量。pb為后一結點的指針變量。在for語句內，用malloc函數建立長度與stu長度相等的空間作為一結點，首地址賦予pb.然后輸入結點數據。如果當前結點為第一結點(i==0)，則把pb值 (該結點指針)賦予head和pf。如非第一結點，則把pb值賦予pf 所指結點的指針域成員next.而pb所指結點為當前的最后結點，其指針域賦NULL。再把pb值賦予pf以作下一次循環準備。

　　creat函數的形參n，表示所建鏈表的結點數，作為for語句的循環次數。圖7.4表示了creat函數的執行過程。

　　[例7.11]寫一個函數，在鏈表中按學號查找該結點。

　　TYPE * search (TYPE *head,int n)

　　{

　　TYPE *p;

　　int i;

　　p=head;

　　while (p->num!=n && p->next!=NULL)

　　p=p->next; /* 不是要找的結點后移一步*/

　　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.函數有兩個形參，head是指向鏈表的指針變量，n為要查找的學號。進入while語句，逐個檢查結點的num成員是否等于n,如果不等于n且指針域不等于NULL(不是最后結點)則后移一個結點，繼續循環。如找到該結點則返回結點指針。如循環結束仍未找到該結點則輸出“未找到”的提示信息。

　　[例7.12]寫一個函數，刪除鏈表中的指定結點。刪除一個結點有兩種情況：

　　1. 被刪除結點是第一個結點。這種情況只需使head指向第二個結點即可。即head=pb->next。其過程如圖7.5所示。

　　2. 被刪結點不是第一個結點，這種情況使被刪結點的前一結點指向被刪結點的后一結點即可。即pf->next=pb->next.

　　函數編程如下：

　　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)

　　/*當不是要刪除的結點，而且也不是最后一個結點時，繼續循環*/

　　{

　　pf=pb;pb=pb->next;}/*pf指向當前結點，pb指向下一結點*/

　　if(pb->num==num)

　　{

　　if(pb==head) head=pb->next;

　　/*如找到被刪結點，且為第一結點，則使head指向第二個結點，

　　否則使pf所指結點的指針指向下一結點*/

　　else pf->next=pb->next;

　　free(pb);

　　printf("The node is deleted\n");}

　　else

　　printf("The node not been foud!\n");

　　end:

　　return head;

　　}

　　函數有兩個形參，head為指向鏈表第一結點的指針變量，num刪結點的學號。 首先判斷鏈表是否為空，為空則不可能有被刪結點。若不為空，則使pb指針指向鏈表的第一個結點。進入while語句后逐個查找被刪結點。找到被刪結點之后再看是否為第一結點，若是則使head指向第二結點(即把第一結點從鏈中刪去)，否則使被刪結點的前一結點(pf所指)指向被刪結點的后一結點(被刪結點的指針域所指)。如若循環結束未找到要刪的結點， 則輸出"末找到"的提示信息。最后返回head值。

　　[例7.13]寫一個函數，在鏈表中指定位置插入一個結點。在一個鏈表的指定位置插入結點， 要求鏈表本身必須是已按某種規律排好序的。例如，在學生數據鏈表中， 要求學號順序插入一個結點。設被插結點的指針為pi. 可在三種不同情況下插入。

　　相關推薦：

　　2012年軟考系統分析師考試60天完美復習計劃

　　2012年軟件水平考試網絡工程師章節筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總