【正文】 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 74 用 typedef定義類型的別名 關(guān)鍵字 typedef可用來為類型標(biāo)識符建立一個 別名，這個別名同樣可用于變量、數(shù)組、函數(shù)等 對象的聲明。 ： 10只猴子圍成一圈選猴王，方法是 3報(bào)數(shù)，數(shù)到第 3者退出，用循環(huán)鏈表模擬。 /*返回鏈表頭指針 */ } /*creat*/ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 73 補(bǔ)充作業(yè) /實(shí)驗(yàn)： ： 用隨機(jī)數(shù)建立 10節(jié)點(diǎn)有序鏈表。 } } p2next=NULL。 else { p2next=p1。 p1score=s。 /*以 0表示數(shù)據(jù)結(jié)束 */ p1=(struct student *)malloc(len)。s)。 scanf(%ld,%f, amp。 ┇ } return(head)。 if(n==0) break。n, amp。 while(1) /*循環(huán)次數(shù)不確定 */ { printf(Enter number,score:)。 float s。 int len。 } /*insert*/ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 71 【 例 】 編寫一個通用的函數(shù)，可根據(jù)需要建立任意 節(jié)點(diǎn)數(shù)的鏈表。 /*插入在其余位置 */ p2next=p0。 np1num)。 } while(p1!=NULL amp。 } else { do /*查找插入位置 */ { p2=p1。 /*↓ 插入在頭部 */ if(np1num) { p0next=head。 /*產(chǎn)生學(xué)號副本 n*/ p1=head。p0score)。 scanf(%ld,%f, amp。 p0=(struct student *)malloc(len)。 int len。 2101 1370 head 1048 2304 90 1012 2414 78 1048 1370 1012 1012 2680 2680 2918 85 NULL C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 69 【 例 】 按上例在鏈表中按學(xué)號順序插入節(jié)點(diǎn) 插入函數(shù)： struct student *insert(struct student *head) { struct student *p0, *p1, *p2。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 67 4. 節(jié)點(diǎn)的插入 插入可分為隨意插入和按順序插入， 隨意插 入 包括插入到頭部、尾部或中間指定位置； 按順 序插入 是指按某關(guān)鍵字的順序插入，而在插入前 鏈表必須已按該關(guān)鍵字進(jìn)行了排序。 } return。 while(p!=NULL) { printf(num=%ld, score=%\n, pnum, pscore)。 /*返回頭指針 */ } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 66 void plink(struct student *head) /*更具通用性 */ { struct student *p。 /*未找到 */ } free(p1)。 if(p1num==n) p2next=p1next。amp。 p1=p1next。 if(p1num==n) head=p1next。 1048 1012 2101 1370 head 2304 90 1012 p NULL 1048 2918 85 1012 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 65 【 例 】 按上例刪除指定學(xué)號的節(jié)點(diǎn) struct student *del(struct student *head, long n) { struct student *p1, *p2。 若：要刪除節(jié)點(diǎn)為首節(jié)點(diǎn)，則將首節(jié)點(diǎn)“鏈節(jié)”成 員賦給鏈頭指針變量。 } return(sum/c)。 /*c統(tǒng)計(jì)節(jié)點(diǎn)數(shù) */ sum=sum+pscore。 p=head。 float sum=0。 } return。 else p=pnext。 i=N。 int i。 //尾節(jié)點(diǎn) } return(head)。 p2=p1。 if(i==1) head=p2=p1。p1num, amp。 printf(Enter num,score:)。 i=N。 len=sizeof(struct student)。 } ┇ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 61 struct student *create( ) { struct student *head, *p1, *p2。 aver=averf(head)。 head=create( )。 clrscr( )。 float aver。 float averf(struct student *head)。 void main( ) { ┇ } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 60 void main( ) { struct student *head, *create(void)。 struct student *next。 函數(shù)間信息傳遞： 主 函 數(shù) create plink averf 無參 頭指針 頭指針 無返回值 平均值 頭指針 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 59 include include define N 3 struct student /*全局結(jié)構(gòu)類型 */ { long num。 輸出鏈表函數(shù) : void plink(struct student *head)。 } } /*main*/ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 58 【 例 】 將上題利用函數(shù)實(shí)現(xiàn)，并求平均成績。 /*p1指向首節(jié)點(diǎn) */ else p1=p1next。 i=N。 i=N。 } /*節(jié)點(diǎn)鏈接 */ if(i==N) p2next=NULL。 /*指向首節(jié)點(diǎn) */ else { p2next=p1。p1score)。 /*↓ 輸入數(shù)據(jù) */ scanf(%ld,%f, amp。i++) /*↙ 強(qiáng)制轉(zhuǎn)換為結(jié)構(gòu)體指針類型 */ { p1=(struct student *)malloc(len)。 /*求類型長 */ for(i=1。 /*TC激活浮點(diǎn)運(yùn)算 */ head=NULL。 int i, len。 /*自引用結(jié)構(gòu)體指針 */ }。 float score。 /*末尾節(jié)點(diǎn) next賦值 0*/ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 55 【 例 】 建立并輸出有 3名學(xué)生數(shù)據(jù)的單鏈表。 p2=p1。p1score)。 scanf(%ld,%f, amp。 /*使 p2也指向新節(jié)點(diǎn) */ 1370 1370 p2 p1 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 54 3) 重復(fù)第 2步，建立并鏈接多個節(jié)點(diǎn)直至所需長 度，將末尾節(jié)點(diǎn)的 next成員賦值 0。 p2next=p1。p1num, amp。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 53 2) 開辟下一節(jié)點(diǎn)的存儲區(qū)域，使 p1指向新節(jié)點(diǎn)、 輸入新節(jié)點(diǎn)數(shù)據(jù)，并將上一個節(jié)點(diǎn)的 next成員 指向新節(jié)點(diǎn)； 2101 head p1 p2 2304 90 1048 操作： p1=(struct student *)malloc(len)。p1score)。 scanf(%ld,%f, amp。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 52 建立鏈表的步驟： 1) 開辟第一個節(jié)點(diǎn)的存儲區(qū)域，使 head、 p p2 指向第一個節(jié)點(diǎn)，并輸入第一個節(jié)點(diǎn)數(shù)據(jù)； 2101 head p1 p2 操作： len=sizeof(struct student)。 即：鏈表特別適合于對大線性表頻繁插入和刪除元素、或成員數(shù)目不定的數(shù)據(jù)結(jié)構(gòu)。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 49 5) 采用鏈表的意義 ?與定長數(shù)據(jù)結(jié)構(gòu)數(shù)組相比，鏈表能更好地利用內(nèi)存，按需分配和釋放存儲空間。 功能： 釋放 p所指向的內(nèi)存塊。 功能： 申請長度為 size個字節(jié)的內(nèi)存空間；若申請 成功，返回存儲塊起始指針，該指針類型為 void *；否則返回空指針 (NULL)。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 48 4) 動態(tài)內(nèi)存分配和釋放 建立和維護(hù)動態(tài)數(shù)據(jù)結(jié)構(gòu)需要實(shí)現(xiàn)動態(tài)內(nèi)存 分配；如在鏈表中插入節(jié)點(diǎn)需要先申請一段存儲 區(qū)域，而刪除一個節(jié)點(diǎn)需要釋放該節(jié)點(diǎn)原先占用 的存儲區(qū)域，這可由標(biāo)準(zhǔn)函數(shù)實(shí)現(xiàn)。 /*鏈節(jié)成員 */ 其中： ?成員 num、 score用于存放一個節(jié)點(diǎn)的具體數(shù)據(jù)； ?成員 next是指針類型，用于存放下一節(jié)點(diǎn)指針， 最后一個節(jié)點(diǎn)的 next 成員存放空指針 NULL； ?成員 next是指向與自身同一類型的結(jié)構(gòu)，這種結(jié) 構(gòu)稱為自引用結(jié)構(gòu)。 structer student *next。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 47 3) 節(jié)點(diǎn)的構(gòu)成 上圖每個節(jié)點(diǎn)具有如下結(jié)構(gòu)體類型： struct student { long num。 鏈表是 連成一行 的數(shù)據(jù)項(xiàng)集合，每一個數(shù)據(jù) 項(xiàng) (元素 )稱為節(jié)點(diǎn)，可以在鏈表中的任意