双向链表的插入，删除，以及链表的快速排序

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

#pragma once//只包含一次头文件
#include <algorithm>
using namespace std;//使用库函数swap
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef  struct  DoubleLinkNode//双向链表
{
	struct   DoubleLinkNode* _next;
	struct   DoubleLinkNode* _prev;
	DataType _data;
}DoubleLinkNode;

//此双向链表是带头结点的
void  InitLink(DoubleLinkNode* pHead);//初始化双链表
DoubleLinkNode* _BuyNode(DataType  x);//买节点
void   PrintLink(DoubleLinkNode* pHead);//打印链表
void  PushBack(DoubleLinkNode* pHead, DataType x);//尾插数据
void  PopBack(DoubleLinkNode*  pHead);//尾删数据
void  PushFront(DoubleLinkNode* pHead, DataType x);//头插数据
void  PopFront(DoubleLinkNode*  pHead);//头删数据
DoubleLinkNode* Find(DoubleLinkNode* pHead,DataType x);//在双链表中找到第一次出现x的位置
void  Insert(DoubleLinkNode* pos, DataType x);//在pos位置插入x
void  Erase(DoubleLinkNode* pos);//删除pos位置的节点
void  Reverse(DoubleLinkNode* pHead);//逆置链表
void  Destory(DoubleLinkNode* pHead);//释放链表中动态开辟的节点
void  QuickSort(DoubleLinkNode* pHead);//快速排序

void  InitLink(DoubleLinkNode* pHead)
{
	assert(pHead);
	pHead->_next = NULL;
	pHead->_prev = NULL;
	pHead->_data = 0;
}
DoubleLinkNode* _BuyNode(DataType  x)
{
	DoubleLinkNode*  tmp = (DoubleLinkNode*)malloc(sizeof(DoubleLinkNode));
	tmp->_data = x;
	tmp->_next = NULL;
	tmp->_prev = NULL;

	return  tmp;
}
void   PrintLink(DoubleLinkNode* pHead)
{
	assert(pHead);
	DoubleLinkNode* cur = pHead->_next;
	if (pHead->_next == NULL)
		return;
	while (cur)
	{
		printf("%d->", cur->_data);
		cur=cur->_next;
	}
	printf("NULL\n");
}
void  PushBack(DoubleLinkNode* pHead, DataType x)
{
	assert(pHead);
	DoubleLinkNode* cur = pHead,*tmp=NULL;
	while (cur->_next)
	{
		cur = cur->_next;
	}
	tmp= _BuyNode(x);
	cur->_next = tmp;
	tmp->_prev = cur;
}
void  PopBack(DoubleLinkNode*  pHead)
{
	assert(pHead);
	if (pHead->_next == NULL)
	{
		printf("已为空\n");
		return;
	}
    DoubleLinkNode*  cur = pHead->_next;
	while (cur->_next)
	{
		cur = cur->_next;
	}
	DoubleLinkNode*  del = cur;
	DoubleLinkNode*  pre = cur->_prev;
	pre->_next = del->_next;
    if(del->_next)
        del->_next->_prev = pre;
	free(del);
}
void  PushFront(DoubleLinkNode* pHead, DataType x)
{
	assert(pHead);
	DoubleLinkNode* cur = pHead->_next;
	DoubleLinkNode* tmp = _BuyNode(x);
	pHead->_next = tmp;
	tmp->_next = cur;

	if(cur)
		cur->_prev = tmp;
	tmp->_prev = pHead;
}
void  PopFront(DoubleLinkNode*  pHead)
{
	assert(pHead);
	if (pHead->_next == NULL)
	{
		printf("已为空\n");
		return;
	}
	DoubleLinkNode*  del = pHead->_next;
	DoubleLinkNode*  next = del->_next;
	pHead->_next = next;
	if (next)
	{
		next->_prev = pHead;
	}
	free(del);
}
DoubleLinkNode* Find(DoubleLinkNode* pHead,DataType x)
{
	assert(pHead);
	if (pHead->_next == NULL)
		return NULL;
	DoubleLinkNode*  cur = pHead->_next;
	while (cur)
	{
		if (cur->_data == x)//如果找到x
			return  cur;
		cur = cur->_next;
	}
	return  NULL;//在链表中未找到x
}
void  Insert(DoubleLinkNode* pos, DataType x)
{
	assert(pos);
	DoubleLinkNode*  tmp = _BuyNode(x);
	DoubleLinkNode*  pre = pos->_prev;
	pre->_next = tmp;
	tmp->_next = pos;

	tmp->_prev = pre;
	pos->_prev = tmp;
}
void  Erase(DoubleLinkNode* pos)
{
	assert(pos);
	DoubleLinkNode*  pre = pos->_prev;
	pre->_next = pos->_next;
	if (pos->_next)//判断pos后的节点非空，要不然访问空结点的prev出错
		pos->_next = pre;

	free(pos);
}
void  Reverse(DoubleLinkNode* pHead)
{
	//法一
	//assert(pHead);
	//if (pHead->_next == NULL&&pHead->_next->_next == NULL)//如果只有一个节点或没有有效节点
	//	return;
	//DoubleLinkNode* newPHead = pHead->_next;
	//DoubleLinkNode* cur = pHead->_next->_next,*pre=NULL;//注意cur的赋值和newPHead的next置空的顺序
	//newPHead->_next = NULL;
	//while (cur)
	//{
	//	pre = cur;
	//	cur=cur->_next;

	//	newPHead->_prev = pre;
	//	
	//	pre->_next = newPHead;
	//	//重新定位newpHead
	//	newPHead = pre;
	//	
	//}
	//pHead ->_next= newPHead;
	//newPHead->_prev = pHead;


	//法二
	assert(pHead);
	if (pHead->_next == NULL&&pHead->_next->_next == NULL)//如果只有一个节点或没有有效节点
		return;
	DoubleLinkNode*  end=pHead->_next->_next,*begin=pHead->_next;
	DataType  tmp = 0;
	while (end->_next)
	{
		end = end->_next;
	}
	while (end->_prev != begin && end != begin)//防止两个结构体指针错过
	{
		tmp = end->_data;
		end->_data = begin->_data;
		begin->_data = tmp;

		begin = begin->_next;
		end = end->_prev;
	}
}
void  Destory(DoubleLinkNode* pHead)
{
	assert(pHead);
	if (pHead->_next == NULL)
		return;
	DoubleLinkNode* cur = pHead->_next,*del=NULL;
	while (cur->_next)//此时cur肯定不为空
	{
		del = cur;
		pHead->_next = del->_next;//如果是最后一个数，给pHead的next赋空
		cur = cur->_next;
		free(del);
		
	}
}
void  QuickSort(DoubleLinkNode* pHead, DoubleLinkNode* end)
{
	if (pHead == end||pHead->_next == end)//为空或只有一个数则返回
		return;
	DoubleLinkNode*  key = pHead;
	DoubleLinkNode*  prev = pHead;
	DoubleLinkNode*  cur = pHead->_next;

	while (cur!=end)
	{
		if (cur->_data < key->_data)
		{
			prev = prev->_next;
			swap(prev->_data, cur->_data);
		}
		cur = cur->_next;
	}
	swap(key->_data, prev->_data);

	QuickSort(key, prev);
	QuickSort(prev->_next, end);
}

#include"DoubleLink.h"
//void  Test1()//测试用例的全面
//{
//	DoubleLinkNode  pHead;
//	InitLink(&pHead);
//	PushBack(&pHead, 1);
//	PushBack(&pHead, 2);
//	PushBack(&pHead, 3);
//	PushBack(&pHead, 4);
//	PushBack(&pHead, 5);
//	PushBack(&pHead, 6);
//	PushBack(&pHead, 7);
//	PrintLink(&pHead);
//
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PopBack(&pHead);
//	PrintLink(&pHead);
//
//	PushFront(&pHead, 1);
//	PushFront(&pHead, 2);
//	PushFront(&pHead, 3);
//	PushFront(&pHead, 4);
//	PushFront(&pHead, 5);
//	PushFront(&pHead, 6);
//	PushFront(&pHead, 7);
//	PrintLink(&pHead);
//
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PopFront(&pHead);
//	PrintLink(&pHead);
//
//
//}
void  Test2()
{
	DoubleLinkNode  pHead;
	InitLink(&pHead);
	PushFront(&pHead, 1);
	PushFront(&pHead, 2);
	PushFront(&pHead, 3);
	PushFront(&pHead, 4);
	PushFront(&pHead, 4);
	PushFront(&pHead, 5);
	PushFront(&pHead, 6);
	PushFront(&pHead, 7);
	PushFront(&pHead, 8);
	PushFront(&pHead, 9);
	PushFront(&pHead, 10);
	QuickSort(pHead._next, NULL);
	PrintLink(&pHead);

	DoubleLinkNode* ret = NULL;
	ret = Find(&pHead, 7);
	/*if (ret)
		printf("%d  %d\n", ret->_prev->_data, ret->_data);
	else
		printf("未找到\n");*/
	//Reverse(&pHead);
	//Insert(ret,6);
	//Erase(ret);

	Destory(&pHead);
}
int  main()
{
	//Test1();
	Test2();
	system("pause");
	return 0;
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1706752

双向链表的插入，删除，以及链表的快速排序

原文：http://10541556.blog.51cto.com/10531556/1706752