双向链表的创建和遍历

双向循环链表

在单链表L中，查找ai的后继 Next(L, ai)，耗时仅为0(1)，因为取ai之后继指针即可。但查找ai的直接前驱 Prior(L, ai)，则需从链表的头指针开始，找到结点ai前一结点即是。故运算Prior(L,ai)依赖表长n，耗时为0(n)。

单链表的缺点

若链表中有一指针值被破坏，则整个链表脱节。这是单链表的不足，为此，引入双向链表。

双向循环链表结点描述

先定义双向链表中的结点： 其中，data和next同单链表，增加一指针域prior，其指向本结点的直接前驱。

结点描述：

typedef int data_t;
 
typedef struct node{
	data_t data;
	struct node *prior;
	struct node *next;
}dlistnode;

双向链表的创建

dlistnode* dlist_create(){
	dlistnode *H,*r,*p;
	int n;
	
	if((H=(dlistnode *)malloc(sizeof(dlistnode)))==NULL)
	{
		puts("malloc failed");
		return NULL;
	}
 
	H->prior = H;
	H->next = H;
	r = H;
 
	while(1){
		printf("please input(-1 exit):");
		scanf("%d",&n);
		if(n==-1)
			break;
 
		if((p=(dlistnode *)malloc(sizeof(dlistnode)))==NULL)
		{
			printf("malloc failed\n");
			return NULL;
		}
 
		p->data=n;
		p->prior=r;
		p->next=r->next;
		r->next=p;
		H->prior=p;
		r=p;
	}
 
	return H;
}

双向链表的遍历

void dlist_show(dlistnode* H)
{
	dlistnode *p;
 
	p=H->next;
	while(p!=H)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	putchar(10);//换行
}

双向链表的创建和遍历完整代码

#include 
#include 
 
typedef int data_t;
 
typedef struct node{
	data_t data;
	struct node *prior;
	struct node *next;
}dlistnode;
 
dlistnode* dlist_create(){
	dlistnode *H,*r,*p;
	int n;
	
	if((H=(dlistnode *)malloc(sizeof(dlistnode)))==NULL)
	{
		puts("malloc failed");
		return NULL;
	}
 
	H->prior = H;
	H->next = H;
	r = H;
 
	while(1){
		printf("please input(-1 exit):");
		scanf("%d",&n);
		if(n==-1)
			break;
 
		if((p=(dlistnode *)malloc(sizeof(dlistnode)))==NULL)
		{
			printf("malloc failed\n");
			return NULL;
		}
 
		p->data=n;
		p->prior=r;
		p->next=r->next;
		r->next=p;
		H->prior=p;
		r=p;
	}
 
	return H;
}
 
void dlist_show(dlistnode* H)
{
	dlistnode *p;
 
	p=H->next;
	while(p!=H)
	{
		printf("%d ",p->data);
		p=p->next;
	}
//putchar输出字符，因为10是整数，所以系统只能将其转换为对应的ASCII字符。
//ASCII中10对应的是，line feed（换行）
	putchar(10);
}
 
int main(int argc, const char *argv[])
{
	dlistnode *H;
 
	H=dlist_create();
	dlist_show(H);
 
	return 0;
}