大胖的部落格

Just a note
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  112 随笔 :: 0 文章 :: 3 评论 :: 0 Trackbacks
数据结构 ---- 单向链表
#include "stdafx.h"
#include<iostream>

using namespace std;


template <class T>
struct ChainNode {
    T                data;
    ChainNode<T>*    link;
};

template <class    T>
class Chain {
public:
    Chain(){first = NULL;}
    ~Chain();
    bool IsEmpty() const {return (NULL == first);}
    int Length() const;
    bool Find(int x, T& t) const;            //寻找第x个元素，值赋给t
    int Search(const T& t) const;            //返回值为t的元素的索引
    Chain<T>& Insert(int i, const T&t);        //在第i个位置插入元素t
    Chain<T>& Delete(int i, T&t);            //删除第i个位置的元素，其值赋给t
    Chain<T>& Reverse();                    //翻转链表

    //重载全局<<操作符，不是类成员函数
    friend ostream& operator <<(ostream& out, const Chain<T>& chain)
    {
        int iLength = chain.Length();
        ChainNode<T>* node = chain.first;
        while((0 != iLength) && (NULL != node)){
            --iLength;
            out<<node->data<<',';
            node = node->link;
        }
        return out;
    }
    
private:
    void Output(ostream& out) const;
    ChainNode<T>*    first;
};

template <class T>
Chain<T>::~Chain()
{
    ChainNode<T>* next = NULL;

    while(NULL != first) {
        next = first->link;
        delete first;
        first = next;
    }
}

template <class    T>
int Chain<T>::Length() const
{
    int i = 0;
    ChainNode<T>* next = first;
    while(NULL != next) {
        next = next->link;
        ++i;
    }
    return i;
}

template <class    T>
Chain<T>& Chain<T>::Insert(int i, const T &t)
{
    if(i < 0) {
        cerr<<"Insert index error!"<<endl;
        return *this;
    }

    ChainNode<T>* node = new ChainNode<T>;
    node->data = t;

    if(NULL == first) {
        first = node;
        node->link = NULL;
        return *this;
    }

    if(0 == i) {
        node->link = first;
        first = node;
        return *this;
    }

    ChainNode<T>* next = first;
    while((i>1) && (NULL != next->link)) {
        --i;
        next = next->link;
    }
    node->link = next->link;
    next->link = node;
    return *this;
}

template <class T>
int Chain<T>::Search(const T& t) const
{
    int i = 0;
    ChainNode<T>* next = first;
    while(NULL != next) {
        ++i;
        if(t == next->data)
            break;
        next = next->link;
    }
    if(NULL == next) {
        return 0;
    }
    return i;
}

template <class    T>
bool Chain<T>::Find(int x, T &t) const
{
    if(x < 1) {
        return false;
    }
    ChainNode<T>* next = first;
    while((x>1) && (NULL != next)) {
        --x;
        next = next->link;
    }
    if(NULL == next) {
        return false;
    }
    t = next->data;
    return true;
}

template <class    T>
Chain<T>& Chain<T>::Delete(int i, T &t)
{
    if(i < 1) {
        cerr<<"Delete index error!"<<endl;
        return *this;
    }
    
    if(NULL == first) {
        cerr<<"Empty Chain!"<<endl;
        return *this;
    }

    if(1 == i) {
        ChainNode<T>* pf = first;
        first = first->link;
        t = pf->data;
        delete pf;
        return *this;
    }

    ChainNode<T>* next = first;
    while((i > 2) && (NULL != next->link->link)) {
        --i;
        next = next->link;
    }
    ChainNode<T>* temp = next->link;;
    next->link = next->link->link;
    t = temp->data;
    delete temp;
    return *this;
    
}

template <class T>
Chain<T>& Chain<T>::Reverse()
{
    if((NULL == first) || (1 == Length())) {
        return *this;
    }
    
    ChainNode<T>* next = first->link;
    ChainNode<T>* tail = first;
    
    while(NULL != tail->link) {
        tail->link = next->link;
        next->link = first;
        first = next;
        next = tail->link;
    }
    return *this;
}

int main()
{
    Chain<int> c;
    c.Insert(0,4);
    c.Insert(1,5);
    c.Insert(2,6);
    c.Insert(0,3);
    c.Insert(7,7);

    cout<<c<<endl;
    c.Reverse();
    cout<<c<<endl;
    return 0;
}
posted on 2009-06-29 10:31 大胖 阅读(211) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理