双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。#pragma once//只包含一次头文件
#include
using namespace std;//使用库函数swap
#include
#include
#include
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 _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);
//Reverse(&pHead);
//Insert(ret,6);
//Erase(ret);
Destory(&pHead);
}
int main()
{
//Test1();
Test2();
system("pause");
return 0;
}