通過定義一個C++類封裝單鏈表這種數據結構,
封裝的方法有:
1.通過輸入創建單鏈表;
2.獲取單鏈表的數據元素個數;
3.打印輸出單鏈表中各個元素;
4.搜索某個元素在單鏈表中的位置;
5.在某個位置之後插入一個結點;
6.在某個位置刪除一個節點;
7.單鏈表逆置;
8.單鏈表是否存在回環的判定;
9.單鏈表的升序排序;
10.兩個單鏈表的升序合並;
11.兩個單鏈表的降序合並。
注:單鏈表的排序采用的是快速排序的方法。
下面是C++寫的程序代碼,附運行截圖。
#include#include #include using namespace std; typedef struct node //結點類型 { int data;//數據域 node* next;//指針域 }node; class LinkList//單鏈表類的定義 { public: LinkList(int N=0)//但參數構造函數,生成含N個元素的鏈表(不包括頭結點) { CreateList(N); len=GetLength(); } node* head;//頭結點指針 int len;//元素個數 public: void CreateList(int n);//根據輸入創建單鏈表 int GetLength();//獲取單鏈表的長度(元素個數) void PrintList();//打印單鏈表的各個元素 int SearchNode(int data);//查找某個元素在單鏈表中的位置,不過不存在,返回0。 bool InsertNode(int pos,int data);//在pos位置後插入值為data的節點 bool DeleteNode(int pos);//刪除pos位置後的第一個元素,刪除成功返回true. void Reverse();//將單鏈表逆置 bool IsLoop();//判斷單鏈表中是否存在會換,存在返回真,不存在返回false void SelfASOrder();//將鏈表中元素升序排列 void ASCMerge(LinkList& L);//與另一個鏈表升序合並 void DESCMerge(LinkList& L);//與L鏈表降序合並 private: void QuikSort(node* start,node* end); }; void LinkList::CreateList(int n)//根據輸入創建單鏈表 { head = new node; head->data=0; head->next=NULL; node *p,*q; int temp; q=head; while(n--) { cin>>temp; p=new node; p->data=temp; p->next=NULL; q->next=p; q=p; p=NULL; } q=NULL; delete q; } void LinkList::PrintList()//打印單鏈表的每一個元素 { len=GetLength(); int l=len; node* p=head->next; while(l--) { cout< data<<" "; p=p->next; } p=NULL; delete p; cout< next)!=NULL) { l++; p=p->next; } return l; } int LinkList::SearchNode(int data)//查找某個元素在單鏈表中的位置,如果不存在這個元素,返回0 { int locate=0; node *p=head->next; while(len--) { if(p->data==data) { locate=10-len; break; } p=p->next; } return locate; } bool LinkList::InsertNode(int pos,int data)//插入節點 { len=GetLength(); if(pos>len)//插入位置超出范圍 return false; node* p=head->next; if(0==pos) { p=head; node* q = new node; q->data=data; q->next=p->next; p->next=q; p=NULL; q=NULL; delete p; delete q; len++; return true; } else { pos=pos-1; while(pos--) { p=p->next; } node* q = new node; q->data=data; q->next=p->next; p->next=q; p=NULL; q=NULL; delete p; delete q; len++; return true; } } bool LinkList::DeleteNode(int pos) { len=GetLength(); if(pos>=len) return false; node* p=head; pos=pos-1; while(pos--) { p=p->next; } node* q=p->next; p->next=p->next->next; delete q; q=NULL; len++; return true; } void LinkList::Reverse() { node *p,*q,*r; if(head->next==NULL) { return; } p=head->next; q=p->next; p->next=NULL; while(q!=NULL) { r=q->next; q->next=p; p=q; q=r; } head->next=p; } bool LinkList::IsLoop() { node *p=head->next; node* q=head->next->next; while((q!=NULL)&&(p!=q)) { p=p->next; q=q->next->next; } if(p==q) return true; else return false; } void LinkList::SelfASOrder()//升序排列,采用快速排序的方法 { node* start,*end; int len=GetLength(); start=head->next; end=start; while((end->next)!=NULL) end=end->next; QuikSort(start,end); } void LinkList::QuikSort(node* start,node*end) { if(start==end) return; int Len=0; node* st=start; node* en=end; while(st!=en) { st=st->next; Len++; } double x=Len/2.0; double xL=floor(x); double xU=ceil(x); double HalfLen=x; int L=xL; int U=xU; node* mid=start; node* midl=start; while(U--) { mid=mid->next; } while(L--) { midl=midl->next; } node* s=start; node* m=mid; int flag=0; for(int i=0;i data)>(m->data)) { s->data^=m->data;//交換 m->data^=(s->data); s->data^=(m->data); } s=s->next; m=m->next; } QuikSort(start,midl); QuikSort(mid,end); } void LinkList::ASCMerge(LinkList& L) { this->SelfASOrder(); L.SelfASOrder(); node* q=(L.head)->next; node* p=head->next; int position=0; while((p!=NULL)&&(q!=NULL)) { if(q->data data) { InsertNode(position,q->data); q=q->next; position++; } else { p=p->next; position++; } } position=GetLength(); while(q!=NULL) { InsertNode(position,q->data); q=q->next; position++; } } void LinkList::DESCMerge(LinkList& L) { ASCMerge(L); Reverse(); } int main() { LinkList L(10); cout<<"Input the L1 List:"< >DataSearch; cout< >DataInsert; cout<<"Input the position to insert:"< >PosInsert; if(L.InsertNode(PosInsert,DataInsert)) { cout<<"Insert successfully! The new list is:"; L.PrintList(); } else cout<<"Insert Failed!"< >PosDel; if(L.DeleteNode(PosDel)) { cout<<"Delete successfully! The new list is:"; L.PrintList(); } else { cout<<"Delete Failed!"< 運行截圖