数据结构c++单链表的实现及相关操作

分手后的思念是犯贱 2023-10-05 21:22 52阅读 0赞

## 1.无参构造函数——单链表的初始化 ##

template<typename DataType>
    LinkList<DataType>::LinkList()
    {
        
       frist=new Node<DataType>;
       frist->next=nullptr;
    }

## 2.判空操作 ##

单链表的判空操作只需判断单链表是否只有头结点，即判断frist->next是否为空。

## 3.遍历操作 ##

template<typename DataType>
    void LinkList<DataType>::PrintList()
    {
        
       Node<DataType> * p=frist->next;   //工作指针p初始化
       while(p!=nullptr)
       {
        
          cout<<p->data<<"\t";
          p=p->next;                     //指针后移
       }
       cout<<endl;
    }

4.求单链表的长度

template<typename DataType>
    int LinkList<DataType>::length()
    {
         
       Node<DataType> * p=frist->next;
       int count=;
       while(p!=nullptr)ype
       {
        
          p=p->next;
          count++;
       }
       return count;
    }

## 5.按位查找 ##

template<typename DataType>
    DataType LinkList<DataType>::Get(int i)
    {
        
        Node<DataType> * p=frist->next;
        int count=1;
        while(p!=nullptr && count<i)
        {
        
           p=p->next;
           count++;
        }
        if(p==nullptr)
        throw"查找位置错误";
        else
        return p->data;
    }

## 6.按值查找 ##

template<typename DataType>
    int LinkList<DataType>::Locate(DataType x)
    {
        
       Node<DataType> * p=frist->next;
       int count=1;
       while(p!=nullptr)
       {
        
         if(p->data==x)
         return count;
         p=p->next;
         count++;
       }
       return 0;
    }

## 7.插入操作 ##

template<typename DataType>
    void LinkList<DataType>::Insert(int i,DataType x)
    {
        
      Node<DataType> * p=frist,*s=nullper;
      int count=0;
      while(p!=nullptr && count<i-1)
      {
        
         p=p->next;
         count++;
      }
      if(p==nullptr)
      throw"插入位置错误";
      else
      {
        
        s=new Node<DataType>;
        s->data=x;
        s->next=p->next;
        p->next=s;
      }
    }

## 8.删除操作 ##

template<typename DataType>
    DataType LinkList<DataType>::Delete(int i)
    {
         
       DataType x;
       Node<DataType> * p=frist,*q=nullptr;
       int count=0;
       while(p!=nullptr && count<i-1)
       {
        
         p=p->next;
         count++;
       }
       if(p==nullptr || p->next==nullptr)
       throw"删除位置错误";
       else{
        
       q=p->next;       //将a2删除，这是就要把a1的指针指向a3
       x=p->data;
       p->next=q->next; //使指向a2的指针指向a3
       delete q;
       return x;
       }
    }

## 9.析构函数——销毁单链表 ##

template<typename DataType>
    LinkList<DataType>::~LinkList()
    {
        
       Node<DataType> * p=frist;
       while(frist!=nullptr)
       {
        
          frist=frist->next;
          delete p;
          p=frist;
       }
    }

## 10.构造函数——建立单链表 ##

(1).头插法

template<typename DataType>
    LinkList<DataType>::LinkList(DataType a[],int n)
    {
        
       frist=new Node<DataType>;
       frist->next=nullptr;             //初始化一个空链表
       for(int i=;i<n;i++)
       {
        
         Node<DataType> * s=nullptr;
         s=new Node<DataType>;
         s->data=a[i];
         s->next=frist->next;
         frist->next=s;
         }
    }

(2).尾插法

template<typename DataType>
    LinkList<DataType>::LinkList(DataType a[],int n)
    {
        
      frist=new Node<DataType>;
      Node<DataType> * r=frist;
      * s=nullptr;
      for(int i=0;i<n;i++)
      {
        
       s=new Node<DataType>;
       s->data=a[i];
       r->next=s;
       r=s;
      }
      r->next=nullptr;
    }