双向链表.cpp

属于利用C++开发的数据结构代码

#include"iostream.h"
#include"stdlib.h"
#define NULL 0

typedef struct DulNode
{
	int data;
	struct DulNode *prior;
	struct DulNode *next;
}DulNode,*DuLinkList;

int length;

void PrintDuList(DuLinkList L)
{
	DuLinkList p;
	cout<<"现在的链表是:"<<endl;
	p=L->next;
	while(p!=NULL)
	{
		cout<<p->data<<' ';
		p=p->next;
	}
	cout<<endl;
}


DuLinkList ListInit_DuL()
{
	DuLinkList q,p,L;
	int a;
	q=(DuLinkList)malloc(sizeof(DulNode));
	q->prior=NULL;
	q->next=NULL;
	L=q;
	cout<<"请输入链表中的数字元素(以0结束):"<<endl;
	cin>>a;
	for(length=1;a!=0;length++)
	{
		p=(DuLinkList)malloc(sizeof(DulNode));
		p->data=a;
		if(q->next==NULL)
		{
			p->prior=q; p->next=q->next;
			q->next=p;
			q=p;
		}
		else
		{
			p->prior=q;        p->next=q->next;
			q->next->prior=p;  q->next=p;
			q=p;
		}
		cin>>a;
	}
	PrintDuList(L);
	return L;
}
	

DuLinkList GetElemP_DuL(DuLinkList L,int i)
{
	//L为带头结点的但链表的头指针
	//当第i个元素存在时返回指向该节点的指针,否则返回NULL
	DuLinkList p;
	int j;
	p=L->next; j=1;
	while(p&&j<i)
	{
		p=p->next; ++j;
	}
	if(!p||j>i) return NULL;
	return p;
}

int ListInsert_DuL(DuLinkList &L,int i,int e)
{
	//在带头结点的双链循环线性表L中第i个位置之前插入元素e
	//成功返回1；不存在第i个元素返回0
	DuLinkList p,s;
	if(!(p=GetElemP_DuL(L,i)))
		return 0;
	if(!(s=(DuLinkList)malloc(sizeof(DulNode)))) return 0;
	s->data=e;
	s->prior=p->prior; p->prior->next=s;
	s->next=p;         p->prior=s;
	return 1;
}


int ListDelete_DuL(DuLinkList &L,int i,int e)
{
	//删除带头结点的双链循环线性表L中第i个元素
	DuLinkList p;
	if(!(p=GetElemP_DuL(L,i)))
		return 0;
	e=p->data;
	if(p->next==NULL)
		p->prior->next=p->next;
	else
	{
		p->prior->next=p->next;
		p->next->prior=p->prior;
	}
	delete p;
	return 1;
}

void main()
{
	int a,i,b,e=0;
	DuLinkList L;
	L=ListInit_DuL();
	cout<<"你现在可以进行以下操作:"<<endl;
	cout<<"1.插入	2.删除	0.退出"<<endl;
	cout<<"请输入你要进行的操作代码:";
	cin>>a;
	while(a!=0)
	{
		switch(a)
		{
		case 1:
			cout<<"请输入你要插入的数字:";
			cin>>b;
			cout<<"请输入你要插入到第几个元素之前:";
			cin>>i;
			if(ListInsert_DuL(L,i,b)==1)
				PrintDuList(L);
			else
				cout<<"链表中不存在第"<<i<<"个元素."<<endl;
			break;
		case 2:
			cout<<"请输入你要删除第几个元素:";
			cin>>i;
			if(ListDelete_DuL(L,i,e)==1)
				PrintDuList(L);
			else
				cout<<"链表中不存在第"<<i<<"个元素."<<endl;
			break;
		}
		cout<<"请输入你要进行的操作代码:";
		cin>>a;
	}
}