[数据结构与算法]考研数据结构:(七)循环双链表(带头节点)的基本操作(只有干货)

/*
	循环双链表的基本操作:
		(1).循环双链表的定义:
		(2).循环双链表的初始化:
		(3)、循环双链表的建立:
			a、头插法建立
			b、尾插法建立
		(4)、循环双链表的插入:
			a、后插
			b、前插
			c、指定位置插入
		(5)、循环双链表删除:
			a、按位序删
			b、前删
			c、后删
		(6)、循环双链表查找:
			a、按位查找
			b、按值查找
		(7)、循环双链表长度
		(8)、循环双链表输出
*/
#include <stdio.h>
#include <stdlib.h>

// 循环双链表的定义 :
typedef struct DNode {
	int data;
	struct DNode *prior,*next;
} DNode,*DListLink;

// 循环双链表的初始化 :
DListLink initListLink(DListLink &L) {
	L = (DNode *)malloc(sizeof(DNode));
	if(!L) return false;
	L->next = L;
	L->prior = L;
	return L;
}

// 判断双链表是否为 NULL
bool isEmpty(DListLink &L) {
	if(L->next == L) {
		return true;
	}
	return false;
}

// 判断是否为 尾节点
bool isTail(DListLink &L,DNode *p) {
	if(p->next == L) return true;
	return false;
}

// 按位查找 : 返回第 I 个节点
DNode *getElem(DListLink &L,int i) {
	DNode *p = L->next;
	int j = 1;
	while(p != L && j < i) {
		p = p->next;
		j ++;
	}
	if(p->next == L) return NULL;
	return p;
}

// 按值查找 : 返回数据域是 e 的节点
DNode *locateElem(DListLink &L,int e) {
	DNode *p = L->next;
	if(!p) return NULL;
	while(p != L && p->data != e) {
		p = p->next;
	}
	return p;
}

// 后插 : 在 P 节点之后插入节点 s
bool insertNextNode(DNode *p,DNode *s) {
	if(!p || !s) return false;
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

// 后插 : 在 p 节点后插入值是 e 的节点
bool insertNextNodeE(DNode *p,int e) {
	if(!p) return false;
	DNode *s;
	s = (DNode *)malloc(sizeof(DNode));
	if(!s) return false;
	s->data = e;
	return insertNextNode(p,s);
}

// 前插 : 在 p 节点前擦汗如节点 s
bool insertBeforeNode(DNode *p,DNode *s) {
	if(!p || !s) return false;
	return insertNextNode(p->prior,s);
}

 //按位插入 : 在第 i 个位置插入值是 e 的节点(位序 i)
bool insertPosition(DListLink &L,int i,int e) {
	DNode *p = getElem(L,i - 1);
	if(!p) return false;
	return insertNextNodeE(p,e);
}

// 删除 : 删除 p 节点的后继节点
bool deleteNextNode(DNode *p) {
	DNode *q = p->next;
	p->next = q->next;
	q->next->prior = p;
	free(q);
	return true;
}

// 删除 : 删除指定节点 s
bool deleteNode(DListLink &L,DNode *s) {
	if(!s) return false;
	return deleteNextNode(s->prior);
}

// 删除 : 删除位序 i 的节点, e 是 i 节点的值
bool deletePositionNode(DListLink &L,int i,int &e) {
	DNode *p;
	p = getElem(L,i - 1);
	DNode *q = p->next;
	e = q->data;
	return deleteNode(L,q);
}

// 循环双链表的长度
int length(DListLink &L) {
	int len = 0;
	DNode *p = L->next;
	while(p != L) {
		p = p->next;
		len ++;
	}
	return len;
}

// 尾插法建立循环双链表
DListLink tailCreateListLink(DListLink &L) {
	initListLink(L);
	DNode *s,*p = L;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		insertNextNodeE(p,x);
		p = p->next;
	}
	return L;
}

// 头插法建立循环双链表
DListLink headCreateListLink(DListLink &L) {
	initListLink(L);
	DNode *s;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		s = (DNode *)malloc(sizeof(DNode));
		insertNextNodeE(L,x);
	}
	return L;
}


// 循环双链表的输出
void print(DListLink &L ) {
	DNode *p = L->next;
	while(p != L) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
	return ;
}

int main() {
	DListLink L;
	// 头插法建立循环双链表
//	headCreateListLink(L);
	// 尾插法建立循环双链表
	printf("------------尾插法建立循环双链表:-----------------\n");
	tailCreateListLink(L);
	print(L);

	printf("--------------循环单链表的长度-------------\n");
	int len = length(L);
	printf("循环单链表的长度是: %d\n",len);

	printf("--------------按位查找 : 查找位序是 3 的循环单链表节点-------------\n");
	DNode *p = getElem(L,3);
	printf("按位查找 : 查找位序是 3 的循环单链表节点 %d\n",p->data);


	printf("--------------按值查找 : 返回数据域是 999 的节点-------------\n");
	DNode *q = locateElem(L,999);
	if(q->data == 999) printf("已找到节点\n");
	else printf("未找到节点!\n");

	printf("--------------后插 : 在节点 p(3) 后面插入数据是 1000 的节点-------------\n");
	print(L);
	insertNextNodeE(p,1000);
	printf("--------------后插 : 在节点 p(3) 后面插入数据是 1000 的节点 后的链表 : -------------\n");
	print(L);

	printf("--------------插入 : 在第 2 个位置插入节点 666-------------\n");
	print(L);
	insertPosition(L,2,666);
	printf("--------------插入 : 在第 2 个位置插入节点 666 的节点后的链表 :-------------\n");
	print(L);

	printf("--------------前插操作 : 在 p 节点前插入节点 u(333)-------------\n");
	DNode *u;
	u = (DNode *)malloc(sizeof(DNode));
	u->data = 333;
	insertBeforeNode(p,u);
	printf("--------------前插操作 : 在 p 节点前插入节点 u(333) 的节点后的链表:-------------\n");
	print(L);

	printf("--------------删除 : 删除指定节点 p-------------\n");
	print(L);
	deleteNode(L,p);
	printf("--------------删除 : 删除指定节点 p 后的链表:-------------\n");
	print(L);


	return 0;
}