双链表

/*头插法*/
void CreateDLink(DLinkNode*& L, ElemType a[], int n)
{
	DLinkNode* s;
	L = (DLinkNode*)malloc(sizeof(DLinkNode));
	L->prior = L->next = NULL;
	
	for (int i = 0; i < n; i++)
	{
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = a[i];
		s->next = L->next;
		
		if (L->next != NULL)
		{
			L->next->prior = s;
		}
		
		L->next = s;
		s->prior = L;
	}
 }

/*尾插法*/
void CreateDLink1(DLinkNode*& L, int a[], int n)
{
	DLinkNode* s, * r;
	L = (DLinkNode*)malloc(sizeof(DLinkNode));
	L->next = L->prior = NULL;
	r = L;

	for (int i = 0; i < n; i++)
	{
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = a[i];
		r->next = s;
		s->next = NULL;
		s->prior = r;
		r = s;
	}
	r->next = NULL;
}

bool ListInsert(DLinkNode*& L, int i, int e)
{
	DLinkNode* p,* s;
	p = L;
	s = (DLinkNode*)malloc(sizeof(DLinkNode));
	int j = 0;

	while (j < i - 1 && p != NULL)
	{
		p = p->next;
		j++;

	}
	if (p == NULL)
		return false;
	else
	{
		s->data = e;
		s->next = p->next;
		if (p->next != NULL)
		{
			p->next->prior = s;
		}
		p->next = s;
		s->prior = p;
		return true;

	}

}

bool ListDelete(DLinkNode*& L, int i, int& e)
{
	DLinkNode* p = L,* q;
	int j = 0;

	if (i < 0)
		return false;
	while (j < i - 1&& p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	else
	{
		q = p->next;
		if (q == NULL)
			return false;
		else
		{
			e = q->data;
			p->next = q->next;
			if (q->next != NULL)
			{
				p->next->prior = p;
			}
			free(q);
			return true;
		}
	}

}

void reserse(DLinkNode*& L)
{
	DLinkNode* p = L->next,* q;
	L->next = NULL;

	while (p != NULL)
	{
		q = p->next;
		p->next = L->next;
		if (L->next != NULL)
		{
			L->next->prior = p;
		}
		L->next = p;
		p->prior = L;   
		p = q;

	}
 }

void sort(DLinkNode*& L)
{
	DLinkNode* p, * q, * pre;
	p = L->next->next;
	L->next->next = NULL;
	
	while (p != NULL)
	{
		pre = L;
		q = p->next;

		while (pre->next != NULL && pre->next->data < p->data)
		{
			pre = pre->next;

		}
		p->next = pre->next;
		if (pre->next != NULL)
		{
			pre->next->prior = p;
		}
		pre->next = p;
		p->prior = pre;

		p = q;

	}
	
}