基本介紹
鍊表的操作,元素的操作,雙向鍊表模板,循環鍊表,
鍊表的操作
線性表的雙向鍊表存儲結構：
typedef struct DuLNode{ElemType data;struct DuLNode *prior,*next;}DuLNode,*DuLinkList;帶頭結點的雙向循環鍊表的基本操作：
void InitList(DuLinkList L){ /* 產生空的雙向循環鍊表L */L=(DuLinkList)malloc(sizeof(DuLNode));if(L)L->next=L->prior=L;elseexit(OVERFLOW);}銷毀雙向循環鍊表L：
void DestroyList(DuLinkList L){DuLinkList q,p=L->next; /* p指向第一個結點 */while(p!=L) /* p沒到表頭 */{q=p->next;free(p);p=q;}free(L);L=NULL;}重置鍊表為空表：
void ClearList(DuLinkList L) /* 不改變L */{ DuLinkList q,p=L->next; /* p指向第一個結點 */while(p!=L) /* p沒到表頭 */{q=p->next;free(p);p=q;}L->next=L->prior=L; /*頭結點的兩個指針域均指向自身 */}驗證是否為空表：
Status ListEmpty(DuLinkList L){ /* 初始條件：線性表L已存在if(L->next==L&&L->prior==L)return TRUE;elsereturn FALSE;}元素的操作
計算表內元素個數
int ListLength(DuLinkList L){ /* 初始條件：L已存在。操作結果： */int i=0;DuLinkList p=L->next; /* p指向第一個結點 */while(p!=L) /* p沒到表頭 */{i++;p=p->next;}return i;}賦值：
Status GetElem(DuLinkList L,int i,ElemType *e){ /* 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR */int j=1; /* j為計數器 */DuLinkList p=L->next; /* p指向第一個結點 */while(p!=L&&j<i){p=p->next;j++;}if(p==L||j>i) /* 第i個元素不存在 */return ERROR;*e=p->data; /* 取第i個元素 */return OK;}查找元素：
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType)){ /* 初始條件：L已存在，compare()是數據元素判定函式 *//* 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。 *//* 若這樣的數據元素不存在，則返回值為0 */int i=0;DuLinkList p=L->next; /* p指向第1個元素 */while(p!=L){i++;if(compare(p->data,e)) /* 找到這樣的數據元素*/return i;p=p->next;}return 0;}查找元素前驅：
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e){ /* 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅， *//* 否則操作失敗，pre_e無定義 */DuLinkList p=L->next->next; /* p指向第2個元素 */while(p!=L) /* p沒到表頭 */{if(p->data==cur_e){*pre_e=p->prior->data;return TRUE;}p=p->next;}return FALSE;}查找元素後繼：
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e){ /* 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼， *//* 否則操作失敗，next_e無定義 */DuLinkList p=L->next->next; /* p指向第2個元素 */while(p!=L) /* p沒到表頭 */{if(p->prior->data==cur_e){*next_e=p->data;return TRUE;}p=p->next;}return FALSE;}查找元素地址：
DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */{ /* 在雙向鍊表L中返回第i個元素的地址。i為0，返回頭結點的地址。若第i個元素不存在，*//* 返回NULL */int j;DuLinkList p=L; /* p指向頭結點 */if(i<0||i>ListLength(L)) /* i值不合法 */return NULL;for(j=1;j<=i;j++)p=p->next;return p;}元素的插入：
Status ListInsert(DuLinkList L,int i,ElemType e){ /* 在帶頭結點的雙鏈循環線性表L中第i個位置之前插入元素e，i的合法值為1≤i≤表長+1 *//* 改進算法2.18，否則無法在第表長+1個結點之前插入元素 */DuLinkList p,s;if(i<1||i>ListLength(L)+1) /* i值不合法 */return ERROR;p=GetElemP(L,i-1); /* 在L中確定第i個元素前驅的位置指針p */if(!p) /* p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅) */return ERROR;s=(DuLinkList)malloc(sizeof(DuLNode));if(!s)return OVERFLOW;s->data=e;s->prior=p; /* 在第i-1個元素之後插入 */s->next=p->next;p->next->prior=s;p->next=s;return OK;}元素的刪除：
Status ListDelete(DuLinkList L,int i,ElemType *e){ /* 刪除帶頭結點的雙鏈循環線性表L的第i個元素，i的合法值為1≤i≤表長 */DuLinkList p;if(i<1) /* i值不合法 */return ERROR;p=GetElemP(L,i); /* 在L中確定第i個元素的位置指針p */if(!p) /* p=NULL,即第i個元素不存在 */return ERROR;*e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return OK;}正序查找：
void ListTraverse(DuLinkList L,void(*visit)(ElemType)){ /* 由雙鏈循環線性表L的頭結點出發，正序對每個數據元素調用函式visit() */DuLinkList p=L->next; /* p指向頭結點 */while(p!=L){visit(p->data);p=p->next;}printf("\n");}void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))逆序查找：
{ /* 由雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函式visit()。另加 */DuLinkList p=L->prior; /* p指向尾結點 */while(p!=L){visit(p->data);p=p->prior;}printf("\n");}雙向鍊表模板
/******************************************************檔案名稱：LinkedList.h*功能：實現雙向鍊表的基本功能*注意：為了使最終程式執行得更快，僅在Debug模式下檢測操作合法性。*另外不對記憶體分配失敗作處理,因為一般情況下應用程式有近2GB真正可用的空間*********************************************************/#pragma once#include <assert.h>template<class T>class LinkedList{private:class Node{public:T data; //數據域,不要求泛型T的實例類有無參構造函式Node* prior; //指向前一個結點Node* next; //指向下一個結點Node(const T& element,Node*& pri,Node*& nt):data(element),next(nt),prior(pri){}Node():data(data){}//泛型T的實例類的複製構造函式將被調用.在Vc2010測試可行};Node* head; //指向第一個結點public://初始化：構造一個空結點，搭建空鏈LinkedList():head(new Node()){head->prior=head->next=head;}//獲取元素總數int elementToatal()const;//判斷是否為空鏈bool isEmpty()const{return head==head->next?true:false;}//將元素添加至最後，注意node的指針設定void addToLast(const T& element){Node* ne=new Node(element,head->prior,head);head->prior=head->prior->next=ne;}//獲取最後一個元素T getLastElement()const{assert(!isEmpty());return head->prior->data;}//刪除最後一個元素，注意node的指針設定void delLastElement(){assert(!isEmpty());Node* p=head->prior->prior;delete head->prior;head->prior=p;p->next=head;}//修改最後一個元素void alterLastEmlent(const T& newElement){assert(!isEmpty());head->prior->data=newElement;}//插入元素void insertElement(const T& element,int position);//獲取元素T getElement(int index)const;//刪除元素T delElement(int index);//修改元素void alterElement(const T & Newelement,int index);//查找元素int findElement(const T& element) const;//正序遍歷void Traverse(void (*visit)(T&element));//逆序遍歷void TraverseBack(void (*visit)(T&element));//重載[]函式T& operator [](int index);//清空鍊表void clearAllElement();//銷毀鍊表~LinkedList();};/****************************************返回元素總數****************************************/template<class T>int LinkedList<T>::elementToatal()const{int Total=0;for(Node* p=head->next;p!=head;p=p->next) ++Total;return Total;}/***********************************************在position指定的位置插入元素。原來position及後面的元*素後移***********************************************/template<class T>void LinkedList<T>::insertElement(const T& element,int position){assert(position>0 && position<=elementToatal()+1);Node* p=head;while(position){p=p->next;position--;}//此時p指向要插入的結點Node* pNew=new Node(element,p->prior,p);p->prior=p->prior->next=pNew;}/****************************************返回找到的元素的副本***************************************/template<class T>T LinkedList<T>::getElement(int index)const{assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,鍊表是否空Node* p=head->next;while(--index) p=p->next;return p->data;}/***********************************刪除指定元素，並返回它**********************************/template<class T>T LinkedList<T>::delElement(int index){assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,鍊表是否空Node* del=head->next;while(--index) del=del->next;//此時p指向要刪除元素del->prior->next=del->next;del->next->prior=del->prior;T delData=del->data;delete del;return delData;}/*****************************************用Newelement代替索引為index的元素*****************************************/template<class T>void LinkedList<T>::alterElement(const T & Newelement,int index){assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,鍊表是否空Node* p=head->next;while(--index) p=p->next;p->data=Newelement;}/*********************************找到返回元素的索引，否則返回0********************************/template<class T>int LinkedList<T>::findElement(const T& element) const{Node* p=head->next;int i=0;while(p!=head){i++;if(p->data==element) return i;p=p->next;}return 0;}/****************************************正向遍歷，以鍊表中每個元素作為參數調用visit函式*****************************************/template<class T>void LinkedList<T>::Traverse(void (*visit)(T&element)){Node* p=head->next;while(p!=head){visit(p->data);//注意此時外部visit函式有許可權修改LinkedList<T>的私有數據p=p->next;}}/**************************************************反向遍歷，以鍊表中每個元素作為參數調用visit函式*************************************************/template<class T>void LinkedList<T>::TraverseBack(void (*visit)(T&element)){Node* p=head->prior;while(p!=head){visit(p->data);//注意此時外部visit函式有許可權修改LinkedList<T>的私有數據p=p->prior;}}/***************************************************返回鍊表的元素引用，並可讀寫.實際上鍊表沒有[]意義上的所有功能*因此[]函式是有限制的.重載它是為了客戶端代碼簡潔，因為從鍊表讀寫*數據是最常用的***************************************************/template<class T>T& LinkedList<T>::operator [](int index){assert(index>0 && index<=elementToatal() && !isEmpty());//[]函式使用前提條件Node* p=head->next;while(--index) p=p->next;return p->data;}/****************************清空鍊表***************************/template<class T>void LinkedList<T>::clearAllElement(){Node* p=head->next,*pTemp=0;while(p!=head){pTemp=p->next;delete p;p=pTemp;}head->prior=head->next=head;//收尾工作}/*******************************析構函式，若記憶體足夠沒必要調用該函式*******************************/template<class T>LinkedList<T>::~LinkedList(){if(head)//防止用戶顯式析構後，對象又剛好超出作用域再調用該函式{clearAllElement();delete head;head=0;}}