C語言初學者入門講座第十二講結構(3)

2019-11-17 05:41:48

字體：大中小

來源：轉載

供稿：網友

　　結構指針變量作函數參數

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

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

　　用結構指針變量作函數參數編程。

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=%f/n",s);
　ave=s/5;
　printf("average=%f/ncount=%d/n",ave,c);
}

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

　　topoic=動態存儲分配

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

　　1.分配內存空間函數malloc

　　調用形式： (類型說明符*) malloc (size) 功能：在內存的動態存儲區中分配一塊長度為"size" 字節的連續區域。函數的返回值為該區域的首地址。 “類型說明符”表示把該區域用于何種數據類型。(類型說明符*)表示把返回值強制轉換為該類型指針?！皊ize”是一個無符號數。例如： pc=(char *) malloc (100); 表示分配100個字節的內存空間，并強制轉換為字符數組類型，函數的返回值為指向該字符數組的指針，把該指針賦予指針變量pc。

　　2.分配內存空間函數 calloc

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

　　3.釋放內存空間函數free

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

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=%d/nName=%s/n",ps->num,ps->name);
　printf("Sex=%c/nScore=%f/n",ps->sex,ps->score);
　free(ps);
}

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

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

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

　　前兩個成員項組成數據域，后一個成員項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<n;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。可在三種不同情況下插入。

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

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

pi->next=pb;
head=pi;

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

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

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

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

#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 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 * 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 deleted/n");
　}
　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("Number/t/tAge/n");
　while(head!=NULL)
　{
　　printf("%d/t/t%d/n",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函數用于輸出鏈表中各個結點數據域值。函數的形參head的初值指向鏈表第一個結點。在while語句中，輸出結點值后，head值被改變，指向下一結點。若保留頭指針head，則應另設一個指針變量，把head值賦予它，再用它來替代head。在main函數中，n為建立結點的數目， num為待刪結點的數據域值；head為指向鏈表的頭指針，pnum為指向待插結點的指針。 main函數中各行的意義是：

　　第六行輸入所建鏈表的結點數；

　　第七行調creat函數建立鏈表并把頭指針返回給head；

　　第八行調print函數輸出鏈表；

　　第十行輸入待刪結點的學號；

　　第十一行調delete函數刪除一個結點；

　　第十二行調print函數輸出鏈表；

　　第十四行調malloc函數分配一個結點的內存空間，并把其地址賦予pnum;

　　第十五行輸入待插入結點的數據域值；

　　第十六行調insert函數插入pnum所指的結點；

　　第十七行再次調print函數輸出鏈表。

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

上一篇：C語言編程常見問題解答之程序的編寫和編譯

下一篇：C語言編程常見問題解答之標準庫函數（2）