C++實(shí)現(xiàn)單鏈表的構(gòu)造
本文實(shí)例為大家分享了C++實(shí)現(xiàn)單鏈表的構(gòu)造代碼,供大家參考,具體內(nèi)容如下
單鏈表的構(gòu)造,包括最常用函數(shù),setData(),Insert(),Remove(),getData(),Search()。
代碼如下:
#include <iostream> #include <stdlib.h> using namespace std; template<class T> struct LinkNode{ T data; LinkNode<T> *link; LinkNode(LinkNode<T> *ptr=NULL){link=ptr;} LinkNode(const T& item, LinkNode<T> *ptr=NULL){data=item; link=ptr;} }; template<class T> class List{ public: List(){first=new LinkNode<T>;} List(const T& x){first=new LinkNode<T>(x);} List(List<T> &L); ~List(){makeEmpty();} void makeEmpty(); int Length()const; LinkNode<T> *getHead()const{return first;} LinkNode<T> *Search(T x); LinkNode<T> *Locate(int i); bool getData(int i, T &x)const; void setData(int i,T &x); bool Insert(int i,T &x); bool Remove(int i, T &x); bool IsEmpty()const{return (first->link==NULL)?true:false;} bool IsFull()const{ return false;} void Sort(); void inputFront(T endTag); void inputRear(T endTag); void output(); List<T>& operator=(List<T> &L); private: LinkNode<T> *first; }; template<class T> void List<T>::makeEmpty(){ //if(first->link==NULL)return; LinkNode<T> *p=first->link; while(p!=NULL){ first->link=p->link; delete p; p=first->link; } } template<class T> LinkNode<T> *List<T>::Search(T x){ LinkNode<T> *p=first->link; while(p!=NULL){ if(p->data==x)break; p=p->link; } return p;//無(wú)論是否找到都返回p,若找到則返回p,沒(méi)有則返回空指針 } template<class T> LinkNode<T> *List<T>::Locate(int i){ //這個(gè)定位函數(shù)的作用還是非常大的,方便后來(lái)的函數(shù)根據(jù)i定位到相應(yīng)位置的節(jié)點(diǎn) if(i<0)return NULL; int sum=0; LinkNode<T> *p=first; while(p!=NULL&&sum<i){ sum++; p=p->link; } return p;//無(wú)論是否為空指針,返回的都是到達(dá)i位置的指針,如果沒(méi)有到達(dá)就是已經(jīng)到結(jié)尾了 } template<class T> bool List<T>::getData(int i, T& x)const{ if(i<0)return false; LinkNode<T> *p=Locate(i); if(p==NULL)return false; else{ x=p->data; return true; } } template<class T> void List<T>::setData(int i, T& x){ if(i<0)return; LinkNode<T> *p=Locate(i); if(p==NULL)return; else{ p->data=x; } } template<class T> bool List<T>::Insert(int i, T &x){ //LinkNode<T> *pre=Locate(i-1); //這里是指插入到第i個(gè)元素之后的情況 LinkNode<T> *cur=Locate(i); if(cur==NULL)return false; LinkNode<T> *p=new LinkNode<T>(x); if(p==NULL){cerr<<"存儲(chǔ)分配錯(cuò)誤!"<<endl;exit(1);} //if(pre==NULL||cur==NULL||p==NULL)return false; else{ p->link=cur->link; cur->link=p; return true; } } template<class T> bool List<T>::Remove(int i, T& x){ //刪除第i個(gè)位置的元素 LinkNode<T> *pre=Locate(i-1); if(pre==NULL)return false; LinkNode<T> *current=pre->link; if(current==NULL)return false; x=current->data; pre->link=current->link; delete current; return true; } template<class T> void List<T>::output(){ LinkNode<T> *current=first->link; while(current!=NULL){ cout<<current->data<<" "; current=current->link; } } template<class T> List<T>& List<T>::operator=(List<T>& L){ //這是賦值方法 LinkNode<T> *srcptr=L.getHead(), *p=srcptr->link; LinkNode<T> *desptr=first=new LinkNode<T>; T value; while(p!=NULL){ value=p->data; desptr->link=new LinkNode<T>(value); desptr=desptr->link; p=p->link; } return *this; //用上面這種方法可以更好地實(shí)現(xiàn)賦值 // LinkNode<T> *pre=L.getHead(); // if(pre==NULL){ // first=NULL; // return *this; // } // LinkNode<T> *p=first=new LinkNode<T>; // first->link=p; // int sum=L.Length(); // T &x; // int i=1; // while(i<=sum){ // L.getData(i++,x); // p=new LinkNode<T>(x); // p=p->link; // } // return *this; } template<class T> int List<T>::Length()const{ int sum=0; LinkNode<T> *p=first->link; while(p!=NULL){ sum++; first->link=p->link; delete p; p=first->link; } return sum; } //前插法建立單鏈表 template<class T> void List<T>::inputFront(T endTag){ LinkNode<T> *newNode; T value; makeEmpty(); cin>>value; while(value!=endTag){ newNode=new LinkNode<T>(value); if(newNode==NULL){cerr<<"內(nèi)存分配錯(cuò)誤!"<<endl; exit(1);} newNode->link=first->link; first->link=newNode; cin>>value; } } //后插法建立單鏈表 template<class T> void List<T>::inputRear(T endTag){ LinkNode<T> *newNode=new LinkNode<T>, *last; T value; last=first=new LinkNode<T>; cin>>value; while(value!=endTag){ newNode=new LinkNode<T>(value); if(newNode==NULL){cerr<<""<<endl;exit(1);} last->link=newNode; last=newNode; cin>>value; } } //復(fù)制構(gòu)造函數(shù) template<class T> List<T>::List(List<T> &L){ //復(fù)制構(gòu)造函數(shù) T value; LinkNode<T> *srcptr=L.gethead(), p=srcptr->link; LinkNode<T> *desptr=first->link=new LinkNode<T>; while(p!=NULL){ value=p->data; desptr=new LinkNode<T>(value); desptr=desptr->link; p=p->link; } }
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C語(yǔ)言之關(guān)于二維數(shù)組在函數(shù)中的調(diào)用問(wèn)題
這篇文章主要介紹了C語(yǔ)言之關(guān)于二維數(shù)組在函數(shù)中的調(diào)用問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-07-07C語(yǔ)言實(shí)現(xiàn)數(shù)字炸彈小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)數(shù)字炸彈小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-11-11C++常用函數(shù)總結(jié)(algorithm 頭文件)
本文給大家詳細(xì)介紹了algorithm 頭文件中最常用的函數(shù)及其使用方法,當(dāng)然這只是其中的一部分,algorithm 頭文件中還有很多其他的函數(shù),感興趣的朋友一起看看吧2023-12-12C語(yǔ)言scandir函數(shù)獲取文件夾內(nèi)容的實(shí)現(xiàn)
scandir?函數(shù)用于列舉指定目錄下的文件列表,本文主要介紹了C語(yǔ)言scandir函數(shù)獲取文件夾內(nèi)容的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)鏈表去重的實(shí)例
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)鏈表去重的實(shí)例的相關(guān)資料,這里提供了題目及實(shí)例代碼,需要的朋友可以參考下2017-07-07opencv實(shí)現(xiàn)角點(diǎn)檢測(cè)
這篇文章主要為大家詳細(xì)介紹了opencv實(shí)現(xiàn)角點(diǎn)檢測(cè),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08