C語(yǔ)言初學(xué)者入門知識(shí)之結(jié)構(gòu)體3

　　前兩個(gè)成員項(xiàng)組成數(shù)據(jù)域，后一個(gè)成員項(xiàng)next構(gòu)成指針域，它是一個(gè)指向stu類型結(jié)構(gòu)的指針變量。鏈表的基本操作對(duì)鏈表的主要操作有以下幾種：

　　1.建立鏈表;

　　2.結(jié)構(gòu)的查找與輸出;

　　3.插入一個(gè)結(jié)點(diǎn);

　　4.刪除一個(gè)結(jié)點(diǎn);

　　下面通過(guò)例題來(lái)說(shuō)明這些操作。

　　[例7.10]建立一個(gè)三個(gè)結(jié)點(diǎn)的鏈表，存放學(xué)生數(shù)據(jù)。為簡(jiǎn)單起見(jiàn)，我們假定學(xué)生數(shù)據(jù)結(jié)構(gòu)中只有學(xué)號(hào)和年齡兩項(xiàng)。

　　可編寫一個(gè)建立鏈表的函數(shù)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);

　　}

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

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

　　creat函數(shù)的形參n，表示所建鏈表的結(jié)點(diǎn)數(shù)，作為for語(yǔ)句的循環(huán)次數(shù)。圖7.4表示了creat函數(shù)的執(zhí)行過(guò)程。

　　[例7.11]寫一個(gè)函數(shù)，在鏈表中按學(xué)號(hào)查找該結(jié)點(diǎn)。

　　TYPE * search (TYPE *head,int n)

　　{

　　TYPE *p;

　　int i;

　　p=head;

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

　　p=p->next; /* 不是要找的結(jié)點(diǎn)后移一步*/

　　if (p->num==n) return (p);

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

　　printf ("Node %d has not been found!\n",n

　　}

　　本函數(shù)中使用的符號(hào)常量TYPE與例7.10的宏定義相同，等于struct stu.函數(shù)有兩個(gè)形參，head是指向鏈表的指針變量，n為要查找的學(xué)號(hào)。進(jìn)入while語(yǔ)句，逐個(gè)檢查結(jié)點(diǎn)的num成員是否等于n,如果不等于n且指針域不等于NULL(不是最后結(jié)點(diǎn))則后移一個(gè)結(jié)點(diǎn)，繼續(xù)循環(huán)。如找到該結(jié)點(diǎn)則返回結(jié)點(diǎn)指針。如循環(huán)結(jié)束仍未找到該結(jié)點(diǎn)則輸出“未找到”的提示信息。

　　[例7.12]寫一個(gè)函數(shù)，刪除鏈表中的指定結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)有兩種情況：

　　1. 被刪除結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)。這種情況只需使head指向第二個(gè)結(jié)點(diǎn)即可。即head=pb->next。其過(guò)程如圖7.5所示。

　　2. 被刪結(jié)點(diǎn)不是第一個(gè)結(jié)點(diǎn)，這種情況使被刪結(jié)點(diǎn)的前一結(jié)點(diǎn)指向被刪結(jié)點(diǎn)的后一結(jié)點(diǎn)即可。即pf->next=pb->next.

　　函數(shù)編程如下：

　　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)

　　/*當(dāng)不是要?jiǎng)h除的結(jié)點(diǎn)，而且也不是最后一個(gè)結(jié)點(diǎn)時(shí)，繼續(xù)循環(huán)*/

　　{

　　pf=pb;pb=pb->next;}/*pf指向當(dāng)前結(jié)點(diǎn)，pb指向下一結(jié)點(diǎn)*/

　　if(pb->num==num)

　　{

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

　　/*如找到被刪結(jié)點(diǎn)，且為第一結(jié)點(diǎn)，則使head指向第二個(gè)結(jié)點(diǎn)，

　　否則使pf所指結(jié)點(diǎn)的指針指向下一結(jié)點(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;

　　}

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

　　[例7.13]寫一個(gè)函數(shù)，在鏈表中指定位置插入一個(gè)結(jié)點(diǎn)。在一個(gè)鏈表的指定位置插入結(jié)點(diǎn)， 要求鏈表本身必須是已按某種規(guī)律排好序的。例如，在學(xué)生數(shù)據(jù)鏈表中， 要求學(xué)號(hào)順序插入一個(gè)結(jié)點(diǎn)。設(shè)被插結(jié)點(diǎn)的指針為pi. 可在三種不同情況下插入。

　　相關(guān)推薦：

　　2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計(jì)劃

　　2012年軟件水平考試網(wǎng)絡(luò)工程師章節(jié)筆記講義匯總

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