【正文】 第十一章 復(fù)雜數(shù)據(jù)類型 C 線性鏈表的基本操作 ? 鏈表的刪除操作 含義： 刪除鏈表中的第 i個結(jié)點 Ni，使線性表的長度減 1。刪除前，節(jié)點 Ni1是 Ni的前驅(qū)， Ni+1是 Ni的后繼；刪除后，結(jié)點 Ni+1成為 Ni1的后繼。 基本思想： 通過單鏈表的頭指針 head，首先找到鏈表中指向第 i個結(jié)點的前驅(qū)節(jié)點的指針 p和指向第 i個節(jié)點的指針 q；然后刪除第 i個結(jié)點。刪除時只需執(zhí)行 pnext = qnext即可，當(dāng)然不要忘了釋放節(jié)點 i的內(nèi)存單元。注意當(dāng) i=0時，表示頭節(jié)點，是不可刪除的。 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 【 例 】 鏈表刪除操作函數(shù) Delete_LinkList 。 void Delete_LinkList(NODE *head, int i) { NODE *p,*q。 int j。 if (i == 0) return。 //刪除的是頭指針，則返回 p = head。 //將 p指向要刪除的第 i個節(jié)點的前驅(qū)節(jié)點 for (j = 1。 j i amp。amp。 pnext != NULL。 j++) p = pnext。 if (pnext == NULL) //表明鏈表中第 i個節(jié)點不存在 { printf (the %d node not foundt!\n, i)。 return。 } head 70 65 78 90 ∧ 0 1 2 3 4 假設(shè) i = 2 p q = pnext。 //q指向待刪除的節(jié)點 i pnext = qnext 。 //刪除節(jié)點 i free(q)。 //釋放節(jié)點 i的內(nèi)存單元 } p q 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 線性鏈表的基本操作 ? 鏈表的輸出操作 含義： 將鏈表中節(jié)點的數(shù)據(jù)域的值顯示出來。如果在輸出過程中，對數(shù)據(jù)進(jìn)行相應(yīng)的比較，則可實現(xiàn)對鏈表的檢索操作。 基本思想： 通過單鏈表的頭指針 head，使指針 p指向?qū)嶋H數(shù)據(jù)鏈表的第一個節(jié)點，輸出其數(shù)據(jù)值，接著 p又指向下一個節(jié)點，輸出其數(shù)據(jù)值，如此進(jìn)行下去，直到尾節(jié)點的數(shù)據(jù)項輸出完為止，即 p為 NULL為止。 void Display_LinkList(NODE *head) { NODE *p。 for (p = headnext。 p != NULL。 p = pnext) printf (%d , pscore)。 printf (\n)。 } 【 例 】 鏈表輸出操作函數(shù) Display_LinkList 。 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 線性鏈表的基本操作 ? 鏈表的銷毀操作 含義： 將創(chuàng)建的鏈表從內(nèi)存中釋放掉，達(dá)到銷毀的目的 基本思想： 每次刪除頭節(jié)點的后繼節(jié)點，最后刪除頭節(jié)點。注意，不要以為只要刪除了頭節(jié)點就可以刪除整個鏈表 ,要知道鏈表是一個節(jié)點一個節(jié)點建立起來的，所以銷毀它也必須一個一個節(jié)點的刪除才行。 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C void Free_LinkList(NODE *head) { NODE *p, *q。 p = head。 while (pnext != NULL) { q = pnext。 pnext = qnext。 free (q)。 } free (head)。 } 【 例 】 鏈表銷毀操作函數(shù) Free_LinkList 。 head 70 65 78 90 ∧ 0 1 2 3 4 p q q q q ∧ 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 線性鏈表應(yīng)用舉例 【 例 】 建立一個學(xué)生成績的線性鏈表，然后對其進(jìn)行插入、刪除、顯示，最后銷毀該鏈表。 include include struct Grade_Info { int score。 struct Grade_Info *next。 } typedef struct Grade_Info NODE。 NODE *Create_LinkList ( )。 void Insert_LinkList (NODE *head, NODE *pnew, int i)。 void Delete_LinkList (NODE *head, int i)。 void Display_LinkList (NODE *head)。 void Free_LinkList (NODE *head)。 void main ( ) { NODE *head, *pnew。 head = Create_LinkList ( )。 //創(chuàng)建鏈表 if (head == NULL) //創(chuàng)建失敗 return。 printf (after create: )。 Display_LinkList (head)。 //輸出鏈表中的值 //新建一插入的節(jié)點 pnew = (NODE *)malloc (sizeof(NODE))。 if (pnew == NULL) //創(chuàng)建失敗 ,則返回 { printf (no enough memory!\n)。 return。 } pnewscore = 88。 //將新節(jié)點插入節(jié)點 3的后面 Insert_LinkList (head, pnew, 3)。 printf (after insert: )。 Display_LinkList (head)。 //輸出鏈表中的值 Delete_LinkList (head, 3)。 //刪除鏈表中節(jié)點 3 printf (after delete: )。 Display_LinkList (head)。 //輸出鏈表中的值 Free_LinkList (head)。 //銷毀鏈表 } 運(yùn)行結(jié)果 (假設(shè)輸入為： 70 65 78 90 95 85 1 )： after create： 70 65 78 90 95 85 after insert： 70 65 78 88 90 95 85 after delete： 70 65 88 90 95 85 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 聯(lián)合體 ? 構(gòu)造數(shù)據(jù)類型，也叫 共用體 ? 用途： 使幾個不同類型的變量共占一段內(nèi)存 (相互覆蓋 ) 聯(lián)合體類型的定義 union [聯(lián)合體類型名 ] { 數(shù)據(jù)類型名 1 成員名 1； 數(shù)據(jù)類型名 2 成員名 2； … … 數(shù)據(jù)類型名 n 成員名 n； }； 類型定義 不分配內(nèi)存 ch i f 2022 2022 2022 2022 共占 4字節(jié) sizeof(union UData) = sizeof(f) 聯(lián)合體的大小是成員中占內(nèi)存最大的成員的大小 union UData { short i。 char ch。 float f。 }。 ch i f 2022 2022 2022 2022 2022 2022 2022 2022 共占 7字節(jié) struct SData { short i。 char ch。 float f。 }。 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 聯(lián)合體變量的定義和引用 ? 聯(lián)合體變量的定義 形式一 : union data { short i。 char ch。 float f。 } a, b。 形式二 : union data { short i。 char ch。 float f。 }。 union data a, b, *p, d[3]。 形式三 : union { short i。 char ch。 float f。 } a,b,c。 f ch i f ch i a b 共用體 變量任何時刻 只有 一個成員 存在 共用體 變量定義分配內(nèi)存 , 長度 =最長成員 所占字節(jié)數(shù) 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C ? 聯(lián)合體變量的引用 聯(lián)合體變量名 .成員名 聯(lián)合體指針名 成員名 或 (*聯(lián)合體指針名 ).成員名 union data { int i。 char ch。 float f。 }。 union data a, b, c, *p, d[3]。 pi pch pf (*p).i (*p).ch (*p).f d[0].i d[0].ch d[0].f 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 聯(lián)合體變量的賦值 ? 聯(lián)合體變量的初始化賦值 定義聯(lián)合體變量時可以對變量賦初值，但 只能對變量的第一個成員賦初值 ，不可象結(jié)構(gòu)體變量那樣對所有的成員賦初值。 union UData { short i。 char ch。 float f。 }。 union UData data = {10}。 //10賦給成員 i union UData data = {39。A39。}。 //39。A39。賦給成員 i，即 i的值為 65（ 39。A39。的 ASCII碼） union UData data = {10, 39。A39。, }。 //錯誤 ， { }中只能有一個值 union UData data = 10。 //錯誤 ，初值必須用 { }括起來 語言程序設(shè)計教程 第二版 第十一章 復(fù)雜數(shù)據(jù)類型 C 聯(lián)合體變量的賦值 ? 聯(lián)合體變量在程序中賦值 定義了聯(lián)合體變量以后，如果要對其賦值，則只能通過對其成員賦值，不可對其整體賦值 。 具有相同聯(lián)合體類型的變量之間也可以相互賦值。 union UData { short i。 char ch。 float f。 }。 union UData data, *p, d[10]。 data = {10}。 //錯誤 data = 10。 //錯誤 = 10。 //正確，將 10賦給 data的成員 i p = amp。data。 //p指向 data pf = 。 //正確，將 data的成員 f d[0].ch = 39。A39。 //正確，將 39。A39。 賦給 d[0]的成員 ch