双链表和循环链表

一、结构体定义

1.双链表

typedef struct DLNode
{
	int data;
	struct DLNode *prior,*next;
}DLNode;

2.循环链表

//同双链表

二、操作

1.尾插法建立双链表

void creatDListT(LNode *&L,int a[],int n)
{
	DLNode *s,*r; //s用来指向新生成的结点，r始终指向L的终端结点
	L=(DLNode*)malloc(sizeof(DLNode)); //申请头结点空间
	L->piror=NULL; //与单链表不同之处
	L->next=NULL;
	r=L; //此时头结点就是终端结点
	
	for(int i=0;i<n;++i)
	{
		s=(LNode*)malloc(sizeof(LNode)); //为新结点申请空间
		s->data=a[i];
		
		r->next=s; // r连接新结点
		s->piror=r; //与单链表不同之处
		r=r->next; // r指向s（新的终端结点）；或r=s;
	}
	r->next=NULL; //链表建立完成，终端结点的next指针指向NULL
}

2.查找结点

//同单链表，注意顺序（next 或 piror）

3插入结点

s->next=p->next;
s->piror=p;
p->next=s;
s->next->piror=s; //假如p指向最后一个结点(p->next==NULL)，此行可以去掉

4删除结点

q=p->next; //引入q只是为了释放被删除结点的空间
p->next=q->next;
q->next->piror=p;
free(q);

循环链表

//循环单链表和循环双链表的操作与单链表寄双链表类似，只需在头尾间建联系即可。
//终端结点r->next=head(L);头结点的piror指向表尾结点r。
//注意判断走到表尾的条件为p->next=head(L);