【文章內(nèi)容簡介】 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 20頁 鏈?zhǔn)?存儲結(jié)構(gòu)結(jié)點（數(shù)據(jù)項）最少有兩個域：數(shù)據(jù)域和指針域 。 采用 不連續(xù) 空間存儲線性表，使用 指針 指向下一元素的位置。 單鏈表 H … a4 120 … a5 NULL … a1 240 … a3 110 … a2 210 … 110 … 120 130 … 160 200 … 210 … 240 160 如果用邏輯狀態(tài)圖表示 a1 a2 an ∧ H1 data next 結(jié)點結(jié)構(gòu) 數(shù)據(jù)域 指針域 ∧ H2 空單鏈表 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 21頁 鏈?zhǔn)酱鎯Y(jié)構(gòu)特點 ： ，不需要空間連續(xù)； ，使它們前后之間建立一一對應(yīng)的關(guān)系（即：前趨和后繼的關(guān)系）。 結(jié)點定義如下： typedef struct node { ElemType data。 /* 數(shù)據(jù)域 */ struct node *next。 /* 指針域 */ } LNode， *LinkList； data next 數(shù)據(jù)域 指針域 【說明】 ELEMTP為通用數(shù)據(jù)類型； next 為指向結(jié)構(gòu)體類型的指針，指示下一結(jié)點（后繼，除最后一個元素）所在的位置。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 22頁 頭指針變量定義方法如下： LinkList H。 算法中用到指向某結(jié)點的指針變量時按如下格式進行說明： LNode *p； 則語句： p=(LinkList)malloc(sizeof(LNode))； 聲明后，系統(tǒng)會分配足夠的空間來容納 Linklist結(jié)構(gòu)，同時指針 p指向新的內(nèi)存位置。 p p所指的結(jié)點為 *p， *p的類型為 LNode型，該結(jié)點的數(shù)據(jù)域為 (*p).data或 pdata， 指針域為 (*p).next 或 pnext。 free(p) 則表示釋放指針 p所指向的結(jié)點空間。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 23頁 單鏈表基本運算的實現(xiàn) 1. 建立單鏈表 (1) 在鏈表的頭部插入結(jié)點建立單鏈表 。如 （ 16， 20， 65， 12）的鏈表的建立過程 。 12 ∧ 65 H ∧ H 12 ∧ H 20 12 ∧ 65 H 16 20 12 ∧ 65 H 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 24頁 【算法 】在鏈表的頭部插入結(jié)點建立單鏈表。 LinkList Creat_LinkList1( ) { LinkList H=(LinkList)malloc(sizeof(LNode))。 /* 生成頭結(jié)點 */ H next=NULL； /* 空表 */ LNode *s。 int x。 /* 設(shè)數(shù)據(jù)元素的類型為 int */ scanf(＂ %d＂ ,amp。x)。 while (x!=1) { s=(LinkList)malloc(sizeof(LNode))。 sdata=x。 snext=Hnext。 Hnext=s。 scanf (＂ %d＂ ,amp。x)。 } return H 。 } 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 25頁 (2) 在單鏈表的尾部插入結(jié)點建立單鏈表。 如 （ 16， 20，65， 12）的鏈表的建立過程 。 ∧ H r H r 16 ∧ H r 16 20 ∧ H r 16 20 65 ∧ r H 16 20 65 12 ∧ 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 26頁 【算法 】在鏈表的尾部插入結(jié)點建立單鏈表。 LinkList Creat_LinkList2( ) { LinkList H=(LinkList)malloc(sizeof(LNode))。 H next=NULL； /* 空表 */ LNode *s,*r=H 。 int x。 /* 設(shè)數(shù)據(jù)元素的類型為 int */ scanf(＂ %d＂ ,amp。x)。 while (x!=1) { s= (LinkList)malloc(sizeof(LNode))。 sdata=x。 s next =rnext 。 rnext=s。 r=s。 /*r 指向新的尾結(jié)點 */ scanf(＂ %d＂ ,amp。x)。 } return H 。 } 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 27頁 2. 求表長 算法思路：設(shè)一個指針ｐ和計數(shù)器ｊ ， 初始化使ｐ指向頭結(jié)點H， ｊ =0。 若ｐ所指結(jié)點還有后繼結(jié)點 ， ｐ向后移動 ， 計數(shù)器加 1， 重復(fù)上述過程 ， 直到 pnext==NULL為止 。 【算法 】設(shè) H是帶頭結(jié)點的單鏈表，求帶頭結(jié)點單鏈表的表長。 Status Length_LinkList (LinkList H) { LNode * p= H 。 int j=0。 while(pnext) { p=pnext。 j++； } return j。 } H 16 20 65 12 ∧ 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 28頁 按序號查找第 k 個數(shù)據(jù)元素 LinkList Get_LinkList(LinkList H,int k)。 {LNode *p=H。 int j=0。 while (pnext!=NULL amp。amp。 jk ) { p=pnext。 j++。 } if (j==k) return p 。 else return NULL。 } 60 76 55 90 ∧ 85 p H 例如： i =3: 當(dāng) p指向 85時， j=1； p指向 60時， j=2； p指向 76時， j=3； 退出循環(huán)。 例如： k =6 。 當(dāng) p指向 85時， j=1； … … 當(dāng) p指向 90時， j=5； 再執(zhí)行 p=pnext時， p= NULL， 退出循環(huán)。 【時間復(fù)雜度均為 O(n) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 29頁 鏈表中查找 x 的算法實現(xiàn) LNode * Locate_LinkList( LinkList H, ElemType x) { LNode * p=Hnext。 while(p!=NULL amp。amp。 pdata!=x) p=pnext。 return p。 } 60 76 55 90 ∧ 85 p L 例如：查找 76， p指向 76結(jié)點時，退出 while循環(huán)，返回 p指向的結(jié)點。 【時間復(fù)雜度均為 O(n) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 30頁 4．插入操作 設(shè) p指向單鏈表中某結(jié)點， s指向待插入的新結(jié)點，將 *s插入到 *p的后面。 p x s ① ② x s p q ② ① ③ ① snext=pnext。 ② pnext=s。 將新結(jié)點 *s 插入到 *p 的前面，在插入操作前