当前位置:编程学习 > VC++ >>

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 ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,