【正文】 20, p)。 } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 44 tp=amp。 gettime(tp)。 /*保存秒成員 */ while(!kbhit()) /*擊鍵測(cè)試 */ { gettime(tp)。 /*輸出畫(huà)面擦除文本 */ sprintf(ch,TIME: %u:%u:%u, /*輸出到 ch中 */ tpti_hour, tpti_min, tpti_sec)。 /*圖形模式文本輸出 */ sound(500)。 /*揚(yáng)聲器發(fā)聲 */ nosound()。 /*更新 t*/ } } } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 45 用指針處理鏈表 1. 鏈表概述 1) 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)概念 數(shù)組和結(jié)構(gòu)體是定長(zhǎng)數(shù)據(jù)結(jié)構(gòu)，而鏈表、堆 棧、隊(duì)列、樹(shù)、圖等是執(zhí)行時(shí)大小可變的動(dòng)態(tài)數(shù) 據(jù)結(jié)構(gòu)。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 46 2) 鏈表的構(gòu)成 單向鏈表圖示： 1048 1370 1012 頭節(jié)點(diǎn) 表內(nèi)節(jié)點(diǎn) 尾節(jié)點(diǎn) 2101 1370 2304 90 1012 2918 85 NULL 1048 head 其中： ?各節(jié)點(diǎn)是相同的結(jié)構(gòu)體類(lèi)型，該類(lèi)型有三個(gè)成員； ? head是指針變量，存放鏈表的頭節(jié)點(diǎn)指針 1048； ?各節(jié)點(diǎn)應(yīng)包含一個(gè)指針成員存放下一節(jié)點(diǎn)的地址； ?各節(jié)點(diǎn)存儲(chǔ)有可能不連續(xù)，但各節(jié)點(diǎn)邏輯上連續(xù)。 float score。 }。 (只有指針成員可自引用 ) ?節(jié)點(diǎn)是在運(yùn)行時(shí)動(dòng)態(tài)生成的。 內(nèi)存分配函數(shù)原形： void *malloc(unsigned size)。 內(nèi)存釋放函數(shù)原形： void free(void *p)。 包含文件： 、 。 ?在鏈表中插入或刪除一個(gè)節(jié)點(diǎn)，只需改變某節(jié)點(diǎn)“鏈節(jié)”成員的指向，而不需要移動(dòng)其它節(jié)點(diǎn)，相對(duì)數(shù)組元素的插入和刪除效率高。 C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 50 6) 鏈表的類(lèi)型 單鏈表： 每個(gè)節(jié)點(diǎn)只有一個(gè)指向后繼節(jié)點(diǎn)的指針 雙向鏈表： 每個(gè)節(jié)點(diǎn)有兩個(gè)用于指向其它節(jié)點(diǎn)的指針；一個(gè)指向前趨節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn) 循環(huán)鏈表： 使最后一個(gè)節(jié)點(diǎn)的指針指向第一個(gè)節(jié)點(diǎn) C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 51 2. 單鏈表的建立和輸出 建立鏈表的準(zhǔn)備工作 : 1) 定義鏈表的節(jié)點(diǎn)類(lèi)型； 2) 定義與節(jié)點(diǎn)同類(lèi)型的鏈表頭指針變量 head并賦值 0，表示鏈表在建立之前是空的； 3) 定義與節(jié)點(diǎn)同類(lèi)型的工作指針變量 p p2。 p1=(struct student *)malloc(len)。p1num, amp。 head=p2=p1。 scanf(%ld,%f, amp。p1score)。 p2=p1。 2101 1370 head p2 2304 90 2918 85 p2 NULL 1048 1370 p1 1012 1012 p1 操作： p1=(struct student *)malloc(len)。p1num, amp。 p2next=p1。 /*使 p2也指向新節(jié)點(diǎn) */ p2next=NULL。 include /*包含 NULL的定義 */ include define N 3 struct student /*結(jié)構(gòu)體類(lèi)型定義 */ { long num。 struct student *next。 void main( ) { ┇ } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 56 void main( ) { struct student *head, *p1, *p2。 sqrt()。 /*head不指向任何位置 */ len=sizeof(struct student)。i=N。 /*申請(qǐng) */ printf(Enter num, score:)。p1num, amp。 if(i==1) head=p2=p1。 p2=p1。 /*標(biāo)記末尾節(jié)點(diǎn) */ } ┇ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 57 ┇ void main( ) { ┇ for(i=1。 i++) /*建立鏈表 */ { ┇ } for(i=1。 i++) /*輸出鏈表 */ { if(i==1) p1=head。 /*p1指向下一節(jié)點(diǎn) */ printf(%d:num=%ld,score=%\n, i, p1num, p1score)。 定義如下函數(shù)： 建立鏈表函數(shù) : struct student *create(void)。 求平均值函數(shù) : float averf(struct student *head)。 float score。 }。 void plink(struct student *head)。 int i, len。 sqrt()。 /*TC中使用 head=NULL。 /*返回鏈表頭指針 */ plink(head)。 /*返回平均值 */ printf(Average=%\n, aver)。 int i, len。 for(i=1。 i++) { p1=(struct student *)malloc(len)。 scanf(%ld,%f, amp。p1score)。 //頭節(jié)點(diǎn) else { p2next=p1。 } //中間節(jié)點(diǎn) if(i==N) p2next=NULL。 //返回鏈表頭指針 } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 62 void plink(struct student *head) /*輸出各節(jié)點(diǎn) */ { struct stduent *p。 for(i=1。 i++) { if(i==1) p=head。 printf(%d:num=%ld,score=%\n, i, pnum, pscore)。 } 2 1 0 18 9 . 51 3 7 01 0 4 8 2 1 0 18 9 . 51 3 7 0P P ? C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 63 float averf(struct student *head) { struct student *p。 int c=0。 /*使 p指向首節(jié)點(diǎn) */ while(p!=NULL) { c++。 p=pnext。 /*返回平均值 */ } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 64 1370 3. 節(jié)點(diǎn)的刪除 步驟： 1) 從頭節(jié)點(diǎn)開(kāi)始按查找關(guān)鍵字查找要?jiǎng)h除的節(jié)點(diǎn)； 2) 找到，則將要?jiǎng)h除節(jié)點(diǎn)的“鏈節(jié)”成員賦給前一節(jié)點(diǎn)的“鏈節(jié)”成員，使刪除的節(jié)點(diǎn)脫離鏈表。 3) 釋放已被刪除節(jié)點(diǎn)占用的空間。 /*↗ n：要?jiǎng)h除學(xué)號(hào) */ p1=head。 /*刪除首節(jié)點(diǎn) */ else { do { p2=p1。 /*繼續(xù)找 */ } while(p1!=NULL amp。 p1num!=n)。 /*找到 */ else printf(Not be found!\n)。 /*釋放被刪除節(jié)點(diǎn)的存儲(chǔ)區(qū) */ return(head)。 p=head。 p=pnext。 } 注： 本形式的鏈表輸出函數(shù)具有通用性，可適應(yīng)由于刪除或插入節(jié)點(diǎn)引起的鏈表長(zhǎng)度的變化。 按順序插入的步驟： 1) 開(kāi)辟待插入節(jié)點(diǎn)的存儲(chǔ)區(qū)域并輸入數(shù)據(jù)； 2) 查找插入位置：從鏈表首節(jié)點(diǎn)開(kāi)始按關(guān)鍵字成 員與待插入節(jié)點(diǎn)相同成員進(jìn)行比較，直到確定了插入位置； C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 68 3) 將插入位置前一節(jié)點(diǎn)的“鏈節(jié)”成員賦給待插入節(jié) 點(diǎn)的“鏈節(jié)”成員； 若：插入點(diǎn)在鏈頭，則將頭指針賦給待插入節(jié)點(diǎn)的 “鏈節(jié)”成員； 4) 將待插入節(jié)點(diǎn)的指針賦給前一節(jié)點(diǎn)“鏈節(jié)”成員； 若：插入點(diǎn)在鏈頭，先將頭指針賦給插入節(jié)點(diǎn)的指針域，再將待插入節(jié)點(diǎn)的指針賦給頭指針變量。 long n。 len=sizeof(struct student)。 /*申請(qǐng)新節(jié)點(diǎn) */ printf(Enter num,score to insert:)。p0num, amp。 n=p0num。 /*從首節(jié)點(diǎn)開(kāi)始查找 */ ┇ C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 70 ┇ p1=head。 head=p0。 p1=p1next。amp。 p0next=p2next。 } return(head)。 struct student *creat( ) /*無(wú)參有返回值 */ { struct student *head=NULL, *p1, *p2。 long n。 len=sizeof(struct student)。 scanf(%ld,%f, amp。s)。 /*輸入 0表示數(shù)據(jù)結(jié)束 */ p1=(struct student *)malloc(len)。 } C 程序設(shè)計(jì) 第十一章 結(jié)構(gòu)體與共用體 NWPU—CC—ZhangYanChun 72 ┇ while(1) { printf(Enter number,score:)。n, amp。 if(n==0) break。 p1num=n。 /*轉(zhuǎn)存入節(jié)點(diǎn) */ if(head==NULL) head=p2=p1。 p2=p1。 /*末尾鏈節(jié)成員賦空 */ return(head)。 提示： 邊生成隨機(jī)數(shù)邊建立節(jié)點(diǎn)，并判斷新節(jié)點(diǎn)應(yīng)插入的位置。 注意： 鏈頭指針；最后一個(gè)節(jié)點(diǎn)鏈節(jié)成員指向頭節(jié)點(diǎn)。 使用一般形式： typedef 原類(lèi)型名 新類(lèi)型名； 其中： 原類(lèi)型名可以是標(biāo)準(zhǔn)的或用戶(hù)定義的；