第7章結構體7.1結構體類型與結構體變量

7.2結構體數組

7.3結構體和函數

7.4鏈表

7.1結構體類型與結構體變量

7.1.1結構體類型的定義

結構體類型中可以包含若干相同或不同類型的成員，這些成員代表相關的信息。例如：日期結構體類型可由均為整型的年、月、日三個成員組成；學生結構體類型可由整型的學號、字符串類型的姓名、字符型的性別、實型數組的考試成績組成。

例如，日期結構體類型可定義為說明：

(1)?struct是結構體類型的標識，是關鍵字。struct和后面的結構體名共同構成結構體類型名。結構體名應符合標識符的命名規則。結構體類型和系統提供的其他標準數據類型(如整型、實型、字符型等)具有一樣的地位和作用，都可以用來定義某個變量的類型，只是結構體類型需要由用戶自己制定。

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

(3)結構體內的各個成員名不能重復，但成員名可以與結構體外其他標識符同名而不產生沖突。7.1.2結構體變量的定義

可用以下三種方式定義結構體變量：

(1)用已經定義的結構體類型定義結構體變量。例如，用前面已經定義的structstudent定義變量stu：

structstudentstu;

(2)定義結構體類型的同時定義結構體變量。例如，定義結構類型structstudent的同時定義變量stu1，stu2：7.1.3結構體變量的指針

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

結構體變量同樣既可以在定義之后進行初始化，也可以在定義的同時進行初始化。若在定義之后進行初始化操作，只能對每個成員單獨進行賦值。若在定義變量的同時進行初始化，則用一對花括號括起各個成員值的列表并用賦值號和變量連接，成員值之間用逗號隔開，具體格式為

結構體類型名結構體變量={成員值列表}；7.1.5結構體變量的引用

對于結構體變量，只能引用結構體變量的成員，不能引用整個結構體變量。引用結構體變量成員有以下兩種形式：

(1)通過結構體變量名引用：

結構體變量名.成員名

其中“.”稱為成員運算符，它在所有運算符中具有最高的優先級，可以把“結構體變量名.成員名”作為一個整體看待。

(2)通過指向結構體變量的指針引用：

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

或

指針變量名

成員名

這兩種表示形式完全等價。結構體成員的運算規則與同類型變量的運算規則相同。

【例7.1】

輸入學生的各項信息，計算總分和平均成績后輸出。

程序如下：圖7.2例7.1的運行結果

7.2結?構?體?數?組

7.2.1結構體數組的定義和初始化

若數組元素的類型為結構體類型，則稱該數組為結構體數組。定義結構體數組的同時也可對數組進行初始化，例如：可以定義指向結構體數組元素的指針變量，然后通過指針對數組元素操作。例如：

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

結構體數組也只能引用其數組元素。結構體數組元素也是通過數組名和下標來引用的，但要注意只能對最低級的成員進行存取和運算。引用的一般形式為

數組名[下標].成員名

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

通過指針引用結構體數組元素的形式和通過指針引用結構變量形式一樣：

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

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

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

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

【例7.2】

計算某班期末考試中所有學生的總分和平均成績。為了調試方便，先假定該班只有3個學生，等程序調通之后，再把學生人數定義為實際人數。

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

7.3結構體和函數

7.3.1結構體指針變量作為函數參數

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

【例7.3】

重新編寫例7.2。

程序如下：7.3.2結構體數組作函數參數

向函數傳遞結構體數組與傳遞其他數組一樣，實質上也是傳遞數組的首地址。形參數組與實參數組使用共同的內存單元。形參和實參是同類型的結構體數組名或結構體指針。

【例7.4】

重新編寫例7.2。

程序如下： 7.4鏈表

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

【例7.5】

建立圖7.5所示的簡單鏈表，并輸出各結點中的數據。程序如下：

在本程序中，所有結點都是在程序中定義的，而不是動態申請空間建立的，所以不能用完后自動釋放，這種鏈表稱為靜態鏈表。圖7.6例7.5的運行結果7.4.2處理動態鏈表需要的函數

動態鏈表的結點是動態分配的，即在需要的時候才開辟某個結點的存儲單元。為了動態地開辟和釋放存儲單元，C語言編譯系統提供了以下函數。

1.?malloc函數

函數原形：

void*malloc(unsignedintsize);

作用：在內存的動態存區分配一個長度為size個字節的連續存區，函數的返回值是一個指向該存區首地址的指針(其類型為void型)。如果由于內存不足等原因使該函數未能成功執行，則返回空指針NULL。

2.?calloc函數

函數原形：

void*calloc(unsignedn,unsignedsize);

作用：在內存的動態存區分配n個長度為size個字節的連續存區，函數的返回值是一個指向該存區首地址的指針(其類型為void型)。如果由于內存不足等原因使該函數未能成功執行，則返回空指針NULL。使用calloc函數能夠為一維數組開辟動態存儲空間，n為數組元素的個數，每個元素的長度為size個字節。

3.?free函數

函數原形：

voidfree(void*p);

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

7.4.3建立動態鏈表

所謂建立動態鏈表，是指在程序執行過程中逐個建立鏈表的各個結點，即逐個開辟結點的內存空間，再輸入該結點的數據，然后建立起前后結點之間的相連關系。

【例7.6】

用建立單向動態鏈表的方法建立圖7.5所示的鏈表。

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

7.4.4對鏈表的刪除

所謂刪除動態鏈表的某個結點，其實并不是真的從內存中把這個結點抹掉，只是撤銷原來的連接關系，把這個結點從鏈表中分離出去。

【例7.7】

寫一個函數刪除例7.5建立的動態鏈表中指定學號的結點。

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

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

如果直到查到表尾都沒有找到要刪除的結點，則輸出“找不到要刪除的結點”。

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

所謂對鏈表的插入，是指將一個新結點插入到一個已經存在的鏈表中。

如果已有一個學生鏈表，各結點是按照其成員項num的數值按升序排列的，現在要求將一個新生的結點按學號插入到鏈表的適當位置。

為了實現結點的插入，首先要找到插入的位置，然后用適當的方法將結點插入到這個位置。由于已有的鏈表是按照學號的升序排列的，所以從第一個結點開始比較，新結點應該插在第一次比新結點的學號大的學生之前，設該結點是第i+1個結點，那么新結點應該插在第i和第i+1個結點之間。即使第i個結點和第i+1個結點的連接斷開，讓第i個結點指向新結點，然后再使新結點指向第i+1個