【C++】線性表——單向連結清單V1.0（源碼提供）

我把連結清單的源代碼貼到這裡（隻提供結點類（node）和連結清單類（Linklist）的定義的頭檔案（.h），其他.cpp測試檔案使用者可自行編寫、調用、測試），假如你在單向連結清單上遇到了問題，我的blog也有幸被你Google或者百度到了，那希望我的這個連結清單代碼能夠幫助你。假如你發現代碼中還存在一些問題，請及時留言給我，大家共同提高。 這個單向連結清單包含大多數常用的成員函數，以便于使用者輕松調用。 /*線性表——單向連結清單V1.0* Coded by Arthur Yoo*/ #ifndef NODE_H #define NODE_H #include<iostream> using namespace std; template <class type>class linklist; template <class type>class node { friend class linklist<type>; public: node(node<type> *p=NULL);//構造頭結點 node(const type &d,node<type> *p=NULL);//構造非頭結點 ~node(); void Setdata(type x);//修改資料 type data; private: node<type> *next; }; template <class type> node<type>::node(node<type> *pp) { next=pp; } template <class type> node<type>::node(const type &d,node<type> *pp) { next=pp; data=d; } template <class type> node<type>::~node() { } template <class type> void node<type>::Setdata(type x) { data=x; } template <class type>class linklist { public: linklist(); ~linklist(); int Getlength() const;//傳回結點數目 type Getcur() const;//傳回目前結點的值 type Get(int i);//傳回第i結點的值 void Set(int i,type const &x);//給第i号元素設定值 int Isempty() const;//判斷是否為空連結清單 void Freelist();//釋放連結清單 void Clearlist();//此函數有問題！此函數有問題！此函數有問題！此函數有問題！此函數有問題！此函數有問題！此函數有問題！ void Insertbef(const type &x);//在目前結點之前插入一個新結點 void Insertaft(const type &x);//在目前結點之後插入一個新結點 void Deletecur();//删除目前結點，并自動填補 node<type> *Locate(type &x);//搜尋值為X的節點，并使之成為目前結點 node<type> *Setcur(int i);//設定第i号結點為目前結點 node<type> *Setnextcur();//目前結點指向下一結點 void Showlist() const; int Isend() const;//判斷是否為尾節點 void AddOrdered();//将連結清單内的值按從大到小順序排列 void Merge(linklist<type> &b);//将本連結清單（已經遞增排序） 與另一已遞增排序的連結清單合并（合并後的連結清單即為本連結清單） private: node<type> *head; node<type> *cur; }; template<class type> linklist<type>::linklist() { head=cur=new node<type>; head->next=NULL; } template<class type> linklist<type>::~linklist() { Freelist(); } template<class type> int linklist<type>::Getlength() const//傳回結點數目 { node<type> *pp=head->next; if(head->next==NULL) return 0; int len=0; while(pp!=NULL) { pp=pp->next; len++; } return len; } template<class type> type linklist<type>::Getcur() const //傳回目前結點的值 { if(cur==head || cur==NULL) {cerr<<"未找到資料。"<<endl;exit(1);} return cur->data; } template<class type> int linklist<type>::Isempty() const //判斷是否為空連結清單 { if(head->next==NULL) return 1; else return 0; } template<class type> void linklist<type>::Freelist() //釋放連結清單 { Clearlist(); delete head; } template<class type> void linklist<type>::Clearlist() { node<type> *pp,*qq; pp=head->next; while(pp!=NULL) { qq=pp; pp=pp->next; delete qq; } cur=head; } template<class type> void linklist<type>::Insertbef(const type &x) //在目前結點之前插入一個新結點 { if(head->next==NULL) { node<type> *newnode=new node<type>(x,NULL); head->next=cur=newnode; } else { node<type> *newnode=new node<type>(x,cur); node<type> *pp=head; while(pp->next!=cur) pp=pp->next; pp->next=newnode; cur=newnode; } } template<class type> void linklist<type>::Insertaft(const type &x) //在目前結點之後插入一個新結點 { if(head->next==NULL || cur==NULL) { node<type> *newnode=new node<type>(x,head->next); head->next=cur=newnode; } else { node<type> *newnode=new node<type>(x,cur->next); cur->next=newnode; cur=newnode; } } template<class type> void linklist<type>::Deletecur()//删除目前結點，并自動填補 { if(cur==head || cur==NULL){cerr<<"不可以删除。"<<endl;exit(1);} else { node<type> *pp=head; while(pp->next!=cur) { pp=pp->next; } pp->next=cur->next; delete cur; cur=pp->next; cout<<"删除目前結點成功！"<<endl; } } template<class type> node<type> *linklist<type>::Locate(type &x) //搜尋值為X的節點，并使之成為目前結點 { cur=head->next; while(cur!=NULL) { if(cur->data==x) break; else cur=cur->next; } return cur; } template<class type> node<type> *linklist<type>::Setcur(int i) //設定第i号結點為目前結點 { if(head==NULL || i<0) return NULL; if(i==0) {cur=head;return head;} int mm=0; cur=head->next; while(mm<i && cur!=NULL) { cur=cur->next; mm++; } return cur; } template<class type> node<type> *linklist<type>::Setnextcur() //目前結點指向下一結點 { if(cur->next!=NULL) cur=cur->next; return cur; } template<class type> void linklist<type>::Showlist() const { if(head->next==NULL) cout<<"此連結清單為空連結清單！"<<endl; else { node<type> *pp=head->next; cout<<pp->data; pp=pp->next; while(pp!=NULL) { cout<<"->"<<pp->data; pp=pp->next; } cout<<endl; } } template<class type> int linklist<type>::Isend() const //判斷是否為尾節點 { if(cur->next==NULL) return 1; else return 0; } template<class type> void linklist<type>::Set(int i,type const &x) { cur=head; int j; for(j=0;j<i;j++) cur=cur->next; cur->data=x; } template<class type> type linklist<type>::Get(int i) { int j;cur=head; for(j=0;j<i;j++) cur=cur->next; return cur->data; } template<class type> void linklist<type>::AddOrdered() { int i,j,n,flag=1; n=this->Getlength(); type temp; for(i=2;i<n+2 && flag==1;i++) { flag=0; for(j=1;j<n+2-i;j++) { if(this->Get(j)>this->Get(j+1)) { flag=1; temp=this->Get(j); this->Set(j,this->Get(j+1)); this->Set(j+1,temp); } } } } template<class type> void linklist<type>::Merge(linklist<type> &b) { node<type> *pa,*pb,*p,*q; pa=head->next; //pa指向本連結清單鍊頭 pb=b.head->next;//pa指向b連結清單的鍊頭 head->next=NULL;//本連結清單初始化 while(pa!=NULL && pb!=NULL) //從pa/pb裡取出小的結點，鍊入新連結清單 { if(pa->data <= pb->data) { q=pa;pa=pa->next; } else { q=pb;pb=pb->next; } q->next=head->next; head->next=q; } if(pa==NULL) {p=pb;} //開始處理未取完元素的那條剩餘連結清單 else {p=pa;} while(p!=NULL) //将剩餘的連結清單鍊入本連結清單 { q=p;p=p->next; q->next=head->next; head->next=q; } } #endif