第2章之線(xiàn)性鏈表(編輯修改稿)
2024-11-03 16:22 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 位置 ,使指針 p指向 ai1 step2 申請(qǐng)并生成新結(jié)點(diǎn) s step3 使 s插入到 ai1和 ai之間 示例 下一頁(yè) 上一頁(yè) 停止放映 [第 20頁(yè) /41] void Insert(LinkListamp。 head, int i, ElemType x) { if(i1) cout不存在第 i個(gè)位置 。 else { LNode *p=head。 //p最終將指向第 i1個(gè)結(jié)點(diǎn) int k=0。 //p目前指向第 0個(gè)結(jié)點(diǎn) (頭結(jié)點(diǎn) ) while( p!=NULLamp。amp。ki1 ) { p=pnext。 k++。 } if(p==NULL) cout i超出鏈表最大位置 。 else { LNode *s=new LNode。 //建立新結(jié)點(diǎn) s sdata = x。 snext=pnext。 //定義結(jié)點(diǎn) s的指針域 pnext=s。 //修改結(jié)點(diǎn) p的指針域 } } } 插入算法 C++源程序 下一頁(yè) 上一頁(yè) 停止放映 [第 21頁(yè) /41] （ 4） 在單鏈表中查找數(shù)據(jù)值為 x的結(jié)點(diǎn) 返回指向第 i個(gè)結(jié)點(diǎn)的指針 。 單鏈表查找算法操作步驟 : step1 初始化 ,指針 P指向頭指針 step2 P非空且當(dāng)前值不為 x的循環(huán) step3 每循環(huán)一次 ,P后移一個(gè)位置 step4 循環(huán)結(jié)束 ,返回指向 ai的指針 P，或空指針 。 下一頁(yè) 上一頁(yè) 停止放映 [第 22頁(yè) /41] Lnode * Find( LinkListamp。 head, ElemType x ) { LNode *p=headnext。 //p指向第一個(gè)結(jié)點(diǎn) while ( p!=NULL amp。amp。 pdata!=x ) //尋找 x循環(huán) p = pnext。 //指針右移 if((p!=NULL)amp。amp。(pdata==x )) return p。 //找到了，返回地址 else return NULL。 //沒(méi)找到返回空指針 } 查找算法 C++源程序 下一頁(yè) 上一頁(yè) 停止放映 [第 23頁(yè) /41] 其他形式的鏈表 鏈表檢索只能從頭指針開(kāi)始 ,且只能順鏈表方向移動(dòng)。 在單鏈表中 ,從表的任一結(jié)點(diǎn) ai找其前趨結(jié)點(diǎn) ,時(shí)間復(fù)雜度是 O（ n）。 如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是單循環(huán)鏈表 。 鏈表可以從兩個(gè)方向檢索，效果更佳；這就是 雙向循環(huán)鏈表 。 下一頁(yè) 上一頁(yè) 停止放映 [第 24頁(yè) /41] 單循環(huán)鏈表 單循環(huán)鏈表表示形式： head ... head a1 a2 an 單循環(huán)鏈表為空的條件 : head next=head 表示形式為 : 下一頁(yè) 上一頁(yè) 停止放映 [第 25頁(yè) /41] 單循環(huán)鏈表特點(diǎn) ? 從表中任一結(jié)點(diǎn)出發(fā) ,均可以找到表中其它結(jié)點(diǎn)。 ? 找其前趨結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（ n）。 下一頁(yè) 上一頁(yè) 停止放映 [第 26頁(yè) /41] 雙向循環(huán)鏈表 ? 在單向循環(huán)鏈表中，也存在檢索前趨結(jié)點(diǎn)費(fèi)時(shí)的問(wèn)題（所需時(shí)間是 O（ n））。 ? 雙向循環(huán)鏈表，其存儲(chǔ)結(jié)構(gòu)： typedef struct DNode { ElemType data。 //數(shù)據(jù)域 struct DNode *prior， *next。 // 指針域 } *LinkList。 下一頁(yè) 上一頁(yè) 停止放映 [第 27頁(yè) /41] 雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu) prior data next 指向后繼結(jié)點(diǎn) 指針域 數(shù)據(jù)域 指向前趨結(jié)點(diǎn) 指針域 下一頁(yè) 上一頁(yè) 停止放映 [第 28頁(yè) /41] 雙向循環(huán)鏈表表示形式 雙向循環(huán)鏈表表示形式： head head ... ...
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1