双向循环链表

//file1
//双向循环链表

//结点
#define ElemType int

typedef struct DuCirNode
{
ElemType data;
struct DuCirNode *prior,*next;
}LNode,*Link;
//表
struct DuCirList
{
Link head,tail;
int len;
};

//file2
#include "DoubleCircularList.h"
#include
using namespace std;
//建立空的双向循环链表

//--------------------------------------

void InitDuCirList(DuCirList &L);
void InsertNode(DuCirList &L,int i);

void InsertFirst(DuCirList &L,LNode *CurNode);
void InsertLast(DuCirList &L,LNode *CurNode);

//--------------------------------------
//建立空双向循环链表
void InitDuCirList(DuCirList &L)
{

L.head=NULL;
L.tail=NULL;
// L.head->next=NULL;
// L.head->prior=NULL;

// L.tail->next=NULL;
// L.tail->prior=NULL;

L.len=0;
}


//-----------------------------------------
//插入结点
void InsertNode(DuCirList &L,int i)
{
//新建一个结点
int count;
Link CurPointer;
Link Pointer;

CurPointer=new LNode;

if(!CurPointer)
{
cout<<"OverFlow!"<return;
}

cout<<"please input the new node's value:"<cin>>CurPointer->data;

CurPointer->prior=NULL;
CurPointer->next=NULL;

//i的合法性验证
if(i<1 || i> L.len +1)
{
cout<<"the position i is overflow"<return;
}

//测试
if(i==1)
{
InsertFirst(L,CurPointer);
cout<<"First already inserted!"<return;
}

if(i==L.len+1)
{
InsertLast(L,CurPointer);
cout<<"Last already inserted!"<return;
}

/*
//当表为空时
if(L.len==0 && i==1)
{
L.head=L.tail=CurPointer;
CurPoniter.prior=CurPointer.next=*CurPointer;

return;
}
*/
//当表不为空时
count=1;
Pointer=L.head;


while(count{
count++;
Pointer=Pointer->next;
}

CurPointer->prior=Pointer->prior;
Pointer->prior->next=CurPointer;

Pointer->prior=CurPointer;
CurPointer->next=Pointer;

L.len++;

cout<<"already inserted"<
}
//-------------------------------------
//删除结点
void DeleteNode(DuCirList &L,int i)
{
Link CurPointer=NULL;
Link Pointer=NULL;
int count;

if(i<1 || i> L.len)
{
cout<<"the position i is overflow"<return;
}

if(i==1)
{
CurPointer=L.head;
L.head=CurPointer->next;
L.head->prior=L.tail;
L.tail->next=L.head;

delete CurPointer;

L.len--;

cout<<"First already delete!"<
return;
}

if(i==L.len)
{
CurPointer=L.tail;
L.tail=CurPointer->prior;
L.tail->next=L.head;
L.head->prior=L.tail;

delete CurPointer;

L.len--;

cout<<"Last already Deletesd!"<
return;
}

count=1;
Pointer=L.head;


while(count{
count++;
Pointer=Pointer->next;
}

CurPointer=Pointer;

Pointer->next->prior=CurPointer->prior;
Pointer->prior->next=CurPointer->next;

delete CurPointer;

L.len--;

cout<<"already deleted!"<

}

//------------

-------------------------
//插入到第一个结点
void InsertFirst(DuCirList &L,LNode *CurNode)
{
//
if(L.len==0)
{
L.head=L.tail=CurNode;
}

CurNode->next=L.head;
CurNode->prior=L.tail;

L.head->prior=CurNode;
L.tail->next=CurNode;

L.len++;
L.head=CurNode;
}
//---------------------------------------
//插入最后一个结点
void InsertLast(DuCirList &L,LNode *CurNode)
{
if(L.len==0)
{
L.head=L.tail=CurNode;
}


CurNode->next=L.head;
CurNode->prior=L.tail;

L.head->prior=CurNode;
L.tail->next=CurNode;

L.len++;
L.tail=CurNode;
}


//-----------------------------------
//顺序输出双向循环链表元素
void DisplayList(DuCirList &L)
{
int count;
Link Pointer;

count=0;
Pointer=L.head;
while(count{
count++;
cout<data<<" ";
Pointer=Pointer->next;
}

cout<}

//------------------------------------
//逆序输出双向循环链表元素
void DisDisplayList(DuCirList &L)
{
int count;
Link Pointer;

count=0;
Pointer=L.tail;
while(count{
count++;
cout<data<<" ";
Pointer=Pointer->prior;
}

cout<}

//------------------------------------
//逆置双向循环链表
void ConverseDuCirList(DuCirList &L)
{
int count=0;
Link Pointer=NULL;
Link CurPointer=NULL;

while(count{
CurPointer=L.head;
L.head=L.head->next;

if(count==0)
{
Pointer=CurPointer;
}

CurPointer->next=Pointer;
Pointer->prior=CurPointer;

Pointer=CurPointer;

count++;

}

L.tail=L.head;
L.head=Pointer;

L.tail->next=L.head;
L.head->prior=L.tail;

}

//测试
#include "DoubleCircularList.h"
#include
using namespace std;

void InitDuCirList(DuCirList &L);
void InsertNode(DuCirList &L,int i);
void DeleteNode(DuCirList &L,int i);
void DisplayList(DuCirList &L);
void DisDisplayList(DuCirList &L);
void ConverseDuCirList(DuCirList &L);
//----------------------------------

int main()
{
DuCirList List;
int pos;

InitDuCirList(List);

for(int i=1;i<4;i++)
{
InsertNode(List,i);
}

// InsertNode(List,1);

// InsertNode(List,2);

// InsertNode(List,3);

DisplayList(List);

cout<<"Please input the position you want to insert:"<cin>>pos;

InsertNode(List,pos);

DisplayList(List);
DisDisplayList(List);

cout<<"Please input the position you want to delete:"<cin>>pos;

DeleteNode(List,pos);
DisplayList(List);
DisDisplayList(List);

ConverseDuCirList(List);
DisplayList(List);
DisDisplayList(List);

return 0;
}