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