单链表操作的相关函数

/******************************************************************************
* 文件：LinearList.h
* 功能：链式存储
* 说明：单链表操作的相关函数
* 时间：2011-4-3
Author: Lzy
*******************************************************************************/

#include <iostream.h>
#include "LinearList.h"

template<class T>
class LinearListLink;                //声明


/********************************************************************
* 类名: LinkNode
* 功能:
* 说明：链式存储节点、与指针域
/********************************************************************/
template<class T>
class LinkNode
{
public:
    friend class LinearListLink<T>;                //LinearListLink定义为友元类

private:
    T data;
    LinkNode<T> *Link;
};

/********************************************************************
* 类名: LinearListLink
* 功能: 链式存储
* 说明：链表的相关操作函数
/********************************************************************/
template<class T>
class LinearListLink : public LinearList<T>                //表头从LinearList派生

{
public:
    LinearListLink(){first = 0;}
    virtual ~LinearListLink();
    virtual bool IsEmpty() const {return first == 0;}
    virtual int Length() const;
    virtual bool Find(int k, T &x) const;
//    virtual int Search(const T &x) const;

    virtual bool Delete(int k, T &x);                //删除第K个元素并将它返回至x

    virtual bool Insert(int k, const T &x);            //在第K个元素之后插入x

    virtual void Output(ostream &out) const;        //输出

//    virtual LinkNode * GetNode(long i);            //返回第i个结点

//    virtual bool Get(LinkNode *node, T &x);        //获取结点值

//    virtual bool Set(LinkNode *node, const T &x);//设置结点值

    virtual LinkNode<T> * GetHead(){return first;}            //获得头结点指针


protected:
    LinkNode<T> *first;                                //指向第一个节点的指针

};

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：~LinearListLink()
* 函数功能：析构函数
* 说    明：用于删除链表中所有节点
/********************************************************************/
template<class T>
LinearListLink<T>::~LinearListLink()
{
    LinkNode<T> *next;
    while(first)
    {
        next = first->Link;                            //下一个结点

        delete first;
        first = next;
    }
}

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：Length()
* 函数功能：返回链表中元素总数
* 说    明：
/********************************************************************/
template<class T>
int LinearListLink<T>::Length() const
{
    LinkNode<T> *current = first;
    int len = 0;
    while(current)
    {
        len++;
        current = current->Link;
    }
    return len;
}

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：Find()
* 函数功能：查表
* 说    明：寻找链表中第K个元素，并将其值送至x
/********************************************************************/
template<class T>
bool LinearListLink<T>::Find(int k, T &x) const
{
    if(k<1)
        return false;
    LinkNode<T> *current = first;
    int index = 0;
    while(index < k && current)        //查找第K个元素，且节点不为空

    {
        index++;
        current = current->Link;
    }

    if(current)
    {
        x = current->data;            //返回第K个元素的值

        return true;
    }
    return false;
}

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：Output
* 函数功能：输出表节点
* 说    明：将链表元素送至输出流
/********************************************************************/
template<class T>
void LinearListLink<T>::Output(ostream &out) const
{
    LinkNode<T> *current;
    for(current = first; current; current = current->Link)    //遍历所有节点

        out<<current->data<<" ";                    //输出

}

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：
* 函数功能：<<重载
* 说    明：
/********************************************************************/
template<class T>
ostream& operator << (ostream &out, const LinearListLink<T> &x)
{
    x.Output(out);
    return out;
}

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：Insert
* 函数功能：元素插入
* 说    明：在第K个节点之后插入x
/********************************************************************/
template<class T>
bool LinearListLink<T>::Insert(int k, const T &x)
{
    if(k < 0)
        throw OutOfBounds();

    LinkNode<T> *p = first;
    for(int index = 1; index < k && p; index++)
        p = p->Link;            //p最终指向第K个节点


    LinkNode<T> *y = new LinkNode<T>;
    y->data = x;                //插入数据


    if(k)
    {
        y->Link = p->Link;
        p->Link = y;            //插在P节点之后

    }
    else
    {
        y->Link = first;
        first = y;                //作为第一个元素插入

    }

    return true;
}

/********************************************************************
* 所属类名: LinearListLink
* 成员名称：Delete
* 函数功能：删除元素
* 说    明：把第K个节点值取至x，然后删除第K个节点
/********************************************************************/
template<class T>
bool LinearListLink<T>::Delete(int k, T &x)
{
    if(k < 1 || !first)                //K>=0,必须不是空表

        throw OutOfBounds();

    LinkNode<T> *p = first;
    if(k == 1)
        first = first->Link;        //p指向第1个元素删除

    else
    {
        LinkNode<T> *q = first;
        for(int index = 1; index < k-1 && q; index++)
            q = q->Link;            //指向第K个节点

        if(!q || !q->Link)            //不存在第K个元素

            throw OutOfBounds();

        p = q->Link;
        q->Link = p->Link;            //从链表中删除该元素

    }
    x = p->data;
    delete p;
    return true;
}

/******************************************************************************
* 文件：单链表测试程序
* 功能：测试程序
* 说明：测试单链表操作的相关函数
* 时间：2011-4-3
Author: Lzy
*******************************************************************************/

#include <iostream.h>
#include "LinearListLink.h"

void main()
{
    LinearListLink<int>L;
    L.Insert(0, 1);            //插入第一个元素

    cout<<"链表长度："<<L.Length()<<endl<<"数据元素："<<L<<endl;

    L.Insert(1, 2);
    L.Insert(2, 3);
    L.Insert(3, 4);
    cout<<"链表长度："<<L.Length()<<endl<<"数据元素："<<L<<endl;

    int z;
    L.Delete(2, z);
    cout<<"删除数据元素："<<z<<endl;
    cout<<"链表长度："<<L.Length()<<endl<<"数据元素："<<L<<endl;

    L.Find(2,z);
    cout<<"找到的数据元素："<<z<<endl;
}