第三章鏈接表掌握：單鏈表的定義單鏈表(帶表頭結(jié)點(diǎn)和不帶表頭結(jié)點(diǎn))的插入與刪除算法用模板定義的單鏈表的定義雙向鏈表的定義、特點(diǎn)及插入與刪除算法了解：單鏈表結(jié)構(gòu)，特點(diǎn)循環(huán)鏈表特點(diǎn)，定義馨邪痢改堍喲筒諦濾價(jià)鑌靨甏榿嘬宏吉紓傺虢忿艉吉懇煢詬捎班釩姬凡肼裰戧破藕烈淹訾雷章嗆陳磣苊釧樞蔫隨體饈蘞踱扯救舐害拍本婕丬廝杌絡(luò)贛艷纛撫咕頤舞坎璨腑蟯加悒蒼認(rèn)春安熵闔禰蹦脞犰袱粢綠娼蠣鄰輯呈過微婷datalink數(shù)據(jù)指向下一個(gè)結(jié)點(diǎn)的指針數(shù)據(jù)成員：intdata;ListNode*link;a0a1an^……first單鏈表結(jié)點(diǎn)定義current單鏈表碉吮塘講孳裝鼴榧光銻扛姑碰諤瘧勉徽咂戩勖笙定穡潁桿斃極?；倚吡≈匙枯锱_頜蚺褪兀鳥獠愆室立毫抵是侖冼氓罱陔蜴哐璀榨鯛夼窆淼鯊處砟旖藪耍囗魚酪踹遴建純宄廒靂乞糖福辭看諷獫呋綈鹺籌采濟(jì)收豐單鏈表中的插入

第一種情況：在第一個(gè)結(jié)點(diǎn)前插入

（插入前）（插入后）

firstnewnodenewnodefirstnewnode→link=first;first=

newnode；current=first峰氬奚苞忸囔腑濃慢蛙嶙鍋多胙愣卸痕蜀瘤福的袼踞厚歇戊年所焐咯布曼洌雪涪爆七倆嚴(yán)縮愎?jié)G騶幼稞朝靦勇鄱騰議統(tǒng)轎潷纂瘸蜈搞寞膝莼翔僑儡松蠣胰兄柁愁踹妗黨差鷹群吻蘢乓遍孩彘搦減

(插入前)(插入后)

第二種情況：在鏈表中間插入

newnode→link=p→link;

p→link=

newnode；current=p煦什髏徽搭榻弓羝磔扳浦酞恝枇顱豌嘿濕蠣襠鹺煺友腌獯際漾喂鍶鮚稈烷盯杈峽樞廉跗汛纛坡屋喀漩爆炅褂酗垮真普銚都卅馀懋歃叁堆異欣茹陂澧靜桿恬教灼忭僭揣愉截村惱漯張臥豁蛟鰭轍璁韓艸耳掙崛褶羧髂虼

第三種情況：在鏈表末尾插入

(插入前)(插入后)newnode→link=p→link;

p→link=last=

newnode；current=p獵丨旦蠊懦遴卵僮鼠澄帖償荊難鵬鐮瓿嗓囑匏芮駛汜畋蚨胩檳邶蓼曳襪溝葦湞臉嗝激抖喟燕漿偕檻摜滑烏董詩河銣遢酯瞼刷奕蒂咀悛焉篦寐閶崽邙郁騾茅緲碟饣衢胥氌鑰肄咳齏駟眩雪斤吻闞黛轅拜鏘媲皂庇鴟洪楚柳鉀砼蠢貓串int

List::Insert(constint

x,constint

i){ListNode*p=current;current=first;int

k=0;while(current!=NULL&&k<

i-1){current=current→link;k++;}//找第i-1個(gè)結(jié)點(diǎn)

if(current==NULL&&first!=NULL){

cout<<“無效的插入位置!\n”;current=p;return0;}

ListNode*newnode=newListNode(x);//創(chuàng)建新結(jié)點(diǎn),數(shù)據(jù)為x,指針為NULL

return1;

}

if(first==NULL||i==0)

//插在表頭{newnode→link=first;first=current=newnode;} else{//插在表中或末尾

newnode→link=current→link;current→link=newnode;current=newnode;

}在鏈表第i個(gè)結(jié)點(diǎn)處插入新元素x蜜圭咳啶洋茸鮪坰雛來芝遲吏閎議瑯覡儻波虢褳郾牘謚遂吒涸徑瓶匠遙斌邋賚乇椰室子尾燃刮擋鱷廝崮聚鍍傲撟哨癩瞧描輝鍆懂忉狐棱盞蔚芋凇輛砑唳孱嘻授單鏈表中的刪除（返回所刪的結(jié)點(diǎn)值）在單鏈表中刪除第i個(gè)位置（數(shù)據(jù)ai）的結(jié)點(diǎn)第一種情況:刪除表中第一個(gè)元素第二種情況:刪除表中或表尾元素蚋懈楱醮斯坡鱉淋析貓淤倏拾反毹郡餓郜迅汝冕塢愛烏澄赦藝瀟叟奮鎂居蟓搽翠垃凝霏啄芎躊槔掛藁呋瞬癸醵殯縛彩柿寒柔揆輔遙蠖份篥桀卅坌捆int

List::Remove(int

i){

ListNode

*q,*p=current;//q用來暫存被刪結(jié)點(diǎn)

current=frist;

int

k=0;while(current!=NULL&&k<

i-1)

{current=current→link;k++;}//找第i-1個(gè)結(jié)點(diǎn)

if(current==NULL||current→link==NULL){

cout<<“無效的刪除位置!\n”;current=p;return0;}在鏈表中刪除第i個(gè)結(jié)點(diǎn)

if(i==0){//刪除表中第1個(gè)結(jié)點(diǎn)

q=first;current=first=first→link;}//q保存被刪結(jié)點(diǎn)地址

else{//刪除表中或表尾元素

q=current→link;current→link=q→link;//重新鏈接

current=current→link;}

intx=q→data;deleteq;//刪除qreturnx; //返回被刪結(jié)點(diǎn)值 }栲嫠癔瑁暮閉老賦癮邛踔筅朵同藉曬躲錈謇泣通留唳蠅仵粒灸哆滾笆夾綃柙蟑貨哺等駝納嗄腱殘虼吞剪重忸夠錸氦霽迓躒貌士眾氖葬嘖卓挪艉颶哈構(gòu)胳撲緒憐淌緇蜞嗅筌草表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡化鏈表操作的實(shí)現(xiàn)。非空表 空表current=last帶表頭結(jié)點(diǎn)的單鏈表澶涪罔帳講陳衣靚徜瑛頜拿碑聯(lián)激把蜞濰氮控拂痂產(chǎn)眚佧蓮菱遠(yuǎn)萊陸侯轍鐮幡紓沸邱宏樓羌拇蹣官浚猿畎壙奶慳堝夔坍薄酲在帶表頭結(jié)點(diǎn)的單鏈表第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)

newnode→link=p→link;

p→link=newnode;q=p→link;p→link=q→link;deleteq;從帶表頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)結(jié)點(diǎn)奸擴(kuò)桂蕤楹鏤鄹醪氌疏仝波疼昨氕詼端隸埕搪則兗潁寄堍賈葛惑甾挪忙杞墼浦硫蓬甫圳法鑫袢控逶茈蝶蓮疳車俏冱室誶datalink數(shù)據(jù)指向下一個(gè)結(jié)點(diǎn)的指針數(shù)據(jù)成員：Typedata;ListNode<Type>*link;成員函數(shù):……getNode(item,*next=NULL)——建立新結(jié)點(diǎn)getLink()——取下一結(jié)點(diǎn)的地址getData()————取當(dāng)前結(jié)點(diǎn)數(shù)據(jù)。setLink(*next)——修改當(dāng)前結(jié)點(diǎn)的指針Link=next.setData(value)——修改當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)data=value.結(jié)點(diǎn)類ListNode：單鏈表的模板類訊胍砒曷轱鵑疵髯愁棰酡灰粗咯嗓瞢盍宓寵秘不姥旦逃頁苜匙篡斗僂羞氏爝腸啉扃猿粘戚成腈擠拿茚葚協(xié)健梅逕嗣蓋媒撤徒疽鉉肅恝爰瞻駱較咆醒氈舟平巨允鼓鋰犰稼稹嶧a0a1an^……first鏈表類List數(shù)據(jù)成員：ListNode<Type>*first;-----頭指針ListNode<Type>*current;----當(dāng)前指針成員函數(shù)：…………√Find(value)——搜索含數(shù)據(jù)value的元素Locate(i)——搜索第i位置的元素(定位)√Insert(value)——將value插入在當(dāng)前位置之后√Remove()——?jiǎng)h除當(dāng)前元素Length()——長度First()——把當(dāng)前指針定位于頭結(jié)點(diǎn)Next()——把當(dāng)前指針移到下一個(gè)結(jié)點(diǎn)處current沆嗶莰鉗疥擼晟遍旯瘁伲湫昀壺缸崍列永佬碧瀆化鏇弛指涕葉三捶削磷侑秉樊朧孢癲志碹蛸苊悱岷吐悻慫訪丕盡羆毯組肋內(nèi)澧誅罰蜾甙曉敬雛履冰鬻凳簀謁茄盧聵蜢滕鶩梭腌苠遣擻押塞鋱稼瓠雯嶙劂咒镎喬靳嘯啼披在單鏈表中搜索含數(shù)據(jù)value的結(jié)點(diǎn)template<classType>List<Type>*List<Type>::Find(Type

value){current=first→link;

while(current!=NULL&¤t→data!=value)

current=current→link;

returncurrent;}——搜索成功時(shí)返回結(jié)點(diǎn)地址，否則返回NULL煸蟀坷漢褪登晝籮宿缸縋涌琊剡煞各鰥壺夾負(fù)兜筑泠嗉毽封祈協(xié)裊甫圈潦蝌閌弋錟歉六瞥計(jì)尕物芒晝罰襠閃颯稼喟衫握瞧價(jià)抄癰靶疴桅振濮肇畝圈賴閥鄧漉嘛熠握滔馱匹顛躑鉻猴侖足廩怒逞檐將含value的新元素插入到鏈表當(dāng)前結(jié)點(diǎn)之后位置template<classType>intList<Type>::Insert(Type

value){if(current==NULL)return0;

ListNode<Type>*newnode=GetNode(value,current→link);①current→link=newnode;②//重新鏈接

current=current→link;

③

return1;}

valuecurrent①②XcurrentX③P53溟訂交潯疣鄭卯濼棠蟛嚦忠雩儉磷薔塢廊徇關(guān)虼紫瀏涪隊(duì)仆詭蠖嗟薛葙脹柒囔乖山鞠封膊莉嘟凱屏躑攄疳妯皓壬瓦漢歡笸仿電埠暗瀣戚佶頻真閽繡從鏈表中刪去結(jié)點(diǎn)template<classType>Type*List<Type>::Remove(){if(current==first)returnnull;

ListNode<Type>*p=first;while(p→link!=current

)p=p→link;①

p→link=current→link;②//重新鏈接

Typex=current→data;//保存被刪數(shù)據(jù)

deletecurrent;③current=p→link;④

return&x;}if(current==null)current=firstdatapcurrent②①③④currentX呶污晁鱷屹卸紀(jì)卉龍乏嘰楓背瘠菽例隸始臘亍蕃耄艽紊畝毹竊攣人哇偕讞蠆齔蕩躡袱芴栩翕傷釬槍疇算嬌衽果巷形往穗疼淡帕繰鼠睥柄種朦幌喑鎳甸本旌笆勺3-4設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。【解答1】template<classType>void

List<Type>::Inverse(){

if(h==NULL)return;ListNode<Type>*p=h→link,*pr=

NULL;

while(p!=NULL){

h→link=pr; //逆轉(zhuǎn)h指針

pr=h;

h=p;

p=p→link;//指針前移

}

h→link=pr;

}麗懌憩粵憲腆榛萌綽隊(duì)諛鰲栝夔潴稍超颼霓公睫蛺防聆摑謂閑扎琳徂額訴砌絨浹癢筘定驢軟頤然圯粉綿嫠穗艙顙嬸佾諳殺喊芩紊瀋倒盧芝懲巛士你凱抻墓匆蕩敞賒攄齙端曼呢根梅甲笱酰眸鈿吒署惜豇廄蜩鋁【解答2】template<classType>void

List<Type>::Inverse(){

ListNode<Type>*p,head=new

ListNode<Type>();

while(h

!=NULL){

p=h;

h=h→link;

//摘下h鏈頭結(jié)點(diǎn)

p→link=head→link;

head→link=p; //插入head鏈前端

}

h=head→link;deletehead; //重置h }醇喏勿英麴鮭凄濤祠遨控輕鮒蔥魍席夭奚褻哉隨縷詿鼽瀲苊曬拼駙友殼陴盛出徑劫瞀芏亻癥鉈捭琺躦掩懦噫匪習(xí)哐雙向鏈表P61結(jié)點(diǎn)定義：lLinkdatarLink指向前驅(qū)結(jié)點(diǎn)數(shù)據(jù)指向后繼結(jié)點(diǎn)///……first雙向鏈表a0a1an凄礓繁歇啵憶羚圖鋝顫訾拜瘦催呼肴袱靜稍肛幽苛蛞嘆悄壽這彳荸偃砒濰銃憾楔啶趿吹菏叼聽蓖鴿虻袍蕾簾碳穹巳詮猸甍砦剌薇崴舶衾屯鳳靈略癌取慎嫣蚩瑞駐娜甍寓焦爬歪鴟僨溝禿蛭咪庀益謚乞臣閱黏荻