C語言程序設(shè)計教程(第4版)-第9章-結(jié)構(gòu)

C語言程序設(shè)計教程

（第4版）第9章結(jié)構(gòu)李麗娟2013年2月第9章結(jié)構(gòu)本章主要內(nèi)容1.了解結(jié)構(gòu)數(shù)據(jù)類型的定義及使用。2.了解結(jié)構(gòu)數(shù)據(jù)類型的意義及作用。3.了解結(jié)構(gòu)變量與函數(shù)的關(guān)系。4.掌握鏈表的作用及操作。5.了解聯(lián)合數(shù)據(jù)類型的定義及使用。6.了解枚舉類型的定義及使用。第9章結(jié)構(gòu)結(jié)構(gòu)體數(shù)據(jù)類型：一種自定義的數(shù)據(jù)類型。由不同數(shù)據(jù)類型的數(shù)據(jù)組合而成的數(shù)據(jù)整體。結(jié)構(gòu)體中所包含的數(shù)據(jù)元素稱之為成員。如：“職員”——→一種結(jié)構(gòu)體描述職員的信息有：編號、姓名、年齡、性別、身份證號碼、民族、文化程度、職務(wù)、住址、聯(lián)系電話等。9.1

結(jié)構(gòu)體數(shù)據(jù)類型9.1.1結(jié)構(gòu)體的定義結(jié)構(gòu)類型的定義形式：

struct結(jié)構(gòu)體名 {

成員項表列; };成員項表列同簡單變量的定義形式相同。例如：對“職員”數(shù)據(jù)，可以定義如下的結(jié)構(gòu)體類型：structperson{longno;

/*職員號*/charname[12];

/*姓名*/intage;

/*年齡*/charsex;

/*性別*/longindentityNo;

/*身份證號*/chareducation[12];

/*學(xué)歷*/charaddr[40];

/*住址*/longtelno;

/*電話號碼*/};9.1

結(jié)構(gòu)體數(shù)據(jù)類型9.1.2結(jié)構(gòu)體變量的定義定義了結(jié)構(gòu)體之后，就可以定義結(jié)構(gòu)體變量。結(jié)構(gòu)變量的定義形式。（1）類型標(biāo)識符

<變量名列表>;例如：

struct

person

stu,worker;（2）在定義一個結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體類型變量：

struct<結(jié)構(gòu)體名> {

成員項列表; }<變量名列表>;（3）直接定義結(jié)構(gòu)體類型的變量：

struct

{

成員項列表;

}<變量名列表>;9.1

結(jié)構(gòu)體數(shù)據(jù)類型9.1.3結(jié)構(gòu)體變量的初始化

（略）9.1.4結(jié)構(gòu)體變量成員的引用（1）引用結(jié)構(gòu)體變量中的成員。

引用格式：<結(jié)構(gòu)變量名>.<成員名>例如：

stu.no、

stu.age、

[0]等。成員名不能單獨代表變量，不能直接使用結(jié)構(gòu)中的成員名。若結(jié)構(gòu)體類型中含有另一個結(jié)構(gòu)類型，訪問該成員時，應(yīng)采取逐級訪問的方法。（2）將結(jié)構(gòu)體變量作為一個整體來使用。結(jié)構(gòu)體變量可以相互賦值。

(條件是這兩個變量必須具有相同的結(jié)構(gòu)體類型。)9.1

結(jié)構(gòu)體數(shù)據(jù)類型例1：閱讀程序example9_1.c，了解結(jié)構(gòu)體成員的使用方法。9.1.5結(jié)構(gòu)體變量成員的輸入/輸出只允許對結(jié)構(gòu)變量的成員進(jìn)行輸入輸出。不允許將結(jié)構(gòu)體變量作為整體進(jìn)行輸入或輸出操作。9.2結(jié)構(gòu)體數(shù)組9.2.1結(jié)構(gòu)體數(shù)組的定義結(jié)構(gòu)體數(shù)組的定義：（1）先定義結(jié)構(gòu)體，再定義結(jié)構(gòu)體數(shù)組。

struct<結(jié)構(gòu)體名> { <成員項表列> };

struct<結(jié)構(gòu)體名>

<數(shù)組名>[<數(shù)組大小>];（2）在定義結(jié)構(gòu)體的同時，定義結(jié)構(gòu)體數(shù)組。

struct<結(jié)構(gòu)體名> { <成員項表列> }<數(shù)組名>[<數(shù)組大小>];9.2結(jié)構(gòu)體數(shù)組（3）直接定義結(jié)構(gòu)體變量而不定義結(jié)構(gòu)體名。 struct { <成員項表列> }<數(shù)組名>[<數(shù)組大小>];9.2.2結(jié)構(gòu)體數(shù)組成員的初始化和引用

（略）9.3結(jié)構(gòu)體變量與函數(shù)9.3.1函數(shù)的形參與實參為結(jié)構(gòu)體作用：傳值例2：閱讀程序example9_2.c，了解結(jié)構(gòu)變量作為函數(shù)參數(shù)的作用。9.3.2函數(shù)的返回值類型為結(jié)構(gòu)體新的C標(biāo)準(zhǔn)中允許函數(shù)的返回值為結(jié)構(gòu)體類型的值。例3：修改例9-2所示的程序，將“輸入購書信息”模塊的返回值修改成結(jié)構(gòu)類型。9.4聯(lián)合體數(shù)據(jù)類型9.4聯(lián)合體數(shù)據(jù)類型聯(lián)合體又稱為共用體。聯(lián)合體類型與結(jié)構(gòu)體類型的同異：相同之處：定義形式與結(jié)構(gòu)體類型的定義形式相同。

不同之處：①關(guān)鍵字不同，共用體的關(guān)鍵字為union。

②占用的內(nèi)存單元不同。特點：

不同類型的數(shù)組項在內(nèi)存中所占用的起始單元是相同的。提示：

注意聯(lián)合類型變量的使用特點。9.4聯(lián)合體數(shù)據(jù)類型比較結(jié)構(gòu)類型變量和聯(lián)合類型變量占用的內(nèi)存情況：結(jié)構(gòu)類型：structmemb{floatv;intn;charc;}stag;聯(lián)合類型：unionmemb{floatv;intn;charc;}utag;stag占用內(nèi)存單元utag占用內(nèi)存單元9.4聯(lián)合體數(shù)據(jù)類型例4：閱讀程序example9_4.c，分析和了解聯(lián)合體變量成員的取值情況。例5：閱讀程序example9_5.c，了解聯(lián)合體類型變量的賦值情況。9.5枚舉數(shù)據(jù)類型枚舉數(shù)據(jù)類型：用標(biāo)識符表示的整數(shù)常量的集合。枚舉類型定義的一般形式：

enum<枚舉類型名>{標(biāo)識符1,標(biāo)識符2,……,標(biāo)識符n};枚舉常量的起始值為0。例如：

enummonths{JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC};標(biāo)識符的值被依次自動設(shè)置為整數(shù)0～11。可以改變標(biāo)識符的取值，例如：

enummonths{JAN＝1,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC};標(biāo)識符的值被依次自動設(shè)置為整數(shù)1～12。9.5枚舉數(shù)據(jù)類型幾點說明：枚舉類型定義中的標(biāo)識符必須是唯一的。可以在枚舉類型定義時為每一個枚舉常量指定不同的值。也可以對中間的某個枚舉常量指定不同的值。例如：

enumclolor{red,blue,green,yellow=5,black,white};由于只指定了yellow的值，則枚舉常量的取值情況為： red=0，blue=1，green=2， yellow=5，black=6，while=7。枚舉常量的值不可更改，但可以作為整型數(shù)使用。9.5枚舉數(shù)據(jù)類型枚舉變量的定義形式：

enum<枚舉類型名>變量名1,變量名2,……變量名n;例如：

enummonthwork_day,rest_day;也可以在定義枚舉類型的同時定義枚舉變量。例如：

enumcolor{red,yellow,green}

light;枚舉常量標(biāo)識符是不能直接輸入/輸出的，要通過其他方式來輸出枚舉常量標(biāo)識符。9.5枚舉數(shù)據(jù)類型例6：閱讀程序example9_6.c，了解枚舉變量的輸出方式。9.6鏈表的概念基本概念：①鏈表指的是將若干個數(shù)據(jù)項按一定的規(guī)則連接起來的表。②鏈表中的數(shù)據(jù)項稱為結(jié)點。③鏈表中每一個結(jié)點的數(shù)據(jù)類型都有一個自引用結(jié)構(gòu)④自引用結(jié)構(gòu)就是結(jié)構(gòu)成員中包含一個指針成員，該指針指向與自身同一個類型的結(jié)構(gòu)。例如：

structnode {intdata；

structnode*nextPtr; }；9.6鏈表的概念鏈表是用鏈節(jié)指針連接在一起的結(jié)點的線性集合。其結(jié)構(gòu)如圖所示：自引用結(jié)構(gòu)成員的變量通常是指針型的。結(jié)構(gòu)成員的引用與成員的類型相關(guān)。假如有：

structnode {

intdata；

structnode*nextPtr; }；定義結(jié)構(gòu)變量：

structnode*pt;結(jié)構(gòu)成員的引用：

pt->data; pt->nextptr;或：

(*pt).data; (*pt).nextptr;9.6鏈表的概念鏈表可以組成較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。根據(jù)數(shù)據(jù)之間的相互關(guān)系，鏈表又可分為單鏈表、循環(huán)鏈表、雙向鏈表等。鏈表的可以建立動態(tài)的數(shù)據(jù)結(jié)構(gòu)，可以將不連續(xù)的內(nèi)存數(shù)據(jù)連接起來。本章重點：單鏈表。其他鏈表參見“數(shù)據(jù)結(jié)構(gòu)”等教程。9.6鏈表的概念9.6.1動態(tài)分配內(nèi)存動態(tài)分配內(nèi)存空間的系統(tǒng)函數(shù)：

malloc()和free()函數(shù)以及sizeof運算符的配合使用

(注：

malloc()和free()函數(shù)在頭文件stdlib.h或alloc.h)。函數(shù)原型及功能如下。1．函數(shù)原型：void*malloc(unsignedsize)功能：從內(nèi)存分配一個大小為size個字節(jié)的內(nèi)存空間。若成功，返回新分配內(nèi)存的首地址；若沒有足夠的內(nèi)存分配，則返回NULL。通常函數(shù)malloc()通常和運算符sizeof一起使用。9.6鏈表的概念例如：

int*p;

p=malloc(20*sizeof(int))；／*分配20個整型數(shù)所需的內(nèi)存空間*／系統(tǒng)分配能存放20個整型數(shù)連續(xù)空間，

p指向該存儲空間的首地址。例如： structstudent {intno;

intscore;

structstudent*next; }; structstudent*stu; stu=malloc(sizeof(structstudent));通過sizeof計算structstudent的字節(jié)數(shù)，分配sizeof（structstudent）個字節(jié)數(shù)的內(nèi)存空間，

stu指向該存儲空間的首地址。9.6鏈表的概念2．函數(shù)原型：voidfree(void*p)功能：釋放由malloc函數(shù)所分配的內(nèi)存塊，無返回值。例如：free(stu);作用：將stu所指的內(nèi)存空間釋放。幾點注意：①結(jié)構(gòu)類型占用的內(nèi)存空間不一定是連續(xù)的，因此，應(yīng)該用sizeof運算符來確定結(jié)構(gòu)類型占用內(nèi)存空間的大小。②使用malloc()函數(shù)時,應(yīng)對其返回值進(jìn)行檢測是否為NULL，以確保程序的正確。③要及時地使用free()函數(shù)釋放不再需要的內(nèi)存空間，避免系統(tǒng)資源過早地用光。④不要引用已經(jīng)釋放的內(nèi)存空間。9.6鏈表的概念9.6.2單鏈表的建立鏈表：通過自引用結(jié)構(gòu)的指針域，將各節(jié)點相互連接。關(guān)于鏈表的基本概念：(1)鏈表的第一個結(jié)點稱頭指針或頭結(jié)點，它指向鏈表在內(nèi)存中的首地址，(2)其后的結(jié)點是通過結(jié)點中的鏈節(jié)指針成員訪問的。(3)鏈表的最后一個結(jié)點稱為尾節(jié)點。尾節(jié)點的指針域通常被設(shè)置成NULL。(4)鏈表中的每一個結(jié)點是在需要的時候建立的。(5)各結(jié)點在內(nèi)存中的存儲地址不一定是連續(xù)的，由系統(tǒng)自動分配的，即有可能是連續(xù)分配內(nèi)存空間，也有可能是跳躍式的不連續(xù)分配內(nèi)存空間。9.6鏈表的概念建立單鏈表的主要步驟：①定義單鏈表的數(shù)據(jù)結(jié)構(gòu)（定義自引用結(jié)構(gòu)）。②建立表頭（建立一個空表）。③利用malloc函數(shù)向系統(tǒng)申請分配一個結(jié)點空間。④將新結(jié)點的指針成員的值賦為空（NULL），若是空表，將新結(jié)點連接到表頭；若非空表，則將新結(jié)點連接到表尾。⑤若有后續(xù)結(jié)點要接入鏈表，則轉(zhuǎn)到③，否則結(jié)束。輸出一個單鏈表的主要步驟：①找出表頭結(jié)束，結(jié)點指針P指向頭結(jié)點。②若P非空，循環(huán)執(zhí)行下列操作。{

輸出結(jié)點值；P指向下一結(jié)點；}9.6鏈表的概念例7：編寫程序，創(chuàng)建一個鏈表，該鏈表可以存放從鍵盤輸入的任意長度的字符串，以按下回車鍵作為輸入的結(jié)束。統(tǒng)計輸入的字符個數(shù)并將其字符串輸出。程序：example9_7.c例8：編寫程序，用鏈表的結(jié)構(gòu)建立一條公交線路的站點信息，從鍵盤依次輸入從起點到終點的各站站名，以單個“#”字符作為輸入結(jié)束，統(tǒng)計站的數(shù)量并輸出這些站點。分析：站點信息結(jié)構(gòu)設(shè)計如下：

structstation { charname[8]; structstation*nextSta; };設(shè)計函數(shù)：structstation*creat_sta(structstation*h)；

/*將鍵盤輸入的站點名依次插入到鏈表h中*/程序：example9_8.c9.6鏈表的概念9.6.3從單鏈表中刪除結(jié)點在鏈表中刪去一個結(jié)點，不允許破壞原鏈表的結(jié)構(gòu)。例如，對于這樣的自引用結(jié)構(gòu)：

structnode {intn;

structnode*next; };假定已建好鏈表：刪除s節(jié)點后的鏈表：9.6鏈表的概念刪除節(jié)點方法：修改指針域的值。根據(jù)被刪節(jié)點的位置，修改指針域的方法要分3種不同情況：①s結(jié)點在表的中間（即不在表頭，也不在表尾）：

p->next=s->next;②s結(jié)點位于表頭：

head=s->next;③s結(jié)點位于表尾：

p->next=NULL;結(jié)點刪除后，用free()函數(shù)釋放被刪除結(jié)點所占用的內(nèi)存空間。例如：free(s);

/*釋放了節(jié)點s所占用的空間。*/9.6鏈表的概念例9：修改例9-8的程序，再從鍵盤輸入一個要刪除的站點名，并將刪除后的站點依次輸出。分析：在例9-8程序的基礎(chǔ)上增加一個刪除節(jié)點的函數(shù)：

structstation*del_sta(structstation*h,

char*str)；函數(shù)功能：

在h所指的鏈表中，刪除結(jié)點值為str所指字符串的結(jié)點。程序：

example9_9.c請分析函數(shù)：

structstation*del_sta(structstation*h,char*str);的算法。思考程序中存在的問題，怎樣處理可以使程序更加完善？9.6鏈表的概念9.6.4向鏈表中插入結(jié)點插入節(jié)點方法：修改指針域的值。根據(jù)節(jié)點插入的位置，修改指針域的方法要分3種不同情況：①s結(jié)點插入到表中（即不在表頭，也不在表尾）修改指針：

s->next=t; p->next=s;9.6鏈表的概念②s結(jié)點插入到表頭。圖(a)所示為插入前的鏈表，圖(b)所示為插入后的鏈表。修改指針：

s->next=t; head=s;9.6鏈表的概念②s結(jié)點插入到表尾。圖(a)所示為插入前的鏈表，圖(b)所示為插入后的鏈表。修改指針：

p->next=s; s->next=NULL;9.6鏈表的概念例10：修改例9-8的程序，從鍵盤輸入一個要加入的站點名，并將加入后的站點依次輸出。分析：可以在例9-8程序的基礎(chǔ)上增加一個增加節(jié)點的函數(shù)：structstation*add_sta(structstation*h,char*stradd,char*strafter);函數(shù)功能：將stradd所指的站點插入到h鏈表中站點原有的站點strafter的后面。程序：example9_10.c9.7程序范例例11：編寫程序，從鍵盤輸入一個矩形的左下角和右上角的坐標(biāo)，輸出該矩形的中心點坐標(biāo)值，再輸入任意一個點的坐標(biāo)，判斷該點是否在矩形內(nèi)。分析：用xd、yd代表矩形的左下角坐標(biāo)；用xu、yu代表矩形的右上角坐標(biāo)；用xm、ym代表矩形的中點坐標(biāo)；設(shè)計函數(shù)：intptin（structpointp,structrectr），用于判斷輸入的點p是否在矩形r的內(nèi)部。程序：example9_11.c9.7程序范例例12：改進(jìn)例8-25的程序。采用結(jié)構(gòu)，設(shè)計一個洗牌和發(fā)牌的程序，用H代表紅桃，D代表方片，C代表梅花，S代表黑桃，用1～13代表每一種花色的面值。分析：可用結(jié)構(gòu)類型來表示撲克牌的花色和面值：

structcard{ char*face;/*撲克牌的面值*/ char*suit;

/*撲克牌的花色*/ };設(shè)計函數(shù)：voidshuffle（Card*）完成對撲克牌洗牌。程序：example9_12.c9.7程序范例例13：修改例9-12，用位段結(jié)構(gòu)成員表示一副牌，發(fā)牌時顯示每張牌的顏色。分析：因為牌的面值只有13種，牌的花色只有4種，牌的顏色只有2種，因此，可用一個位段結(jié)構(gòu)來表示一副牌：struc