数据结构书上例子

 

//List.h#include
      
       #include 
       
        using namespace std;template 
        
         struct LinkNode{    T data;    LinkNode
         
           *link;    LinkNode
          
            (LinkNode
           
             *ptr=NULL) {link=ptr;} LinkNode
            
              (const T& item,LinkNode
             
               *ptr=NULL) { data=item;link=ptr;}};template 
              
               class List{public: List() //初始化 {first=new LinkNode
               
                ;} List(const T& x){first = new LinkNode
                
                 (x);} List(List
                 
                   &L); ~List(){makeEmpty();} void makeEmpty(); //置空 LinkNode
                  
                   * getHead() const { return first;} LinkNode
                   
                     *Search(T x); //查找x LinkNode
                    
                      *Locate(int i); //寻找第i个节点 bool getData(int i, T & x); //第i个节点的值赋给x bool Insert(int i, T& x); //第i个位置插入i bool IsEmpty()const { return first->link==NULL?true:false;} bool Sort(); //排序 bool input(); //输入数据 List
                     
                       &operator=(List
                      
                        &L); //重载= friend ostream& operator << 
                       
                         (ostream& out,List
                        
                          &L); //重载<< friend istream&operator >> (istream&in,List
                         
                           &L) { LinkNode
                          
                            *p,*q; T a; L.makeEmpty(); p=L.getHead(); while(!in.eof()) { in>>a; q=new LinkNode
                           
                            (a); p->link=q; p=q; } p->link=NULL; return in; } //重载>>protected: LinkNode
                            
                              *first;};template
                             
                              ostream& operator << (ostream& out,List
                              
                                &L){ LinkNode
                               
                                 *q=L.first->link; while(q!=NULL) { out<
                                
                                 data<
                                 
                                  link; } return out;};template 
                                  
                                   List
                                   
                                    ::List(List
                                    
                                      &L){ T value; LinkNode
                                     
                                       *stcptr=L.getHead(); LinkNode
                                      
                                        *destptr=first=new LinkNode
                                       
                                        ; while(stcptr->link!=NULL){ value=stcptr->link->data; destptr->link=new LinkNode
                                        
                                         (value); destptr=destptr->link; stcptr=stcptr->link; } destptr->link=NULL;};template
                                         
                                          void List
                                          
                                           ::makeEmpty(){ LinkNode
                                           
                                             *q; while(first->link!=NULL){ q=first->link; first->link=q->link; delete q; }};template
                                            
                                             LinkNode
                                             
                                              * List
                                              
                                               ::Search(T x){ LinkNode
                                               
                                                 *current=first->link; while(current!=NULL){ if(current->data==x) break; else current=current->link; } return current;};template
                                                
                                                 LinkNode
                                                 
                                                  * List
                                                  
                                                   ::Locate(int i){ if(i<0) return NULL; LinkNode
                                                   
                                                    * current=first; int k=0; while(current!=NULL&&k
                                                    
                                                     link; k++; } return current;};//取出链表第i个元素值template
                                                     
                                                      bool List
                                                      
                                                       ::getData(int i, T&x){ if(i<=0) return false; LinkNode
                                                       
                                                        *current=Locate(i); if(current==NULL) return false; else { x=current->data; return true; }};template 
                                                        
                                                         bool List
                                                         
                                                          ::Insert(int i,T&x){ LinkNode
                                                          
                                                           *current=Locate(i); if(current==NULL) return false; LinkNode
                                                           
                                                             *newnode=new LinkNode
                                                            
                                                             (x); if (newnode==NULL) { cout<<"error"<
                                                             
                                                              link=current->link; current->link=newnode; return true;};template
                                                              
                                                               List
                                                               
                                                                & List
                                                                
                                                                 ::operator=(List
                                                                 
                                                                  & L){ T value; LinkNode
                                                                  
                                                                    *srcptr =L.getHead(); LinkNode
                                                                   
                                                                    *destptr=first=new LinkNode
                                                                    
                                                                     ; while(srcptr->link!=NULL) { value=srcptr->link->data; destptr->link=new LinkNode
                                                                     
                                                                      (value); destptr=destptr->link; srcptr=srcptr->link; } destptr->link=NULL; return *this;};template
                                                                      
                                                                       bool List
                                                                       
                                                                        ::Sort(){ LinkNode
                                                                        
                                                                          *q; LinkNode
                                                                         
                                                                           *p=first; T x1,x2; int N=0; while(p->link!=NULL) { N++; p=p->link; } while (N==1) { cout<<"the list is kongde"<
                                                                          
                                                                           i;j--) { getData(j-1,x1); getData(j,x2); if(x1>x2) { p=Locate(j-1); q=Locate(j); p->data=x2; q->data=x1; } } }};template
                                                                           
                                                                            bool List
                                                                            
                                                                             ::input(){ T x; LinkNode
                                                                             
                                                                              *current=getHead(); cout<<"输入数据（以0结束）"<
                                                                              
                                                                               >x; while(x!=0){ LinkNode
                                                                               
                                                                                 *node=new LinkNode
                                                                                
                                                                                 (x); node->link=current->link; current->link=node; cin>>x; } return true;}//main.cpp#include
                                                                                 
                                                                                  #include 
                                                                                  
                                                                                   #include"List.h"using namespace std;int main(){ List
                                                                                   
                                                                                     list; int x; int i; cout<<"测试输入"<
                                                                                    
                                                                                     >i; cin>>x; if(!list.Insert(i,x)) cout<<"插入失败"<
                                                                                     

list1(list); cout<<"链表如下："<

>i; LinkNode

*current=list.Search(i); if (!current) { cout<<"不存在"<

>i; current->data=i; } cout<<"链表如下："<

list2; ifstream sin("data.txt");/* cout<<"输入文件名和路径"<

>list2; cout<<"链表如下："<

#include

#include"List.h"using namespace std;int main(){ cout<<"测试从文本读取"<