Java双向链表快速排序_双向链表的插入，删除，以及链表的快速排序
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。#pragma?once//只包含一次頭文件
#include?
using?namespace?std;//使用庫函數(shù)swap
#include
#include
#include
typedef?int?DataType;
typedef??struct??DoubleLinkNode//雙向鏈表
{
struct???DoubleLinkNode*?_next;
struct???DoubleLinkNode*?_prev;
DataType?_data;
}DoubleLinkNode;
//此雙向鏈表是帶頭結(jié)點(diǎn)的
void??InitLink(DoubleLinkNode*?pHead);//初始化雙鏈表
DoubleLinkNode*?_BuyNode(DataType??x);//買節(jié)點(diǎn)
void???PrintLink(DoubleLinkNode*?pHead);//打印鏈表
void??PushBack(DoubleLinkNode*?pHead,?DataType?x);//尾插數(shù)據(jù)
void??PopBack(DoubleLinkNode*??pHead);//尾刪數(shù)據(jù)
void??PushFront(DoubleLinkNode*?pHead,?DataType?x);//頭插數(shù)據(jù)
void??PopFront(DoubleLinkNode*??pHead);//頭刪數(shù)據(jù)
DoubleLinkNode*?Find(DoubleLinkNode*?pHead,DataType?x);//在雙鏈表中找到第一次出現(xiàn)x的位置
void??Insert(DoubleLinkNode*?pos,?DataType?x);//在pos位置插入x
void??Erase(DoubleLinkNode*?pos);//刪除pos位置的節(jié)點(diǎn)
void??Reverse(DoubleLinkNode*?pHead);//逆置鏈表
void??Destory(DoubleLinkNode*?pHead);//釋放鏈表中動態(tài)開辟的節(jié)點(diǎn)
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后的節(jié)點(diǎn)非空，要不然訪問空結(jié)點(diǎn)的prev出錯
pos->_next?=?pre;
free(pos);
}
void??Reverse(DoubleLinkNode*?pHead)
{
//法一
//assert(pHead);
//if?(pHead->_next?==?NULL&&pHead->_next->_next?==?NULL)//如果只有一個節(jié)點(diǎn)或沒有有效節(jié)點(diǎn)
//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)//如果只有一個節(jié)點(diǎn)或沒有有效節(jié)點(diǎn)
return;
DoubleLinkNode*??end=pHead->_next->_next,*begin=pHead->_next;
DataType??tmp?=?0;
while?(end->_next)
{
end?=?end->_next;
}
while?(end->_prev?!=?begin?&&?end?!=?begin)//防止兩個結(jié)構(gòu)體指針錯過
{
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;//如果是最后一個數(shù)，給pHead的next賦空
cur?=?cur->_next;
free(del);
}
}
void??QuickSort(DoubleLinkNode*?pHead,?DoubleLinkNode*?end)
{
if?(pHead?==?end||pHead->_next?==?end)//為空或只有一個數(shù)則返回
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);
/*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;
}
總結(jié)
以上是生活随笔為你收集整理的Java双向链表快速排序_双向链表的插入，删除，以及链表的快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何连接两个窗口JAVA_java-如何
- 下一篇： java如何写外键关联_JAVA基础:H