?? 模板鏈表_02b.h
字號:
//EXAMPLE9_02B.H
#ifndef EXAMPLE9_02B_H
#define EXAMPLE9_02B_H
#include <iostream>
#include "EXAMPLE9_02.H"
//結點類帶參數構造函數的實現
using namespace std;
template<class T>
ListNode<T>::ListNode(const T& nItem, ListNode<T> *ptrNext):
Data(nItem),ptrNext(ptrNext)
{}
//返回指向后續結點的指針
template<class T>
ListNode<T> *ListNode<T>::NextListNode() const
{
return ptrNext;
}
template<class T>
void ListNode<T>::InsertAfter(ListNode<T> *ptr)
{
ptr->ptrNext=ptrNext; //將ptr的ptrNext指針指向本結點的后續結點
ptrNext=ptr;//本結點的ptrNext指針指向ptr
}
template<class T>
ListNode<T> *ListNode<T>::DeleteAfter()
{
ListNode<T> *ptrTemp=ptrNext;
if(ptrNext==NULL) //處理本結點為尾結點時的情況
return NULL;
ptrNext=ptrTemp->ptrNext; //一般情況
return ptrTemp;
}
//鏈表類構造函數,4個私有指針成員設置為空,鏈表初始長度設置為0,初始當前結點
//初始位置為-1
template<class T>
LinkedList<T>::LinkedList(void):ptrFront(NULL),ptrTail(NULL),
ptrPrev(NULL),ptrCurr(NULL),nListLength(0),nPosition(-1)
{ }
//重載"="號運算符
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& list)
{
if(this!=&list)
{
DeleteAll();
CopyList(list);
}
return *this;
}
//拷貝構造函數
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& list)
{
CopyList(list);
}
//重新設置當前指針的位置
template<class T>
void LinkedList<T>::Reset(int nPos)
{
int nStartPos;
if(!ptrFront) //如果當前指針為空,鏈表為空直接返回
{
return;
}
if(nPos>=nListLength||nPos<0) //位置越界檢查
{
cerr<<"Invalid Position!"<<endl;
return;
}
if(nPos==0) //置當前指針為頭結點
{
ptrPrev=NULL;
ptrCurr=ptrFront;
nPosition=0;
}
else //一般情況
{
ptrCurr=ptrFront->NextListNode();
ptrPrev=ptrFront;
nStartPos=1;
for(nPosition=nStartPos;nPosition!=nPos;nPosition++)
//尋找該位置并使當前指針指向該位置
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
}
}
//當前指針指向當前結點的后續結點
template<class T>
void LinkedList<T>::Next()
{
if(ptrCurr)
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++;
}
}
//將數據為nItem的結點插入到鏈表頭
template<class T>
void LinkedList<T>::InsertFront(const T& nItem)
{
ListNode<T> *newListNode=GetListNode(nItem); //獲得一個封裝有該數據
//的結點
newListNode->SetNext(ptrFront);
ptrFront=newListNode;
nListLength++;
}
//將數據為nItem的結點插入到鏈表尾
template<class T>
void LinkedList<T>::InsertTail(const T& nItem)
{
ListNode<T> *newListNode;
if(ptrCurr==NULL) InsertFront(nItem); //若鏈表為空,使之成為頭結點
//(也是尾結點)
else //一般情況
{
while(ptrCurr->NextListNode()) //尋找尾結點
ptrCurr=ptrCurr->NextListNode();
newListNode=GetListNode(nItem);
ptrCurr->InsertAfter(newListNode);
}
}
//將數據為nItem的結點插入到鏈表的當前位置之前
template<class T>
void LinkedList<T>::InsertAt(const T& nItem)
{
ListNode<T> *newListNode;
if(!ptrPrev) //插入到頭結點
{
newListNode=GetListNode(nItem,ptrFront);
newListNode->SetNext(ptrFront);
ptrFront=newListNode;
nListLength++;
}
else //一般情況
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
if(ptrPrev==ptrTail)
{
ptrTail=newListNode;
nPosition=nListLength;
}
ptrCurr=newListNode;
}
//將數據為nItem的結點插入到鏈表當前結點之后
template<class T>
void LinkedList<T>::InsertAfter(const T& nItem)
{
ListNode<T> *newListNode;
if(!ptrCurr) //處理空鏈表的情況，如果當前鏈表為空
{
newListNode=GetListNode(nItem);
ptrCurr=newListNode;
ptrFront=ptrCurr;
}
else //一般情況
{
newListNode=GetListNode(nItem);
ptrCurr->InsertAfter(newListNode);
}
if(ptrPrev==ptrTail)
{
ptrTail=newListNode;
nPosition=nListLength;
}
ptrCurr=newListNode;
nListLength++;
}
//刪除鏈表中的當前結點
template<class T>
void LinkedList<T>::DeleteCurr()
{
ListNode<T> *ptr;
if(!ptrCurr) //處理空鏈表的情況
{
cerr<<"The List is empty!"<<endl;
exit(1);
}
if(!ptrPrev) //刪除頭結點的情況
{
ptr=ptrFront;
ptrFront=ptrFront->NextListNode();
}
else //一般情況
{ptr=ptrPrev->DeleteAfter();}
if(ptr==ptrTail)
{
ptrTail=ptrPrev;
nPosition--;
}
ptrCurr=ptr->NextListNode();
FreeListNode(ptr);
nListLength--;
}
//刪除鏈表中所有結點并釋放資源
template<class T>
void LinkedList<T>::DeleteAll()
{
ListNode<T> *ptrCurrPos,
*ptrNextPos;
ptrCurrPos=ptrFront;
while(ptrCurrPos) //循環處理刪除鏈表中的各個結點
{
ptrNextPos=ptrCurrPos->NextListNode();
FreeListNode(ptrCurrPos);
ptrCurrPos=ptrNextPos;
}
ptrFront=NULL;
ptrTail=NULL;
ptrPrev=NULL;
ptrCurr=NULL;
nListLength=0;
nPosition=-1;
}
//刪除鏈表的頭結點
template<class T>
int LinkedList<T>::DeleteHead()
{
ListNode<T> *ptr=ptrFront;
if(ptrFront)
{
ptrFront=ptrFront->NextListNode();
delete ptr;
nListLength--;
return 1;
}
else //處理鏈表為空的情況
{
cout<<"The List is empty!"<<endl;
return 0;
}
}
//獲得鏈表中當前結點的數據
template<class T>
T& LinkedList<T>::GetData()
{
if(nListLength==0||!ptrCurr) //空鏈表的處理
{
cerr<<"Invalid!"<<endl;
exit(1);
}
return ptrCurr->ShowData();
}
//逐項拷貝鏈表中的各個結點
template<class T>
void LinkedList<T>::CopyList(const LinkedList<T> &list)
{
ListNode<T> *ptr=list.ptrFront;
ptrCurr=NULL;
while(ptr) //遍歷list并創建新鏈表
{
InsertAfter(ptr->ShowData());
ptr=ptr->NextListNode();
}
if(nPosition==-1) //list為空
return;
ptrPrev=NULL;
ptrCurr=ptrFront;
for(int nPos=0;nPos!=list.CurrPosition();nPos++)
//將新鏈表的各個數據成員設置與原鏈表相同
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
nPosition=nPos;
nListLength=list.ListLength();
}
//獲得下一個新結點,返回新結點地址
template<class T>
ListNode<T> *LinkedList<T>::GetListNode(const T& nItem, ListNode<T> *preNext)
{
ListNode<T> *newListNode;
newListNode=new ListNode<T>(nItem,preNext);
if(!newListNode)
{
cerr<<"Memory allocation failure!"<<endl;
exit(1);
}
return newListNode;
}
//輸出鏈表中的各個結點數據
template<class T>
void LinkedList<T>::DisplayList()
{
ListNode<T> *p;
p=ptrFront;
cout<<endl<<"（";
while(p) //遍歷鏈表
{
cout<<p->ShowData()<<",";
p=p->NextListNode();
}
cout<<"）"<<endl;
}
//在鏈表中查找數據
template<class T>
int LinkedList<T>::Find(T& nItem)
{
ptrCurr=ptrFront;
ptrPrev=NULL;
while(ptrCurr)
{
if(ptrCurr->ShowData()==nItem)
return 1;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++; //控制當前指針位置
}
return 0;
}
//刪除鏈表中滿足條件的結點
template<class T>
void LinkedList<T>::Delete(T key)
{
ptrCurr=ptrFront;
ptrPrev=NULL;
if(!ptrCurr)
return;
while(ptrCurr&&ptrCurr->ShowData()!=key) //查找相應的結點
{
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
nPosition++;
}
if(ptrCurr) //如果找到該結點,刪除它
{
if(!ptrPrev) ptrFront=ptrFront->NextListNode();
else ptrPrev->DeleteAfter();
delete ptrCurr;
}
}
template<class T>
void LinkedList<T>::InsertOrder(T nItem)
{
ListNode<T> *newListNode,
*next, //用于遍歷鏈表
*prev; //next指向結點的前一個結點的指針
ptrPrev=NULL;
ptrCurr=ptrFront;
prev=ptrCurr;
next=ptrCurr->NextListNode();
while(prev->ShowData()==next->ShowData()&&(next))
//判斷原鏈表的排序方式,升序或者降序
{
prev=next;
next=next->NextListNode();
}
if(!next) InsertFront(nItem); //如果原鏈表中所有結點均相等,則將結點
//作為原鏈表的首結點
else if(prev->ShowData()>next->ShowData()) //降序排列時
{
while(ptrCurr) //尋找插入位置
{
if(nItem>=ptrCurr->ShowData()) break;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
if(!ptrPrev) InsertFront(nItem);
else
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
}
else //升序排列時
{
while(ptrCurr) //尋找插入位置
{
if(nItem<=ptrCurr->ShowData()) break;
ptrPrev=ptrCurr;
ptrCurr=ptrCurr->NextListNode();
}
if(!ptrPrev) InsertFront(nItem);
else
{
newListNode=GetListNode(nItem);
ptrPrev->InsertAfter(newListNode);
}
}
}
#endif
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -