VC++2012编程演练数据结构双循环链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

我们来创建一个工程实践之

类的声名如下

[cpp]
#if !defined(AFX_DCIRLINKL_H__4D93E797_B8BC_4781_BD9A_0EF8A6458A75__INCLUDED_)
#define AFX_DCIRLINKL_H__4D93E797_B8BC_4781_BD9A_0EF8A6458A75__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

//双向循环链表的类定义
typedef int ElemType;
//双向链表结点的类型定义
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior;//左指针
struct DuLNode *next;//右指针
}DuLNode;
#define LEN 20

class DuLinkList
{private:
DuLNode *head;//指向表头的指针
DuLNode *curr;//当前结点指针
int count;// 双向循环链表的结点个数
public:
    //构造函数
    DuLinkList();
    //析构函数
    ~DuLinkList(){delete head;}
    //创建有序或无序的带头结点的双向循环链表
    DuLNode *CreateCLinkL(int,int,int mark=0);
    //清空单循环链表
    void ClearCList();
    //求双向循环链表长度
    int CListSize();
    //检查双向循环链表是否为空
    bool CListEmpty();
    //返回指向第pos个结点的指针
    DuLNode *Index(int pos);
    //返回双向循环链表中指定序号的结点值
    ElemType GetElem(int pos);
    //遍历双向循环链表
    void TraverseCList();
    //当前指针curr指向pos结点并返回curr
    DuLNode *Reset(int pos=0);
    //当前指针curr指向下一结点并返回
    DuLNode *Next();
    //当前指针curr指向上一结点并返回
    DuLNode *Prior();
    // 判双向循环链表当前指针curr==head 否
    bool EndOCList();
    //判双向循环链表当前指针curr->next是否到达表尾
    bool EndCList();
    //判双向循环链表当前指针curr->prior是否到达表尾
    bool PEndCList();
    //删除curr->next所指结点,并返回所删结点的data
    ElemType DeleteNt();
    //从双向循环链表中查找元素
    bool FindCList(ElemType& item);
    //更新双向循环链表中的给定元素
    bool UpdateCList(const ElemType &item,ElemType &e);
    //向链表中第pos个结点前插入域值为item的新结点
    void InsertCLfront(const ElemType& item,int pos);
    //向链表中第pos个结点后插入域值为item的新结点
    void InsertCLafter(const ElemType& item,int pos);
    //从链表中删除第pos个结点并返回被删结点的data
    ElemType DeleteCList(int pos);
};

#endif // !defined(AFX_DCIRLINKL_H__4D93E797_B8BC_4781_BD9A_0EF8A6458A75__INCLUDED_)

类的实现如下
[cpp]
#include "stdafx.h"
#include "dcirlinkl.h"

//双向循环链表的实现
#include<iostream>
#include<stdlib.h>

//构造函数
DuLinkList::DuLinkList()
{head=new DuLNode;
head->prior=head;
head->next=head;
curr=NULL;
count=0;
}
//创建有序或无序的带头结点的双向循环链表
DuLNode *DuLinkList::CreateCLinkL(int n,int m,int mark)
{ElemType x,a[LEN];
srand(m);
for(int i=0;i<n;i++) a[i]=rand()%100;
for(int i=0;i<n-1;i++)
{int k=i;
   for(int j=i+1;j<n;j++)
    if(a[k]>a[j]) k=j;
   if(k!=i)
   {x=a[k];a[k]=a[i];a[i]=x;}}
DuLNode *p;
head=new DuLNode;
head->prior=NULL;
head->next=curr=p=new DuLNode;
curr->prior=head;
for(int i=0;i<n;i++){
if(mark==1) p->data=a[i];//升序
else
   if(mark==-1) p->data=a[n-1-i];//降序
   else p->data=rand()%100;//无序
if(i<n-1){curr=curr->next=new DuLNode;
   curr->prior=p;p=curr;}
count++;}
head->prior=curr;
curr->next=head;
return head;
}
//清空双向循环链表
void DuLinkList::ClearCList()
{DuLNode *cp,*np;
cp=head->next;
while(cp!=head)
{np=cp->next;delete cp;cp=np;}
head=NULL;
}
//求双向循环链表长度
int DuLinkList::CListSize()
{DuLNode* p=head->next;
int i=0;
while(p!=head)
{i++;p=p->next;}
return i;
} www.zzzyk.com
//检查双向循环链表是否为空
bool DuLinkList::CListEmpty()
{return head->next==head;}
//返回指向第pos个结点的指针
DuLNode *DuLinkList::Index(int pos)
{if(pos<1)
{cerr<<"pos is out range!"<<endl;exit(1);}
DuLNode* p=head->next;
int i=0;
while(p!=head)
{i++;
   if(i==pos) break;
   p=p->next;}
if(p!=head) return p;
else {cerr<<"pos is out range!"<<endl;
return NULL;}
}
//返回双向循环链表中指定序号的结点值
ElemType DuLinkList::GetElem(int pos)
{if(pos<1)
{cerr<<"pos is out range!"<<endl;exit(1);}
DuLNode* p=head->next;
int i=0;
while(p!=head)
{i++;
   if(i==pos) break;
   p=p->next;}
if(p!=head) return p->data;
else {cerr<<"pos is out range!"<<endl;
return pos;}
}
//遍历双向循环链表
void DuLinkList::TraverseCList()
{DuLNode *p=head->next;
while(p!=head)
{cout<<setw(4)<<p->data;
   p=p->next;}
cout<<endl;
}
//当前指针curr指向pos结点并返回curr
DuLNode *DuLinkList::Reset(int pos)
{DuLNode* p=curr=head->next;
int i=-1;
while(p!=head)
{i++;
   if(i==pos) bre

补充：软件开发 , Vc ,