【文章內容簡介】 ndl。return 0。}（一）學習鏈表的建立過程，關鍵是掌握3個指針的作用。頭指針head永遠指向鏈表的第一個結點；對q指針，永遠讓它指向鏈表的最末一個結點；指針p每次都指向一個待插入的結點，且這個結點要插到q結點的后面。先使用語句qnext=p，接著讓q指針指向剛插入的的p結點，使用q=p讓q永遠指向鏈表的最末一個結點，使用qnext=NULL，這樣就能把p解放出來，又可去指向待插入的下一個結點。（二）學習鏈表的插入過程，需要用到4個指針：pHead，pNode，r，q。讓pHead永遠指向鏈表的第一個結點，pNode指向待插入的結點，讓r和q為一前一后兩個同步移動的指針，用來查找pNode結點的正確位置。一開始讓r指向鏈表頭，讓q指向相鄰的下一個結點，即r=pHead。q=pHeadnext。之后就比較pNode結點和q結點的num值。如果pNodenumqnum。說明尚未找到正確的插入點!讓r和q同步后移一個結點，即r=q。q=qnext。如果pNodenum=qnum；則將pNode結點插入到r結點后q結點之前，即rnext=pNode。pNodenext=q。帶頭結點單鏈表的C++完整描述includeincludecstdiotemplateclass datatypeclass NODE{ public:datatype data。NODEdatatype *next。}。templateclass datatypeclass LIST{ private:NODEdatatype *head。public:LIST(){ head=new NODEdatatype。headnext=NULL。}。int length()。bool isempty(){ return headnext==NULL?true:false。}bool get_data(int i,datatype amp。x)。bool get_succ(int i,datatype amp。x)。bool get_prior(int i,datatype amp。x)。bool replace_data(int i,const datatype x)。bool insert_data(datatype datd,int i)。bool delete_data(int i)。bool find_data(datatype x,datatype amp。result)。void print_list()。~LIST(){ NODEdatatype *p。while(head){ p=head。head=headnext。delete p。}}}。templateclass datatypeint LISTdatatype::length(){ int counter=0。NODEdatatype *current。current=headnext。while(current!=NULL){ current=currentnext。counter++。}return counter。}templateclass datatypebool LISTdatatype::get_data(int i,datatype amp。x){ NODEdatatype *current。int j=1。if((i1)||(ilength())){ cout非法位置讀取元素，不能讀取!endl。return false。}current=headnext。while(current!=NULL){ j++。current=currentnext。}x=currentdata。return true。}templateclass datatypebool LISTdatatype::get_succ(int i,datatype amp。x){ NODEdatatype *current。int j=1。if((i1)||(ilength())){ cout非法位置讀取元素!不能讀取!endl。return false。}current=headnext。while(current!=NULLamp。amp。ji){ j++。current=currentnext。}if(currentnext!=NULL){ x=currentnextdata。return true。}else{ cout第i個元素無后繼，不能讀取!endl。return false。}}templateclass datatypebool LISTdatatype::get_prior(int i,datatype amp。x){ NODEdatatype *current,*previous。int j=1。if((i1)||(ilength())){ cout非法位置讀取元素，不能讀取!endl。return false。}previous=head。current=headnext。while(current!=NULLamp。amp。ji){ j++。previous=current。current=currentnext。}if(previous!=head){ x=previousdata。return true。}else{ cout第i個元素無前驅，不能讀取!endl。return false。}}