鏈表的建立、合并與拆分 C++

《鏈表的建立、合并與拆分 C++》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2鏈表的建立、合并與拆分【實驗簡介】鏈表是用鏈接存儲的方式來表達線性表，它用指針表示結(jié)點間的邏輯關(guān)系，鏈表適用于插入或刪除頻繁，存儲空間需求不定的情形?！緦嶒瀮?nèi)容】定義一個鏈表存儲的線性表，除已給出的表元素插入、刪除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在應用程序中建立兩個整型的單鏈表對象A和B，應用線性表的基本操作對表的實例對象進行操作測試。1.設線性鏈表A=(a1,a2,…,am),，B=(b1,b2,…bn)，按下列規(guī)則合并A，B為線性表C的算法，即使得C=(a1,b1,…,am,bm,b(m+1),…,bn)當m<=n或C=(a1,b1,…,an,b

2、n,a(n+1),…,am)當m>nC表利用A表和B表中的結(jié)點空間構(gòu)成。2.將C表原地逆置。3.將C表的中偶數(shù)和奇數(shù)分別鏈接為兩個循環(huán)鏈表D和E。說明：每一次合并、拆分和逆置等操作的結(jié)果均要輸出?！局饕a】6#include#includeclassList;structLinkNode//定義一個結(jié)點,有數(shù)據(jù)域和指針域{intdata;LinkNode*link;LinkNode(LinkNode*ptr=NULL)//構(gòu)造函數(shù){link=ptr;}LinkNode(constint&item,LinkNode*ptr=NUL

3、L)//構(gòu)造函數(shù){data=item;link=ptr;}};classList//線性鏈表類{protected:LinkNode*first;public:List(){first=newLinkNode();}//構(gòu)造函數(shù)List(constint&x){first=newLinkNode(x);}//帶一個整型參數(shù)的構(gòu)造函數(shù)List(List&L);//復制構(gòu)造函數(shù)Listjishu(List&L);//存放數(shù)據(jù)為奇數(shù)的線性鏈表函數(shù)Listoushu(List&L);//存放數(shù)據(jù)為偶數(shù)的線性鏈表函數(shù)voidmakeEmpty();//將線性鏈表置空~List(){m

4、akeEmpty();}//析構(gòu)函數(shù)voidsetData(inti,int&x);//給線性鏈表的第i個結(jié)點賦值xboolgetData(inti,int&x);//獲取線性鏈表的第i個結(jié)點的值,并把他存儲在變量x里LinkNode*Locate(inti);//定位線性鏈表的第i個結(jié)點,并返回該結(jié)點的指針LinkNode*getHead()const{returnfirst;}//獲取線性鏈表的頭指針intLength()const//求線性鏈表的長度{LinkNode*p=first->link;intcount=0;while(p!=NULL){p=p->link;

5、count++;}returncount;}boolInsert(inti,int&x);//在第i個元素后插入xvoidinput();//在鏈表里面輸入值。voidoutput();//輸出鏈表里面的元素。voidnizhi();//將線性鏈表逆置voidfenList(List&a,List&b);//將線性鏈表拆分為兩個鏈表,其中a鏈//表存放原鏈表中數(shù)據(jù)域為奇數(shù)的結(jié)點,b鏈表存放原鏈表中數(shù)據(jù)域為偶數(shù)的鏈表LinkNode*search();//搜索x在線性鏈表中的位置,函數(shù)返回表項序號boolRemove(int&x);6//將鏈表中第i個結(jié)點的元素刪除Listh

6、ebing(List&A,List&B);//合并鏈表的函數(shù),并按照題目要求的順序合并voidxunhuan();//把一個線性單鏈表置為循環(huán)線性鏈表};List::List(List&L)//復制構(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=s

7、rcptr->link;}destptr->link=NULL;}ListList::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