1、1,程序設(shè)計(jì)基礎(chǔ),諶 衛(wèi) 軍,清華大學(xué)軟件學(xué)院,2006年秋季,第 九 章,2,第 九 章 結(jié)構(gòu)體,3,9.1 結(jié)構(gòu)體的定義和使用,9.1.1 引言,為了實(shí)現(xiàn)學(xué)校的信息化管理，清華大學(xué)決 定構(gòu)造一個(gè)學(xué)生個(gè)人信息的數(shù)據(jù)庫(kù)，該數(shù) 據(jù)庫(kù)包含了每一個(gè)學(xué)生的各種信息，包括 學(xué)號(hào)、姓名、性別、年齡、電話、宿舍等 等。請(qǐng)問(wèn)：如何來(lái)構(gòu)造該數(shù)據(jù)庫(kù)？,4,問(wèn)題分析：,（1）該數(shù)據(jù)庫(kù)涉及到大量的數(shù)據(jù)； （2）數(shù)據(jù)庫(kù)中的數(shù)據(jù)可能是變化的； （3）有些數(shù)據(jù)是密切相關(guān)的，例如：每一 個(gè)學(xué)生都有一組相關(guān)的數(shù)據(jù)（學(xué)號(hào)、 姓名、性別、年齡等）來(lái)描述他。,5,學(xué)號(hào) 姓名 性別 年齡 電話 宿舍,數(shù)組法,6,數(shù)組法的弊端： 只是解

2、決了問(wèn)題1、2，并沒(méi)有很好地解決問(wèn)題3，同一位學(xué)生的所有信息是密切相關(guān)的、在邏輯上應(yīng)該是一個(gè)整體。而現(xiàn)在只能通過(guò)數(shù)組下標(biāo)這種松散的方法來(lái)建立它們之間的聯(lián)系； 必須維護(hù)另外一個(gè)數(shù)據(jù)結(jié)構(gòu)，來(lái)記錄每一位學(xué)生的數(shù)組下標(biāo)號(hào)。因?yàn)樵谠L問(wèn)一個(gè)學(xué)生的信息時(shí)，必須知道相應(yīng)的數(shù)組下標(biāo)號(hào)； 使用起來(lái)很不方便，有些功能難以實(shí)現(xiàn)，如根據(jù)學(xué)生的學(xué)號(hào)、姓名或其他屬性來(lái)進(jìn)行排序。,7,學(xué)生1,學(xué)生2,需要把不同類(lèi)型 的數(shù)據(jù)組織在一 起，而已有方法 無(wú)法解決此問(wèn)題, 必須引入新的類(lèi) 型，即結(jié)構(gòu)體。,8,結(jié)構(gòu)體：由一個(gè)或多個(gè)變量（類(lèi)型可以相 同，也可以不同）所組成的一個(gè)組合項(xiàng)。 該組合項(xiàng)有一個(gè)名字，它內(nèi)部的每個(gè)變量 （稱(chēng)為字段或

3、成員變量）也有相應(yīng)的名字。,student char ID7020449 char name20Zhang char genderM int age19 char phone962771100 char addr30紫荊6-401,9,9.1.2 結(jié)構(gòu)體的定義,在C程序中，有幾種方法來(lái)定義一個(gè)結(jié)構(gòu)體 （struct），通常的步驟是： 定義一個(gè)新的結(jié)構(gòu)體類(lèi)型，并指明它內(nèi)部的各個(gè)成員變量； 使用該類(lèi)型來(lái)定義相應(yīng)的結(jié)構(gòu)體變量。 結(jié)構(gòu)體類(lèi)型的定義只在程序的開(kāi)頭出現(xiàn)一 次，而結(jié)構(gòu)體變量的聲明可以根據(jù)需要在 程序中出現(xiàn)多次。,10,定義一個(gè)結(jié)構(gòu)體類(lèi)型,struct 類(lèi)型名1 成員變量1； 類(lèi)型名n 成員變

4、量n； ;,一般形式之一：,11,typedef struct 類(lèi)型名1 成員變量1； 類(lèi)型名n 成員變量n； ;,一般形式之二：,12,定義結(jié)構(gòu)體變量,struct 變量1, 變量2, ;,一般形式之一：, 變量1, 變量2, ;,一般形式之二：,13,struct student_tag char ID7; char name20; char gender; int age; char phone9; char addr30; ;,typedef struct char ID7; char name20; char gender; int age; char phone9; char ad

5、dr30; student_T;,定義一個(gè)結(jié)構(gòu)體類(lèi)型，此時(shí)并沒(méi)有定義（創(chuàng)建） 任何結(jié)構(gòu)體變量，因此沒(méi)有分配任何內(nèi)存空間。,14,struct student_tag x; 或者： student_T x;,ID,name,gender,age,phone,addr,x,定義結(jié)構(gòu)體變量 x 后， 為它分配相應(yīng)的內(nèi)存 空間。,sizeof(x) = ?,72,15,struct student_tag char ID7; char name20; char gender; int age; char phone9; char addr30; x, y;,在定義結(jié)構(gòu)體類(lèi)型的同時(shí)，去定義它的變量。,1

6、6,9.1.3 結(jié)構(gòu)體變量的使用,對(duì)一個(gè)結(jié)構(gòu)體變量的最基本的操作就是去 訪問(wèn)它的各個(gè)成員變量。訪問(wèn)的方式為： 結(jié)構(gòu)體變量名.成員變量名 一個(gè)成員變量就是一個(gè)普通的變量，可以 對(duì)它進(jìn)行各種通常的變量操作。,17,student_T x;,ID,name,gender,age,phone,addr,x,strcpy(x.ID, “020449”);,020449,strcpy(, “Zhang”);,Zhang,scanf(“%c”, ,M,x.age = 19;,19,strcpy(x.phone, str);,62771100,scanf(“%s”, x.addr);,紫荊6-40

7、1,18,Cant And Can,不能做什么？ 不能直接比較兩個(gè)結(jié)構(gòu)體變量(=、!=)，student_T x, y；(x = y)；(x != y)； 不能用scanf/printf來(lái)輸入或輸出整個(gè)結(jié)構(gòu)體變量。,19,Cant And Can,能做什么？ 能夠進(jìn)行結(jié)構(gòu)體變量的整體賦值，如：student_T x, y； y = x； 能夠定義一個(gè)返回值類(lèi)型為結(jié)構(gòu)體類(lèi)型的函數(shù)，把被調(diào)用函數(shù)當(dāng)中的某個(gè)結(jié)構(gòu)體變量的值返回給主調(diào)函數(shù)。,20,student_T x, y; y = x; 等價(jià)于,ID,name,gender,age,phone,addr,x,strcpy(y.ID, x.ID);

8、strcpy(, ); y.gender = x.gender; y.age = x.age; strcpy(y.phone, x.phone); strcpy(y.addr, x.addr);,020449,Zhang,M,19,62771100,紫荊6-401,21,9.1.4 結(jié)構(gòu)體變量的初始化,對(duì)于一個(gè)結(jié)構(gòu)體變量，也可以在定義的時(shí) 候，指定它的初始值，即把它的各個(gè)成員 變量的初始值依次列出來(lái)。,student_T x = 020449, Zhang, M, 19, 62771100, 紫荊6-401 ;,22,9.2 結(jié)構(gòu)體數(shù)組與指針,9.2.1 結(jié)構(gòu)體數(shù)組,如

9、何來(lái)構(gòu)造學(xué)生個(gè)人信息數(shù)據(jù)庫(kù)？ 為每位學(xué)生單獨(dú)定義一個(gè)結(jié)構(gòu)體變量？No 可以采用結(jié)構(gòu)體數(shù)組的方法，用每一個(gè)數(shù) 組元素來(lái)描述一位學(xué)生的信息。,23,student_T stu1000; 或者是： struct student_tag stu1000;,stu,stu0,stu1,24,#define MAX_NAME 8 #define MAX_STUDENTS 50 typedef struct char nameMAX_NAME + 1; int id; double score; StudentRecord_T; StudentRecord_T aMAX_STUDENTS;,下列這些變量的類(lèi)

10、型是什么？ aa0 a4.id, px = ,name,id,score,x,px,26,name,id,score,x *px,px,如何來(lái)訪問(wèn)x的成員變量？ x.成員變量名，如：, x.id； (*px).成員變量名，如：(*px).name, (*px).id； px-成員變量名，“-”稱(chēng)為指向運(yùn)算符或箭頭運(yùn)算符，如：px-name, px-id。,27,StudentRecord_T a10; StudentRecord_T *px; px = a;,a,a0,a1,px 指向 a0； px + 1指向 a1； px + i 指向 ai;,28,9.3 結(jié)構(gòu)

11、體作為函數(shù)參數(shù),在使用結(jié)構(gòu)體來(lái)作為函數(shù)的參數(shù)時(shí)，它的 用法與整型、字符類(lèi)型、實(shí)數(shù)類(lèi)型等其他 的、除數(shù)組以外的數(shù)據(jù)類(lèi)型是完全一樣的。 也就是說(shuō)，既可以用結(jié)構(gòu)體變量來(lái)作為函 數(shù)參數(shù)，實(shí)現(xiàn)單向的值傳遞；也可以用指 向結(jié)構(gòu)體變量的指針來(lái)作為函數(shù)參數(shù)， 實(shí)現(xiàn)地址的傳遞。,29,問(wèn)題描述：,已知一條直線的2個(gè)端點(diǎn)坐標(biāo)，計(jì)算該直線的 中點(diǎn)的坐標(biāo)。,/* 用一個(gè)結(jié)構(gòu)體來(lái)描述一個(gè)點(diǎn) */ typedef struct double x, y; point_T;,30,point_T midpoint(point_T pt1, point_T pt2); void main( ) point_T a = 0.0,

12、 0.0, b = 5.0, 10.0, m; m = midpoint(a, b); point_T midpoint(point_T pt1, point_T pt2) point_T mid; mid.x = (pt1.x + pt2.x) / 2.0; mid.y = (pt1.y + pt2.y) / 2.0; return(mid); ,31,point_T midpoint(point_T pt1, point_T pt2); void main( ) point_T a = 0.0, 0.0, b = 5.0, 10.0, m; m = midpoint(a, b); poin

13、t_T midpoint(point_T pt1, point_T pt2) point_T mid; mid.x = (pt1.x + pt2.x) / 2.0; mid.y = (pt1.y + pt2.y) / 2.0; return(mid); ,main,a,b,m,midpoint,pt1,pt2,mid,2.5 5.0,0.0 0.0,5.0 10.0,2.5 5.0,在主函數(shù)和 midpoint函數(shù) 中各定義了三 個(gè)結(jié)構(gòu)體變量, 需要較多數(shù)據(jù) 傳遞。,x y,x y,32,void main( ) point_T a = 0.0, 0.0, b = 5.0, 10.0, m;

14、set_midpoint( ,指針作為函數(shù)參數(shù),33,void main( ) point_T a = 0.0, 0.0, b = 5.0, 10.0, m; set_midpoint( ,main,a,b,m,set_midpoint,pt1,pt2,mid,2.5 5.0,x y,34,9.4 鏈表,9.4.1 鏈表的基本概念,例：在鐵路的中轉(zhuǎn)站，有10個(gè)集裝箱待運(yùn)。每 個(gè)集裝箱上有如下五項(xiàng)說(shuō)明： 箱號(hào)（比如 AZ81920） 貨物名稱(chēng)（比如 蘋(píng)果） 重量（比如 10噸） 發(fā)貨地點(diǎn)（比如 山東） 到貨地點(diǎn)（比如 廣東）,35,36,如何在程序中來(lái)描述該列火車(chē)？ 如何來(lái)描述火車(chē)頭？ 如何來(lái)描

15、述每一個(gè)集裝箱？ 如何來(lái)描述各節(jié)車(chē)廂之間的鏈接關(guān)系？,37,head,結(jié)點(diǎn)2,需要引入一種新的數(shù)據(jù)結(jié)構(gòu)：鏈表。鏈表中的 每一個(gè)元素稱(chēng)為一個(gè)“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)該 包括兩部分：一為用戶需要使用的實(shí)際數(shù)據(jù)； 二為下一個(gè)結(jié)點(diǎn)的起始地址。另外，鏈表還有 一個(gè)頭指針head，指向鏈表的首結(jié)點(diǎn)。,結(jié)點(diǎn)1,結(jié)點(diǎn)3,38,如何來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu)？顯然要用到結(jié)構(gòu)體數(shù)據(jù) 類(lèi)型。定義如下的結(jié)構(gòu)體類(lèi)型：,struct Train_tag,struct Train_tag *next;,char Num8; char Name10; int Weight; char From20; char To20;,數(shù)據(jù)域,指針域,

16、39,9.4.2 對(duì)鏈表的操作,1. 創(chuàng)建靜態(tài)鏈表,在程序中定義一組結(jié)構(gòu)體變量或一個(gè)結(jié)構(gòu)體 數(shù)組，然后用它們來(lái)作為鏈表的結(jié)點(diǎn)，把它 們鏈接成一個(gè)鏈表的形式。 優(yōu)點(diǎn)：不必去關(guān)心內(nèi)存的分配與釋放。 缺點(diǎn)：需要事先知道鏈表結(jié)點(diǎn)的個(gè)數(shù)。,40,head,結(jié)點(diǎn)2,結(jié)點(diǎn)1,結(jié)點(diǎn)10,struct Train_tag charNum8;/* 集裝箱編號(hào) */ charName10;/* 貨物名稱(chēng) */ intWeight;/* 貨物重量 */ charFrom20;/* 發(fā)貨地點(diǎn) */ charTo20;/* 到貨地點(diǎn) */ struct Train_tag *next;/* 指向下一結(jié)點(diǎn) */ array

17、10, *head;,41,思路：用第i(0-9)個(gè)數(shù)組元素來(lái)描述第 i + 1個(gè)鏈表結(jié)點(diǎn),head,結(jié)點(diǎn)2,結(jié)點(diǎn)1,結(jié)點(diǎn)10,array0,array1,array9,思考 2 分鐘,42,void Create( ) int i; head = ,43,2. 創(chuàng)建動(dòng)態(tài)鏈表,在程序當(dāng)中為鏈表的每一個(gè)結(jié)點(diǎn)動(dòng)態(tài)地分配 相應(yīng)的存儲(chǔ)空間，并把它們鏈接成一個(gè)鏈表 的形式。 優(yōu)點(diǎn)：按需分配，鏈表的長(zhǎng)度可動(dòng)態(tài)增長(zhǎng)。 缺點(diǎn)：由程序員來(lái)進(jìn)行內(nèi)存的分配與釋放。,44,【例】 創(chuàng)建一個(gè)鏈表，并輸入每一個(gè)結(jié)點(diǎn)的各種描 述信息（集裝箱編號(hào)、貨物名稱(chēng)、貨物 重量、發(fā)貨地點(diǎn)、到貨地點(diǎn)等），直到用戶 輸入的貨物重量等于0，

18、表示鏈表結(jié)束。,45,struct Train_tag charNum8;/* 集裝箱編號(hào) */ charName10;/* 貨物名稱(chēng) */ intWeight;/* 貨物重量 */ charFrom20;/* 發(fā)貨地點(diǎn) */ charTo20;/* 到貨地點(diǎn) */ struct Train_tag *next;/* 指向下一結(jié)點(diǎn) */ ; struct Train_tag *head, *p, *q;,46, 只要用戶輸入的 Weight 不為 0，就要構(gòu)建鏈表?；舅悸肥菍⒁粋€(gè)一個(gè)的結(jié)點(diǎn)添加至鏈表中。首先用指針 p 來(lái)申請(qǐng)一個(gè)結(jié)構(gòu)體變量的內(nèi)存空間，并且裝入用戶輸入的各種描述信息，然后將指針

19、 q 和 head都指向它。如下圖：,創(chuàng)建鏈表的過(guò)程可歸納為如下三個(gè)步驟,DX11089 玩具 5噸 從上海 到深圳,圖 鏈表的第一個(gè)結(jié)點(diǎn)建成,p,q,head和結(jié)點(diǎn)分別存放在哪？,47, 后繼結(jié)點(diǎn)的創(chuàng)建：如果用戶輸入的Weight又不為 0，就要構(gòu)建鏈表的第二個(gè)結(jié)點(diǎn)。首先用指針 p 來(lái)申請(qǐng)一個(gè)結(jié)構(gòu)體變量的內(nèi)存空間，并且裝入用戶輸入的各種描述信息，然后把第一個(gè)結(jié)點(diǎn)的next指針去指向它，從而建立兩個(gè)結(jié)點(diǎn)之間的鏈接關(guān)系。最后再把 q 指向新的結(jié)點(diǎn)。如下圖：,DX11089 玩具 5噸 從上海 到深圳,圖 鏈表的第二個(gè)結(jié)點(diǎn)建成,CY20011 電飯鍋 8噸 從上海 到湖南,如何實(shí)現(xiàn)這種鏈接關(guān)系？,

20、48,DX11089 玩具 5噸 從上海 到深圳,第三個(gè)結(jié)點(diǎn)加入鏈表的過(guò)程：,CY20011 電飯鍋 8噸 從上海 到湖南,CZ21026 蘋(píng)果 8噸 從山東 到福建,49, 鏈表創(chuàng)建過(guò)程的結(jié)束：如果用戶輸入的Weight等于 0，意味著鏈表創(chuàng)建過(guò)程的結(jié)束，此時(shí)指針 q 所指向的就是鏈表的最后一個(gè)結(jié)點(diǎn)，所以要把該結(jié)點(diǎn)的next指針賦值為NULL，表示這里已是鏈尾，后面不會(huì)再連結(jié)點(diǎn)。如下圖：,DX11089 玩具 5噸 從上海 到深圳,CY20011 電飯鍋 8噸 從上海 到湖南,AZ81920 花生 10噸 從山東 到廣東,50,void Create( ) int Weight; head

21、= p = q = NULL; while( 1 ) printf(輸入貨物重量：); scanf(%d, ,51,3. 訪問(wèn)鏈表,在創(chuàng)建好一個(gè)鏈表之后，可以依次地訪問(wèn)該 鏈表當(dāng)中的各個(gè)結(jié)點(diǎn)的數(shù)據(jù)。, struct Train_tag *p; p = head; while(p != NULL) printf(%s, %s, %d, %s, %sn, p-Num, p-Name, p-Weight, p-From, p-To); p = p-next; ,void Display( struct Train_tag *head),52,4. 刪除鏈表結(jié)點(diǎn),假設(shè)列車(chē)現(xiàn)在到達(dá)長(zhǎng)沙站，因此需要把到貨

22、 地點(diǎn)為湖南的車(chē)廂（假設(shè)有且僅有一節(jié)）， 從列車(chē)上摘下來(lái)，然后列車(chē)?yán)^續(xù)向南行駛。 這里就需要用到鏈表結(jié)點(diǎn)的刪除技術(shù)。,53,DX11089 玩具 5噸 從上海 到湖南,CY20011 電飯鍋 8噸 從上海 到深圳,AZ81920 花生 10噸 從山東 到廣東,情形一、待刪除的是首結(jié)點(diǎn),p = head; head = p-next; free(p);,54,DX11089 玩具 5噸 從上海 到深圳,CY20011 電飯鍋 8噸 從上海 到湖南,AZ81920 花生 10噸 從山東 到廣東,情形二、待刪除的不是首結(jié)點(diǎn),q-next = p-next;free(p);,55,DX11089 玩具

23、 5噸 從上海 到深圳,CY20011 電飯鍋 8噸 從上海 到湖南,AZ81920 花生 10噸 從山東 到廣東,如何找到目的地為湖南的結(jié)點(diǎn)？,56,void Delete( struct Train_tag *head) struct Train_tag *p, *q; if(head = NULL) printf(空鏈表); return; p = head; while(p != NULL) / 刪除的是中間結(jié)點(diǎn) ,若刪除的是尾結(jié)點(diǎn)呢？,57,5. 插入鏈表結(jié)點(diǎn),原則： 插入操作不應(yīng)破壞原有鏈接關(guān)系； 需要插入的這個(gè)結(jié)點(diǎn)應(yīng)該把它放在合適的位置上，也就是說(shuō)，應(yīng)該有一個(gè)插入位置的查找過(guò)程。

24、,58,head,先看下面一個(gè)簡(jiǎn)單的例子： 已有一個(gè)如圖所示的鏈表。它是按結(jié)點(diǎn)中的貨物重量從小到大排序的?，F(xiàn)在要插入一個(gè)新的結(jié)點(diǎn)，該結(jié)點(diǎn)的貨物重量為7噸。,59,定義： struct Train_tag *head; / 頭指針 struct Train_tag *p; / 鏈表當(dāng)前結(jié)點(diǎn) struct Train_tag *q; / 鏈表上一結(jié)點(diǎn) struct Train_tag *pNode; / 待插入的結(jié)點(diǎn),60,DX11089 玩具 5噸 從上海 到湖南,head = pNode;,第一種情況：鏈表為空，即 head = NULL 待插入的 pNode 結(jié)點(diǎn)就是鏈表中的第一個(gè)結(jié)點(diǎn)。,6

25、1,第二種情況： pNode 結(jié)點(diǎn)的 Weight 值小于等于鏈表首結(jié)點(diǎn)的 Weight 值，即 pNode-Weight Weight 這時(shí)要將 pNode 結(jié)點(diǎn)插入到首結(jié)點(diǎn)的前面：,62,執(zhí)行的語(yǔ)句：,pNode-next = head; head = pNode;,63,第三種情況： 即pNode結(jié)點(diǎn)的 Weight 要大于首結(jié)點(diǎn)的 Weight 值，這時(shí)肯定地說(shuō) pNode 結(jié)點(diǎn)要插入到首結(jié)點(diǎn)之 后，但究竟插入到哪里需要先找到正確的位置。 我們?cè)O(shè)指針q和指針p分別指向相鄰的兩個(gè)結(jié)點(diǎn)， q 在前 p 在后（即q更靠近首結(jié)點(diǎn)）。 首先讓q = head，讓 p = head-next，然后

26、讓它們 順序往后移動(dòng)，每次移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)著滿足： q-Weight Weight Weight 時(shí)，pNode 就插在 q 與 p 之間。,64,q = p; p = p-next;,pNode-next = p; q-next = pNode;,移動(dòng)指針：,插入結(jié)點(diǎn)：,65,void Insert(struct Train_tag *head, struct Train_tag *pNode) struct Train_tag *p, *q; / 第一種情形，鏈表為空 if(head = NULL) head = pNode; return; / 第二種情形，新結(jié)點(diǎn)的Weight小于等于首

27、結(jié)點(diǎn) if(pNode-Weight Weight) pNode-next = head; head = pNode; return; ,66,/ 第三種情形，循環(huán)地查找正確的插入位置 q = head; p = head-next; while(p != NULL) if(pNode-Weight Weight) break; else q = p; p = p-next; / 將pNode結(jié)點(diǎn)插入在正確的位置(q和p之間) pNode-next = p; q-next = pNode; ,67,while(p != NULL) if(pNode-Weight Weight) break; else q = p; p = p-next; ,如果新結(jié)點(diǎn)的Weight大于所有結(jié)點(diǎn)？,在這種情形下，當(dāng)循環(huán)語(yǔ)句結(jié)束后，指針q是 指向鏈表的尾結(jié)點(diǎn)，而指針 p = NULL。,68,插入結(jié)點(diǎn)： pNode-next = p; q-next = pNode;,p,NULL,NULL,69,6. 鏈表的釋放,對(duì)于靜態(tài)鏈表，它們所占用的內(nèi)存空間是由系統(tǒng)自動(dòng)來(lái)分配和釋放的； 對(duì)于動(dòng)態(tài)鏈表，必須由程序員自己來(lái)進(jìn)行內(nèi)存的分配與釋放。,70,void Destroy( struct Train_tag *head) struct Train_tag *p, *q; p = h