數(shù)據(jù)結構學習記錄連載3（鏈表的學習）

基本要求：

1) 用模板方法建立鏈表的結點類ListNode和單鏈表類LinList，編寫程序實現(xiàn)向單鏈表插入100整數(shù)，然后，以插入次序刪除這100個整數(shù)。

提高要求：

1) 簡單修改程序，將單鏈表類LinList改為雙向循環(huán)鏈表類。向雙向循環(huán)鏈表插入100字符，然后，以插入次序刪除這100個字符。

2) 編寫函數(shù)實現(xiàn)單鏈表類LinList的對象B連接到單鏈表類LinList的對象A的尾部：Void Concatenate(LinList& A， LinList& B)。

1.ListNode.h結點定義：

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：ListNode.h
* 摘 要： 節(jié)點類的定義
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include<iostream.h>
#include<stdio.h>

template<class T> class LinkList; //前視定義，否則，無法定義友元
template<class T> class ListNode
{
 friend class LinkList<T>;  //定義友元
private:
 ListNode<T> *next;    //指向下一個結點的指針
public:
 T data;
 ListNode(ListNode<T> *ptrNext = NULL); //構造函數(shù)，用于構造頭結點
 ListNode(const T& item, ListNode<T> *ptrNext = NULL);//構造函數(shù)，非頭結點
 ~ListNode() {};     //析構函數(shù)
 friend void Concatenate(LinkList<T>& target, LinkList<T>& souce);
};

template<class T>
ListNode<T>::ListNode(ListNode<T> *ptrNext):next(ptrNext)
{
 
}

template<class T>
ListNode<T>::ListNode(const T &item, ListNode<T> *ptrNext)
{
 data = item;
 next = ptrNext;
}

2.LinkList.h定義單鏈表類及實現(xiàn)：

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：LinkList.h
* 摘 要： 單鏈表類的定義
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include "ListNode.h"

template <class T>
class LinkList
{
private:
 ListNode<T> *head;      //指向頭結點的指針
 int size;        //單鏈表的元素個數(shù)
 ListNode<T> *currPtr;     //當前結點
public:
 LinkList(void);       //構造函數(shù)
 ~LinkList();      //析構函數(shù)

 //線性表操作要求的成員函數(shù)
 int GetListSize(void) const;   //返回鏈表的元素個數(shù)
 int ListIsEmpty(void) const;   //判斷單鏈表是否為空
 ListNode<T> *Index(int pos);   //定位
 void Insert(const T& item, int pos); //插入
 T Delete(int pos);      //刪除
 T GetData(int pos);      //取元素
 void ClearList(void);     //清空鏈表

 //遍歷單鏈表的成員函數(shù)
 ListNode<T> *Reset(int pos=0);   //把第pos個結點設置為當前結點currPtr
 ListNode<T> *Next(void);    //currPtr指向下一個結點
 int EndOfList(void) const;    //currPtr是否指在鏈表尾

 friend void Concatenate(LinkList<T>& target, LinkList<T>& souce);
}; 

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：LinkList.cpp
* 摘 要： 單鏈表的各個功能函數(shù)的現(xiàn)實
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

template <class T>
LinkList<T>::LinkList(void) 
{
 size = 0;
 head = new ListNode<T>();
}

template <class T>
LinkList<T>::~LinkList()
{
 ClearList(); //釋放所有非頭結點的結點
 delete head; //釋放頭結點
}

/*
* 函數(shù)名稱: GetListSize
* 輸　入:
* 輸　出:
* 功能描述: 返回順序表的元素個數(shù)size
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
int LinkList<T>::GetListSize(void) const 
{
 return size;
}

/*
* 函數(shù)名稱: ListIsEmpty
* 輸　入:
* 輸　出:
* 功能描述: 判斷是否為空,空返回1;非返回0
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
int LinkList<T>::ListIsEmpty(void) const
{
 return size == 0 ? 1 : 0;
}

/*
* 函數(shù)名稱: Index
* 輸　入: pos
* pos: 定位數(shù)據(jù)元素結點
* 輸　出:
* 功能描述: 定位至第pos個數(shù)據(jù)元素結點，返回指向第pos個結點的指針
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
ListNode<T> *LinkList<T>::Index(int pos)
{
 if (pos < -1 || pos > size)
 {
  cout << "參數(shù)pos越界出錯!" << endl;
  exit(0);
 }

 if (pos == -1)
 {
  return head;
 }

 ListNode<T> *p = head->next;
 int i = 0;
 while (p != NULL && i <pos)
 {
  p = p->next;
  i++;
 }

 return p;
}

/*
* 函數(shù)名稱: Insert
* 輸　入: pos
* pos: 插入數(shù)據(jù)元素結點的位置
* item: 插入數(shù)據(jù)結點的數(shù)據(jù)
* 輸　出:
* 功能描述: 在pos個結點之前插入一個data域為item的新結點
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
void LinkList<T>::Insert(const T& item, int pos)
{
 if (pos < 0 || pos > size)
 {
  cout << "參數(shù)pos越界出錯!" << endl;
  exit(0);
 }

 ListNode<T> *p = Index(pos - 1);
 ListNode<T> *newNode = new ListNode<T>(item, p->next);
 p->next = newNode;
 size++;
}

/*
* 函數(shù)名稱: Delete
* 輸　入: pos
* pos: 刪除數(shù)據(jù)元素結點的位置
* 輸　出:
* 功能描述: 刪除第pos個結點，并返回被刪除結點的data
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
T LinkList<T>::Delete(int pos)
{
 T temp;
 if (pos < 0 || pos > size-1)
 {
  cout << "參數(shù)pos越界出錯!" << endl;
  exit(0);
 }

 ListNode<T> *q, *p = Index(pos - 1);
 q = p->next;
 p->next = p->next->next;
 temp = q->data;
 delete q;
 size--;

 return temp;
}

/*
* 函數(shù)名稱: ClearList
* 輸　入: pos
* pos: 刪除數(shù)據(jù)元素結點的位置
* 輸　出:
* 功能描述: 清空表為初始化狀態(tài)
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
void LinkList<T>::ClearList(void)
{
 ListNode<T> *p = head->next;
 ListNode<T> *q;

 while (p != NULL)
 {
  q = p;
  p = p->next;
  delete q;
 }
 size = 0;
}

/*
* 函數(shù)名稱: Reset
* 輸　入: pos
* pos: 數(shù)據(jù)元素結點的位置
* 輸　出:
* 功能描述: 使currPtr指向結點pos，并返回currPtr
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
ListNode<T> *LinkList<T>::Reset(int pos)
{
 if (pos < -1 || pos > size - 1)
 {
  cout << "參數(shù)pos越界出錯!" << endl;
  exit(0);
 }

 if (pos == -1)
 {
  return head;
 }

 if (pos == 0)
 {
  currPtr = head->next;
 }
 else
 {
  currPtr = head->next;
  ListNode<T> prevPtr = head;
  for (int i=0; i<pos; i++)
  {
   prevPtr = currPtr;
   currPtr = currPtr->next;
  }
 }

 return currPtr;
}

/*
* 函數(shù)名稱: Next
* 輸　入: 
* 輸　出:
* 功能描述: 使currPtr指向下一個結點
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
ListNode<T> *LinkList<T>::Next(void)
{
 if (currPtr != NULL)
 {
  currPtr = currPtr->next;
 }

 return currPtr;
}

/*
* 函數(shù)名稱: EndOfList
* 輸　入: 
* 輸　出:
* 功能描述: currPtr是否指在鏈表尾
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
int LinkList<T>::EndOfList(void) const
{
 return currPtr == NULL ? 1 : 0;
}

/*
* 函數(shù)名稱: GetData
* 輸　入: pos
* pos: 需要得到結點數(shù)據(jù)的位置
* 輸　出:
* 功能描述: 獲取pos處結點的數(shù)據(jù)
* 作　者: 吳友強
* 日　期: 2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
T LinkList<T>::GetData(int pos)
{
 if (pos < 0 || pos > size-1)
 {
  cout << "參數(shù)pos越界出錯!" << endl;
  exit(0);
 }

 ListNode<T> *p = Index(pos);
 return p->data;
}

4.LinkListTest.cpp測試程序：

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：SeqListTest.cpp
* 摘 要： 測試鏈表的功能
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include <iostream.h>
#include <stdlib.h>

#include "LinkList.h"

int main(int argc, char *argv[])
{
 LinkList<int> targetList, sourceList;

 for (int i=0; i<10; i++)
 {
  targetList.Insert(i+10, i);
 }

 for (i=0; i<5; i++)
 {
  sourceList.Insert(i+5, i);
 }
//  cout << "測試GetData()成員函數(shù)結果如下:" << endl;
//  int n = linkList.GetListSize();
//  for (i=0; i<n; i++)
//  {
//   cout << linkList.GetData(i) << " ";
//  }
//
//  cout << endl << "測試遍歷成員函數(shù)結果如下:" << endl;
//  ListNode<int> *p = linkList.Reset(0);
//
//  while (!linkList.EndOfList())
//  {
//   cout << p->data << " ";
//   p = linkList.Next();
//  }
//
//  cout << endl << "測試Delete()成員函數(shù)結果如下:" << endl;
//  n = linkList.GetListSize();
//  for (i=n-1; i>=0; i--)
//  {
//   linkList.Delete(i);
//  }
//
//  cout << "測試GetData()成員函數(shù)結果如下:" << endl;
//  n = linkList.GetListSize();
//  for (i=0; i<n; i++)
//  {
//   cout << linkList.GetData(i) << " ";
//  }

 Concatenate(targetList, sourceList);

 int n = targetList.GetListSize();
 for (i=0; i<n; i++)
 {
  cout << targetList.GetData(i) << " ";
 }
 return 0;
}

5.注意事項：（1）如果單鏈表的定義與接口的實現(xiàn)分開到兩個不同的頭文件和CPP文件，編譯會出錯，解決把法是把CPP文件刪除在頭文件最后加上一句：#include "LinkList.cpp"

（2）上面注釋部分是測試基本函數(shù)功能的，我同時在里面測試了提高要求2，提高2的現(xiàn)實在下一篇中給出。