結(jié)構(gòu)指針變量作函數(shù)參數(shù)

　　 在ANSI C標準中允許用結(jié)構(gòu)變量作函數(shù)參數(shù)進行整體傳送。 但是這種傳送要將全部成員逐個傳送， 特別是成員為數(shù)組時將會使傳送的時間和空間開銷很大，嚴重地降低了程序的效率。 因此最好的辦法就是使用指針，即用指針變量作函數(shù)參數(shù)進行傳送。 這時由實參傳向形參的只是地址，從而減少了時間和空間的開銷。

　　 [例7.8]題目與例7.4相同，計算一組學生的平均成績和不及格人數(shù)。

　　 用結(jié)構(gòu)指針變量作函數(shù)參數(shù)編程。

struct stu
{
　 int num;
　 char *name;
　 char sex;
　 float score;}boy[5]={
　　 {101,”Li ping”,’M’,45},
　　 {102,”Zhang ping”,’M’,62.5},
　　 {103,”He fang”,’F’,92.5},
　　 {104,”Cheng ling”,’F’,87},
　　 {105,”Wang ming”,’M’,58},
　 };
main()
{
　 struct stu *ps;
　 void ave(struct stu *ps);
　 ps=boy;
　 ave(ps);
}
void ave(struct stu *ps)
{
　 int c=0,i;
　 float ave,s=0;
　 for(i=0;i<5;i++,ps++)
　 {
　　 s+=ps->score;
　　 if(ps->score<60) c+=1;
　 }
　 printf(“s=%fn”,s);
　 ave=s/5;
　 printf(“average=%fncount=%dn”,ave,c);
}

　　 本程序中定義了函數(shù)ave，其形參為結(jié)構(gòu)指針變量ps。boy 被定義為外部結(jié)構(gòu)數(shù)組，因此在整個源程序中有效。在main 函數(shù)中定義說明了結(jié)構(gòu)指針變量ps，并把boy的首地址賦予它，使ps指向boy 數(shù)組。然后以ps作實參調(diào)用函數(shù)ave。在函數(shù)ave 中完成計算平均成績和統(tǒng)計不及格人數(shù)的工作并輸出結(jié)果。與例7.4程序相比，由于本程序全部采用指針變量作運算和處理，故速度更快，程序效率更高。.

　　 topoic=動態(tài)存儲分配

　　 在數(shù)組一章中，曾介紹過數(shù)組的長度是預先定義好的， 在整個程序中固定不變。C語言中不允許動態(tài)數(shù)組類型。例如： int n;scanf(“%d”,&n);int a[n]; 用變量表示長度，想對數(shù)組的大小作動態(tài)說明， 這是錯誤的。但是在實際的編程中，往往會發(fā)生這種情況， 即所需的內(nèi)存空間取決于實際輸入的數(shù)據(jù)，而無法預先確定。對于這種問題， 用數(shù)組的辦法很難解決。為了解決上述問題，C語言提供了一些內(nèi)存管理函數(shù)，這些內(nèi)存管理函數(shù)可以按需要動態(tài)地分配內(nèi)存空間， 也可把不再使用的空間回收待用，為有效地利用內(nèi)存資源提供了手段。 常用的內(nèi)存管理函數(shù)有以下三個：

　　 1.分配內(nèi)存空間函數(shù)malloc

　　 調(diào)用形式： (類型說明符*) malloc (size) 功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一塊長度為”size” 字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。 “類型說明符”表示把該區(qū)域用于何種數(shù)據(jù)類型。(類型說明符*)表示把返回值強制轉(zhuǎn)換為該類型指針。“size”是一個無符號數(shù)。例如： pc=(char *) malloc (100); 表示分配100個字節(jié)的內(nèi)存空間，并強制轉(zhuǎn)換為字符數(shù)組類型， 函數(shù)的返回值為指向該字符數(shù)組的指針， 把該指針賦予指針變量pc。

　　 2.分配內(nèi)存空間函數(shù) calloc

　　 calloc 也用于分配內(nèi)存空間。調(diào)用形式： (類型說明符*)calloc(n,size) 功能：在內(nèi)存動態(tài)存儲區(qū)中分配n塊長度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。(類型說明符*)用于強制類型轉(zhuǎn)換。calloc函數(shù)與malloc 函數(shù)的區(qū)別僅在于一次可以分配n塊區(qū)域。例如： ps=(struet stu*) calloc(2,sizeof (struct stu)); 其中的sizeof(struct stu)是求stu的結(jié)構(gòu)長度。因此該語句的意思是：按stu的長度分配2塊連續(xù)區(qū)域，強制轉(zhuǎn)換為stu類型，并把其首地址賦予指針變量ps。

　　 3.釋放內(nèi)存空間函數(shù)free

　　 調(diào)用形式： free(void*ptr); 功能：釋放ptr所指向的一塊內(nèi)存空間，ptr 是一個任意類型的指針變量，它指向被釋放區(qū)域的首地址。被釋放區(qū)應是由malloc或calloc函數(shù)所分配的區(qū)域：[例7.9]分配一塊區(qū)域，輸入一個學生數(shù)據(jù)。

main()
{
　 struct stu
　 {
　　 int num;
　　 char *name;
　　 char sex;
　　 float score;
　 } *ps;
　 ps=(struct stu*)malloc(sizeof(struct stu));
　 ps->num=102;
　 ps->name=”Zhang ping”;
　 ps->sex=’M’;
　 ps->score=62.5;
　 printf(“Number=%dnName=%sn”,ps->num,ps->name);
　 printf(“Sex=%cnScore=%fn”,ps->sex,ps->score);
　 free(ps);
}

　　 本例中，定義了結(jié)構(gòu)stu，定義了stu類型指針變量ps。 然后分配一塊stu大內(nèi)存區(qū)，并把首地址賦予ps，使ps指向該區(qū)域。再以ps為指向結(jié)構(gòu)的指針變量對各成員賦值，并用printf 輸出各成員值。最后用free函數(shù)釋放ps指向的內(nèi)存空間。 整個程序包含了申請內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存空間三個步驟， 實現(xiàn)存儲空間的動態(tài)分配。鏈表的概念在例7.9中采用了動態(tài)分配的辦法為一個結(jié)構(gòu)分配內(nèi)存空間。每一次分配一塊空間可用來存放一個學生的數(shù)據(jù)， 我們可稱之為一個結(jié)點。有多少個學生就應該申請分配多少塊內(nèi)存空間， 也就是說要建立多少個結(jié)點。當然用結(jié)構(gòu)數(shù)組也可以完成上述工作， 但如果預先不能準確把握學生人數(shù)，也就無法確定數(shù)組大小。 而且當學生留級、退學之后也不能把該元素占用的空間從數(shù)組中釋放出來。 用動態(tài)存儲的方法可以很好地解決這些問題。 有一個學生就分配一個結(jié)點，無須預先確定學生的準確人數(shù)，某學生退學， 可刪去該結(jié)點，并釋放該結(jié)點占用的存儲空間。從而節(jié)約了寶貴的內(nèi)存資源。 另一方面，用數(shù)組的方法必須占用一塊連續(xù)的內(nèi)存區(qū)域。 而使用動態(tài)分配時，每個結(jié)點之間可以是不連續(xù)的(結(jié)點內(nèi)是連續(xù)的)。 結(jié)點之間的聯(lián)系可以用指針實現(xiàn)。 即在結(jié)點結(jié)構(gòu)中定義一個成員項用來存放下一結(jié)點的首地址，這個用于存放地址的成員，常把它稱為指針域?？稍诘谝粋€結(jié)點的指針域內(nèi)存入第二個結(jié)點的首地址， 在第二個結(jié)點的指針域內(nèi)又存放第三個結(jié)點的首地址， 如此串連下去直到最后一個結(jié)點。最后一個結(jié)點因無后續(xù)結(jié)點連接，其指針域可賦為0。這樣一種連接方式，在數(shù)據(jù)結(jié)構(gòu)中稱為“鏈表”。

　　 在鏈表中，第0個結(jié)點稱為頭結(jié)點， 它存放有第一個結(jié)點的首地址，它沒有數(shù)據(jù)，只是一個指針變量。 以下的每個結(jié)點都分為兩個域，一個是數(shù)據(jù)域，存放各種實際的數(shù)據(jù)，如學號num，姓名name，性別sex和成績score等。另一個域為指針域， 存放下一結(jié)點的首地址。鏈表中的每一個結(jié)點都是同一種結(jié)構(gòu)類型。例如， 一個存放學生學號和成績的結(jié)點應為以下結(jié)構(gòu)：

struct stu
{
　 int num;
　 int score;
　 struct stu *next;
}

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

　　 1.建立鏈表；

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

　　 3.插入一個結(jié)點；

　　 4.刪除一個結(jié)點；

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

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

　　 可編寫一個建立鏈表的函數(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<n;i++)
　 {
　　 pb=(TYPE*) malloc(LEN);
　　 printf(“input Number and Agen”);
　　 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ù)外首先用宏定義對三個符號常量作了定義。這里用TYPE表示struct stu，用LEN表示sizeof(struct stu)主要的目的是為了在以下程序內(nèi)減少書寫并使閱讀更加方便。結(jié)構(gòu)stu定義為外部類型，程序中的各個函數(shù)均可使用該定義。

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

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

　　 [例7.11]寫一個函數(shù)，在鏈表中按學號查找該結(jié)點。

TYPE * search (TYPE *head,int n)
{
　 TYPE *p;
　 int i;
　 p=head;
　 while (p->num!=n && p->next!=NULL)
　　 p=p->next; /* 不是要找的結(jié)點后移一步*/
　　 if (p->num==n) return (p);
　　 if (p->num!=n&& p->next==NULL)
　　 printf (“Node %d has not been found!n”,n
}

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

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

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

　　 2. 被刪結(jié)點不是第一個結(jié)點，這種情況使被刪結(jié)點的前一結(jié)點指向被刪結(jié)點的后一結(jié)點即可。即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)
　　 /*當不是要刪除的結(jié)點，而且也不是最后一個結(jié)點時，繼續(xù)循環(huán)*/
　 {
　　 pf=pb;pb=pb->next;}/*pf指向當前結(jié)點，pb指向下一結(jié)點*/
　　 if(pb->num==num)
　　 {
　　　 if(pb==head) head=pb->next;
　　　　 /*如找到被刪結(jié)點，且為第一結(jié)點，則使head指向第二個結(jié)點，
　　　　　 否則使pf所指結(jié)點的指針指向下一結(jié)點*/
　　　 else pf->next=pb->next;
　　　 free(pb);
　　　 printf(“The node is deletedn”);}
　　 else
　　　 printf(“The node not been foud!n”);
　　　 end:
　　 return head;
　 }

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

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

　　 1. 原表是空表，只需使head指向被插結(jié)點即可。

　　 2. 被插結(jié)點值最小，應插入第一結(jié)點之前。這種情況下使head指向被插結(jié)點，被插結(jié)點的指針域指向原來的第一結(jié)點則可。即：

pi->next=pb;
head=pi;

　　 3. 在其它位置插入。這種情況下，使插入位置的前一結(jié)點的指針域指向被插結(jié)點，使被插結(jié)點的指針域指向插入位置的后一結(jié)點。即為：pi->next=pb;pf->next=pi；

　　 4. 在表末插入。這種情況下使原表末結(jié)點指針域指向被插結(jié)點，被插結(jié)點指針域置為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;/*在第一結(jié)點之前插入*/
　　　 else pf->next=pi;/*在其它位置插入*/
　　　 pi->next=pb; }
　　 else
　　 {
　　　 pb->next=pi;
　　　 pi->next=NULL;
　　 } /*在表末插入*/
　 }
　 return head;
}

　　 本函數(shù)有兩個形參均為指針變量，head指向鏈表，pi 指向被插結(jié)點。函數(shù)中首先判斷鏈表是否為空，為空則使head指向被插結(jié)點。表若不空，則用while語句循環(huán)查找插入位置。找到之后再判斷是否在第一結(jié)點之前插入，若是則使head 指向被插結(jié)點被插結(jié)點指針域指向原第一結(jié)點，否則在其它位置插入， 若插入的結(jié)點大于表中所有結(jié)點，則在表末插入。本函數(shù)返回一個指針， 是鏈表的頭指針。 當插入的位置在第一個結(jié)點之前時， 插入的新結(jié)點成為鏈表的第一個結(jié)點，因此head的值也有了改變， 故需要把這個指針返回主調(diào)函數(shù)。

　　 [例7.14]將以上建立鏈表，刪除結(jié)點，插入結(jié)點的函數(shù)組織在一起，再建一個輸出全部結(jié)點的函數(shù)，然后用main函數(shù)調(diào)用它們。

#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<n;i++)
　 {
　　 pb=(TYPE *)malloc(LEN);
　　 printf(“input Number and Agen”);
　　 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 * 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;
　 }
　 if(pb->num==num)
　 {
　　 if(pb==head) head=pb->next;
　　 else pf->next=pb->next;
　　 printf(“The node is deletedn”);
　 }
　 else
　　 free(pb);
　　 printf(“The node not been found!n”);
　 end:
　 return head;
}
TYPE * insert(TYPE * head,TYPE * pi)
{
　 TYPE *pb ,*pf;
　 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;
　　　 else pf->next=pi;
　　　 pi->next=pb;
　　 }
　　 else
　　 {
　　　 pb->next=pi;
　　　 pi->next=NULL;
　　 }
　 }
　 return head;
}
void print(TYPE * head)
{
　 printf(“NumberttAgen”);
　 while(head!=NULL)
　 {
　　 printf(“%dtt%dn”,head->num,head->age);
　　 head=head->next;
　 }
}
main()
{
　 TYPE * head,*pnum;
　 int n,num;
　 printf(“input number of node: “);
　 scanf(“%d”,&n);
　 head=creat(n);
　 print(head);
　 printf(“Input the deleted number: “);
　 scanf(“%d”,&num);
　 head=delete(head,num);
　 print(head);
　 printf(“Input the inserted number and age: “);
　 pnum=(TYPE *)malloc(LEN);
　 scanf(“%d%d”,&pnum->num,&pnum->age);
　 head=insert(head,pnum);
　 print(head);
}

　　 本例中，print函數(shù)用于輸出鏈表中各個結(jié)點數(shù)據(jù)域值。函數(shù)的形參head的初值指向鏈表第一個結(jié)點。在while語句中，輸出結(jié)點值后，head值被改變，指向下一結(jié)點。若保留頭指針head， 則應另設一個指針變量，把head值賦予它，再用它來替代head。在main函數(shù)中，n為建立結(jié)點的數(shù)目， num為待刪結(jié)點的數(shù)據(jù)域值；head為指向鏈表的頭指針，pnum為指向待插結(jié)點的指針。 main函數(shù)中各行的意義是：

　　 第六行輸入所建鏈表的結(jié)點數(shù)；

　　 第七行調(diào)creat函數(shù)建立鏈表并把頭指針返回給head；

　　 第八行調(diào)print函數(shù)輸出鏈表；

　　 第十行輸入待刪結(jié)點的學號；

　　 第十一行調(diào)delete函數(shù)刪除一個結(jié)點；

　　 第十二行調(diào)print函數(shù)輸出鏈表；

　　 第十四行調(diào)malloc函數(shù)分配一個結(jié)點的內(nèi)存空間， 并把其地址賦予pnum;

　　 第十五行輸入待插入結(jié)點的數(shù)據(jù)域值；

　　 第十六行調(diào)insert函數(shù)插入pnum所指的結(jié)點；

　　 第十七行再次調(diào)print函數(shù)輸出鏈表。

　　 從運行結(jié)果看，首先建立起3個結(jié)點的鏈表，并輸出其值；再刪103號結(jié)點，只剩下105，108號結(jié)點；又輸入106號結(jié)點數(shù)據(jù)， 插入后鏈表中的結(jié)點為105，106，108。聯(lián)合“聯(lián)合”也是一種構(gòu)造類型的數(shù)據(jù)結(jié)構(gòu)。 在一個“聯(lián)合”內(nèi)可以定義多種不同的數(shù)據(jù)類型， 一個被說明為該“聯(lián)合”類型的變量中，允許裝入該“聯(lián)合”所定義的任何一種數(shù)據(jù)。 這在前面的各種數(shù)據(jù)類型中都是辦不到的。例如， 定義為整型的變量只能裝入整型數(shù)據(jù)，定義為實型的變量只能賦予實型數(shù)據(jù)。