// Chain.h

#ifndef _CHAIN_H_
#define _CHAIN_H_

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

template<class T>
class Chain
{
public:
    Chain();
    ~Chain();

    bool IsEmpty() const;

    int Length() const;

    bool Find(int index, T &value) const;

    int Search(T value) const;

    Chain<T>& Insert(int index, const T &value);

    Chain<T>& Delete(int index, T &value);

    Chain<T>& Reverse(void);

    void Output() const;

private:
    ChainNode<T> *first;
    int len;
};

#endif // _CHAIN_H_
// Chain.cpp
#include "stdafx.h"
#include "Chain.h"
#include <iostream>
using namespace std;

template<class T>
Chain<T>::Chain()
{
    first = NULL;
    len = 0;
}

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

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

template<class T>
bool Chain<T>::IsEmpty() const
{
    return (first == NULL);
}

template<class T>
int Chain<T>::Length() const
{
    return len;
}

template<class T>
bool Chain<T>::Find(int index, T &value) const
{
    ChainNode<T> *cur = first;

    if (index < 1 || index > len + 1)
    {
        return false;
    }

    for (int i = 1; i < index && cur; i++)
    {
        cur = cur->link;
    }

    if (cur)
    {
        value = cur->data;
        return true;
    }

    return false;
}

template<class T>
int Chain<T>::Search(T value) const
{
    ChainNode<T> *cur = first;
    int pos = 1;

    while (cur && cur->data != value)
    {
        cur = cur->link;
        pos++;
    }

    if (cur)
    {
        return pos;
    }

    return 0;
}

template<class T>
Chain<T>& Chain<T>::Insert(int index, const T &value)
{
    ChainNode<T> *cur = first;

    if (index < 0 || index > len + 1)
    {
        cout << "Insert error" << endl;
    }

    for (int i = 1; i < index && cur; i++)
    {
        cur = cur->link;
    }

    if (index > 0 && !cur)
    {
        cout << "Insert Out bounds" << endl;
    }

    ChainNode<T> *newNode = new ChainNode<T>;
    newNode->data = value;

    if (index)
    {
        newNode->link = cur->link;
        cur->link = newNode;
    }
    else
    {
        newNode->link = first;
        first = newNode;
    }

    len++;
    return *this;
}

template<class T>
Chain<T>& Chain<T>::Delete(int index, T &value)
{
    ChainNode<T> *cur = first;

    if (index < 1 || index > len)
    {
        cout << "Delete Out bounds" << endl;
    }

    if (index == 1)
    {
        first = cur->link;
    }
    else
    {
        ChainNode<T> *prev = first;
        for (int i = 1; i < index - 1 && prev; i++)
        {
            prev = prev->link;
        }
        cur = prev->link;
        prev->link = cur->link;
    }
    value = cur->data;
    delete cur;

    len--;

    return *this;
}

template<class T>
void Chain<T>::Output() const
{
    ChainNode<T> *cur = first;

    while (cur)
    {
        cout << cur->data << ' ';
        cur = cur->link;
    }
}

template<class T>
Chain<T>& Chain<T>::Reverse(void)
{
    ChainNode<T> *p1 = first;
    ChainNode<T> *p2 = p1->link;
    ChainNode<T> *p3 = p2->link;

    p1->link = NULL;
    while (p3 != NULL)
    {
        p2->link = p1;
        p1 = p2;
        p2 = p3;
        p3 = p3->link;
    }
    p2->link = p1;
    first = p2;

    return *this;
}
// main.cpp
#include "stdafx.h"
#include "Chain.h"
#include "Chain.cpp"
#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
    Chain<int> chain;
    int value;

    /*************Insert**********/
    for (int i = 0; i < 10; i++)
    {
        chain.Insert(i, i + 1);
    }

    /*************Output**********/
    chain.Output();
    cout << endl;

    /************IsEmpty***********/
    cout << "IsEmpty = " << chain.IsEmpty() << endl;

    /*************Length**********/
    cout << "Length = " << chain.Length() << endl;

    /*************Find************/
    chain.Find(4, value);
    cout << "value = " << value << endl;

    /*************Search**********/
    cout << "search = " << chain.Search(3) << endl;

    /*************Delete**********/
    chain.Delete(8, value);
    cout << "delete value = " << value << endl;

    /*************Output**********/
    chain.Output();
    cout << endl;

    /*************Reverse************/
    chain.Reverse();
    cout << "Reverse: ";
    chain.Output();
    cout << endl;

    cin.get();
    return 0;
}

2011-08-12

聊天