双向链表的查找、插入和删除

双向链表的查找

#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);
}
 
dlistnode* dlist_get(dlistnode *H,int pos)
{
	int i=0;
	dlistnode *p=H;
 
	if(pos <0){
		puts("pos < 0,invalid!");
		return NULL;
	}
 
	while(i
		p=p->next;
		i++;
		if(p==H){
			puts("pos > length,invalid");
			return NULL;
		}
 
	}
	return p;
}
 
int main(int argc, const char *argv[])
{
	dlistnode *H,*p;
	int pos;
 
 
	H=dlist_create();
	dlist_show(H);
 
	while(1)
	{
		printf("input pos(-1 exit):");
		scanf("%d",&pos);
		if(pos==-1)
			break;
		p=dlist_get(H,pos);
 
		if(p)
			printf("%d\n",p->data);
	}
	return 0;
}

双向链表的插入

从指定节点前面插入数据

#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);
}
 
dlistnode* dlist_get(dlistnode *H,int pos)
{
	int i=0;
	dlistnode *p=H;
 
	if(pos <0){
		puts("pos < 0,invalid!");
		return NULL;
	}
 
	while(i
		p=p->next;
		i++;
		if(p==H){
			puts("pos > length,invalid");
			return NULL;
		}
 
	}
	return p;
}
 
int dlist_insert(dlistnode *H,data_t value,int pos)
{
	dlistnode *p,*q;
 
	p=dlist_get(H,pos);
	if(p==NULL)
		return -1;
 
	if((q=(dlistnode *)malloc(sizeof(dlistnode)))==NULL)
	{
		printf("malloc failed\n");
		return -1;
	}
	
	q->data = value;
 
	q->prior=p->prior;
	q->next=p;
	p->prior->next=q;
	p->prior = q;
 
	return 0;
}
 
int main(int argc, const char *argv[])
{
	dlistnode *H;
	int pos;
	data_t data;
 
 
	H=dlist_create();
	dlist_show(H);
 
	while(1)
	{
		printf("input pos(-1 exit):");
		scanf("%d",&pos);
		if(pos==-1)
			break;
		printf("input data:");
		scanf("%d",&data);
		dlist_insert(H,data,pos);
	}
	dlist_show(H);
 
	return 0;
}

双向链表的删除

#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);
}
 
dlistnode* dlist_get(dlistnode *H,int pos)
{
	int i=0;
	dlistnode *p=H;
 
	if(pos <0){
		puts("pos < 0,invalid!");
		return NULL;
	}
 
	while(i
		p=p->next;
		i++;
		if(p==H){
			puts("pos > length,invalid");
			return NULL;
		}
 
	}
	return p;
}
 
int dlist_delete(dlistnode *H,int pos)
{
	dlistnode *p;
 
	p=dlist_get(H,pos);
	if(p==NULL)
		return -1;
 
	p->prior->next = p->next;
	p->next->prior = p->prior;
 
	free(p);
	p=NULL;
 
	return 0;
}
 
int main(int argc, const char *argv[])
{
	dlistnode *H;
	int pos;
 
	H=dlist_create();
	dlist_show(H);
 
	while(1)
	{
		printf("input pos(-1 exit):");
		scanf("%d",&pos);
		if(pos==-1)
			break;
		dlist_delete(H,pos);
	}
	dlist_show(H);
 
	return 0;
}