本文共 5093 字，大约阅读时间需要 16 分钟。

类定义（这是有头结点的类型）

template
   
    class ChainNode{
       friend Chain
    
     ;private:    T data;    ChainNode
     
       *next;};template
      
       class Chain
       
        {
   public:    Chain();    ~Chain();    bool isEmpty()const{
   return first->data == 0;}    int length()const;    bool find(int k,T& x)const;    int search(const T &x)const;    Chain
        
         & Delete(int k,T& x); Chain
         
          & insert(int k,T& x); void output(Chain
          
           & k);private: ChainNode
           
             *first; //define the first node of the chain which has no message};
           
          
         
        
       
      
     
    
   

分析与总结

• 因为链表能访问任何结点的任何信息，所以需要再结点类ChainNode中，将链表Chain类声明为友类，使得其可以访问其中的任何元素
• 个人认为这样定义就很浪费，为什么不将结点类和链表类进行合并。况且就算如果这样做了，也可以将节点类某个实例对象直接声明链表类的成员，那就不可以不用再进行分配空间，直接再栈中进行分配空间
• 这样设置头结点有一个很大的为题：首先如果所给的数据类型不是整型，那这个头结点就不能用来存放链表的长度。但是如果强制设置为整型，那不就和结点类不一样了吗？
• 给函数命名的时候一定不能，不要使用C++的关键字，delete，是关键字。

构造器和析构函数

template
   
    Chain
    
     ::Chain(){
       first = new ChainNode();    if(first ==NULL)    {
           cout<<"construct the linkedlist absortively!"<
     
      data = 0;    first->next = NULL:}template
      
       Chain
       
        ::~Chain(){
           ChainNode
        
          *temp = first; while(temp) { temp = first->next; delete first; first = temp; } cout<<"deconstruct the linkedlist triumphantly!!"<
        
       
      
     
    
   

分析与总结

• 生成具有的头结点的链表，在初始化方法中，需要将生成头结点，为其申请相关的内存空间，并指明各个相关信息的位置

• 对链表进行清空和对链表进行析构是一样的吗？如果是析构，不应该释放所有的空间吗？为什么你还保留一个头结点。

length和find函数

template
   
    int Chain
    
     ::length()const{
       return first->data;}/*    description:find the element whose value is x                copy the element to the a    caution:the index of the element id from one in the view of user*/template
     
      bool Chain
      
       ::find(int k,T& x)const{
       ChainNode *temp = first;    int i = 0;    //if temp is NULL ,temp->nex t is NULL;    while(temp && i < k)    {
           temp = temp->next;        i ++;    }           if(temp || i < K)    {
           return false;    }    x = temp->data;    return true;    }
      
     
    
   

分析与总结

• 注意“temp = temp->next”，获取某个对象的成员函数的前提是，这个对象并不是空，是存在的，所以这句话之前一定要加上对应的判定语句，确保其不为空。

if(temp){
   }

search函数

/*    description:search the index of x    return:if return 0,x does not exist in the linkedlist*/template
   
    int Chain
    
     ::search(const T& x)const{
       ChainNode
     
       *temp = first->next;    int i = 1;        while(temp)    {
           if(temp->data == x)        {
               return i;        }        i ++;        temp = temp->next;    }        if(temp)    {
           cout<<"the element does not exist!"<
     
    
   

分析与总结

• 当找不到对应的元素的时候，需要进行的返回值的特殊处理。返回为零，说明对应的值不存在

delete

/*    description:delete the element whose index is k,dan copy its value to x*/template
   
    Chain
    
     * Chain
     
      ::delete(int k,T& x){
       ChainNode
      
        *temp = first;    int i = 0    //if temp is NULL ,temp->nex t is NULL;    while(temp && i < k  - 1)    {
           temp = temp->next;        i ++;    }    if(!temp||(!temp->next || i < k - 1))    {
           cout<<"the element you want to delete does not exist!"<
       
         *temp2 = temp->next;    temp->next = temp2->next;    x = temp2->data    delete temp2;	//caution:decrease the length of the linkedlist	first->data --;    return *this;}
       
      
     
    
   

分析与总结

• 凡是调用对应的结点的相关的属性，前提是确保该对象是实际存在的，不为空

  

• 在链表中将对应结点移出逻辑结构的时候，就需要释放相关的空间

• 返回引用的函数，是终止函数直接return ，不要返回return 0
• 判定对应的指针是否为空需要加上否定，老是忘记

• 删除了对应的数据节点，就需要将长度减一，不要忘记。同插入指针一样。

insert和output

/*    description:insert the x after the element whose index is k*/template
   
    Chain
    
     & Chain
     
      ::insert(int k,const T& x){
       ChainNode
      
        *temp = first;    int i = 0    //if temp is NULL ,temp->nex t is NULL;    while(temp && i < k  - 1)    {
           temp = temp->next;        i ++;    }    if(!temp|| i < k - 1))    {
           cout<<"the index you want to insert does not exist"<
       
         *temp2 = new ChainNode
        
         ; temp2->data = x; temp2->next = temp->next; temp->next = temp2; //caution:you should increase the length of the array first->length ++; return *this;}template 
         
          void Chain
          
           ::output(){ //caution：you have refer the index of the next element of the first //so,you should judge if the element does exist if(isEmpty()) { return ; } ChainNode
           
             *temp = first->next; while(temp) { cout<
            
             date<<" "; temp = temp->next; }}
            
           
          
         
        
       
      
     
    
   

分析与总结：

• 创建新的模板类的对象的时候一定加上"",
  
• 是否已经对传入的索引进行了判定，如果索引是不合格的，那就不对了
• 判定是否为空，你怎么想的，为什么会在这个问题上想那么久？
  
• 关于索引的逻辑：对于使用者而言，确实是从1开始的，1就是第一个结点。但是映射到程序里面，需要注意，你的索引起始值和判定索引值的比较，具体是向后移动几次。

测试代码

#include 
   
    #include "linklist.h"using namespace std;int main(){
       cout<<"insert the element!!"<