補充資料結(jié)構(gòu)與自定義類型

1第

九

章結(jié)構(gòu)與其他自定義類型29.1結(jié)構(gòu)類型的認識回憶：使用數(shù)組的好處是可以用一個變量定義邏輯上相關(guān)的一批數(shù)據(jù)，使每個分量具有相同的名字、不同的下標(biāo)，但有一個限制，即一個數(shù)組變量包含的所有成分元素必須為同一類型，例如：inta[3]。3學(xué)

號姓

名性

別高考分數(shù)生

源010031張三女567北京010032李四女539深圳010033王五男460上海……………思考：如果要存儲假設(shè)干學(xué)生的信息〔如下表〕使用數(shù)組可以嗎？4

定義結(jié)構(gòu)類型student：structstudent{longnum;

/*學(xué)號*/

charname[6];

/*姓名*/charsex;

/*性別*/intscore;/*高考分數(shù)*/char*place;

/*生源*/};

59.2結(jié)構(gòu)類型的定義

形式：struct

結(jié)構(gòu)名{成員表列；};structdate{intyear,month,day;};【例】定義代表日期信息、藥品信息的結(jié)構(gòu)類型。structdate{intyear;intmonth;intday;};6

structmedicine{char*code;char*name;floatprice;char*place;structdatevalidity;};codenamepriceplacevalidityyearmonthday結(jié)構(gòu)類型medicine：79.3結(jié)構(gòu)變量

9.3.1結(jié)構(gòu)變量1.結(jié)構(gòu)變量的定義structstudent{longnum;charname[6];charsex;intscore;charplace[12];};〔1〕先定義結(jié)構(gòu)類型，再引用該類型定義的變量structstudentxia,ding,li;8〔2〕定義結(jié)構(gòu)類型的同時說明變量structstudent{longnum;charname[6];charsex;intscore;charplace[12];}xia,ding,li;92.結(jié)構(gòu)變量的引用

結(jié)構(gòu)變量通常都以成員的形式加以引用，結(jié)構(gòu)變量成員的標(biāo)記形式為：成員運算符【例】設(shè)有如下說明：

structdate{intyear,month,day;};結(jié)構(gòu)變量名.成員名10

以下語句序列是對藥品結(jié)構(gòu)變量drug1、drug2進行賦值、輸入和輸出運算：

structmedicine{char*code;char*name;floatprice;char*place;structdatevalidity;}drug1,drug2;11=“penicillin〞;drug1.price=6.38;=“vitamineC〞;if(drug2.code＝＝“99103x〞)drug2.price=drug2.price-7.5;scanf(“%d%d%d〞,&drug1.validity.year,&drug1.validity.month,&drug1.validity.day);puts();puts();123.結(jié)構(gòu)變量的初始化【例】結(jié)構(gòu)變量在定義時被賦初值。structmedicine

{char*code;char*name;floatprice;char*place;

structdate

validity;};structmedicinedrug1,drug2={“01-56p〞,“vitamineC〞,22.65,“Shanghai〞,{2002,12,31}};139.3.2結(jié)構(gòu)數(shù)組1.結(jié)構(gòu)數(shù)組的定義

形式：結(jié)構(gòu)類型

數(shù)組名[常量表達式]

structdate

{intyear,month,day;};

structmedicine

{char*code;char*name;floatprice;char*place;structdatevalidity;};structmedicinedrug[10];142.結(jié)構(gòu)數(shù)組的引用

結(jié)構(gòu)數(shù)組是以下標(biāo)變量的成員名形式加以引用的。其標(biāo)記形式為：for(i=0;i<N;i++){gets(&p[i].name);scanf(“%ld%d〞,&p[i].num,&p[i].score);}結(jié)構(gòu)數(shù)組名[下標(biāo)].成員名【例】#defineN100structstudent{char*name;longnum;intscore;}p[N];對數(shù)組p[N]賦初值的語句如下：153.結(jié)構(gòu)數(shù)組的初始化

與結(jié)構(gòu)變量一樣，結(jié)構(gòu)數(shù)組也允許定義時被初始化?！纠縮tructstudent{char*name;longnum;intscore;}p[]={{“Zhangsan〞,1001,536},{“Lisi〞,1002,494},{“Wangwu〞,1003,501}};16經(jīng)過初始化以后，p數(shù)組的存儲結(jié)構(gòu)和內(nèi)容如以下圖所示：Zhangsan1001536Lisi1002494Wangwu1003501p[0]p[1]p[2]174.結(jié)構(gòu)數(shù)組應(yīng)用舉例【例】假設(shè)干學(xué)生的姓名、學(xué)號和某單科考試成績，試編寫程序，對學(xué)生記錄按考試成績從高分至低分排序，程序輸出排序以后的學(xué)生表，并報告姓名為××〔由鍵盤隨即輸入〕的同學(xué)的名次號。具體源程序代碼見書P157，例9.5。189.3.3結(jié)構(gòu)指針定義一個指針，使其指向結(jié)構(gòu)變量，這樣的指針稱為“結(jié)構(gòu)指針〞。1.結(jié)構(gòu)指針的定義

形式：

結(jié)構(gòu)類型*指針名【例】structproduct{charcode[5];charname[20];floatprice;intstock;};structproductx,y[2],*px=&x,*py=y;19F0103電冰箱2050.00160T0216電視機1900.00290W3008洗衣機768.5093pxxpyyy[0]y[1]*px=&x,具體的執(zhí)行過程為：structproductx,y[2],*py=y;20形式：指針名->成員名或〔*指針名〕.成員名【例】以上圖為例，那么以下語句都是通過結(jié)構(gòu)指針引用結(jié)構(gòu)變量的成員。2.通過結(jié)構(gòu)指針引用結(jié)構(gòu)變量21F0103電冰箱2050.00160T0216電視機1900.00290W3008洗衣機768.5093pxxpyyy[0]y[1](*px).price-=200;px－>price-=200;(++py)－>stock+=10;1850/*電冰箱降價200元*//*洗衣機庫存加10*/10322結(jié)構(gòu)指針作為函數(shù)的參數(shù)使得結(jié)構(gòu)變量也能像普通變量一樣實現(xiàn)“傳地址〞調(diào)用。調(diào)用發(fā)生時，實參傳遞給形參的是自身結(jié)構(gòu)的存儲地址，使形式參數(shù)直接指向了實在實參，形參不再另占內(nèi)存單元，從而使函數(shù)體中對形式參數(shù)所作的改變就是對實在參數(shù)所作。3.結(jié)構(gòu)指針作為函數(shù)的參數(shù)23【例】10名學(xué)生的三門單科考試成績，求每一門課程的總平均分。242526運行結(jié)果為：27習(xí)題集28【例1】運行結(jié)果為：29【例2】運行結(jié)果為：30【例3】31【例4】見實驗教程P66-程序改錯?！纠?】見實驗教程P66-程序填空?！纠?】見實驗教程P59-程序填空。329.4動態(tài)數(shù)據(jù)結(jié)構(gòu)“鏈表〞常用的動態(tài)數(shù)據(jù)結(jié)構(gòu)(特點：需之那么有，不需那么無)有鏈表、樹、圖等等。9.4.1鏈表概述1.什么是鏈表順序存儲——將邏輯上相鄰的數(shù)據(jù)分配在物理上相鄰的存儲單元中，數(shù)據(jù)之間的邏輯關(guān)系通過存儲單元的鄰接關(guān)系來表達；鏈接存儲——將邏輯上相鄰的數(shù)據(jù)分配在物理上離散的存儲單元中，然后在每一個存儲單元中粘貼一張標(biāo)有相鄰者存儲地址的標(biāo)簽，使數(shù)據(jù)之間的邏輯關(guān)系通過地址的鏈接關(guān)系來表達。332.鏈表實例以下圖表示存放整數(shù)11，13，17，19的鏈表：head1079115312861390頭結(jié)點末結(jié)點頭指針數(shù)據(jù)域指針域1079115312861390NUL4.2單鏈表結(jié)點的類型定義111153數(shù)據(jù)域：存儲數(shù)據(jù)指針域：存儲后續(xù)結(jié)點的地址35

單鏈表結(jié)點的類型定義：

struct

結(jié)構(gòu)名

{數(shù)據(jù)成員表列；

struct

結(jié)構(gòu)名

*指針名；};head1079115312861390107911115313128617139019NULL36【例】定義素數(shù)鏈表的結(jié)點類型structprime。素數(shù)鏈表：head11131719NULL

要求素數(shù)鏈表結(jié)點只包含一個數(shù)據(jù)成員，因此結(jié)點類型可定義為：struct

prime

{intdata；struct

prime

*next;};37【例】定義學(xué)生鏈表的結(jié)點類型structstudent。假設(shè)一個學(xué)生記錄包括學(xué)號、姓名、性別和高考成績，那么學(xué)生鏈表的結(jié)點類型可定義為：structstudent{longnum;char*name;charsex;intscore;structstudent*next;};structstudent*p,*q;38structstudent{longnum;char*name;charsex;intscore;structstudent*next;};010201倪桂蘭女568structstudent*p,*q;p->num=010201;p->name=“倪桂蘭〞；p->sex=‘女’;p->score=568;010202劉寧寧女544pq->num=010202;q->name=“劉寧寧〞；q->sex=‘女’;q->score=544;qp->next=q;399.4.3動態(tài)存儲分配函數(shù)2.calloc函數(shù)

函數(shù)原型：void*calloc(unsignedn,unsignedsize)1.malloc函數(shù)函數(shù)原型：void*malloc(unsignedsize)函數(shù)功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一塊長度為size字節(jié)的連續(xù)空間，并返回該存儲區(qū)域的首地址；假設(shè)函數(shù)調(diào)用失敗，返回空指針NULL。40函數(shù)功能：在內(nèi)存的動態(tài)存儲區(qū)中分配長度為size字節(jié)的連續(xù)空間n塊，并返回該存儲區(qū)域的首地址。假設(shè)函數(shù)調(diào)用失敗，就返回空指針NULL。3.free函數(shù)

函數(shù)原型：voidfree(void*p)

函數(shù)功能：釋放當(dāng)前正被指針p所指向的內(nèi)存區(qū)域，將它歸還給系統(tǒng)以作它用。419.4.4創(chuàng)立鏈表創(chuàng)立鏈表從空表開始，循環(huán)地將新結(jié)點逐一產(chǎn)生出來，并按預(yù)定的鏈接關(guān)系插入到鏈表中去的過程。010201倪桂蘭女568010202劉寧寧女544010230潘俊男626NULLhead…42結(jié)點插入通常有兩種預(yù)定關(guān)系：“棧〞式結(jié)構(gòu)——新結(jié)點總是從表首插入，使得最先插入到鏈表中去的結(jié)點被擠壓到鏈尾，成為末結(jié)點，而最后插入的結(jié)點成為鏈表的頭結(jié)點；“隊列〞式結(jié)構(gòu)——新結(jié)點總是從表尾插入；1〕創(chuàng)立“棧〞式鏈表43p

3設(shè)head為鏈表頭指針，p為創(chuàng)立動態(tài)結(jié)點的工作指針，那么：①建空表：head＝NULL；②創(chuàng)立新結(jié)點，p=(結(jié)點類型*)malloc(結(jié)點長度)并對結(jié)點的數(shù)據(jù)域賦值：③新結(jié)點進棧：p->next=head;head=p;④重復(fù)②、③步驟假設(shè)干次；head

NULLheadp

3NULLheadp

3NULLhead^44【例】用上述步驟往鏈表中插入兩個結(jié)點：head^p

3headp

3NULL①②③③‘②‘

3NULLheadp

5

5

3NULLheadp45【例】編寫程序，建立一個存儲字符及其ASCII碼的鏈表，規(guī)定ASCII碼的范圍為[m，n]〔32<m<n<126〕,程序最后輸出鏈表中全部結(jié)點的內(nèi)容。字符的ASCII碼字符46“棧〞式鏈表的特點：先進后出47指針后移48運行程序：492.創(chuàng)立“隊列〞式鏈表

隊列式鏈表結(jié)點插入位置在鏈尾，頭指針一旦指向了首結(jié)點后，就不會再動，而新結(jié)點插入鏈表時必須與末結(jié)點拉鏈，這就需要增加一個跟蹤末結(jié)點的指針last。現(xiàn)在假設(shè)head為頭指針，p為創(chuàng)立新結(jié)點的工作指針，last為跟蹤末結(jié)點的指針。創(chuàng)立隊列式鏈表的算法步驟：50②對末結(jié)點指針last初始化：last＝head；head

3

headlast

3p

5①創(chuàng)立首結(jié)點，并對數(shù)據(jù)域賦值：head＝〔結(jié)點類型*〕malloc〔結(jié)點長度〕；③開辟后續(xù)新結(jié)點：p=(結(jié)點類型*)malloc(結(jié)點長度)；51④新結(jié)點插入表尾：last->next=p；

3

headlast

5p

3head

5plast⑤last指針后移至末結(jié)點：last＝last->next；52⑥重復(fù)③、④、⑤步驟假設(shè)干次，如下所示；p

7③’

開辟后續(xù)新結(jié)點：p=(結(jié)點類型*)malloc(結(jié)點長度)；④’

新結(jié)點插入表尾：last->next=p；

3head

5plastp753⑦終止鏈表的延伸：last->next＝NULL；⑤last指針后移至末結(jié)點：last＝last->next；

3head

5lastp7lasthead357NUlllast549.4.5結(jié)點的刪除與插入1.刪除結(jié)點

刪除結(jié)點——解除該結(jié)點的鏈接關(guān)系，使之與鏈表脫鉤，再調(diào)用free函數(shù)收回它的存儲空間?！?〕被刪結(jié)點p為鏈表首結(jié)點p=head;/*使p指針指向首結(jié)點*/head=head->next;/*頭指針后移一個結(jié)點*/free(p);/*收回首結(jié)點的存儲空間*/55刪除學(xué)生鏈表的首結(jié)點1001倪蘭女5681002王

田女5371003劉寧女5441004應(yīng)

浩男4991005潘

俊男626NULLheadp＝headhead＝head－>next×free(p)56〔2〕被刪結(jié)點為鏈表的中間結(jié)點或末結(jié)點1113171997NULLheadprep

pre－>next=p－>next;

借助兩個工作指針p和pre，尋找被刪結(jié)點的過程如下：p指針從頭至尾對鏈表的結(jié)點逐一掃描，而pre指針總是跟蹤p當(dāng)前所指結(jié)點的前驅(qū)結(jié)點，與p指針保持同步移動，p指針一旦找到了被刪結(jié)點，執(zhí)行下面的語句即可實現(xiàn)刪除：free(p);57【例】結(jié)點刪除的例子見書P171頁?！纠縿?chuàng)立偶數(shù)〔2～10之間〕鏈表，并刪除指定偶數(shù)，要求輸出創(chuàng)立的鏈表以及刪除后的結(jié)果。58

2.結(jié)點的插入+>=?&NULLheadp…insert*【例】將以下圖中的insert指針指向的結(jié)點插入到頭指針為head的鏈表中，且指針p已經(jīng)指向插入點。59〔1〕在結(jié)點之后插入+>=?&NULLheadp…insert*p－>next=insert;insert－>next=p－>next;思考：上述兩個拉鏈語句的次序能顛倒嗎？60〔2〕在結(jié)點之前插入+>=?&NULLhead…insert*insert－>next=p;preppre－>next=insert;思考：上述兩個拉鏈語句的次序能顛倒嗎？【例】結(jié)點插入的例子見書P173頁例9.11。619.5共用體類型

共用體——同一塊內(nèi)存區(qū)域在不同時刻存儲不同類型的數(shù)據(jù)，是一種內(nèi)存覆蓋技術(shù)。共用體能使多個類型不同的變量共享一塊內(nèi)存區(qū)域，這些變量在不同的時間去占用這一片內(nèi)存。9.5.1共用體類型的定義

形式：

union共用體名{成員表列};關(guān)鍵字，代表共用體類型有時也會省略62

【例】unionstudent{longnum;charname[10];intscore;}zhang,lin;這種類型使長度為10個字節(jié)的內(nèi)存區(qū)域〔最長成員所占的字節(jié)數(shù)〕既能存儲long型數(shù)據(jù)，又能存儲字符串和int型數(shù)據(jù)，并在定義類型的同時也定義了兩個unionstudent類型的變量zhang和lin?！舅伎碱}】zhang和lin所占據(jù)的存儲字節(jié)均為多少？如果將上述類型改為structstudent，那么變量zhang和lin又占據(jù)多少字節(jié)？639.5.2共用體變量的引用

形式：

共用體變量名.成員名【例】=“wangfen〞;lin.score=83;

【例】unionstudent{longnum;charname[10];intscore;}zhang,lin;64〔1〕任何時刻，只有一個成員的值被存儲：lin.num=990011;lin.score=83;〔2〕共用體變量和各成員具有相同的存儲地址，即&zhang與&zhang.num、&、&zhang.score為同一個地址值；〔3〕不能對共用體變量以