数据结构算法与应用-C++语言描述笔记（单链表）

单链表，快速的插入和删除。

#ifndef __CHAIN_NODE_H__
#define __CHAIN_NODE_H__

#include <iostream>
using namespace std;

template <class T>
class Chain;

template <class T>
class ChainNode
{
    friend Chain<T>;
private:
    T data;
    ChainNode<T> *next;
};

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

    int length() const;

    bool Find(int k, T&x) const;
    int Search(const T& x) const;
    Chain<T>& Delete(int k, T&x);
    Chain<T>& Insert(int k, const T& x);
    void Output(ostream& out) const;
private:
    ChainNode<T> *first;
};

template <class T>
Chain<T>::~Chain()
{
    ChainNode<T> *next;
    while(first)
    {
        next = first->next;
        delete first;
        first = next;
    }
}

template <class T>
int Chain<T>::length() const
{
    ChainNode<T> *current = first;
    int len = 0;
    while(current)
    {
        len++;
        current = current->next;
    }
    return len;
}

template <class T>
bool Chain<T>::Find(int k, T&x) const
{
    bool result = false;
    ChainNode<T> *current = first;
    int index = 1;
    // 只需迭代k-1次

    while(index<k && current)
    {
        current = current->next;
        index ++;
    }

    if (current)
    {
        x = current->data;
        result = true;
    }
    return result;
}

template <class T>
int Chain<T>::Search(const T& x) const
{
    ChainNode<T> *current = first;
    int index = 1;
    while(current && current->data!=x)
    {
        current = current->next;
        index++;
    }
    if (current)
        return index;
    return 0;
}

template <class T>
void Chain<T>::Output(ostream& out) const
{
    ChainNode<T> * current;
    for(current=first; current; current=current->next)
        cout << current->data << " ";
}

template <class T>
Chain<T>& Chain<T>::Delete(int k, T&x)
{
    if (k<1 || !first)
        throw;
    ChainNode<T> *p = first;
    if (k == 1)
        first = first->next;
    else
    {
        // 首先要定位到K元素的上一位置

        ChainNode<T> *q = first;
        for(int index=1; index < k-1; index++)
        {
            q = q->next;
        }
        if (!q || !q->next)
            throw;

        p = q->next;
        q->next = p->next;

        x = p->data;
        delete p;
        return *this;
    }
}

template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{
    if (k<0)
        throw;
    ChainNode<T> *p = first;
    // 迭代的步数，第一个元素不需要迭代，第二个迭代一步，第K个元素迭代K-1步

    for(int index=1; index<k && p; index ++)
    {
        p = p->next;
    }

    if (k>0 && !p)
        throw;
    ChainNode<T>* y= new ChainNode<T>;
    y->data = x;
    if(k)
    {
        y->next = p->next;
        p->next = y;
    }
    else
    {
        y->next = first;
        first = y;
    }
    return *this;
}

#endif