標籤:雙鏈表元素操作

雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個數據結點中都有兩個指針,分別指向直接後繼和直接前驅。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。

1鏈表的操作

銷毀雙向循環鏈表L
void DestroyList(DuLinkList *L)
{
DuLinkList q,p=(*L)->next; "
while(p!=*L) "
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
}
驗證是否為空表
Status ListEmpty(DuLinkList L)
{ /* 初始條件:線性表L已存在
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}

2元素的操作

賦值
Status GetElem(DuLinkList L,int i,ElemType *e)
{ "
int j=1; "
DuLinkList p=L->next; "
while(p!=L&&j<i)
{
p=p->next;
j++;
}
if(p==L||j>i) "
return ERROR;
*e=p->data; "
return OK;
}
查找元素前驅
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{ "
"
DuLinkList p=L->next->next; "
while(p!=L) "
{
if(p->data==cur_e)
{
*pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
查找元素地址
DuLinkList GetElemP(DuLinkList L,int i) "
{ "
"
int j;
DuLinkList p=L; "
if(i<0||i>ListLength(L)) "
return NULL;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
元素的刪除
Status ListDelete(DuLinkList L,int i,ElemType *e)
{ "
DuLinkList p;
if(i<1) "
return ERROR;
p=GetElemP(L,i); "
if(!p) "
return ERROR;
*e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
逆序查找
{ "
DuLinkList p=L->prior; "
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}

3雙向鏈表模板

/*****************************************************
*文件名: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;
}
}
上一篇[低丘緩坡]    下一篇 [製表符]

相關評論

同義詞:暫無同義詞