連結清單

template <class T>

class ListNode

{

  T data;

  ListNode<T> * link;

public:

  ListNode();

  ListNode(T value);

  ~ListNode();

  void SetLink(ListNode<T>* next);

  ListNode<T> * GetLink();

  T& Getdata();

};

void ListNode<T>::SetLink(ListNode<T> *next)

  link=next;

}

ListNode<T> * ListNode<T>::GetLink()

  return link;

T& ListNode<T>::Getdata()

  return data;

ListNode<T>::ListNode()

  link=NULL;

ListNode<T>::ListNode(T value)

  data=value;

#include "ListNode.h"

template <class T>    

class List

  ListNode<T> * first;

  ListNode<T> * tail;

  List();

  bool AddTail(T value);

  bool RemoveTail();

  bool Insert(int index,T value);

  bool Remove(int index);

  T& Get(int index);

  bool IsEmpty();

  int GetCount();

  void RemoveAll();

  ListNode<T> * GetHead();

  ListNode<T> * GetTail();

  void SetTail(ListNode<T> * newTail);

  ListNode<T> * GetNode(int index);

  ListNode<T> * GetCur();

  ListNode<T> * GetCurNext();

List<T>::List()

  first=tail=new ListNode<T>;

  tail->SetLink(NULL);

bool List<T>::AddTail(T value)

  ListNode<T> * add=new ListNode<T>(value);

  tail->SetLink(add);

  tail=tail->GetLink();

  if(tail!=NULL)

    return true;

  else

    return false;

bool List<T>::RemoveTail()

  return Remove(this->GetCount()-1);

bool List<T>::Insert(int index, T value)

  if(index<0 || index>this->GetCount()-1)

  {

    cout<<"插入位置錯誤！"<<endl;

  }

  ListNode<T> * curr=first;

  while(index)

    curr=curr->GetLink();

    --index;

  add->SetLink(curr->GetLink());

  curr->SetLink(add);

  if(curr->GetLink() !=NULL)

bool List<T>::Remove(int index)

    cout<<"删除位置錯誤！"<<endl;

  ListNode<T> * cur,* curpre;

  cur=first;

  curpre=cur->GetLink();

    cur=cur->GetLink();

    curpre=curpre->GetLink();

  if(tail==curpre)

    tail=cur;

  cur->SetLink(curpre->GetLink());

  if(curpre!=NULL)

T& List<T>::Get(int index)

    cout<<"傳回位置錯誤！"<<endl;

  ListNode<T> * cur;

  cur=first->GetLink();

  return cur->Getdata();

bool List<T>::IsEmpty()

  return first->GetLink()==NULL;

int List<T>::GetCount()

  int count=0;

  while(cur!=NULL)

    count++;

  return count;

void List<T>::RemoveAll()

  while(first->GetLink()!=NULL)

    cur=first->GetLink();

    first->SetLink(cur->GetLink());

    delete cur;

  tail=first;

ListNode<T> * List<T>::GetHead()

  return first;

ListNode<T> * List<T>::GetTail()

  return tail;

void List<T>::SetTail(ListNode<T> *newTail)

  tail=newTail;

ListNode<T> * List<T>::GetNode(int index)

    cout<<"位置錯誤！"<<endl;

  return cur;

ListNode<T> * List<T>::GetCurNext()

  cur=this->GetCur();

  cur=cur->GetLink();

兩個順序連結清單合并：

#include <iostream>

#include "List.h"

using namespace std;

int main()

  List<int> listFirst;

  List<int> listSecond;

  listFirst.AddTail(1);

  listFirst.AddTail(5);

  listFirst.AddTail(8);

  listFirst.AddTail(9);

  listFirst.AddTail(13);

  listSecond.AddTail(0);

  listSecond.AddTail(3);

  listSecond.AddTail(4);

  listSecond.AddTail(6);

  listSecond.AddTail(11);

  listSecond.AddTail(17);

  while(listSecond.GetCount()!=0)

    int indexFirst=0;

    while(listSecond.Get(0)>listFirst.Get(indexFirst))

    {

      ++indexFirst;

      if(indexFirst==listFirst.GetCount())

      {

        break;

      }

    }

    if(indexFirst==listFirst.GetCount())

      listFirst.AddTail(listSecond.Get(0));

      listSecond.Remove(0);

    else

      listFirst.Insert(indexFirst,listSecond.Get(0));

  for(int i=0;i<listFirst.GetCount();i++)

    cout<<listFirst.Get(i)<<endl;

  return 0;

}