时间戳

首页 > 技术文章 > 第二章 线性表——单链表操作

第二章 线性表——单链表操作

19991201xiao 2018-04-03 23:08 原文

#include <iostream>
using namespace std;
template <typename T>
struct Node
{
    T data;
    Node * next;
};
template<typename T>
class LinkList
{
    public:
        LinkList(T a[],int n=0);    //有参构造函数，建立有n个元素的单链表 
        ~LinkList();                //析构函数 
        bool IsEmpty();
        int Length();                    //求链表的长度 
        T GetNode(int i);             //按位查找。在单链表中查找第i个结点的元素值 
        int LocateNode(T x);          //按值查找。在单链表中查找值为x的元素序号 
        LinkList<T> & Insert(int i,T x);   //插入操作，在低i个位置插入值为x的元素 
        LinkList<T> & Delete(int i);          //删除操作，删除序号为i的结点 
        void ShowList();                //遍历操作，按序号依次输出各元素 
    private:
        Node<T>*head;           //单链表的头指针 
};
template<typename T>
//单链表遍历算法 ShowList 
void LinkList<T>::ShowList()
{
    Node<T> * p;
    p=head;                        
    while(p->next)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}
template<class T>
//求线性长度算法 Length 
int LinkList<T>::Length()
{
    int n=0;
    Node<T> * p;
    p=head;
    while(p->next)
    {
        p=p->next;
        n++;
    }
    return n;
}
template<typename T>
//单链表按位查找算法 Get 
T LinkList<T>::GetNode(int i)
{
    if(i<1 || i>Length()+1)
    {
        cout<<"非法位置，终止运行！"<<endl;
        exit(1);
    }
    else
    {
        int j=1;
        Node<T> *p;
        p=head->next;
        while(j!=i)
        {
            p=p->data;
            j++;
        }
        return p->data;
    }
}
template<class T>
//单链表按值查找算法 Locate
int LinkList<T>::LocateNode(T x)
{
    int n=0;
    Node<T> *p;
    p=head;
    while(p->next)
    {
        p=p->next;
        n++;
        if(p->data==x)return n;
    }
    return 0;
 }
 template<class T>
 //单链表插入算法 Insert 
 LinkList<T>&LinkList<T>::Insert(int i,T x)
 {
     if(i<1||Length()+1)
     {
         cout<<"非法位置，终止运行"<<endl;
        exit(1); 
     }
     else
     {
         int j=0;
         Node<T> *p,*q;
         p=head;
         while(p->next&&j<i-1)
         {
             p=p->next;
             j++;
         }
         q=new Node<T>;
         q->data=x;
         q->next=p->next;
         p->next=q;
     }
     return *this;
 }
 template<typename T>
 //头插法建立单链表 LinkList
 LinkList<T>::LinkList(T a[],int n)
 {
     Node<T> *p;
    head=new Node<T>;
    head->next=NULL;
    for(int i=0;i<n;i++)
    {
        p=new Node<T>;
        p->data=a[i];
        p->next=head->next;
        head->next=p;
     }
  }
  template<typename T>
 //尾插法建立单链表 LinkList
 /*LinkList<T>::LinkList(T a[],int n)
 {
     Node<T> *p,*r;
     head=new Node<T>;
     r=head;
     head->next=NULL;
     for(int i=0;i<n;i++)
     {
         p=new Node<T>;
         p->data=a[i];
         r->next=p;//将新结点插到终端结点的后面 
         r=p;//尾指针指向新结点 
     }
     r->next=NULL; 
  }*/
  //template<typename T>
  //单链表删除操作 Delete
  LinkList<T>&LinkList<T>::Delete(int i)
  {
      if(IsEmpty())
      {
          cout<<"空链表，不能删除！"<<endl;
          exit(1);
      }
    if(i<1 || i>Length())
    {
        cout<<"非法位置，终止运行"<<endl;
        exit(1);
        }
    else
    {
        int j=0;
        Node<T> *p,*q;
        p=head;
        while(i>0 && p->next)
        {
            p=p->next;
            i--;
        }
        q=p->next;
        p->next=q->next;
        delete q;
    }
    return *this;
   }
   template<typename T>
   LinkList<T>::~LinkList()
   {
       Node<T> *p,*q;
       p=head;
       while(p)
       {
           q=p;
           p=p->next;
           delete q;
       }
   }
   //判断链表是否为空 
   template<typename T>
   bool LinkList<T>::IsEmpty()
   {
       return(Length()==0);
   }
   int main()
   {
       int a[5]={1,2,3,4,5};
       LinkList list;
    list(int a,int 5);
    list.ShowList();
    return 0;
   }

 

推荐阅读