Chinaunix首页 | 论坛 | 博客
  • 博客访问: 631835
  • 博文数量: 1008
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 5175
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-31 09:44
文章分类
文章存档

2012年(1008)

我的朋友

分类:

2012-08-01 11:08:44

原文地址:C++单链表 作者:luozhiyong131

/*

 * C++单链表实现函数

 * Lzy     2011-七夕

 */

 

#include

using namespace std;

 

template <class T>

class LinearListLink;       //前向声明

 

 

template <class T>

class LinkNode                //定义模板类链表节点

{

private:

    T data;                    //数据域

    LinkNode<T> *next;       //指针域

public:

    friend class LinearListLink<T>;          //声明LinearListLink为友元类

};

 

template <class T>

class LinearListLink

{

protected:

    LinkNode<T> *head;               //头指针

public:

    LinearListLink();

    bool IsEmpty() const {return head->next==NULL;}  //链表是否为空

    int Length() const;                              //返回链表长度

    bool Find(int k, T &x);          //寻找链表中第K个元素

    int Search(const T &x) const;           //按值查找元素的位置

    LinkNode<T> * GetNode(int i);            //返回第i个结点

    bool Insert(int k, const T &x);            //在第K个位置插入x

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

    void Output() const;                      //输出

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

    ~LinearListLink(){delete head;};

};

 

/*

 * 链表元素输出

 */

template <class T>

void LinearListLink<T>::Output() const

{

    LinkNode<T> *current = head->next;     //指向第一个节点

 

    while(current)                            //指针是否指向链表尾

    {

        cout<<current->data<<" ";

        current = current->next;         //指针沿链表移动

    }

}

 

/*

 *   功能:删除第K个元素并将它返回至x

 */

template <class T>

bool LinearListLink<T>::Delete(int k, T &x)

{

    LinkNode<T> *current = GetNode(k-1);     //找到第k个节点前一个节点

    if(current)

    {

        LinkNode<T> *p = current->next;

        x = p->data;                  //弹出数据

        current->next = p->next;             //数据插入

        delete p;                      //释放空间

 

        return true;

    }

 

    return false;

}

 

/*

 * 功能:在第K个位置插入x

 */

template <class T>

bool LinearListLink<T>::Insert(int k, const T &x)

{

    LinkNode<T> *current = GetNode(k-1);     //找到第k个节点前一个节点

    if(current)

    {

        LinkNode<T> *p = new LinkNode<T>;

        p->data = x;                  //保存数据

        p->next = current->next;

        current->next = p;               //数据插入

 

        return true;

    }

 

    return false;

}

 

/*

 * 功能:寻找链表中第i个元素

 *       返回第i个节点地址

 */

template <class T>

LinkNode<T> * LinearListLink<T>::GetNode(int i)

{

    if(i < 0 || i > Length())               //检查K是否合法

    {

        cout<<"GetNode: "<<i<<"无效"<<endl;

        return NULL;

    }

 

    LinkNode<T> *current = head;        //指向头节点,头节点标号为0

    for(int index = 0; index < i && current; index++)

    {

        current = current->next;         //指针沿链表移动

    }

 

    if(current)

    {

        return current;

    }

    else

    {

        cout<<"没有: "<<i<<"数据"<<endl;

        return NULL;

    }

}

 

/*

 * 功能:寻找链表中第K个元素

 *       并将其值送至x

 */

template <class T>

bool LinearListLink<T>::Find(int k, T &x)

{

    LinkNode<T> *current = GetNode(k);     //指向第k个节点

    if(current)

    {

        x = current->data;                   //返回第k个位置的节点值

        return true;

    }

    else

        return false;

}

 

/*

 * 功能:按值查找元素在链表中的位置

 */

template <class T>

int LinearListLink<T>::Search(const T &x) const

{

    if(IsEmpty() == true)

    {

        cout<<"ListLink is Empty"<<endl;

        return 0;

    }

 

    LinkNode<T> *current = head->next;     //指向第一个节点

    int index = 1;

 

    while(current && current->data != x)

    {

        current = current->next;         //指针沿链表移动

        index++;

    }

 

    if(current)

    {

        return index;

    }

    else

    {

        cout<<"没有: "<<x<<"数据"<<endl;

        return false;

    }

}

 

/*

 * 功能:计算链表长度

 * 出口参数:链表长度

 */

template <class T>

int LinearListLink<T>::Length() const

{

    LinkNode<T> *current = head->next;     //指向第一个节点

    int len = 0;

 

    while(current)                            //指针是否指向链表尾

    {

        current = current->next;         //指针沿链表移动

        len++;                             //计数加一

    }

    return len;                               //返回链表长度

}

 

/*

 * 构造函数初始化链表头

 */

template <class T>

LinearListLink<T>::LinearListLink()

{

    head = new LinkNode<T>;

    head->next = NULL;

}

 

/*

 * 测试程序

 */

int main(void)

{

    LinearListLink<int> L;

    L.Length();

 

    for(int i=1; i<20; i++)              //插入数据

        L.Insert(i,i);

 

    L.Output();

    cout<<endl;

 

    cout<<"链表长度"<<L.Length()<<endl;

    cout<<"数据为13的位置 "<<L.Search(13)<<endl;

 

    L.Insert(9,20);                       //在弟9个位置插入20

    int i;

    L.Find(9,i);

    cout<<"9个位置的数据 "<<i<<endl;

 

    L.Delete(9,i);

    cout<<"删除的数据 "<<i<<endl;

 

 

    return 0;

}

 

源码: C++单链表.rar   

阅读(184) | 评论(0) | 转发(0) |
0

上一篇:纯虚函数

下一篇:虚函数实例

给主人留下些什么吧!~~