数据结构学习笔记三 循环链表及双向链表

一 ：循环链表
首位相接的链表，将单链表的尾指针指向表头结点，就得到了单循环链表，
一般，在循环链表中设置一个头结点，这样空的循环链表就是自成循环的头结点表示；另外多采用
尾指针表示单循环链表，比如尾指针是rear,则rear->next->next和rear分别表示头结点和尾结点。

优点：从任意结点都可以访问到表中所有结点。

二 ：双链表
在单链表中每个节电里面再增加一个指向其直接前驱的指针域prior.就形成了双（向）链表。
如果将头结点和尾结点连接起来就是双向循环链表

双链表使得插入和删除（无论是插在前面还是后面）要比单链表简单。

下面是简单的双链表实现：

#include "stdlib.h"
#include "stdio.h"
typedef char DataType;
typedef struct dlistnode {
	DataType data;
	struct dlistnode *prior,*next;
} DListNode;
typedef DListNode * DLinkList;
DLinkList CreateListD(void) {
	char ch;
	DLinkList head =(DLinkList)malloc(sizeof(DListNode));// 生成一个头结点
	DListNode * s1,* s2;			//工作指针
	s2=head;
	while((ch=getchar())!='\n') {
		s1=(DLinkList)malloc(sizeof(DListNode));//生成新的节点
		s1->data=ch;
		s2->next=s1;
		s1->prior=s2;
		s2=s1;
	}
	s2->next=NULL;
	return head;
}
// 插入指定元素前面
void DInsertBefore(DListNode *p,DataType x) {
	DListNode * s=(DLinkList)malloc(sizeof(DListNode));	//生成新的节点
	s->data=x;
	s->prior=p->prior;
	s->next=p;
	p->prior->next=s;
	p->prior=s;
}
// 删除指定的元素
void DDeleteNode(DListNode *p) {
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);
}

// 打印链表
void PrintAll(DLinkList head) {
	DListNode *p;
	p=head;
	printf("链表元素一览：\n");
	while(p!=NULL) {
		printf("%c\n",p->data);
		p=p->next;
	}
}
main() {
	DLinkList DL=CreateListD();
	PrintAll(DL);
}