第9章 結(jié)構(gòu)體與鏈表

1、第九章第九章 結(jié)構(gòu)體、鏈表結(jié)構(gòu)體、鏈表 9.1 結(jié)構(gòu)體結(jié)構(gòu)體類型與結(jié)構(gòu)體變量類型與結(jié)構(gòu)體變量 9.2 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組 9.3 結(jié)構(gòu)體的指針結(jié)構(gòu)體的指針 9.4 向函數(shù)傳遞結(jié)構(gòu)體型數(shù)據(jù)向函數(shù)傳遞結(jié)構(gòu)體型數(shù)據(jù) 9.5 鏈鏈表表 9.1 結(jié)結(jié) 構(gòu)構(gòu) 體類型與結(jié)構(gòu)體變量體類型與結(jié)構(gòu)體變量 9.1.1 結(jié)構(gòu)體類型結(jié)構(gòu)體類型 一種構(gòu)造類型數(shù)據(jù)一種構(gòu)造類型數(shù)據(jù) 結(jié)構(gòu)體結(jié)構(gòu)體由若干不同類型的數(shù)據(jù)項(xiàng)組成，由若干不同類型的數(shù)據(jù)項(xiàng)組成， 構(gòu)成結(jié)構(gòu)體的各個(gè)數(shù)據(jù)項(xiàng)稱為構(gòu)成結(jié)構(gòu)體的各個(gè)數(shù)據(jù)項(xiàng)稱為結(jié)構(gòu)體成員結(jié)構(gòu)體成員。 一個(gè)學(xué)生的信息有學(xué)號(hào)、姓名、性別、年齡、住址、成績 等。 一本圖書的信息有分類編號(hào)、書名、作者、出

2、版社、出版 日期、價(jià)格、庫存量等。 如何描述這些類型不同的相關(guān)數(shù)據(jù)？ 9.1.2 結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的定義 結(jié)構(gòu)體類型定義的一般形式： struct 結(jié)構(gòu)體名 數(shù)據(jù)類型1 成員名1; 數(shù)據(jù)類型2 成員名2; 數(shù)據(jù)類型n 成員名n; ; lstructstruct為關(guān)鍵字；為關(guān)鍵字； l結(jié)構(gòu)體名結(jié)構(gòu)體名是用戶定義的是用戶定義的類類 型標(biāo)識(shí)型標(biāo)識(shí)。 l 中是組成該結(jié)構(gòu)體的中是組成該結(jié)構(gòu)體的 成員成員。成員的。成員的數(shù)據(jù)類型數(shù)據(jù)類型可可 以是以是C語言所允許的任何語言所允許的任何 數(shù)據(jù)類型數(shù)據(jù)類型。 例如， 定義結(jié)構(gòu)體類型， 描述下列數(shù)據(jù)。 (1) 學(xué)生情況， 包含學(xué)生的學(xué)號(hào)、 姓名、 性別

3、、 年 齡、C語言課程成績： struct student int no； /*學(xué)號(hào)*/ char name10； /*姓名*/ char sex； /*性別*/ int age； /*年齡*/ float cscore； /*C成績*/ ； 如考慮30門課程成績， 加上總成績與平均成績，可作 如下定義： struct student int no； /*學(xué)號(hào)*/ char name10； /*姓名*/ char sex； /*性別*/ int age； /*年齡*/ float score31； /*30門課程成績*/ float tcj， acj； /*總成績， 平均成績*/ ； (2)

4、個(gè)人數(shù)據(jù)，包含姓名、性別、年齡、身高、體 重、住址: struct person char name10； /*姓名*/ char sex； /*性別*/ int age； /*年齡*/ float height； /*身高*/ float weight； /*體重*/ char add40； /*住址*/ ； (3) 日期， 包括年、 月、 日: struct date int year； /*年*/ month； /*月*/ day； /*日*/ ； 如考慮時(shí)間， 可作如下定義： struct time int hh； /*時(shí)*/ int mm； /*分*/ int ss； /*秒*/ ；

5、 (4) 復(fù)數(shù): struct complex float re； /*實(shí)部*/ float ie； /*虛部*/ ； (5) 三角形: struct sjx float a， b， c； /*三邊*/； 結(jié)構(gòu)體的成員還可是一個(gè)已定義好的結(jié)構(gòu)體類型 struct date int year,month,day; struct student int no; char name10; char sex; birthday; /* 成員為結(jié)構(gòu)體類型成員為結(jié)構(gòu)體類型 */ float cscore; ; 9.1.3 結(jié)構(gòu)體型變量的定義與初始化結(jié)構(gòu)體型變量的定義與初始化 利用已定義的結(jié)構(gòu)體類型名定義變

6、量 struct 結(jié)構(gòu)體名 變量名表； struct student int no； char name10； char sex； int age； float cscore； ； p100;/*100個(gè)人的數(shù)據(jù)*/ nonamesex age cscore 210124 在定義結(jié)構(gòu)體類型的同時(shí)定義變量 struct 結(jié)構(gòu)體名 成員定義表； 變量名表； struct student int no； char name10； char sex； int age； float cscore； t1； struct person char name10； char sex； int age； flo

7、at height； float weight； char add40； p100； /*100個(gè)人的數(shù)據(jù)*/ 直接定義結(jié)構(gòu)體類型變量 struct 成員定義表； 變量名表； struct int no； char name10； char sex； int age； float cscore； t1； 結(jié)構(gòu)體變量的初始化 struct date int year,month,day; struct student int no; char name10; char sex; birthday; float cscore; 用sizeof運(yùn)算符計(jì)算結(jié)構(gòu)體變量所占內(nèi)存空間 sizeof(a) 的

8、結(jié)果為2+10+1+6+4=23 sizeof(struct student3) 的結(jié)果為23 9.1.4 結(jié)構(gòu)體變量的引用結(jié)構(gòu)體變量的引用 對(duì)結(jié)構(gòu)體變量，只能引用其成員， struct date int year,month,day; struct student int no; char name10; char sex; birthday; float cscore; a; 結(jié)構(gòu)體變量a的各成員可分別表示為a.no、 、a.sex、a.birthday、a.cscore a.birthday.year a.birthday.month a.birthday.day 例例 9

9、.1 求某同學(xué)上學(xué)期5門課程的總成績與平均成績。 /*程序9 - 1， 求某同學(xué)的總成績與平均成績*/ main() struct st char xm8; int cj5; float tcj,acj; stu; int i; scanf(%s,stu.xm); /*輸入*/ for(i=0; i5;i+) scanf(%d, stu.tcj=0.0; /*求總成績*/ for(i=0;i5;i+) stu.tcj+=stu.cji; stu.acj=stu.tcj/5; /*求平均成績*/ printf(%s的總成績=%6.2f, 平均成績=%6.2f,stu.xm,stu.tcj, st

10、u.acj); /*輸出*/ 9.2 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組 結(jié)構(gòu)體數(shù)組的定義與結(jié)構(gòu)體變量的定義一樣有以 下三種形式： (1) struct 標(biāo)識(shí)符 成員表 ； struct 標(biāo)識(shí)符 數(shù)組名常量； (2) struct 標(biāo)識(shí)符 成員表 數(shù)組名常量； (3) struct 成員表 數(shù)組名常量； 例如，100個(gè)同學(xué)的情況， 我們可以定義結(jié)構(gòu)體 數(shù)組allst描述： struct student int no； char name8； char sex； int age； float score31； float tcj， acj； allst100； 對(duì)結(jié)構(gòu)體數(shù)組allst的操作要轉(zhuǎn)化成對(duì) alls

11、ti進(jìn)行操作，而allsti的操作 要轉(zhuǎn)化成對(duì)allsti.no、allst 、allsti.sex、allst i.age、allsti.score、allst i.tcj、allsti.acj進(jìn)行操作。 例例 9.2 鍵入30名學(xué)生的3門課的成績，打印平均分。 main() struct st char xm8; int score3; float average; stu30; int i,j; for(i=0;i30;i+) scanf(%s,stui.xm); stui.average=0; for(j=0;j3;j+) scanf(%d, stui.average+=s

12、tui.scorej; stui.average/=3; printf(n); for(i=0;i30;i+) printf(%s:%.2f,stui.xm,stui.average); 例例 9.3 假設(shè)有5個(gè)候選人，有20人參加投票，規(guī)定只能在5個(gè) 候選人中選一個(gè)，多選或選這5人以外者均為廢票。 試用結(jié) 構(gòu)體數(shù)組編寫程序，統(tǒng)計(jì)出5位候選人各人所得票數(shù)。 struct ttt char name10; int count; ; main() struct ttt dp5=Zhang, 0, Li, 0, Wang, 0, Liu, 0, Zhao, 0; char tp10; int i,j

13、; for(i=1; i=20; i+) scanf(%s, tp); for(j=0; j5; j+) if(strcmp(tp, )=0)dpj.count+; for(i=0; iyear p-month p-day “-”是指向結(jié)構(gòu)體成員運(yùn)是指向結(jié)構(gòu)體成員運(yùn) 算符，優(yōu)先級(jí)為一級(jí)算符，優(yōu)先級(jí)為一級(jí) 例例9.4輸入今天的日期，然后輸出該日期。輸入今天的日期，然后輸出該日期。 main( ) struct date /* 在函數(shù)中定義結(jié)構(gòu)體類型在函數(shù)中定義結(jié)構(gòu)體類型 */ int year, month, day; today,*p= /* 定義結(jié)構(gòu)體變量及其指針定義結(jié)構(gòu)體變

14、量及其指針 */ printf (Enter today date(YYYY/MM/DD):); scanf(%d/%d/%d, printf(Today:%d/%d/%dn,p-year,p-month, p-day); 3. 指向結(jié)構(gòu)體數(shù)組的指針 例9.5利用結(jié)構(gòu)體指針輸出一組化學(xué) 元素名稱及其原子量。 struct list int i; char name4; float w; tab4=1,H,1.008,2,He,4.0026, 3,Li,6.941,4,Be,9.01218; tab數(shù)組 1 Htab0 1.008 2 Hetab1 4.0026 3 Litab2 6.941 4

15、 Betab3 9.01218 第九章第九章 結(jié)構(gòu)體、鏈表結(jié)構(gòu)體、鏈表 main( ) struct list *p; printf(NotNametAtomic Weightn); for (p=tab; pi, p-name, p-w); tab數(shù)組 1 Htab0 1.008 2 Hetab1 4.0026 3 Litab2 6.941 4 Betab3 9.01218 p p p p p 1 H 1.008 2 He 4.0026 3 Li 6.941 4 Be 9.01218 9.4 向函數(shù)傳遞結(jié)構(gòu)體型數(shù)據(jù) 結(jié)構(gòu)體的成員作實(shí)參，與普通變量使用一樣。 2.結(jié)構(gòu)體變量作為實(shí)參，形參為相同

16、結(jié)構(gòu)體類型的變量， 實(shí)參變量中各成員的值會(huì)賦給形參對(duì)應(yīng)成員。 3.結(jié)構(gòu)體數(shù)組作實(shí)參，形參為基類型是該結(jié)構(gòu)體類型的指 針變量。 例書9.3 9.5鏈表 1. 鏈表的基本結(jié)構(gòu) head 1000 1032 3284 1296 1382 2008 圖圖9.2 動(dòng)態(tài)單向鏈表示意圖動(dòng)態(tài)單向鏈表示意圖 C 3284 H 1296 A 1382 I 2008 N NULLNULL 1000 1032 鏈表中每個(gè)元素稱為一個(gè)結(jié)點(diǎn)。 構(gòu)成鏈表的結(jié)點(diǎn)必須是結(jié)構(gòu)體類型數(shù)據(jù)。 struct node char c; struct node *next; ; 相鄰結(jié)點(diǎn)的地址不一定是連續(xù)的，依靠指針將 它們連接起來。 例

17、：靜態(tài)創(chuàng)建鏈表 #define NULL 0 struct node int data; struct node *next; ; typedef struct node NODETYPE; main() NODETYPE a,b,c,*h,*p; a.data=10; b.data=20; c.data=30; h= a.next= b.next= c.next=NULL; p=h; while(p!=NULL) printf(%d,p-data); p=p-next; printf(n); (1) malloc（size） 在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)一個(gè)長度為size字節(jié)的連續(xù)空 間。 (2)

18、 calloc（n， size） 在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)n個(gè)長度為size 字節(jié)的連續(xù)空 間，函數(shù)返回值為分配空間的首地址。若此函數(shù)未被成功 執(zhí)行，函數(shù)返回值為0。 (3) free（p） 釋放由指針p所指向的存儲(chǔ)單元，而存儲(chǔ)單元的大小是 最近一次調(diào)用malloc（ ）或calloc（ ）函數(shù)時(shí)所申請(qǐng)的存儲(chǔ) 空間。 例9.6調(diào)用malloc函數(shù)分配所需存儲(chǔ)單元。 #include main( ) struct st int n; struct st *next; *p; p=(struct st *)malloc(sizeof(struct st); p-n=5; p-next=NULL; p

19、rintf(p-n=%dtp-next=%xn,p-n,p-next); 將函數(shù)返回值轉(zhuǎn)換將函數(shù)返回值轉(zhuǎn)換 成結(jié)構(gòu)體指針成結(jié)構(gòu)體指針 #define NULL 0 struct slist int data; struct slist *next; ; typedef struct slist SLIST; 動(dòng)態(tài)創(chuàng)建單向鏈表 SLIST *creat_list() int n; SLIST *h,*s,*r; h=(SLIST *)malloc(sizeof(SLIST); r=h; scanf(%d, while(n!=-1) s=(SLIST *)malloc(sizeof(SLIST);

20、 s-data=n; r-next=s; r=s; scanf(%d, r-next=NULL; return h; 順序訪問鏈表中各結(jié)點(diǎn)的數(shù)據(jù) void print_list(SLIST *head) SLIST *p; p=head-next; if(p=NULL) printf(list is nulln); else printf(head); do printf(-%d,p-data); p=p-next; while(p!=NULL); printf(-endn); 插入結(jié)點(diǎn),在值為x的結(jié)點(diǎn)前，插入值為y的結(jié)點(diǎn)，若值為x結(jié) 點(diǎn)不存在則插入表尾 insert_list(SLIST *head,int x,int y) SLIST *s,*p,*q; s=(SLIST *)malloc(sizeof(SLIST); s-data=y; q=head; p=head-next; while(p!=NULL)p=p-next; s-next=p; q-next=s; 10 p q 8s 刪除鏈表中的結(jié)點(diǎn) void delete_node(SLIST *head,int x) SLIST *p,*q; q=head; p=head-nex