学步园

循环双向链表，包括链表的结点插入，删除等操作。

相比非循环的双向链表更加好控制一点。

// LinkList_D2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream"

using namespace std;
typedef int DataType;
typedef struct DLNode
{
	DataType data;
	struct DLNode * prior;
	struct DLNode * next;
}DLNode,*DLinkList;

void PrintDLinkList(DLinkList &L);
void CreateDList(DLinkList &L,int n);
int DListInsert(DLinkList &L,int i,DataType e);
int DListDelete(DLinkList &L,int i,DataType &e);

// 循环双向链表
int _tmain(int argc, _TCHAR* argv[])
{
	// 创建链表
	DLinkList L;
	CreateDList(L,5); //创建具有5个结点的双向链表
	PrintDLinkList(L); // 输出链表
	// 测试插入元素
	DListInsert(L,1,100); //在第一个元素前插入元素
	PrintDLinkList(L);
	DListInsert(L,2,200);
	PrintDLinkList(L);
	// 测试删除元素
	printf("node deleted\n");
	int e;
	DListDelete(L,1,e);
	PrintDLinkList(L);

	printf("node deleted\n");
	DListDelete(L,6,e);
	PrintDLinkList(L);

	printf("node deleted\n");
	DListDelete(L,3,e);
	PrintDLinkList(L);

	getchar();
	getchar();
	return 0;
}

// 输出结点
void PrintDLinkList(DLinkList &L)
{
	DLinkList p=L->next; //指向第一个结点
	while (p!=L) // 判断是否返回头结点
	{
		printf("%5d",p->data);
		p=p->next;
	}
	printf("\n");
}


// 创建长度为n的链表,在头结点之前插入新的结点,循环链表
void CreateDList(DLinkList &L,int n)
{
	L=(DLinkList)malloc(sizeof(DLNode));
	L->next=L;
	L->prior=L; // 让头结点的next, prior都指向自身
	printf("please input n nodes:\n");
	for(int i=n;i>0;--i)
	{
		DLinkList p=(DLinkList)malloc(sizeof(DLNode));
		scanf("%d",&p->data); 
		p->prior=L;
		L->next->prior=p;
		p->next=L->next;
		L->next=p;
	}
}

// 在第i个元素之前插入元素,循环链表
int DListInsert(DLinkList &L,int i,DataType e)
{
	DLinkList p=L->next; //指向第一个结点
	int j=1;
	while(p!=L&&j<i)
	{
		p=p->next;
		j++;
	}
	if (p==L||j>i)
	{
		return -1;
	}
	DLinkList s=(DLinkList)malloc(sizeof(DLNode));
	if(!s) return -1;
	s->data=e;
	s->prior=p->prior;
	p->prior->next=s;
	s->next=p;
	p->prior=s;
	return 1;
}

// 删除指定位置的元素, 循环链表
int DListDelete(DLinkList &L,int i,DataType &e)
{
	DLinkList p=L->next; // 指向第一个元素
	int j=1;
	while(p!=L&&j<i)
	{
		p=p->next;
		j++;
	} // 指向第i个元素
	if(p==L||j>i) return -1;
	// 删除元素
	p->prior->next=p->next;
	p->next->prior=p->prior;
}