#include <stdio.h>
#include <stdlib.h>
//雙鏈表的定義：
typedef char DataType;
typedef struct dlistnode	//結點類型定義
{	DataType data;
	struct dlistnode *prior,*next;
}DListNode;
typedef DListNode *DLinkList;

void main()
{
	DLinkList head;
	DListNode *p;
	DataType x;
	int i;
	DLinkList DCreateList(void);
	DLinkList DGetNode(DLinkList head,int i);
	void DInsertBefore(DLinkList p,DataType x);
	void DPrintList(DLinkList head);
	head=DCreateList();		//建立雙鏈表
	DPrintList(head);		//打印雙鏈表
	printf("請輸入欲插入的元素：");
	scanf("%c",&x);
	printf("請輸入欲插入元素的位置：");
	scanf("%d",&i);
	p=DGetNode(head,i);		//尋找第i個結點
	if(p==NULL)
	{	printf("插入位置非法\n");
		exit(0);
	}
	DInsertBefore(p,x);
	DPrintList(head);		//打印雙鏈表
}

//雙鏈表的建立：
DLinkList DCreateList(void)
{	char ch;
	DLinkList head=(DListNode *)malloc(sizeof(DListNode));
	DListNode *s,*r;
	head->next=NULL;
	head->prior=NULL;
	r=head;					//尾指針初值指向頭結點
	while ((ch=getchar())!='\n')
	{	s=(DListNode *)malloc(sizeof(DListNode));	//生成新結點
		s->data=ch;
		r->next=s;
		s->prior=r;
		r=s;
	}
	r->next=head;
	head->prior=r;
	return head;			//返回頭指針
}

//雙鏈表的打印：
void DPrintList(DLinkList head)
{
	DListNode *p;
	for(p=head->next;p!=head;p=p->next)
		printf("%c",p->data);
	printf("\n");
}

//雙鏈表的查找
DLinkList DGetNode(DLinkList head,int i)
{//在帶頭結點的雙鏈表head中查找第i個結點
	int j;
	DListNode *p;
	p=head;j=0;				//從頭結點開始掃描
	while (p->next!=head && j<i)
	{	p=p->next;
		j++;
	}
	if (i==j)
		return p;			//找到了第i個結點
	else
		return NULL;		//找不到滿足條件的結點
}

//雙鏈表的插入
void DInsertBefore(DLinkList p,DataType x)
{//將值為x的新結點插入到帶頭結點的雙鏈表的*p之前
	DListNode *s=(DListNode *)malloc(sizeof(DListNode));	//生成新結點
	s->data=x;
	s->prior=p->prior;
	s->next=p;
	p->prior->next=s;
	p->prior=s;
}