【正文】 LinkList)malloc(sizeof(LNode))。 if (p==NULL) { printf(＂ 插入位置 i錯＂ )。 … H ai1 x ai p ① ② s ③ ④ … 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 32頁 int Insert_LinkList( LinkList H, int i, ElemType x) /* 在單鏈表 H的第 i個位置上插入值為 x的元素 */ { LNode * p,*s。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 31頁 【算法 】將新結(jié)點(diǎn) s插入到第 i個結(jié)點(diǎn)的位置上，即插入到 ai1與ai 之間。 snext=qnext。 q=H。 ② pnext=s。 【時間復(fù)雜度均為 O(n) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 30頁 4．插入操作 設(shè) p指向單鏈表中某結(jié)點(diǎn)， s指向待插入的新結(jié)點(diǎn)，將 *s插入到 *p的后面。 return p。amp。 【時間復(fù)雜度均為 O(n) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 29頁 鏈表中查找 x 的算法實(shí)現(xiàn) LNode * Locate_LinkList( LinkList H, ElemType x) { LNode * p=Hnext。 例如： k =6 。 else return NULL。 j++。amp。 int j=0。 } 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)。 while(pnext) { p=pnext。 Status Length_LinkList (LinkList H) { LNode * p= H 。 若ｐ所指結(jié)點(diǎn)還有后繼結(jié)點(diǎn) ， ｐ向后移動 ， 計數(shù)器加 1， 重復(fù)上述過程 ， 直到 pnext==NULL為止 。 } return H 。 /*r 指向新的尾結(jié)點(diǎn) */ scanf(＂ %d＂ ,amp。 rnext=s。 sdata=x。x)。 int x。 LinkList Creat_LinkList2( ) { LinkList H=(LinkList)malloc(sizeof(LNode))。 如 （ 16， 20，65， 12）的鏈表的建立過程 。 } return H 。 scanf (＂ %d＂ ,amp。 snext=Hnext。 while (x!=1) { s=(LinkList)malloc(sizeof(LNode))。 /* 設(shè)數(shù)據(jù)元素的類型為 int */ scanf(＂ %d＂ ,amp。 /* 生成頭結(jié)點(diǎn) */ H next=NULL； /* 空表 */ LNode *s。 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é)點(diǎn)建立單鏈表。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 23頁 單鏈表基本運(yùn)算的實(shí)現(xiàn) 1. 建立單鏈表 (1) 在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表 。 p p所指的結(jié)點(diǎn)為 *p， *p的類型為 LNode型，該結(jié)點(diǎn)的數(shù)據(jù)域?yàn)? (*p).data或 pdata， 指針域?yàn)? (*p).next 或 pnext。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 22頁 頭指針變量定義方法如下： LinkList H。 /* 數(shù)據(jù)域 */ struct node *next。 H1 data next 結(jié)點(diǎn)結(jié)構(gòu) 數(shù)據(jù)域 指針域 ∧ H2 空單鏈表 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 21頁 鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn) ： ，不需要空間連續(xù)； ，使它們前后之間建立一一對應(yīng)的關(guān)系（即：前趨和后繼的關(guān)系）。 采用 不連續(xù) 空間存儲線性表，使用 指針 指向下一元素的位置。 注意： 與順序存儲結(jié)構(gòu)的不同點(diǎn)是內(nèi)存位置 不一定 相鄰，即每一個數(shù)據(jù)項(xiàng)都有一個鏈接字段，用來存放下一個數(shù)據(jù)項(xiàng)的地址，形成鏈表結(jié)構(gòu)。 } 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 19頁 線性表的鏈?zhǔn)酱鎯瓦\(yùn)算實(shí)現(xiàn) 問題的引入： 規(guī)定 好數(shù)組元素的多少(即數(shù)組長度 )，事先難估計，多了造成浪費(fèi)存儲空間，少了不夠用； ，降低程序執(zhí)行效率。 while(j=Blength) Celem[k++]=Belem[j++]。 else Celem[k++]=Belem[j++]。amp。k=1。 i=1。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 18頁 【例 23】有兩個順序表 A 和 B， 其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表 C， 要求 C 的元素也是從小到大排列。 /*查找失敗 */ else return i。 Lelem[i]!=x) i++。 while(i=Llength amp。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 17頁 4．按值查找 【算法 】在線性表中查找與給定值 x相等的數(shù)據(jù)元素。 } 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 16頁 90 55 78 60 86 例如：刪除元素 75，則90和 55兩個元素應(yīng)向前移。 Llength。j=Llength1。 return ERROR 。 a1 a2 … ai1 ai ai+1 … an a1 a２ … ai1 ai+1 … an 1 2 … i1 i i+1 n1 n n+1 刪除算法 int Delete_SeqList(SeqList *L, int i) { int j。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 15頁 3. 刪除運(yùn)算 刪除第 i個元素， i 的取值范圍為：1≤ i≤n 。設(shè)在第 i個位置上作插入的概率為 Pi， 則平均移動數(shù)據(jù)元素的次數(shù)： 設(shè)： Pi=1/ (n+1) ， 即為等概率情況，則： ??????????????11112)1(11)1(E niniiinninninp這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。 i的取值范圍為 ： 1≤i≤n+1 即有 n＋ 1個位置可以插入。 /* 插入成功，返回 */ } 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 13頁