【文章內容簡介】 t student)； struct student stu； stu． num=12345； strcpy(stu． name， Li Li)； stu． score[0]=67． 5； stu． score[1]=89； stu． score[2]=78． 6； print(stu)； } void print(struct student stu) {printf(FORMAT， ， ， [0]， [1]， [2])； printf(\n)； } 運行結果為： 12345 Li Li 67． 500000 89． 000000 78． 599998 struct student被定義為外部類型，這樣，同一源文件中的各個函數都可以用它來定義變量的類型。main函數中的 stu定義為 struct student類型變量，print函數中的形參 stu也定義為 struct student類型變量。在 main函數中對 stu的各成員賦值。在調用print函數時以 stu為實參向形參 stu實行“值傳遞”。 在 print函數中輸出結構體變量 stu各成員的值。 例 。 可以在上面程序的基礎上作少量修改即可。請注意程序注釋。 define FORMAT %d\n%s\n%f\n%f\n%f\n struct student {int num； char name[20]； float score[3]； } stu={12345， Li Li， ， 89， }； main() { void print(struct student *)。 /*形參類型修改成指向結構體的指針變量 */ print(amp。stu)； /*實參改為 stu的起始地址 */ } void print(struct student *p) /*形參類型修改了 */ {printf(FORMAT， pnum， pname， pscore[0]， pscore[1]， pscore[2])； /*用指針變量調用各成員之值 */ printf(\n)； } 此程序改用在定義結構體變量 stu時賦初值，這樣程序可簡化些。print函數中的形圖 p被定義為指向 struct student類型數據的指針變量。注意在調用 print函數時，用結構體變量 stu的起始地址 amp。stu作實參。在調用函數時將該地址傳送給形參 p(p是指針變量 )。這樣 p就指向 stu，見圖 。在 print函數中輸出 p所指向的結構體變量的各個成員值，它們也就是 stu的成員值。 圖 main函數中的對各成員賦值也可以改用 scanf函數輸入。即用 scanf(%d%s%f%f%f， amp。stu． num，stu． name， amp。stu． score[0]， amp。stu． score[1]，amp。stu． score[2])； 輸入時用下面形式輸入： 12345LiLi67． 58978． 6 注意：輸入項表列中 stu． name前沒有“ amp。”符號，因為 stu． name是字符數組名，本身代表地址，不應寫成 amp。stu． name。 用指針作函數參數比較好，能提高運行效率。 用指針處理鏈表 鏈表概述 ? 鏈表是一種常見的重要的數據結構。它是動態(tài)地進行存儲分配的一種結構。我們知道，用數組存放數據時，必須事先定義固定的長度 (即元素個數 )。比如，有的班級有 100人，而有的班只有 30人，如果要用同一個數組先后存放不同班級的學生數據，則必須定義長度為 100的數組。如果事先難以確定一個班的最多人數，則必須把數組定得足夠大，以能存放任何班級的學生數據。顯然這將會浪費內存。鏈表則沒有這種缺點，它根據需要開辟內存單元。圖 (單向鏈表 )的結構。 圖 鏈表有一個“頭指針”變量，圖中以 head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數據，二為下一個結點的地址。可以看出， head指向第一個元素；第一個元素又指向第二個元素 …… 直到最后一個元素，該元素不再指向其他元素，它稱為“表尾”，它的地址部分放一個“ NULL”(表示“空地址” )，鏈表到此結束。 可以看到鏈表中各元素在內存中可以不是連續(xù)存放的。要找某一元素，必須先找到上一個元素，根據它提供的下一元素地址才能找到下一個元素。如果不提供“頭指針” (head)，則整個鏈表都無法訪問。鏈表如同一條鐵鏈一樣，一環(huán)扣一環(huán)，中間是不能斷開的。打個通俗的比方：幼兒園的老師帶領孩子出來散步，老師牽著第一個小孩的手，第一個小孩的另一只手牽著第二個孩子 …… 這就是一個“鏈”，最后一個孩子有一只手空著，他是“鏈尾”。要找這個隊伍，必須先找到老師，然后順序找到每一個孩子。 可以看到，這種鏈表的數據結構，必須利用指針變量才能實現。即：一個結點中應包含一個指針變量，用它存放下一結點的地址。 前面介紹了結構體變量，用它作鏈表中的結點是最合適的。一個結構體變量包含若干成員，這些成員可以是數值類型、字符類型、數組類型，也可以是指針類型。我們用這個指針類型成員來存放下一個結點的地址。例如，可以設計這樣一個結構體類型： struct student {int num； float score； struct student next； }； 其中成員 num和 score用來存放結點中的有用數據 (用戶需要用到的數據 )，相當于圖 A，B， C， D。 next是指針類型的成員，它指向 struct student類型數據 (這就是 next所在的結構體類型 )。一個指針類型的成員既可以指向其他類型的結構體數據，也可以指向自己所在的結構體類型的數據?，F在， next是 struct student類型中的一個成員，它又指向 struct student類型的數據。用這種方法就可以建立鏈表。見圖 。 圖 圖中每一個結點都屬于 struct student類型，它的成員 next存放下一結點的地址，程序設計人員可以不必具體知道各結點的地址，只要保證將下一個結點的地址放到前一結點的成員 next中即可。請注意：上面只是定義了一個 struct student類型，并未實際分配存儲空間。只有定義了變量才分配內存單元。 簡單鏈表 下面通過一個例子來說明如何建立和輸出一個簡單鏈表。 例 建立一個如圖 ，它由 3個學生數據的結點組成。輸出各結點中的數據。 define NULL 0 struct student {long num。 float score。 struct student *next。 }。 main() { struct student a， b， c， *head， *p。 a. num=99101。 =。 b. num=99103。 =90。 c. num=99107。 =85。/*對結點的 num和 score成員賦值 */ head=amp。a。 /*將結點 a的起始地址賦給頭指針 head*/ =amp。b。 /*將結點 b的起始地址賦給 a結點的 next成員 */ =amp。c。 /*將結點 c的起始地址賦給 b結點的 next成員 */ =NULL。 /*c結點的 next成員不存放其他結點地址 */ p=head。 /*使 p指針指向 a結點 */ do {printf(%ld %\n， pnum， pscore)。/*輸出 p指向的結點的數據 */ p=pnext。 /*使 p指向下一結點 */ } while(p!=NULL)。 /*輸出完 c結點后 p的值為 NULL*/ } 請讀者仔細考慮：①各個結點是怎樣構成鏈表的。②沒有頭指針 head行不行？③ p起什么作用？沒有它行不行？開始時使 head指向 a結點， b結點， c結點，這就構成鏈表關系?！?=NULL” 的作用是使 用的存儲單元。在輸出鏈表時要借助 p，先使 p指向 a結點，然后輸出 a結點中的數據，“ p=pnext” 是為輸出下一個結點做準備。 pnext的值是 b結點的地址，因此執(zhí)行“ p=pnext”后 p就指向 b結點，所以在下一次循環(huán)時輸出的是 b結點中的數據。本例是比較簡單的，所有結點都是在程序中定義的，不是臨時開辟的，也不能用完后釋放，這種鏈表稱為“靜態(tài)鏈表”。 處理動態(tài)鏈表所需的函數 前面講過，鏈表結構是動態(tài)地分配存儲的，即在需要時才開辟一個結點的存儲單元。怎樣動態(tài)地開辟和釋放存儲單元呢？ C語言編譯系統(tǒng)的庫函數提供了以下有關函數。 1． malloc函數 其函數原型為 void *malloc(unsigned int size)。 其作用是在內存的動態(tài)存儲區(qū)中分配一個長度為 siｚ e的連續(xù)空間。此函數的值 (即“返回值” )是一個指向分配域起始地址的指針 (基類型為 void)。如果 此函數未能成功地執(zhí)行 (例如內存空間不足 )，則返回空指針 (NULL)。 2． calloc函數 其函數原型為 void *calloc(unsigned n， unsigned siｚ e)。 其作用是在內存的動態(tài)區(qū)存儲中分配 n個長度為 siｚe的連續(xù)空間。函數返回一個指向分配域起始地址的指針；如果分配不成功，返回 NULL。 用 calloc函數可以為一維數組開辟動態(tài)存儲空間， n為數組元素個數，每個元素長度為 size。 3． free函數 其函數原型為 void free(void *p)。 其作用是釋放由 p指向的內存區(qū)，使這部分內存區(qū)能被其他變量使用。 p是調用 calloc或 malloc函數時返回的值。 free函數無返回值。 請注意：以前的 C版本提供的 malloc和 calloc函數得到的是指向字符型數據的指針。 ANSI C提供的 malloc和calloc函數規(guī)定為 void 類型。 有了本節(jié)所介紹的初步知識，下面就可以對鏈表進行操作了 (包括建立鏈表、插入或刪除鏈表中一個結點等 )。有些概念需要在后面的應用中逐步建立和掌握。 建立動態(tài)鏈表 所謂建立動態(tài)鏈表是指在程序執(zhí)行過程中從無到有地建立起一個鏈表，即一個一個地開辟結點和輸入各結點數據，并建立起前后相鏈的關系。 例 有 3名學生數據的單向動態(tài)鏈表。 先考慮實現此要求的算法(見圖 )。 圖 設 3個指針變量： head、 p p2，它們都是用來指向struct student類型數據的。先用 malloc函數開辟第一個結點，并使 p p2指向它。然后從鍵盤讀入一個學生的數據給 p1所指的第一個結點。我們約定學號不會為零，如果輸入的學號為 0，則表示建立鏈表的過程完成，該結點不應連接到鏈碇小Ｏ仁筯ead的值為 NULL(即等于 0)，這是鏈表為“空”時的情況 (即 head不指向任何結點，鏈表中無結點 )，以后增加一個結點就使 head指向該結點。 如果輸入的 p1num不等于 0，則輸入的是第一個結點數據 (n=1)，令 head=p1，即把 p1的值賦給 head，也就是使 head也指向新開辟的結點 (圖 )。 p1所指向的新開辟的結點就成為鏈表中第一個結點。 然后再開辟另一個結點并使 p1指向它，接著輸入該結點的數據 (見圖 (a))。如果輸入的 p1num≠0，則應鏈入圖 2個結點 (n=2)，由于n≠1，則將 p1的值賦給 p2next，此時 p2指向第一個結點，因此執(zhí)行“ p2next=p1” 就將新結點的地址賦給第一個結點的 next成員，使第一個結點的 next成員指向第二個結點 (見圖 (b))。接著使 p2=p1，也就是使 p2指向剛才建立的結點，見圖 (c)。接著再開辟一個結點并使 p1指向它，并輸入該結點的數據 (見圖 (a))，在第三次循環(huán)中，由于 n=3(n≠1)，又將 p1的值賦給 p2next，也就是將第 3個結點連接到第 2個結點之后，并使p2=p1，使 p2指向最后一個結點 (見圖 (b))。