#include<stdio.h>
#include<stdlib.h>
#include<malloc.h> 
typedef char Elemtype;
typedef struct node
{
	Elemtype data;
	struct node *prior,*next;
}Dlink;
void Initlist(Dlink *&L)
{
	L=(Dlink *)malloc(sizeof(Dlink));
	L->prior=L->next=NULL;
}//初始化双链表
int Getlength( Dlink *L)
{
	int i=0;
	Dlink *p=L->next;
	while(p!=NULL)
	{
		i++;
		p=p->next;
	 } 
	 return i;
}//求双链表表长 
int Getelem(Dlink *L,int i,Elemtype &e)
{
	int j=1;
	Dlink *p=L->next;
	if(i<1||i>Getlength(L))
		return 0;
	while(j<i)
	{
		p=p->next;
		j++;
	}
	e=p->data;
	return 1;
}//求线性表中第i个元素
int Locate(Dlink *L,Elemtype x)
{
	int i=1;
	Dlink *p=L->next;
	while(p!=NULL&&p->data!=x)
	{
		p=p->next;
		i++;
	}
	if(p==NULL)
		return 0;
	else
		return i;		
 } //按值查找
int Inselem(Dlink *L,Elemtype x,int i)
{
	int j=1;
	Dlink *p=L,*s;
	s=(Dlink *)malloc(sizeof(Dlink));
	s->data=x;
	s->prior=s->next=NULL;
	if(i<1||i>Getlength(L)+1)
		return 0;
	while(j<i)
	{
		p=p->next;
		j++;
	}
	s->next=p->next;
	s->prior=p;
	if(p->next!=NULL)
		p->next->prior=s;
	p->next=s;
	return 1;
 } //插入元素 
 int Delelem(Dlink *L,int i)
 {
 	int j=1;
 	Dlink *p=L,*q;
 	if(i<1||i>Getlength(L))
 		return 0;
 	while(j<i)
 	{
 		p=p->next;
 		j++;
	 }
	 q=p->next;
	 p->next=q->next;
	 if(q->next!=NULL)
	 	q->next->prior=p;
	free(q);
	return 1;
 }//删除元素 
void Dislist(Dlink *L)
{
	Dlink *p=L->next;
	while(p!=NULL)
	{
		printf("%3c",p->data);
		p=p->next;
	}
	printf("\n");
}//输出元素
int main()
{
	int i;
	Elemtype e;
	Dlink *L;
	Initlist(L);
	Inselem(L,'5',1);
	Inselem(L,'2',2);
	Inselem(L,'6',3);
	Inselem(L,'4',4);
	Inselem(L,'1',5);
	Inselem(L,'7',6);
	printf("双链表为:\n");
	Dislist(L);
	printf("长度为:%d\n",Getlength(L));
	printf("请输入要查找的位置:\n");
	scanf("%d",&i);
	Getelem(L,i,e);
	printf("第%d个元素是:%c\n",i,e);
	printf("请输入要查找的元素e:");
	scanf("%s",&e);
	printf("元素 %c 是第 %d 个元素\n",e,Locate(L,e));
	printf("请输入要删除的元素位置:\n");
	scanf("%d",&i);
	Delelem(L,i);
	printf("线性表为:\n");
	Dislist(L);
	return 0;
}