簡介
結構與聯合
結構類型定義和結構變數說明
在實際問題中，一組數據往往具有不同的數據類型。例如， 在學生登記表中，姓名應為字元型；學號可為整型或字元型；年齡應為整型；性別應為字元型；成績可為整型或實型。 顯然不能用一個數組來存放這一組數據。因為數組中各元素的類型和長度都必須一致，以便於編譯系統處理。為了解決這個問題，Ｃ語言中給出了另一種構造數據類型——“結構”。它相當於其它高級語言中的記錄。
“結構”是一種構造類型，它是由若干“成員”組成的。 每一個成員可以是一個基本數據類型或者又是一個構造類型。 結構既是一種“構造”而成的數據類型， 那么在說明和使用之前必須先定義它，也就是構造它。如同在說明和調用函式之前要先定義函式一樣。
結構的定義
定義一個結構的一般形式為：
struct 結構名
{
成員表列
};
成員表由若干個成員組成， 每個成員都是該結構的一個組成部分。對每個成員也必須作類型說明，其形式為：
類型說明符 成員名;
成員名的命名應符合標識符的書寫規定。例如：
struct stu
{
int num;
char name[20];
char sex;
float score;
};
在這個結構定義中，結構名為stu，該結構由4個成員組成。第一個成員為num，整型變數；第二個成員為name，字元數組；第三個成員為sex，字元變數；第四個成員為score，實型變數。應注意在括弧後的分號是不可少的。結構定義之後，即可進行變數說明。 凡說明為結構stu的變數都由上述4個成員組成。由此可見，結構是一種複雜的數據類型，是數目固定，類型不同的若干有序變數的集合。
結構類型變數的說明
說明結構變數有以下三種方法。以上面定義的stu為例來加以說明。
1. 先定義結構，再說明結構變數。如：
struct stu
{
int num;
char name[20];
char sex;
float score;
};
struct stu boy1,boy2;
說明了兩個變數boy1和boy2為stu結構類型。也可以用宏定義使一個符號常量來表示一個結構類型，例如：
#define STU struct stu
STU
{
int num;
char name[20];
char sex;
float score;
};
STU boy1,boy2;
2. 在定義結構類型的同時說明結構變數。例如：
struct stu
{
int num;
char name[20];
char sex;
float score;
}boy1,boy2;
3. 直接說明結構變數。例如：
struct
{
int num;
char name[20];
char sex;
float score;
}boy1,boy2;
第三種方法與第二種方法的區別在於第三種方法中省去了結構名，而直接給出結構變數。三種方法中說明的boy1,boy2變數都具有圖7.1所示的結構。說明了boy1,boy2變數為stu類型後，即可向這兩個變數中的各個成員賦值。在上述stu結構定義中，所有的成員都是基本數據類型或數組類型。成員也可以又是一個結構， 即構成了嵌套的結構。例如，圖7.2給出了另一個數據結構。 按圖7.2可給出以下結構定義：
struct date{
int month;
int day;
int year;
}
struct{
int num;
char name[20];
char sex;
struct date birthday;
float score;
}boy1,boy2;
首先定義一個結構date，由month(月)、day(日)、year(年) 三個成員組成。 在定義並說明變數 boy1 和 boy2 時，其中的成員birthday被說明為data結構類型。成員名可與程式中其它變數同名，互不干擾。結構變數成員的表示方法在程式中使用結構變數時，往往不把它作為一個整體來使用。
在ANSI C中除了允許具有相同類型的結構變數相互賦值以外， 一般對結構變數的使用，包括賦值、輸入、輸出、 運算等都是通過結構變數的成員來實現的。
表示結構變數成員的一般形式是：結構變數名.成員名 例如：boy1.num 即第一個人的學號 boy2.sex 即第二個人的性別如果成員本身又是一個結構則必須逐級找到最低級的成員才能使用。例如：boy1.birthday.month 即第一個人出生的月份成員可以在程式中單獨使用，與普通變數完全相同。
結構變數的賦值
前面已經介紹，結構變數的賦值就是給各成員賦值。 可用輸入語句或賦值語句來完成。
[例7.1]給結構變數賦值並輸出其值。
main(){
struct stu
{
int num;
char *name;
char sex;
float score;
} boy1,boy2;
boy1.num=102;
boy1.name="Zhang ping";
printf("input sex and score\n");
scanf("%c %f",&boy1.sex,&boy1.score);
boy2=boy1;
printf("Number=%d\nName=%s\n",boy2.num,boy2.name);
printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);
}
struct stu
{
int num;
char *name;
char sex;
float score;
}boy1,boy2;
boy1.num=102;
boy1.name="Zhang ping";
printf("input sex and score\n");
scanf("%c %f",&boy1.sex,&boy1.score);
boy2=boy1;
printf("Number=%d\nName=%s\n",boy2.num,boy2.name);
printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);
本程式中用賦值語句給num和name兩個成員賦值，name是一個字元串指針變數。用scanf函式動態地輸入sex和score成員值，然後把 boy1的所有成員的值整體賦予boy2。最後分別輸出boy2 的各個成員值。本例表示了結構變數的賦值、輸入和輸出的方法。
結構變數的初始化
如果結構變數是全局變數或為靜態變數， 則可對它作初始化賦值。對局部或自動結構變數不能作初始化賦值。
[例7.2]外部結構變數初始化。
struct stu /*定義結構*/
{
int num;
char *name;
char sex;
float score;
} boy2,boy1={102,"Zhang ping",'M',78.5};
main()
{
boy2=boy1;
printf("Number=%d\nName=%s\n",boy2.num,boy2.name);
printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);
}
struct stu
{
int num;
char *name;
char sex;
float score;
}boy2,boy1={102,"Zhang ping",'M',78.5};
main()
{
boy2=boy1;
……
}
本例中，boy2,boy1均被定義為外部結構變數，並對boy1作了初始化賦值。在main函式中，把boy1的值整體賦予boy2， 然後用兩個printf語句輸出boy2各成員的值。
[例7.3]靜態結構變數初始化。
main()
{
static struct stu /*定義靜態結構變數*/
{
int num;
char *name;
char sex;
float score;
}boy2,boy1={102,"Zhang ping",'M',78.5};
boy2=boy1;
printf("Number=%d\nName=%s\n",boy2.num,boy2.name);
printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);
}
static struct stu
{
int num;
char *name;
char sex;
float score;
}boy2,boy1={102,"Zhang ping",'M',78.5};
本例是把boy1，boy2都定義為靜態局部的結構變數， 同樣可以作初始化賦值。
結構數組
數組的元素也可以是結構類型的。 因此可以構成結構型數組。結構數組的每一個元素都是具有相同結構類型的下標結構變數。 在實際套用中，經常用結構數組來表示具有相同數據結構的一個群體。如一個班的學生檔案，一個車間職工的工資表等。
結構數組的定義方法和結構變數相似，只需說明它為數組類型即可。例如：
struct stu
{
int num;
char *name;
char sex;
float score;
}boy[5];
定義了一個結構數組boy1，共有5個元素，boy[0]～boy[4]。每個數組元素都具有struct stu的結構形式。 對外部結構數組或靜態結構數組可以作初始化賦值，例如：
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};
}
當對全部元素作初始化賦值時，也可不給出數組長度。
[例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()
{
int i,c=0;
float ave,s=0;
for(i=0;i<5;i++)
{
s+=boy.score;
if(boy.score<60) c+=1;
}
printf("s=%f\n",s);
ave=s/5;
printf("average=%f\ncount=%d\n",ave,c);
}
本例程式中定義了一個外部結構數組boy，共5個元素， 並作了初始化賦值。在main函式中用for語句逐個累加各元素的score 成員值存於s之中，如score的值小於60(不及格)即計數器C加1， 循環完畢後計算平均成績，並輸出全班總分，平均分及不及格人數。
[例7.5]建立同學通訊錄
#include"stdio.h"
#define NUM 3
struct mem
{
char name[20];
char phone[10];
};
main()
{
struct mem man[NUM];
int i;
for(i=0;i<NUM;i++)
{
printf("input name:\n");
gets(man.name);
printf("input phone:\n");
gets(man.phone);
}
printf("name\t\t\TPHONE\n\n");
for(i=0;i<NUM;i++)
printf("%s\t\t\t%s\n",man.name,man.phone);
}
本程式中定義了一個結構mem，它有兩個成員name和phone 用來表示姓名和電話號碼。在主函式中定義man為具有mem 類型的結構數組。在for語句中，用gets函式分別輸入各個元素中兩個成員的值。然後又在for語句中用printf語句輸出各元素中兩個成員值。
結構指針變數
結構指針變數的說明和使用一個指針變數當用來指向一個結構變數時， 稱之為結構指針變數。
結構指針變數中的值是所指向的結構變數的首地址。 通過結構指針即可訪問該結構變數， 這與數組指針和函式指針的情況是相同的。結構指針變數說明的一般形式為：
struct 結構名*結構指針變數名
例如，在前面的例7.1中定義了stu這個結構， 如要說明一個指向stu的指針變數pstu，可寫為：
struct stu *pstu;
當然也可在定義stu結構時同時說明pstu。與前面討論的各類指針變數相同，結構指針變數也必須要先賦值後才能使用。賦值是把結構變數的首地址賦予該指針變數， 不能把結構名賦予該指針變數。如果boy是被說明為stu類型的結構變數，則： pstu=&boy是正確的，而： pstu=&stu是錯誤的。
結構名和結構變數是兩個不同的概念，不能混淆。結構名只能表示一個結構形式，編譯系統並不對它分配記憶體空間。 只有當某變數被說明為這種類型的結構時，才對該變數分配存儲空間。因此上面&stu這種寫法是錯誤的，不可能去取一個結構名的首地址。 有了結構指針變數，就能更方便地訪問結構變數的各個成員。
其訪問的一般形式為： (*結構指針變數).成員名 或為：
結構指針變數->成員名
例如： (*pstu).num或者： pstu->num
應該注意(*pstu)兩側的括弧不可少， 因為成員符“.”的優先權高於“*”。如去掉括弧寫作*pstu.num則等效於*(pstu.num)，這樣，意義就完全不對了。 下面通過例子來說明結構指針變數的具體說明和使用方法。
[例7.6]
struct stu
{
int num;
char *name;
char sex;
float score;
} boy1={102,"Zhang ping",'M',78.5},*pstu;
main()
{
pstu=&boy1;
printf("Number=%d\nName=%s\n",boy1.num,boy1.name);
printf("Sex=%c\nScore=%f\n\n",boy1.sex,boy1.score);
printf("Number=%d\nName=%s\n",(*pstu).num,(*pstu).name);
printf("Sex=%c\nScore=%f\n\n",(*pstu).sex,(*pstu).score);
printf("Number=%d\nName=%s\n",pstu->num,pstu->name);
printf("Sex=%c\nScore=%f\n\n",pstu->sex,pstu->score);
}
本例程式定義了一個結構stu，定義了stu類型結構變數boy1 並作了初始化賦值，還定義了一個指向stu類型結構的指針變數pstu。在main函式中，pstu被賦予boy1的地址，因此pstu指向boy1 。然後在printf語句內用三種形式輸出boy1的各個成員值。 從運行結果可以看出：
結構變數.成員名
(*結構指針變數).成員名
結構指針變數->成員名
這三種用於表示結構成員的形式是完全等效的。結構數組指針變數結構指針變數可以指向一個結構數組， 這時結構指針變數的值是整個結構數組的首地址。結構指針變數也可指向結構數組的一個元素，這時結構指針變數的值是該結構數組元素的首地址。設ps為指向結構數組的指針變數，則ps也指向該結構數組的0 號元素，ps+1指向1號元素，ps+i則指向i號元素。 這與普通數組的情況是一致的。
[例7.7]用指針變數輸出結構數組。
struct stu
{
int num;
char *name;
char sex;
float score;
}boy[5]={
{101,"Zhou ping",'M',45},
{102,"Zhang ping",'M',62.5},
{103,"Liou fang",'F',92.5},
{104,"Cheng ling",'F',87},
{105,"Wang ming",'M',58},
};
main()
{
struct stu *ps;
printf("No\tName\t\t\tSex\tScore\t\n");
for(ps=boy;ps<boy+5;ps++)
printf("%d\t%s\t\t%c\t%f\t\n",ps->num,ps->name,ps->sex,ps->
score);
}
在程式中，定義了stu結構類型的外部數組boy 並作了初始化賦值。在main函式內定義ps為指向stu類型的指針。在循環語句for的表達式1中，ps被賦予boy的首地址，然後循環5次，輸出 boy數組中各成員值。 應該注意的是， 一個結構指針變數雖然可以用來訪問結構變數或結構數組元素的成員，但是，不能使它指向一個成員。也就是說不允許取一個成員的地址來賦予它。因此，下面的賦值是錯誤的。 ps=&boy[1].sex;而只能是：ps=boy;(賦予數組首地址)
或者是：
ps=&boy[0];(賦予0號元素首地址)
結構指針變數作函式參數
在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=動態存儲分配
在數組一章中，曾介紹過數組的長度是預先定義好的， 在整個程式中固定不變。Ｃ語言中不允許動態數組類型。例如： int n;scanf("%d",&n);int a[n]; 用變數表示長度，想對數組的大小作動態說明，這是錯誤的。但是在實際的編程中，往往會發生這種情況， 即所需的記憶體空間取決於實際輸入的數據，而無法預先確定。對於這種問題，用數組的辦法很難解決。為了解決上述問題，Ｃ語言提供了一些記憶體管理函式，這些記憶體管理函式可以按需要動態地分配記憶體空間，也可把不再使用的空間回收待用，為有效地利用記憶體資源提供了手段。 常用的記憶體管理函式有以下三個：
1.分配記憶體空間函式malloc
調用形式： (類型說明符*) malloc (size) 功能：在記憶體的動態存儲區中分配一塊長度為"size" 位元組的連續區域。函式的返回值為該區域的首地址。 “類型說明符”表示把該區域用於何種數據類型。(類型說明符*)表示把返回值強制轉換為該類型指針。“size”是一個無符號數。例如： 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。這樣一種連線方式，在數據結構中稱為“鍊表”。圖7.3為鍊表的示意圖。
在圖7.3中，第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。其過程如圖7.6所示。
函式編程如下：
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指向被插結點即可。見圖7.7(a)
2. 被插結點值最小，應插入第一結點之前。這種情況下使head指向被插結點，被插結點的指針域指向原來的第一結點則可。即：pi->next=pb;
head=pi; 見圖7.7(b)
3. 在其它位置插入，見圖7.7(c)。這種情況下，使插入位置的前一結點的指針域指向被插結點，使被插結點的指針域指向插入位置的後一結點。即為：pi->next=pb;pf->next=pi；
4. 在表末插入，見圖7.7(d)。這種情況下使原表末結點指針域指向被插結點，被插結點指針域置為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。聯合“聯合”也是一種構造類型的數據結構。 在一個“聯合”內可以定義多種不同的數據類型，一個被說明為該“聯合”類型的變數中，允許裝入該“聯合”所定義的任何一種數據。 這在前面的各種數據類型中都是辦不到的。例如，定義為整型的變數只能裝入整型數據，定義為實型的變數只能賦予實型數據。
在實際問題中有很多這樣的例子。例如在學校的教師和學生中填寫以下表格： 姓 名 年 齡 職 業 單位 “職業”一項可分為“教師”和“學生”兩類。對“單位”一項學生應填入班級編號，教師應填入某系某教研室。 班級可用整型量表示，教研室只能用字元類型。要求把這兩種類型不同的數據都填入“單位”這個變數中， 就必須把“單位”定義為包含整型和字元型數組這兩種類型的“聯合”。
“ 聯合”與“結構”有一些相似之處。但兩者有本質上的不同。在結構中各成員有各自的記憶體空間，一個結構變數的總長度是各成員長度之和。而在“聯合”中，各成員共享一段記憶體空間， 一個聯合變數的長度等於各成員中最長的長度。應該說明的是，這裡所謂的共享不是指把多個成員同時裝入一個聯合變數內， 而是指該聯合變數可被賦予任一成員值，但每次只能賦一種值，賦入新值則衝去舊值。如前面介紹的“單位”變數，如定義為一個可裝入“班級”或“教研室”的聯合後，就允許賦予整型值（班級)或字元串（教研室)。要么賦予整型值，要么賦予字元串，不能把兩者同時賦予它。聯合類型的定義和聯合變數的說明一個聯合類型必須經過定義之後， 才能把變數說明為該聯合類型。
一、聯合的定義
定義一個聯合類型的一般形式為：
union 聯合名
{
成員表
};
成員表中含有若干成員，成員的一般形式為： 類型說明符 成員名 成員名的命名應符合標識符的規定。
例如：
union perdata
{
int class;
char office[10];
};
定義了一個名為perdata的聯合類型，它含有兩個成員，一個為整型，成員名為class；另一個為字元數組，數組名為office。聯合定義之後，即可進行聯合變數說明，被說明為perdata類型的變數，可以存放整型量class或存放字元數組office。
二、聯合變數的說明
聯合變數的說明和結構變數的說明方式相同， 也有三種形式。即先定義，再說明；定義同時說明和直接說明。以perdata類型為例，說明如下：
union perdata
{
int class;
char officae[10];
};
union perdata a,b; /*說明a,b為perdata類型*/
或者可同時說明為：
union perdata
{ int class;
char office[10]; }a,b;或直接說明為： union
{ int class;
char office[10]; }a,b
經說明後的a,b變數均為perdata類型。 它們的記憶體分配示意圖如圖7—8所示。a,b變數的長度應等於 perdata 的成員中最長的長度， 即等於
office數組的長度，共10個位元組。從圖中可見，a,b變數如賦予整型值時，只使用了2個位元組，而賦予字元數組時，可用10個位元組。
聯合變數的賦值和使用
對聯合變數的賦值，使用都只能是對變數的成員進行。 聯合變數的成員表示為： 聯合變數名.成員名例如，a被說明為perdata類型的變數之後，可使用 a.class a.office 不允許只用聯合變數名作賦值或其它操作。也不允許對聯合變數作初始化賦值，賦值只能在程式中進行。還要再強調說明的是，一個聯合變數，每次只能賦予一個成員值。換句話說，一個聯合變數的值就是聯合變員的某一個成員值。
[例7.15]設有一個教師與學生通用的表格，教師數據有姓名，年齡，職業，教研室四項。學生有姓名，年齡，職業，班級四項。
編程輸入人員數據， 再以表格輸出。
main()
{
struct
{
char name[10];
int age;
char job;
union
{
int class;
char office[10];
} depa;
}body[2];
int n,i;
for(i=0;i<2;i++)
{
printf("input name,age,job and department\n");
scanf("%s %d %c",body.name,&body.age,&body.job);
if(body.job=="s")
scanf("%d",&body.depa.class);
else
scanf("%s",body.depa.office);
}
printf("name\tage job class/office\n");
for(i=0;i<2;i++)
{
if(body.job=="s")
printf("%s\t%3d %3c %d\n",body.name,body.age
,body.job,body.depa.class);
else
printf("%s\t%3d %3c %s\n",body.name,body.age,
body.job,body.depa.office);
}
}
本例程式用一個結構數組body來存放人員數據， 該結構共有四個成員。其中成員項depa是一個聯合類型，這個聯合又由兩個成員組成，一個為整型量class，一個為字元數組office。在程式的第一個for語句中，輸入人員的各項數據，先輸入結構的前三個成員name,age和job，然後判別job成員項，如為"s"則對聯合depa·class輸入(對學生賦班級編號)否則對depa·office輸入(對教師賦教研組名)。
在用scanf語句輸入時要注意，凡為數組類型的成員，無論是結構成員還是聯合成員，在該項前不能再加"&"運算符。如程式第18行中
body.name是一個數組類型，第22行中的body.depa.office也是數組類型，因此在這兩項之間不能加"&"運算符。程式中的第二個for語句用於輸出各成員項的值：
本章小結
1. 結構和聯合是兩種構造類型數據，是用戶定義新數據類型的重要手段。結構和聯合有很多的相似之處，它們都由成員組成。成員可以具有不同的數據類型。成員的表示方法相同。都可用三種方式作變數說明。
2. 在結構中，各成員都占有自己的記憶體空間，它們是同時存在的。一個結構變數的總長度等於所有成員長度之和。在聯合中，所有成員不能同時占用它的記憶體空間，它們不能同時存在。聯合變數的長度等於最長的成員的長度。
3. “.”是成員運算符，可用它表示成員項，成員還可用“->”運算符來表示。
4. 結構變數可以作為函式參數，函式也可返回指向結構的指針變數。而聯合變數不能作為函式參數，函式也不能返回指向聯合的指針變數。但可以使用指向聯合變數的指針，也可使用聯合數組。
5. 結構定義允許嵌套，結構中也可用聯合作為成員，形成結構和聯合的嵌套。
6. 鍊表是一種重要的數據結構，它便於實現動態的存儲分配。本章介紹是單向鍊表，還可組成雙向鍊表，循環鍊表等。
