十-线性表-双链表

2017-01-04 19:18:27来源:CSDN作者:liuxiao2030人点击

第七城市

双链表可以类似于单链表的结点类型定义,只不过在结点中多了一个指向前向结点域的指针。

template<class T>struct DLinkList{	T data;   //存放数据元素;	DLinkList<T> *next; //指向下一个结点的域;	DLinkList<T> *prior; //指向前一个结点的域;};

双链表类模板DLinkListClass<T>的基本运算方法如下:

template<class T>   class DLinkListClass  //双链表类模板;{	DLinkList<T>  *dhead; //双链表头结点指针;public:	DLinkListClass();	~DLinkListClass();	void CreateListF(T a[],int n);   //采用头插法建立双链表;	void CreateListR(T a[],int n);   //采用尾插法建立双链表;	void DispList();                 //输出双链表中的所有结点值;	int ListLength();                //求双链表数据结点的个数;	bool GetElem(int i,T &e);        //求双链表中的某个数据元素值;	int LocateElem(T e);             //按元素值查找;	bool ListInsert(int i,T e);      //插入数据元素;	bool ListDelete(int i);          //删除数据元素;};

构造函数:

template<class T>DLinkListClass<T>::DLinkListClass(){	dhead=new DLinkList<T>();	dhead->prior=dhead->next=NULL;}
析构函数:
template<class T>DLinkListClass<T>::~DLinkListClass(){	DLinkList<T> *p,*pre;	pre=dhead;	p=pre->next;	while(p!=NULL)	{		delete pre;		pre=p;		p=p->next;	}	delete pre;}

双链表结点中有两个指针域,一个指向其后继结点,另一个指向其前趋结点。因此,双链表中访问一个结点的前后结点更方便。

1、建立双链表

头插法,类似于单链表:

template<class T>void DLinkListClass<T>::CreateListF(T a[],int n){	DLinkList<T> *p ;	p=dhead;	for (int i=0;i<n;i++)	{		DLinkList<T> *s=new DLinkList<T>();		s->data=a[i];		s->next=p->next;		if (p->next!=NULL)			p->next->prior=s;		p->next=s;		s->prior=dhead;	}}

尾插法:

template<class T>void DLinkListClass<T>::CreateListR(T a[],int n){	DLinkList<T> *p;	p=dhead;	for (int i=0;i<n;i++)	{		DLinkList<T> *s=new DLinkList<T>();		s->data=a[i];		p->next=s;		s->prior=p;		p=s;	}	p->next=NULL;}
双链表有些运算可参考前面的单链表,这里补充双链表的插入和删除算法。
插入算法:
template<class T>bool DLinkListClass<T>::ListInsert(int i,T e)//i表示插入的逻辑位置;{	int j=0;	DLinkList<T> *p;	p=dhead;  //p指向头结点;	while(j<i-1&&p!=NULL)//因为插入的逻辑位置为i,所以查找第i-1个结点;	{		j++;		p=p->next;	}	if (p==NULL)		return false;	else	{		DLinkList<T> *s=new DLinkList<T>();		s->data=e;		s->next=p->next;		if (p->next!=NULL)//若*p结点存在后继结点,修改其prior域;			p->next->prior=s;		s->prior=p;		p->next=s;	}}
删除算法:
template<class T>bool DLinkListClass<T>::ListDelete(int i){	DLinkList<T> *p;	p=dhead;	int j=0;	while(j<i-1&&p!=NULL)	{		j++;		p=p->next;	}	if (p==NULL)		return false;	else	{		DLinkList<T> *q=p->next;		if (q==NULL)			return false;		p->next=q->next;		if (p->next!=NULL)			p->next->prior=p;		delete q;		return ture;	}}




第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台