雙向連結清單也叫雙連結清單，是連結清單的一種，它的每個資料結點中都有兩個指針，分别指向直接後繼和直接前驅。是以，從雙向連結清單中的任意一個結點開始，都可以很友善地通路它的前驅結點和後繼結點。#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;
}