带头结点的单链表的实现

链表结点数据类型的定义

//链表结点数据类型的定义 
template<typename T> 
struct Node 
{ 
     T data;
       Node<T> *next; 
};

 单链表的实现

//单链表的实现 
template<typename T> 
class LinkList{ 
    public: 
        LinkList(T a[],int n) 
        { 
            first=new Node<T>; 
            first->next=NULL; 
            } 
            ~LinkList(); 
            int Length(); 
            T Get(int i); 
            int Locate(T x); 
            void Insert(int i,T x); 
            T Delete(int i); 
            void PrintList(); 
            private: 
                Node<T> *first;//单链表的头指针 
};

单链表的构造—-头插法

//单链表的构造----头插法 
template<typename T> 
LinkList::LinkList(T a[],int n) 
{ 
    first=new Node<T>;//生成头结点 
    first->next=NULL; 
    Node<T> *s; 
    for(int i=0;i<n;i++)
    { 
        s=new Node<T>; 
        s->data=a[i]; 
        s->next=first->next; 
        first->next=s; 
    } 
}

单链表的构造—-尾插法

//单链表的构造----尾插法 
template<typename T> 
LinkList::LinkList(T a[],int n) 
{ 
    Node<T> *r,*s;//尾指针 
    first=new Node<T>;//生成头结点 
    r=first;//建空表 
    for(int i=0;i<n;i++) 
    { 
        s=new Node<T>; 
        s->data=a[i];//为每一个数组元素建立一个结点 
        r->next=s; 
        r=s;//插入到终端结点之后 
    } 
}

单链表的遍历

//单链表的遍历
template<typename T>
LinkList::PrintList()
{
    Node<T> *p;
    p=first->next;
    while(p)
    {
        cout<<p->data;
        p=p->next;
    }
}

单链表中按位置查找

 //单链表中按位置查找
 template<typename T>
 LinkList::Get(int i)
 {
     Node<T> *p;
     int j;
     p=first->next;
     j=1;
     while(p&&j<i)
    {
        p=p->next;//工作指针后移
        j++;
    }
    if(!p)
        throw "位置";
    else
        return p->data;
}

单链表的插入操作(按位置进行插入)

 

//单链表的插入操作(按位置进行插入)
template<typename T>
LinkList::Insert(int i,T x)
{
    Node<T> *p;//工作指针p初始化
    int j;
    while(p&&j<i-1)
    {
        p=p->next;//查找第i-1个结点,并使工作指针p指向该结点
        j++;
    } if(!p)
    throw "位置";//若查找不成功,说明位置错误,抛出异常
    else{
        Node<T> *s;//否则,生成一个元素值为x的新结点s
        s=new Node<T>;
        s->data=x;//将s插入到p之后
        s->next=p->next;
        p->next=s;
        }
}

单链表中的结点删除(删除结点是i的结点)

//单链表中的结点删除(删除结点是i的结点)
template<typename T>
LinkList::Delete(int i)
{
    Node<T> *p;
    int j;
    p=first;//工作指针p初始化,累加器j清0,p要指向头结点
    j=0;
    while(p&&j<i-1)//查找第i-1个结点并使工作指针p指向该结点
    {
        p=p->next;
        j++;
    }
    if(!p||!p->next)
        throw "位置";//若p不存在或p的后继结点不存在,抛出异常
    else{
        Node<T> *q;
        T x;
        q=p->next;
        x=q->data;//否则暂存被删结点和被删元素
        p->next=q->next;//摘链
        delete q;//释放被删结点
        return x;
        }
}

析构函数

//析构函数
template<typename T>
LinkList::~LinkList()
{
    Node<T> *q;
    while(first)
    {
        q=first->next;
    delete first;
    first=q;
    }
}

发布者

deng

听闻余生久不遇,相逢别错过。

发表评论

电子邮件地址不会被公开。 必填项已用*标注