雙向循環(huán)鏈表.ppt

《雙向循環(huán)鏈表.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、鏈表指針的方向？2.7雙向鏈表單鏈表？循環(huán)鏈表？單向的優(yōu)點(diǎn)？雙向的雙向鏈表1雙向鏈表雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的鏈表。在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接后繼元素結(jié)點(diǎn),另一個(gè)指向直接前趨元素結(jié)點(diǎn)。2.7雙向鏈表2雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)圖示存儲(chǔ)數(shù)據(jù)元素存儲(chǔ)后繼結(jié)點(diǎn)地址存儲(chǔ)前驅(qū)結(jié)點(diǎn)地址數(shù)據(jù)域data左指針left右指針right2.7雙向鏈表3雙向鏈表結(jié)構(gòu)…a1a2a3an…2.7雙向鏈表left_endright_end雙向鏈表中有指向頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的兩個(gè)指針left_end和right_end。雙向鏈表中雙指針的設(shè)置，可以快速的找

2、到某結(jié)點(diǎn)的前趨和后繼結(jié)點(diǎn)。4雙向鏈表類定義—結(jié)點(diǎn)類templateclassdblist;//前視類定義templateclassdnode{friendclassdblist;//友類聲明private:Typedata;//數(shù)據(jù)dnode*left,*right;//左、右指針};2.7雙向鏈表5雙向鏈表類定義—雙向鏈表類templateclassdblist{private:intn;//表長(zhǎng)度dnode*left_end,*right_end;//表

3、頭,表尾指針public:dblist(){left_end=right_end=0;};//構(gòu)造函數(shù)~dblist();//析構(gòu)函數(shù)boolempty()const{returnn==0;}//測(cè)試表是否為空intsize()const{returnn;}//表的長(zhǎng)度boolretrieve(intk,Type&x)const;//查找表位置k處的元素intlocate(constType&x)const;//計(jì)算元素x在表中的位置dblist&insert(intk,constType&x);//插入結(jié)點(diǎn)dblist&erase(

4、intk,Type&x);//刪除結(jié)點(diǎn)voidprint_list(ostream&out)const;//輸出雙鏈表｝；2.7雙向鏈表6雙向循環(huán)鏈表雙向鏈表通常采用帶表頭結(jié)點(diǎn)的循環(huán)鏈表形式?！環(huán)eadera1a2an…非空表2.7雙向鏈表空表header7雙向循環(huán)鏈表類定義—雙向循環(huán)鏈表類templateclassdbclist{private:intn;//表長(zhǎng)度dnode*header;//表頭,表尾指針public:dbclist();//構(gòu)造函數(shù)~dbclist(){erase();deleteheader};//

5、析構(gòu)函數(shù)voiderase();//刪除表結(jié)點(diǎn)boolempty()const{returnn==0;}//測(cè)試表是否為空intsize()const{returnn;}//表的長(zhǎng)度boolretrieve(intk,Type&x)const;//查找表位置k處的元素intlocate(constType&x)const;//計(jì)算元素x在表中的位置dblist&insert(intk,constType&x);//插入結(jié)點(diǎn)dblist&erase(intk,Type&x);//刪除結(jié)點(diǎn)voidprint_list(ostream&ou

6、t)const;//輸出雙鏈表};2.7雙向鏈表8構(gòu)造函數(shù)—僅頭結(jié)點(diǎn)templatedbclist::dbclist(){dnode*y=newdnode;//申請(qǐng)新結(jié)點(diǎn)yy->left=y;y->right=y;//構(gòu)建雙向循環(huán)鏈header=y;//表中只有一個(gè)哨兵結(jié)點(diǎn)n=0;//空表}空表headery2.7雙向鏈表9析構(gòu)函數(shù)—erase()函數(shù)templatevoiddbclist::erase(){dnode*current;//當(dāng)前結(jié)點(diǎn)dnod

7、e*next;//下一結(jié)點(diǎn)if(header==0)return;//已是空表current=header->right;//current初始化while(!empty()){//若表非空則依次刪除表中結(jié)點(diǎn)next=current->right;deletecurrent;n--;//n實(shí)際控制循環(huán)次數(shù)current=next;}}2.7雙向鏈表headera1a2an……currentnextcurrentnextcurrentnextcurrent10基本思想:從第1個(gè)結(jié)點(diǎn)開始依次向后掃描，直到找到位置k上的元素，并存于x中，且返回ture

8、，位置k無效返回false。查找位置k元素并存于x中