단일 링크 템 플 릿 클래스

링크 는 가장 기본 적 인 데이터 구조 로 불 연속 적 인 데이터 의 집합 이다. 링크 의 모든 노드 는 노드 요 소 를 포함 하 는 것 을 제외 하고 다음 노드 의 주 소 를 포함한다.링크 에 대해 삽입, 삭제, 찾기, 표시 등 을 실현 할 수 있 습 니 다.

/*
 *       List.h
 */ 
#ifndef _LIST_H_
#define _LIST_H_

#include <iostream>
using namespace std;

template <class TYPE>
class List
{
public:
    List();
    List(TYPE x[], int n);
    List(const List<TYPE> *l);
    ~List();
    void insert(const TYPE &x);
    bool remove(const TYPE &x);
    void display() const;
    int size() const;
    int at(int x, TYPE &k) const;
private:
    struct ListNode
    {
        TYPE data;
        ListNode *next;
    };
    ListNode *list;
    void insert(ListNode *&l, const TYPE &x);
    bool remove(ListNode *&l, const TYPE &x);
    void display(ListNode *l) const;
    int size(ListNode *l) const;
    int at(ListNode *l, int x, TYPE &k) const;
};

#endif

//     
template <class TYPE>
List<TYPE>::List()
{
    list = new ListNode;
    list->next = NULL;
}

//          
template <class TYPE>
List<TYPE>::List(TYPE x[], int n)
{
    list = new ListNode;
    list->next = NULL;
    for(int i = 0; i < n; ++i)
    {
        insert(list, x[i]);
    }
}

//          
template <class TYPE>
List<TYPE>::List(const List<TYPE> *l)
{
    if(l->list == NULL)
        list = NULL;
    else
    {
        ListNode *p = l->list->next;
        ListNode *pt = list = new ListNode;
        while(p)
        {
            ListNode *q = new ListNode;
            q->data = p->data;
            q->next = NULL;
            pt->next = q;
            pt = q;
            p = p->next;
        }
    }
}

//     
template <class TYPE>
List<TYPE>::~List()
{
    List *p = list->next;
    while(p)
    {
        list->next = p->next;
        free(p);
        p = list->next;
    }
}

//           
template <class TYPE>
void List<TYPE>::insert(const TYPE &x)
{
    insert(list, x);
}

//      List    
template <class TYPE>
void List<TYPE>::insert(ListNode *&l, const TYPE &x)
{
    ListNode *node = new ListNode;
    node->data = x;
    node->next = l->next;
    l->next = node;
}

//     x ，      true，    false
template <class TYPE>
bool List<TYPE>::remove(const TYPE &x)
{
    remove(list, x);
}

template <class TYPE>
bool List<TYPE>::remove(ListNode *&l, const TYPE &x)
{
    if(l == NULL)
        return false;

    ListNode *p = l->next;
    ListNode *pre = l;
    while(p && p->data != x)
    {
        pre = p;
        p = p->next;
    }
    if(p)
    {
        pre->next = p->next;
        delete p;
    }
    return true;
}

//       
template <class TYPE>
void List<TYPE>::display() const
{
    display(list);
}

template <class TYPE>
void List<TYPE>::display(ListNode *l) const
{
    if(l != NULL)
    {
        ListNode *p = l->next;
        if(p == NULL)
        {
            cout << "    ！" << endl;
            return;
        }
        while(p)
        {
            cout << p->data << " ";
            p = p->next;
        }
    }
    else
        cout << "     ！" << endl;
}

//          
template <class TYPE>
int List<TYPE>::size() const
{
    size(list);
}

template <class TYPE>
int List<TYPE>::size(ListNode *l) const
{
    int s = 0;
    if(l != NULL)
    {
        ListNode *p = l->next;
        while(p)
        {
            s++;
            p = p->next;
        }
    }
    return s;
}

/*
 *             
 *               -1
 *               k    1
 */
template <class TYPE>
int List<TYPE>::at(int x, TYPE &k) const
{
    return at(list, x, k);
}

template <class TYPE>
int List<TYPE>::at(ListNode *l, int x, TYPE &k) const
{
    if(size(l) < x || x <= 0)
    {
        return -1;
    }
    else
    {
        int i = 0;
        ListNode *p = l->next;
        while(p && i < x)
        {
            p = p->next;
            i++;
        }
        k = p->data;
    }
    return 1;
}