《C語言程序設(shè)計(jì)》課件第7章

第7章結(jié)構(gòu)體7.1結(jié)構(gòu)體類型與結(jié)構(gòu)體變量

7.2結(jié)構(gòu)體數(shù)組

7.3結(jié)構(gòu)體和函數(shù)

7.4鏈表

7.1結(jié)構(gòu)體類型與結(jié)構(gòu)體變量

7.1.1結(jié)構(gòu)體類型的定義

結(jié)構(gòu)體類型中可以包含若干相同或不同類型的成員，這些成員代表相關(guān)的信息。例如：日期結(jié)構(gòu)體類型可由均為整型的年、月、日三個(gè)成員組成；學(xué)生結(jié)構(gòu)體類型可由整型的學(xué)號(hào)、字符串類型的姓名、字符型的性別、實(shí)型數(shù)組的考試成績組成。

例如，日期結(jié)構(gòu)體類型可定義為說明：

(1)?struct是結(jié)構(gòu)體類型的標(biāo)識(shí)，是關(guān)鍵字。struct和后面的結(jié)構(gòu)體名共同構(gòu)成結(jié)構(gòu)體類型名。結(jié)構(gòu)體名應(yīng)符合標(biāo)識(shí)符的命名規(guī)則。結(jié)構(gòu)體類型和系統(tǒng)提供的其他標(biāo)準(zhǔn)數(shù)據(jù)類型(如整型、實(shí)型、字符型等)具有一樣的地位和作用，都可以用來定義某個(gè)變量的類型，只是結(jié)構(gòu)體類型需要由用戶自己制定。

(2)結(jié)構(gòu)體所有成員的定義用花括號(hào)括起來。結(jié)構(gòu)體成員的定義方式和變量的定義方式一樣，成員類型可以是基本類型的，也可以是構(gòu)造類型。各成員之間用分號(hào)隔開。

(3)結(jié)構(gòu)體內(nèi)的各個(gè)成員名不能重復(fù)，但成員名可以與結(jié)構(gòu)體外其他標(biāo)識(shí)符同名而不產(chǎn)生沖突。7.1.2結(jié)構(gòu)體變量的定義

可用以下三種方式定義結(jié)構(gòu)體變量：

(1)用已經(jīng)定義的結(jié)構(gòu)體類型定義結(jié)構(gòu)體變量。例如，用前面已經(jīng)定義的structstudent定義變量stu：

structstudentstu;

(2)定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體變量。例如，定義結(jié)構(gòu)類型structstudent的同時(shí)定義變量stu1，stu2：7.1.3結(jié)構(gòu)體變量的指針

可以定義指針變量指向結(jié)構(gòu)體類型變量。例如，語句“structstudent*p=&stu;”定義了指向結(jié)構(gòu)體的指針變量p，并且使其指向結(jié)構(gòu)體變量stu。stu的存儲(chǔ)結(jié)構(gòu)和p指針的示意圖如圖7.1所示。圖7.1結(jié)構(gòu)體變量的存儲(chǔ)結(jié)構(gòu)及其指針7.1.4結(jié)構(gòu)體變量的初始化

結(jié)構(gòu)體變量同樣既可以在定義之后進(jìn)行初始化，也可以在定義的同時(shí)進(jìn)行初始化。若在定義之后進(jìn)行初始化操作，只能對每個(gè)成員單獨(dú)進(jìn)行賦值。若在定義變量的同時(shí)進(jìn)行初始化，則用一對花括號(hào)括起各個(gè)成員值的列表并用賦值號(hào)和變量連接，成員值之間用逗號(hào)隔開，具體格式為

結(jié)構(gòu)體類型名結(jié)構(gòu)體變量={成員值列表}；7.1.5結(jié)構(gòu)體變量的引用

對于結(jié)構(gòu)體變量，只能引用結(jié)構(gòu)體變量的成員，不能引用整個(gè)結(jié)構(gòu)體變量。引用結(jié)構(gòu)體變量成員有以下兩種形式：

(1)通過結(jié)構(gòu)體變量名引用：

結(jié)構(gòu)體變量名.成員名

其中“.”稱為成員運(yùn)算符，它在所有運(yùn)算符中具有最高的優(yōu)先級(jí)，可以把“結(jié)構(gòu)體變量名.成員名”作為一個(gè)整體看待。

(2)通過指向結(jié)構(gòu)體變量的指針引用：

(*指針變量名).成員名

或

指針變量名

成員名

這兩種表示形式完全等價(jià)。結(jié)構(gòu)體成員的運(yùn)算規(guī)則與同類型變量的運(yùn)算規(guī)則相同。

【例7.1】

輸入學(xué)生的各項(xiàng)信息，計(jì)算總分和平均成績后輸出。

程序如下：圖7.2例7.1的運(yùn)行結(jié)果

7.2結(jié)?構(gòu)?體?數(shù)?組

7.2.1結(jié)構(gòu)體數(shù)組的定義和初始化

若數(shù)組元素的類型為結(jié)構(gòu)體類型，則稱該數(shù)組為結(jié)構(gòu)體數(shù)組。定義結(jié)構(gòu)體數(shù)組的同時(shí)也可對數(shù)組進(jìn)行初始化，例如：可以定義指向結(jié)構(gòu)體數(shù)組元素的指針變量，然后通過指針對數(shù)組元素操作。例如：

structstudent*p=&stu[2];這條語句定義了指針變量p，并使其指向結(jié)構(gòu)體數(shù)組stu的第2個(gè)元素。圖7.3結(jié)構(gòu)體數(shù)組stu的邏輯示意圖7.2.2結(jié)構(gòu)體數(shù)組的引用

結(jié)構(gòu)體數(shù)組也只能引用其數(shù)組元素。結(jié)構(gòu)體數(shù)組元素也是通過數(shù)組名和下標(biāo)來引用的，但要注意只能對最低級(jí)的成員進(jìn)行存取和運(yùn)算。引用的一般形式為

數(shù)組名[下標(biāo)].成員名

例如，stu[1].number、stu[0].score[2]和stu[2].ave等是合法的引用形式。

通過指針引用結(jié)構(gòu)體數(shù)組元素的形式和通過指針引用結(jié)構(gòu)變量形式一樣：

(*指針變量名).成員名或指針變量名

成員名例如，語句“p=&stu[1]；”之后，(*p).number(第1個(gè)學(xué)生的學(xué)號(hào))、(p-1)-

score[2](第0個(gè)學(xué)生的第2門課的成績)、p

ave;(第1個(gè)學(xué)生的平均成績)是合法的引用形式。

【例7.2】

計(jì)算某班期末考試中所有學(xué)生的總分和平均成績。為了調(diào)試方便，先假定該班只有3個(gè)學(xué)生，等程序調(diào)通之后，再把學(xué)生人數(shù)定義為實(shí)際人數(shù)。

程序如下：圖7.4例7.2的運(yùn)行結(jié)果程序說明：main函數(shù)中“floatarg,*point2=&arg;”語句告訴TC需要做浮點(diǎn)數(shù)輸入轉(zhuǎn)換，以便TC把浮點(diǎn)轉(zhuǎn)換格式安裝到可執(zhí)行程序里。因?yàn)門C開發(fā)時(shí)(80年代)，DOS下的存儲(chǔ)資源緊缺，因此TC在編譯時(shí)盡量不加入無關(guān)部分。在沒發(fā)現(xiàn)需要做浮點(diǎn)轉(zhuǎn)換時(shí)，就不將這個(gè)浮點(diǎn)轉(zhuǎn)換格式安裝到可執(zhí)行程序里。但有時(shí)TC不能正確識(shí)別，實(shí)際確實(shí)需要浮點(diǎn)轉(zhuǎn)換，因此就會(huì)出現(xiàn)“scanf:floatingpointformatsnotlinked。Abnormalprogramtermination”的錯(cuò)誤信息，使程序無法正常運(yùn)行。為了避免這種情況，在小程序中，往往要加入這樣的語句提醒TC。

7.3結(jié)構(gòu)體和函數(shù)

7.3.1結(jié)構(gòu)體指針變量作為函數(shù)參數(shù)

C語言允許函數(shù)之間傳遞結(jié)構(gòu)體變量，但是形參結(jié)構(gòu)體變量占用內(nèi)存空間，而且接收實(shí)參數(shù)據(jù)將帶來空間和時(shí)間的巨大開銷。因此語法上雖然允許，但一般很少采用這種方式，而采用結(jié)構(gòu)體指針作為函數(shù)參數(shù)。參數(shù)傳遞時(shí)只需傳遞一個(gè)地址，空間和時(shí)間的代價(jià)都很小。而且，可以通過指針對實(shí)參結(jié)構(gòu)體變量的空間操作，從而改變實(shí)參的值。

【例7.3】

重新編寫例7.2。

程序如下：7.3.2結(jié)構(gòu)體數(shù)組作函數(shù)參數(shù)

向函數(shù)傳遞結(jié)構(gòu)體數(shù)組與傳遞其他數(shù)組一樣，實(shí)質(zhì)上也是傳遞數(shù)組的首地址。形參數(shù)組與實(shí)參數(shù)組使用共同的內(nèi)存單元。形參和實(shí)參是同類型的結(jié)構(gòu)體數(shù)組名或結(jié)構(gòu)體指針。

【例7.4】

重新編寫例7.2。

程序如下： 7.4鏈表

鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)需要?jiǎng)討B(tài)地分配存儲(chǔ)單元，因此不會(huì)浪費(fèi)內(nèi)存空間。圖7.5表示了一種最簡單的鏈表——單向鏈表。圖7.5最簡單的一種鏈表由圖7.5可知，鏈表有一個(gè)“頭指針(head)”變量，其中的地址指向鏈表的第一個(gè)元素(稱為“結(jié)點(diǎn)”)。鏈表的每個(gè)結(jié)點(diǎn)都包括兩個(gè)部分：一為用戶的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址。所以，在鏈表中，頭指針指向第一個(gè)結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)又指向第二個(gè)結(jié)點(diǎn)，……，最后一個(gè)結(jié)點(diǎn)稱為“表尾”，它的地址部分存放“NULL”，表示地址為空，即不再指向任何結(jié)點(diǎn)，因此鏈表到此結(jié)束。顯然，鏈表的各個(gè)結(jié)點(diǎn)在內(nèi)存中可以不是連續(xù)存放的。觀察鏈表的結(jié)點(diǎn)，我們自然會(huì)想到，利用結(jié)構(gòu)體變量來表示結(jié)點(diǎn)是最合適不過的。對于圖7.5的鏈表結(jié)點(diǎn)，顯然可以用以下結(jié)構(gòu)體表示：7.4.1靜態(tài)鏈表的建立與輸出

【例7.5】

建立圖7.5所示的簡單鏈表，并輸出各結(jié)點(diǎn)中的數(shù)據(jù)。程序如下：

在本程序中，所有結(jié)點(diǎn)都是在程序中定義的，而不是動(dòng)態(tài)申請空間建立的，所以不能用完后自動(dòng)釋放，這種鏈表稱為靜態(tài)鏈表。圖7.6例7.5的運(yùn)行結(jié)果7.4.2處理動(dòng)態(tài)鏈表需要的函數(shù)

動(dòng)態(tài)鏈表的結(jié)點(diǎn)是動(dòng)態(tài)分配的，即在需要的時(shí)候才開辟某個(gè)結(jié)點(diǎn)的存儲(chǔ)單元。為了動(dòng)態(tài)地開辟和釋放存儲(chǔ)單元，C語言編譯系統(tǒng)提供了以下函數(shù)。

1.?malloc函數(shù)

函數(shù)原形：

void*malloc(unsignedintsize);

作用：在內(nèi)存的動(dòng)態(tài)存區(qū)分配一個(gè)長度為size個(gè)字節(jié)的連續(xù)存區(qū)，函數(shù)的返回值是一個(gè)指向該存區(qū)首地址的指針(其類型為void型)。如果由于內(nèi)存不足等原因使該函數(shù)未能成功執(zhí)行，則返回空指針NULL。

2.?calloc函數(shù)

函數(shù)原形：

void*calloc(unsignedn,unsignedsize);

作用：在內(nèi)存的動(dòng)態(tài)存區(qū)分配n個(gè)長度為size個(gè)字節(jié)的連續(xù)存區(qū)，函數(shù)的返回值是一個(gè)指向該存區(qū)首地址的指針(其類型為void型)。如果由于內(nèi)存不足等原因使該函數(shù)未能成功執(zhí)行，則返回空指針NULL。使用calloc函數(shù)能夠?yàn)橐痪S數(shù)組開辟動(dòng)態(tài)存儲(chǔ)空間，n為數(shù)組元素的個(gè)數(shù)，每個(gè)元素的長度為size個(gè)字節(jié)。

3.?free函數(shù)

函數(shù)原形：

voidfree(void*p);

作用：釋放p指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)域能夠被其他變量使用，p為最近一次malloc/calloc的返回值，即最近一次分配的空間。free函數(shù)沒有返回值。

7.4.3建立動(dòng)態(tài)鏈表

所謂建立動(dòng)態(tài)鏈表，是指在程序執(zhí)行過程中逐個(gè)建立鏈表的各個(gè)結(jié)點(diǎn)，即逐個(gè)開辟結(jié)點(diǎn)的內(nèi)存空間，再輸入該結(jié)點(diǎn)的數(shù)據(jù)，然后建立起前后結(jié)點(diǎn)之間的相連關(guān)系。

【例7.6】

用建立單向動(dòng)態(tài)鏈表的方法建立圖7.5所示的鏈表。

為了建立一個(gè)單向動(dòng)態(tài)鏈表，需要設(shè)置3個(gè)指針變量：head、p1和p2，它們都指向structstudent類型數(shù)據(jù)，p1指向新開的結(jié)點(diǎn)，p2指向鏈表中最后一個(gè)結(jié)點(diǎn)。先使head的值為NULL，即不指向任何結(jié)點(diǎn)，鏈表為空。圖7.7建立第一個(gè)結(jié)點(diǎn)首先建立圖7.7所示的第一個(gè)結(jié)點(diǎn)。先用malloc函數(shù)開辟第一個(gè)結(jié)點(diǎn)，即在內(nèi)存的動(dòng)態(tài)存區(qū)分配一個(gè)一定長度的連續(xù)存區(qū)，并且使p1指向它，由于當(dāng)前鏈表為空，所以p2也指向剛分配的連續(xù)存區(qū)。再從鍵盤上讀入第一個(gè)學(xué)生的數(shù)據(jù)(學(xué)號(hào)和成績)給p1指向的結(jié)點(diǎn)。由于實(shí)際上沒有學(xué)號(hào)為0的學(xué)生，所以以輸入的學(xué)號(hào)為0表示學(xué)生數(shù)據(jù)已經(jīng)讀完，鏈表建成，不再繼續(xù)建立新結(jié)點(diǎn)的循環(huán)。在輸入第一個(gè)學(xué)生的數(shù)據(jù)之前，鏈表中沒有結(jié)點(diǎn)，所以頭指針head為NULL。當(dāng)輸入的學(xué)號(hào)不為0時(shí)，就開始為這個(gè)學(xué)生建立結(jié)點(diǎn)，當(dāng)n=1時(shí)，表示當(dāng)時(shí)的結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)，所以把這個(gè)結(jié)點(diǎn)的指針p1的值賦給head，head就指向了鏈表的頭部。當(dāng)圖7.7所示的第1個(gè)結(jié)點(diǎn)建立以后，為了建立下一個(gè)學(xué)生的結(jié)點(diǎn)，再用malloc函數(shù)開辟一個(gè)結(jié)點(diǎn)，并且用p1指向這個(gè)新結(jié)點(diǎn)，如圖7.8(a)所示；接著讀入第二個(gè)學(xué)生的數(shù)據(jù)，由于讀入的學(xué)號(hào)非0，所以第二次進(jìn)入建立結(jié)點(diǎn)的循環(huán)，由于結(jié)點(diǎn)數(shù)n不為1，所以將p1的值賦給p2->next，使第一個(gè)結(jié)點(diǎn)連到了第二個(gè)結(jié)點(diǎn)，如圖7.8(b)所示，然后，又將p1的值賦給p2，使第二個(gè)結(jié)點(diǎn)的p1、p2兩個(gè)指針又回到圖7.7第一個(gè)結(jié)點(diǎn)剛建立的狀態(tài)，準(zhǔn)備建立下一個(gè)結(jié)點(diǎn)。如此周而復(fù)始，就可以建立第三、第四或者更多的結(jié)點(diǎn)，如圖7.9和圖7.10所示。圖7.8建立第2個(gè)結(jié)點(diǎn)圖7.9建立第3個(gè)結(jié)點(diǎn)圖7.10建立第4個(gè)結(jié)點(diǎn)當(dāng)讀入的學(xué)號(hào)為0時(shí)，表示學(xué)生數(shù)據(jù)已經(jīng)輸入完畢，所以不再進(jìn)入建立新結(jié)點(diǎn)的while循環(huán)，而置p2->next為NULL,表示剛才建立的結(jié)點(diǎn)是尾結(jié)點(diǎn)，此時(shí)，雖然p1指向新開辟的結(jié)點(diǎn)，但是這個(gè)“新結(jié)點(diǎn)”并不包含在鏈表之內(nèi)，從鏈表中不可能找到這個(gè)結(jié)點(diǎn)。

7.4.4對鏈表的刪除

所謂刪除動(dòng)態(tài)鏈表的某個(gè)結(jié)點(diǎn)，其實(shí)并不是真的從內(nèi)存中把這個(gè)結(jié)點(diǎn)抹掉，只是撤銷原來的連接關(guān)系，把這個(gè)結(jié)點(diǎn)從鏈表中分離出去。

【例7.7】

寫一個(gè)函數(shù)刪除例7.5建立的動(dòng)態(tài)鏈表中指定學(xué)號(hào)的結(jié)點(diǎn)。

所謂刪除指定學(xué)號(hào)的結(jié)點(diǎn)，就是從頭結(jié)點(diǎn)開始，逐個(gè)比較每個(gè)結(jié)點(diǎn)的num是否等于該指定的學(xué)號(hào)，如果相等就將該結(jié)點(diǎn)刪除，否則就比較下一個(gè)結(jié)點(diǎn)，直到檢查到鏈表的表尾為止。為此先設(shè)置兩個(gè)指針p1和p2，使p1指向第1個(gè)結(jié)點(diǎn)如圖7.11(a)所示。首先檢查第一個(gè)結(jié)點(diǎn)，如果要?jiǎng)h除的結(jié)點(diǎn)不是第1個(gè)結(jié)點(diǎn)，首先將p1的值賦給p2，使p2指向剛才檢查過的結(jié)點(diǎn),然后使p1指向下一個(gè)結(jié)點(diǎn)(即p1=p1->next)，如圖7.11(b)所示，如此一次一次地使指針后移，直到查到要?jiǎng)h除的結(jié)點(diǎn)或者一直查到表尾都沒有找到要?jiǎng)h除的結(jié)點(diǎn)為止。

如果找到了要?jiǎng)h除的結(jié)點(diǎn)，而且是第一個(gè)結(jié)點(diǎn)，則將p1->next賦給head，如圖7.11(c)所示，于是第1個(gè)結(jié)點(diǎn)就被刪除了(實(shí)際是和鏈表脫離了，而不再是鏈表的一部分)。如果找到了要?jiǎng)h除的結(jié)點(diǎn)，但不是第一個(gè)結(jié)點(diǎn)，譬如查到圖7.11(a)的第2個(gè)結(jié)點(diǎn)時(shí)(現(xiàn)在p1指向第2個(gè)結(jié)點(diǎn))，發(fā)現(xiàn)它是要?jiǎng)h除的結(jié)點(diǎn)，則將p1->next賦給p2->next，如圖7.11(d)所示，于是第1個(gè)結(jié)點(diǎn)不再指向第2個(gè)結(jié)點(diǎn)，而是指向第3個(gè)結(jié)點(diǎn)了，因此把第2個(gè)結(jié)點(diǎn)與鏈表脫離了。

如果直到查到表尾都沒有找到要?jiǎng)h除的結(jié)點(diǎn)，則輸出“找不到要?jiǎng)h除的結(jié)點(diǎn)”。

如果所查找的鏈表一個(gè)結(jié)點(diǎn)都沒有，即頭指針為空，完全是個(gè)空表，則輸出“空表”信息。圖7.11刪除結(jié)點(diǎn)圖7.12是刪除結(jié)點(diǎn)的算法框圖。圖7.12刪除結(jié)點(diǎn)的算法框圖7.4.5對鏈表的插入操作

所謂對鏈表的插入，是指將一個(gè)新結(jié)點(diǎn)插入到一個(gè)已經(jīng)存在的鏈表中。

如果已有一個(gè)學(xué)生鏈表，各結(jié)點(diǎn)是按照其成員項(xiàng)num的數(shù)值按升序排列的，現(xiàn)在要求將一個(gè)新生的結(jié)點(diǎn)按學(xué)號(hào)插入到鏈表的適當(dāng)位置。

為了實(shí)現(xiàn)結(jié)點(diǎn)的插入，首先要找到插入的位置，然后用適當(dāng)?shù)姆椒▽⒔Y(jié)點(diǎn)插入到這個(gè)位置。由于已有的鏈表是按照學(xué)號(hào)的升序排列的，所以從第一個(gè)結(jié)點(diǎn)開始比較，新結(jié)點(diǎn)應(yīng)該插在第一次比新結(jié)點(diǎn)的學(xué)號(hào)大的學(xué)生之前，設(shè)該結(jié)點(diǎn)是第i+1個(gè)結(jié)點(diǎn)，那么新結(jié)點(diǎn)應(yīng)該插在第i和第i+1個(gè)結(jié)點(diǎn)之間。即使第i個(gè)結(jié)點(diǎn)和第i+1個(gè)結(jié)點(diǎn)的連接斷開，讓第i個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)，然后再使新結(jié)點(diǎn)指向第i+1個(gè)