資源描述:
《鏈表的建立、合并與拆分C++》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、2鏈表的建立、合并與拆分【實(shí)驗(yàn)簡(jiǎn)介】鏈表是用鏈接存儲(chǔ)的方式來(lái)表達(dá)線性表,它用指針表示結(jié)點(diǎn)間的邏輯關(guān)系,鏈表適用于插入或刪除頻繁,存儲(chǔ)空間需求不定的情形?!緦?shí)驗(yàn)內(nèi)容】定義一個(gè)鏈表存儲(chǔ)的線性表,除已給出的表元素插入、刪除、查找等基本操作外,再提供表的合并、拆分和逆置等操作。在應(yīng)用程序中建立兩個(gè)整型的單鏈表對(duì)象A和B,應(yīng)用線性表的基本操作對(duì)表的實(shí)例對(duì)象進(jìn)行操作測(cè)試。1.設(shè)線性鏈表A=(a1,a2,…,am),,B=(b1,b2,…bn),按下列規(guī)則合并A,B為線性表C的算法,即使得C=(a1,b1,…,am,
2、bm,b(m+1),…,bn)當(dāng)m<=n或C=(a1,b1,…,an,bn,a(n+1),…,am)當(dāng)m>nC表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。2.將C表原地逆置。3.將C表的中偶數(shù)和奇數(shù)分別鏈接為兩個(gè)循環(huán)鏈表D和E。說明:每一次合并、拆分和逆置等操作的結(jié)果均要輸出。【主要代碼】6#include#includeclassList;structLinkNode//定義一個(gè)結(jié)點(diǎn),有數(shù)據(jù)域和指針域{intdata;LinkNode*link;LinkNode(Li
3、nkNode*ptr=NULL)//構(gòu)造函數(shù){link=ptr;}LinkNode(constint&item,LinkNode*ptr=NULL)//構(gòu)造函數(shù){data=item;link=ptr;}};classList//線性鏈表類{protected:LinkNode*first;public:List(){first=newLinkNode();}//構(gòu)造函數(shù)List(constint&x){first=newLinkNode(x);}//帶一個(gè)整型參數(shù)的構(gòu)造函數(shù)List(List&L);//
4、復(fù)制構(gòu)造函數(shù)Listjishu(List&L);//存放數(shù)據(jù)為奇數(shù)的線性鏈表函數(shù)Listoushu(List&L);//存放數(shù)據(jù)為偶數(shù)的線性鏈表函數(shù)voidmakeEmpty();//將線性鏈表置空~List(){makeEmpty();}//析構(gòu)函數(shù)voidsetData(inti,int&x);//給線性鏈表的第i個(gè)結(jié)點(diǎn)賦值xboolgetData(inti,int&x);//獲取線性鏈表的第i個(gè)結(jié)點(diǎn)的值,并把他存儲(chǔ)在變量x里L(fēng)inkNode*Locate(inti);//定位線性鏈表的第i個(gè)結(jié)點(diǎn),
5、并返回該結(jié)點(diǎn)的指針LinkNode*getHead()const{returnfirst;}//獲取線性鏈表的頭指針intLength()const//求線性鏈表的長(zhǎng)度{LinkNode*p=first->link;intcount=0;while(p!=NULL){p=p->link;count++;}returncount;}boolInsert(inti,int&x);//在第i個(gè)元素后插入xvoidinput();//在鏈表里面輸入值。voidoutput();//輸出鏈表里面的元素。voidn
6、izhi();//將線性鏈表逆置voidfenList(List&a,List&b);//將線性鏈表拆分為兩個(gè)鏈表,其中a鏈//表存放原鏈表中數(shù)據(jù)域?yàn)槠鏀?shù)的結(jié)點(diǎn),b鏈表存放原鏈表中數(shù)據(jù)域?yàn)榕紨?shù)的鏈表LinkNode*search();//搜索x在線性鏈表中的位置,函數(shù)返回表項(xiàng)序號(hào)boolRemove(int&x);6//將鏈表中第i個(gè)結(jié)點(diǎn)的元素刪除Listhebing(List&A,List&B);//合并鏈表的函數(shù),并按照題目要求的順序合并voidxunhuan();//把一個(gè)線性單鏈表置為循環(huán)線性鏈
7、表};List::List(List&L)//復(fù)制構(gòu)造函數(shù){intvalue;LinkNode*srcptr=L.getHead();LinkNode*destptr=first=newLinkNode;while(srcptr->link!=NULL){value=srcptr->link->data;destptr->link=newLinkNode(value);destptr=destptr->link;srcptr=srcptr->link;}destptr->link=NULL;}ListL
8、ist::jishu(List&L)//存放數(shù)據(jù)為奇數(shù)的鏈表{intvalue;LinkNode*srcptr=L.getHead();LinkNode*destptr=first=newLinkNode;while(srcptr->link!=NULL){if(srcptr->link->data%2!=0){value=srcptr->link->data;destptr->link=newLinkNode(value);destptr