?? clist.cpp
字號:
#ifndef SCK_CLIST_CPP
#define SCK_CLIST_CPP
/////////////////////////////////////////////////////////////////////////////
// CList.cpp 雙向鏈表類標準C++的聲明及實現
// CopyRight(C) 1996,2008 TCSY 公司 圣誕節新版
// Pentium Working Room ShanChengKun 2003.12.24 更新
/////////////////////////////////////////////////////////////////////////////
#define EMPTY_NODE 0 // 空節點，Del()返回
#define START_NODE 1 // 首節點，Del()標志
#define MIDDLE_NODE 2 // 中節點，Del()返回
#define LAST_NODE 3 // 尾節點，Del()標志
template<class T> class CList; // 前置聲明的CList類
//-------------------------------------------------------------------------//
// 自定義的通用鏈表節點類，T為簡單數據類型
template<class T> // 鏈表節點指針
class CNode
{
friend class CList<T>; // 友元.CList類
long no; // 此節點的序號
T data; // 此節點的數據
CNode<T> *prior; // 前驅節點指針
CNode<T> *next; // 后繼節點指針
public: // 不負責釋放由前驅后繼的節點指針所指向的內存
CNode() {no = -1; prior = next = NULL;} // 默認構造函數
CNode(T& dat) {no = -1; data = dat; prior = next = NULL;}
T GetData(void) {return data;} // 獲取節點數據
void SetData(T& dat) {data = dat;} // 設置節點數據
};
//-------------------------------------------------------------------------//
// 自定義的通用鏈表類模板，T為簡單數據類型
template<class T> // 數據雙向搜索
class CList
{
long sum; // 所有節點總數
CNode<T> *start; // 首節點的指針
CNode<T> *last; // 尾節點的指針
CNode<T> *curr; // 當前位置指針
public: // 向鏈首走＝向上(向前)，向鏈尾走＝向下(向后)
long Sum(void) {return sum;} // 所有節點總數
void Rewind(int w) {curr = (w ? last : start);} // 0鏈首，1鏈尾
T& operator()(void) {return curr->data;} // 引用當前節點
long GetNth(void) {return (curr ? curr->no : -1);}// 取當前序號
T& operator[](long nth) {Seek(nth - curr->no); return curr->data;}
CNode<T> *GetCurrPtr(void) {return curr;} // 獲取當前指針
bool SetCurrPtr(CNode<T> *ptr)
{
if(!curr || !ptr) return false; // 設置當前指針
curr = ptr; return true;
}
bool Prev(void) // 移動到上一點
{
if(!curr || !curr->prior) return false;
curr = curr->prior; return true;
}
bool Next(void) // 移動到下一點
{
if(!curr || !curr->next) return false;
curr = curr->next; return true;
}
CList() {sum = 0; start = last = curr = NULL;} // 缺省構造函數
CList(CList<T>& list); // 拷貝構造函數
CList(T& dat) {sum = 0; start = last = curr = NULL; Add(dat);}
~CList() {Destroy();} // 默認析構函數
bool Add(T& dat); // 尾追加為當前
int Del(int bSort = 0); // 刪當前指向下
bool Ins(T& dat, int bType, int bSort = 0); // 當前前后插入
void SortNo(void); // 上點號起重編
bool Seek(long num); // -首向、+尾向
void Destroy(void) {Rewind(1); while(Del());} // 釋放鏈表節點
CList<T>& operator = (CList<T>& list); // 重置為一新鏈
CList<T>& operator = (T& dat); // 重置為單節點
CList<T>& operator += (CList<T>& list); // 尾部追加新鏈
CList<T>& operator += (T& dat); // 尾部追加節點
// 鏈表相加操作函數、右加節點操作函數、左加節點操作函數
friend CList<T> operator + (CList<T>& list1, CList<T>& list2);
friend CList<T> operator + (CList<T>& list, T& dat);
friend CList<T> operator + (T& dat, CList<T>& list);
};
//-------------------------------------------------------------------------//
// 鏈表類的復制拷貝構造函數(此函數必須準確無誤)
template<class T>
CList<T>::CList(CList<T>& list)
{
sum = 0; start = last = curr = NULL; // 注意這很重要
if(!list.Sum()) return; // 不拷貝空鏈表
list.Rewind(0); // 返回到鏈首點
do {if(!Add(list())) break;} while(list.Next());// 遍歷整個鏈表
}
// 在尾部追加一個數據節點
template<class T>
bool CList<T>::Add(T& dat)
{
CNode<T> *info = new CNode<T>(dat); // 申請拷貝空間
if(!info) return false;
info->no = sum++; // 置序號總數增
if(last) {info->prior = last; last->next = info; last = curr = info;}
else start = last = curr = info; return true; // 尾加載新節點
}
// 刪除(空0、首1、中2、尾3)節點，默認不重排序號
template<class T>
int CList<T>::Del(int bSort)
{
if(!curr) return EMPTY_NODE; // 當前為空鏈表
int nStyle = MIDDLE_NODE; // 默認中間刪除
CNode<T> *prior = curr->prior, *next = curr->next;
if(prior) prior->next = next;
else {start = next; nStyle = START_NODE;} // 刪除的是首點
if(next) next->prior = prior;
else {last = prior; nStyle = LAST_NODE;} // 刪除的是尾點
delete curr; curr = (next ? next : prior);
sum--; if(bSort) SortNo(); return nStyle; // 返回刪除類型
}
// 在當前節點(0前/后1)插入，當前指向新點。默認不重排序號
template<class T>
bool CList<T>::Ins(T& dat, int bType, int bSort)
{
if(curr == NULL) return Add(dat); // 空則尾部追加
CNode<T> *info = new CNode<T>(dat); // 申請新點空間
if(!info) return false;
if(bType != 0) // 在當前點之后
{
CNode<T> *&next = curr->next; // 引用當前后繼
info->prior = curr; info->next = next;
if(next) next->prior = info; else last = info;
curr = next = info; // 分尾點和中點
}
else // 在當前點之前
{
CNode<T> *&prior = curr->prior; // 引用當前前驅
info->prior = prior; info->next = curr;
if(prior) prior->next = info; else start = info;
curr = prior = info; // 分首點和中點
}
sum++; if(bSort) SortNo(); return true; // 增總數并返回
}
// 以當前首向一節點序號為基數，重新編號
template<class T>
void CList<T>::SortNo(void)
{
if(!curr) return; // 上點序號為基
curr->no = curr->prior ? curr->prior->no + 1 : 0;
CNode<T> *info = curr; // 從當前點開始
while(info->next)
{
info->next->no = info->no + 1; // 依次重新編號
info = info->next; // 不移當前指針
}
}
// (負=首向、正=尾向)移動當前指針|num|次
template<class T>
bool CList<T>::Seek(long num)
{
long count = 0, number = (num >0 ? num : -num); // 絕對移動次數
CNode<T> *info = curr;
while(info && count < number) // 是否已經足夠
{
info = (num > 0 ? info->next : info->prior);// 尾向首向移動
if(info) count++;
}
if(count != number) return false; // 比較移動次數
curr = info; return true; // 當前指新位置
}
//-------------------------------------------------------------------------//
// 等號賦值函數＝(置鏈為一新鏈)
template<class T>
CList<T>& CList<T>::operator = (CList<T>& list)
{
if(&list == this) return *this; // 不作自身拷貝
Destroy(); if(!list.Sum()) return *this; // 不拷貝空鏈表
list.Rewind(0); // 返回到首節點
do {if(!Add(list())) break;} while(list.Next());// 遍歷整個鏈表
return *this; // 返回實例引用
}
// 等號賦值函數＝(置鏈為單節點)，無法感知dat為本身節點
template<class T>
inline CList<T>& CList<T>::operator = (T& dat)
{
Destroy(); Add(dat); return *this; // 清空追加節點
}
// 加等號賦值函數＋＝(尾部追加新鏈)
template<class T>
CList<T>& CList<T>::operator += (CList<T>& list)
{
if(&list == this || !list.Sum()) return *this; // 非自身不拷空
list.Rewind(0); // 返回到首節點
do {if(!Add(list())) break;} while(list.Next());// 遍歷整個鏈表
return *this; // 返回實例引用
}
// 加等號賦值函數＋＝(尾部追加節點)
template<class T>
inline CList<T>& CList<T>::operator += (T& dat)
{
Add(dat); return *this; // 增加新單節點
}
//-------------------------------------------------------------------------//
// 鏈表相加操作函數
template<class T>
inline CList<T> operator + (CList<T>& list1, CList<T>& list2)
{
CList temp(list1); temp += list2; return temp; // 兩個鏈表相加
}
// 右加節點操作函數
template<class T>
inline CList<T> operator + (CList<T>& list, T& dat)
{
CList temp(list); temp.Add(dat); return temp; // 尾部追加節點
}
// 左加節點操作函數
template<class T>
inline CList<T> operator + (T& dat, CList<T>& list)
{
CList temp(dat); temp += list; return temp; // 采用+=運算符
}
/////////////////////////////////////////////////////////////////////////////
#endif // #ifndef SCK_CLIST_CPP
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -