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

1第

九

章結(jié)構(gòu)與其他自定義類型29.1結(jié)構(gòu)類型的認(rèn)識

回顧：

使用數(shù)組的好處是可以用一個變量定義邏輯上相關(guān)的一批數(shù)據(jù)，使每個分量具有相同的名字、不同的下標(biāo)，但有一個限制，即一個數(shù)組變量包含的所有成分元素必須為同一類型，例如：inta[3]。

3學(xué)

號姓

名性

別高考分?jǐn)?shù)生

源010031張三女567北京010032李四女539深圳010033王五男460上?！伎迹?/p>

如果要存儲若干學(xué)生的信息（如下表）使用數(shù)組可以嗎？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;92.結(jié)構(gòu)變量的引用

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

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

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

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();139.3.2結(jié)構(gòu)數(shù)組1.結(jié)構(gòu)數(shù)組的定義

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

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

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ù)組也允許定義時被初始化。【例】structstudent{char*name;longnum;intscore;}p[]={{“Zhangsan”,1001,536},{“Lisi”,1002,494},{“Wangwu”,1003,501}};174.結(jié)構(gòu)數(shù)組應(yīng)用舉例【例】已知若干學(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電視機(jī)1900.00290W3008洗衣機(jī)768.5093pxxpyyy[0]y[1]*px=&x,具體的執(zhí)行過程為：structproductx,y[2],*py=y;21F0103電冰箱2050.00160T0216電視機(jī)1900.00290W3008洗衣機(jī)768.5093pxxpyyy[0]y[1](*px).price-=200;px－>price-=200;(++py)－>stock+=10;1850/*電冰箱降價200元*//*洗衣機(jī)庫存加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é)生的三門單科考試成績，求每一門課程的總平均分。2526運(yùn)行結(jié)果為：29【例2】運(yùn)行結(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)系來體現(xiàn)；

鏈接存儲——將邏輯上相鄰的數(shù)據(jù)分配在物理上離散的存儲單元中，然后在每一個存儲單元中粘貼一張標(biāo)有相鄰者存儲地址的標(biāo)簽，使數(shù)據(jù)之間的邏輯關(guān)系通過地址的鏈接關(guān)系來體現(xiàn)。33

2.鏈表實例

下圖表示存放整數(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ù)調(diào)用失敗，返回空指針NULL。40

函數(shù)功能：在內(nèi)存的動態(tài)存儲區(qū)中分配長度為size字節(jié)的連續(xù)空間n塊，并返回該存儲區(qū)域的首地址。若函數(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)系：

“?！笔浇Y(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é)點進(jìn)棧：p->next=head;head=p;④重復(fù)②、③步驟若干次；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“?！笔芥湵淼奶攸c：先進(jìn)后出47指針后移48運(yùn)行程序：49

2.創(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ù)③、④、⑤步驟若干次，如下所示；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ù)收回它的存儲空間。

（1）被刪結(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）不能對共用體變量以整體形式引用，下面語句均錯：scanf(“%ld%s%d”,&lin);zhang=lin;

共用體變量的所有成員共享一段內(nèi)存，長度為最長成員的字節(jié)數(shù)，使用時要注意以下一些問題：