復制代碼
創(chuàng)新互聯(lián)公司是一家集成都做網(wǎng)站、成都網(wǎng)站建設、成都外貿(mào)網(wǎng)站建設、網(wǎng)站頁面設計、網(wǎng)站優(yōu)化SEO優(yōu)化為一體的專業(yè)網(wǎng)站制作公司，已為成都等多地近百家企業(yè)提供網(wǎng)站建設服務。追求良好的瀏覽體驗,以探求精品塑造與理念升華,設計最適合用戶的網(wǎng)站頁面。 合作只是第一步，服務才是根本,我們始終堅持講誠信，負責任的原則，為您進行細心、貼心、認真的服務,與眾多客戶在蓬勃發(fā)展的市場環(huán)境中,互促共生。
代碼如下:
?php
/**
*
快速排序
quick
sort
*
**/
function
sort_quick($arrData)
{
if(empty($arrData)
||
!is_array($arrData))
return
false;
$flag
=
$arrData[0];
$len
=
count($arrData)
-
1;
if($len
==
0)
return
$arrData;
//
如果只有一個數(shù)據(jù)的數(shù)組直接返回
$arrLeft
=
array();
$arrRight
=
array();
$len_l
=
0;
$len_r
=
0;
for($i
=
1;
$i
=
$len;$i++)
{
if($arrData[$i]
$flag)
{
$arrLeft[$len_l]
=
$arrData[$i];
//
小于的放左邊
$len_l++;
}
else
{
$arrRight[$len_r]
=
$arrData[$i];
//
大于等于的放右邊
$len_r++;
}
}
//
合并數(shù)組
$arrResult
=
array();
if($len_l)
{
$arrLeft
=
sort_quick($arrLeft);
for($i
=
0;$i
=
$len_l
-
1;
$i++
)
{
$arrResult[$i]
=
$arrLeft[$i];
}
}
$arrResult[$len_l]
=
$flag;
$len_l++;
if($len_r)
{
$arrRight
=
sort_quick($arrRight);
for($i
=
0;$i
=
$len_r
-
1;
$i++
)
{
$arrResult[$len_l]
=
$arrRight[$i];
$len_l++;
}
}
echo
"==
",$flag,"
==========================================br/";
echo
"data
:
",print_r($arrData),"br/";
echo
"filter
left:
",print_r($arrLeft),"br/";
echo
"filter
right:
",print_r($arrRight),"br/";
echo
"return
:
",print_r($arrResult),"br/";
return
$arrResult;
}
//$list
=
array(4,3,2,1,5,7,3,7);
$list
=
array(4,51,6,73,2,5,9,33,50,3,4,6,1,4,67);
$list
=
sort_quick($list);
echo
"pre";print_r($list);
1、順序表（數(shù)組）
順序表是在計算機內(nèi)存中以數(shù)組的形式保存的線性表，線性表的順序存儲是指用一組 地址連續(xù)的存儲單元 依次存儲線性表中的各個元素、使得線性表中在邏輯結(jié)構上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)元素之間邏輯上的相鄰關系，采用順序存儲結(jié)構的線性表通常稱為順序表。順序表是將表中的結(jié)點依次存放在計算機內(nèi)存中一組地址連續(xù)的存儲單元中。
數(shù)組在內(nèi)存中是連續(xù)的存儲的，所以索引速度很快（ 根據(jù) Loc(ai)=Loc(a1)+(i-1)w,(1=i=n) ,其中Loc(a1) 是基地址既第一個元素地址，i是索引數(shù)，w是存儲單元，每個元素的存儲單元都是相同的，所以只要知道了基地址和存儲單元，就能查詢到任意索引的值；例如 索引為4，查第4個值，假如w=1, Loc(4)=Loc(1)+(4-1)1 ,既首個地址加上索引減一再乘以存儲單元就找到索引的地址了，從而直接訪問到該元素的值，時間復雜度O(1),所以比較快），而且賦值與修改元素也很簡單?？梢岳玫刂吩L問元素，時間復雜度為O(1);可以用二分法查找元素、效率高。
但是，在對順序表進行插入和刪除時，需要通過移動數(shù)據(jù)元素來實現(xiàn)(比如：插入或者刪除一個元素時，整個表需要遍歷移動元素來重新排一次順序，C#中如ArrayList ,List 等)，比較影響效率。
2、鏈表
2.1、 單鏈表
鏈表中的數(shù)據(jù)是以節(jié)點來表示的，每個節(jié)點的構成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個節(jié)點的地址數(shù)據(jù)。
個人理解：鏈表實際上是把一些具有相同類型的元素(節(jié)點)通過其存儲的地址信息連接起來。例如：某個(節(jié)點)元素中除了存儲數(shù)據(jù)信息外，還保存了另外一個同種類型元素的引用地址A，在訪問該引用地址A時，就會訪問到A的內(nèi)容，也就是下個節(jié)點的內(nèi)容，同理，A也存儲了另外的同種類型元素的引用地址B,以此類推，形成一個鏈表。
大白話可以說是有一個普通平常的類Node，由于該類有個屬性next也是Node引用類型的，既該屬性next存的是Node類型的引用地址，所以該類在調(diào)用next的時候，就會訪問到next存放的地址所指向內(nèi)容，也就是下一個節(jié)點的內(nèi)容。
b、然后建立一個鏈表節(jié)點類NodeT，使用泛型
然后由鏈表類LinkListT 實現(xiàn)ILstDST接口，下面只寫了Add方法
2.2、 雙向鏈表
2.3、 循環(huán)鏈表
//用vc調(diào)試過了有問題可以提出
#includestdio.h
#define listsize 100
typedef struct
{
int data[listsize];
int length;
}sqlist;//順序表的類型
void createtsqlist(sqlist L,int a[],int n)//用數(shù)組創(chuàng)建順序表
{
L.length=0;
for(int i=0;in;i++)
{
L.data[L.length++]=a[i];
}
}
void findvalue(sqlist L,int x) //查找x是否在順序表內(nèi)
{
for(int i=0;iL.length;i++)
{
if(L.data[i]==x)
{
printf("%d是第%d個元素\n",x,i+1);return;
}
}
printf("%d不在順序表內(nèi)\n",x);
}
void search_bin(sqlist L,int x)//折半查找有序表
{
int low=1;int high=L.length;int mid;
while(low=high)
{
mid=(low+high)/2;
if(x==L.data[mid])
{
printf("%d是第%d元素\n",x,mid+1);return;
}
else if(xL.data[mid])high=mid-1;
else low=mid+1;
}
printf("%d不在順序表內(nèi)\n",x);
}
void main()
{
int a[10]={1,23,45,34,67,87,9,13,7,11};
int b[10]={1,2,3,4,5,6,9,14,19,23};//保證b中元素有序
sqlist L1,L2;//L2創(chuàng)建為有序表
createtsqlist(L1,a,10);
findvalue(L1,45);//查找45是否在表內(nèi)可以換成其他數(shù)
createtsqlist(L2,b,10);
search_bin(L2,14);//查找14是否在表內(nèi)可以換成其他數(shù)
}
沒錯。確實是這樣。這里有一段我寫的順序鏈表源代碼、代碼分倆個文件：Node、List
節(jié)點類模板
#ifndef NODE_H
#define NODE_H
using namespace std;
templateclass T
class Node
{
private:
NodeT *Next;//節(jié)點指針域，指向下一個節(jié)點
public:
T data;//數(shù)據(jù)存儲域
Node();//無參構造函數(shù)
Node(NodeT n);
Node(const T data,NodeT *ptrNext=NULL);//有參構造函數(shù)
void insertAfter(NodeT *p);//往后插入
NodeT *insertH(NodeT *p);//往頭部插入
NodeT *deleteAfter();//刪除后一個節(jié)點
NodeT *NextNode();//返回指針域，即指向下一個節(jié)點的指針
};
templateclass T
NodeT::Node()
{
Next=NULL;
}
templateclass T
NodeT::Node(NodeT n)
{
Next=n.Next;
}
templateclass T
NodeT::Node(const T data,NodeT *ptrNext/*=NULL*/):data(data),Next(ptrNext){}
templateclass T
void NodeT::insertAfter(NodeT *p)
{
p-Next=Next;
Next=p;
}
templateclass T
NodeT *NodeT::insertH(NodeT *p)
{
p-Next=this;
return p;
}
templateclass T
NodeT *NodeT::NextNode()
{
return Next;
}
templateclass T
NodeT *NodeT::deleteAfter()
{
NodeT*p=Next;
Next=p-Next;
return p;
}
#endif
鏈表類模板
#ifndef LIST_H
#define LIST_H
#include"Node.h"
using namespace std;
templateclass T
class List
{
private:
NodeT *pH,//表頭指針
*pE,//表尾指針
*pPre,//前向指針
*pCur;//當前指針域
int nPos,//當前位置
nLength;//當前表的長度，元素個數(shù)
NodeT *NewNode(const T item,NodeT*ptrNext=NULL);//建立新的節(jié)點，指針域默認為空
void freeNode(NodeT *p){delete p;};
public:
List();//無參構造函數(shù)
List(const ListT l);//復制構造函數(shù)
//ListT operator=(const ListT l);
int GetSize()const;//獲取表長
bool isEmpty()const;//判斷是否為空
bool isEnd()const;//是否到達表尾
bool isStart()const;//是否在表頭
void Reset(int pos=1);//設置當前記錄位置
int CurrentPos()const;//返回當前記錄位置
void MoveNext();//記錄指針向下移一步
void InsertEnd(const T item);//表尾插入
void InsertHead(const T item);//表頭插入
void InsertAfter(const T item);//當前記錄之后插入
void InsertPrev(const T item);//當前記錄之前插入
void DeleteCurrent();//刪除當前記錄
void Clear();//清空所有記錄，只保留頭指針
T Data();//訪問數(shù)據(jù)域
const T Data()const;//數(shù)據(jù)域的常引用
};
templateclass T
ListT::List(const ListT l)
{
l.Reset();
Clear();
while(!l.isEnd())
{
InsertEnd(l.Data());
l.MoveNext();
}
InsertEnd(l.Data());
}
templateclass T
void ListT::Clear()
{
while(!isEmpty())
{
DeleteCurrent();
}
}
templateclass T
void ListT::DeleteCurrent()
{
if(GetSize()==1)
{
pPre=pCur=pE=pH;
nPos=0;
}
else if(isStart())
{
pH=pH-NextNode();
pPre=pH;
pCur=pH-NextNode();
}
else
{
NodeT *p=pH;
while(pPre!=p-NextNode())
{
p=p-NextNode();
}
if(isEnd())
{
pPre=pCur=pE=p;
}
else
{
pPre=p-deleteAfter();
}
nPos--;
}
nLength--;
}
templateclass T
NodeT *ListT::NewNode(const T item,NodeT *ptrNext/*=NULL*/)
{
NodeT *newNode=new NodeT(item,NULL);
if(newNode==NULL)
{
cout"Failed,exiting....";
exit(1);
}
return newNode;
}
templateclass T
ListT::List():pH(NULL),pE(NULL),pPre(NULL),pCur(NULL),nLength(0),nPos(0)
{}
templateclass T
int ListT::GetSize()const
{
return nLength;
}
templateclass T
bool ListT::isEmpty()const
{
return nLength==0;
}
templateclass T
bool ListT::isStart()const
{
return nPos==1;
}
templateclass T
bool ListT::isEnd()const
{
return nPos==nLength;
}
templateclass T
void ListT::Reset(int pos/*=1*/)
{
if(isEmpty())
{
cout"^.^是空表噢，游標不能移動啦~"endl;
}
else if(posGetSize())
{
cout"^.^超過鏈表長度啦，請重新輸入試試看~"endl;
}
else
{
nPos=1;
pPre=pH;
pCur=pH-NextNode();
for(int p=1;ppos;p++)
{
MoveNext();
}
}
}
templateclass T
void ListT::InsertHead(const T item)
{
if(isEmpty())
{
nPos++;
pPre=pCur=pH=pE=NewNode(item,NewNode(item));
}
else
{
pH=pH-insertH(NewNode(item));
}
nLength++;
}
templateclass T
void ListT::InsertAfter(const T item)
{
if(isEmpty())
{
nPos++;
pCur=pPre=pH=pE=NewNode(item,NewNode(item));
}
else if(!isEmpty())
{
pPre-insertAfter(NewNode(item));
}
else
{
pE-insertAfter(NewNode(item));
pCur=pE=pE-NextNode();
}
nLength++;
}
templateclass T
void ListT::InsertPrev(const T item)
{
if(isEmpty())
{
nPos++;
pCur=pPre=pH=pE=NewNode(item,NewNode(item));
}
else if(isStart())
{
nPos++;
pH=pH-insertH(NewNode(item));
}
else
{
nPos++;
NodeT *p=pH;
while(pPre!=p-NextNode())
{
p=p-NextNode();
}
p-insertAfter(pPre-insertH(NewNode(item)));
}
nLength++;
}
templateclass T
int ListT::CurrentPos()const
{
return nPos;
}
templateclass T
void ListT::InsertEnd(const T item)
{
if(isEmpty())
{
nPos++;
pH=pPre=pH=pE=NewNode(item,NewNode(item));
}
else
{
pE-insertAfter(NewNode(item));
pE=pE-NextNode();
if(isEnd())
{
pCur=pE;
}
}
nLength++;
}
templateclass T
void ListT::MoveNext()
{
if(isEmpty())
{
cout"^.^是空表噢，游標不能往下移動啦~"endl;
}
else if(isEnd())
{
cout"^.^到表尾噢，游標不能往下移動啦~"endl;
}
else
{
nPos++;
pPre=pCur;
pCur=pCur-NextNode();
}
}
templateclass T
T ListT::Data()
{
return pPre-data;
}
templateclass T
const T ListT::Data()const
{
return pPre-data;
}
#endif
順序表的優(yōu)點是便于隨機存儲，缺點是不便于插入刪除等操作，因為插入刪除一個元素需要移動其后的所有元素，但是鏈表不存在這個問題，鏈表只要改變指針就行，時間復雜度小，所以鏈表于順序表恰恰相反，優(yōu)點是便于插入刪除等操作，缺點是隨機存儲沒有順序表方便。
重慶分公司
重慶分公司
