#ifndef D_LINK_H_INCLUDED
#define D_LINK_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>

typedef struct DbNode
{
	int data;
        DbNode *left;
	DbNode *right;
}DbNode;

/*求2的n次幂*/
int power(int i)
{
	if(i < 2)
		return i == 0 ? 1 : 2;
	return 2 * power(i - 1);
}

/*建立一个空的双链表*/
DbNode *init()
{
	return NULL;
}

/*对双链表初始化*/
DbNode *creat(DbNode *head)
{
	DbNode *p,*q,*h = head;
	int i=0;
	while(i < 10)
	{
		p = (DbNode *)malloc(sizeof(DbNode));
		p->data = power(i);
		if(!h)
		{
			p->left = NULL;
			q = p;
			h = p;
		}
		else
		{
			p->left = q;
			q->right = p;
			q = p;
		}
		p->right = NULL;
		i++;
	}
	return h;
}

/*输出双链表中各个结点的值*/
void display_rlink(DbNode *head)
{
	DbNode *p = head;
	if(!head)
	{
		printf("\n该双链表是空的\n");
	}
	else
	{
		while(p)
		{
			printf("%d ",p->data);
			p = p->right;
		}
	}
}

/*在指定节点前插入节点*/
DbNode *insert(DbNode *head,int value,int value1)
{
	DbNode *p = head;
	DbNode *q = (DbNode *)malloc(sizeof(DbNode));
	q->data = value1;
	while(p->right != NULL)
	{
		if(p->data == value)
			break;
		p = p->right;
	}
	if(p == head)
	{
		q->left = NULL;
		q->right = head;
		if(!head)  /*双链表为空*/
		{
			head = q;
		}
		else
		{
			head->left = q;
			head = q;
		}
	}
	else if(p->right == NULL)
	{
		q->right = NULL;
		q->left = p;
		p->right = q;
	}
	else
	{
		p = p->left;
		q->left = p;
		q->right = p->right;
		p->right->left = q;
		p->right = q;
	}
	return head;
}

/*在双链表中删除一个值为x的结点*/
DbNode *dele(DbNode * head,int x)
{
	DbNode *p = head;
	if(!head)
	{
		printf("该双链表为空，无法进行删除操作\n");
		return head;
	}
	else
	{
		while(p && p->data != x)
		{
			p = p->right;
		}
		if(!p)     /*没有找到要删除的结点*/
		{
			printf("\n没有找到值为%d的结点，无法进行删除操作\n",x);
			return head;
		}
		else
		{
			if(p == head && p->right)  /*被删除的结点是第一个结点且表中不只一个结点*/
			{
				head = head->right;
				head->left = NULL;
				free(p);
				return head;
			}
			if(p == head && !head->right)
			{
				free(p);
				return NULL;           /*双链表置空*/
			}
			else    
			{
				if(!p->right)          /*被删除的结点是双链表中最后一个结点*/
				{
					p->left->right = NULL;
					free(p);
					return head;
				}
				else                   /*q是两个以上结点中的一个非开始也非终端的结点*/
				{
					p->left->right = p->right;
					p->right->left = p->left;
					free(p);
					return head;
				}
			}
		}
	}
}
#endif

#include "d_link.h"
int main()
{
	int i,x;
	DbNode *p,*q,*h,*rear;
	h = init();
	h = creat(h);
	display_rlink(h);
	h = insert(h,128,127);
	printf("插入127后\n");  /*题目没指定插入数值，用的127测试*/
	display_rlink(h);
	printf("删除128后\n");
	h = dele(h,128);
	display_rlink(h);
	return 0;
}