复制代码
创新互联公司是一家集成都做网站、成都网站建设、成都外贸网站建设、网站页面设计、网站优化SEO优化为一体的专业网站制作公司，已为成都等多地近百家企业提供网站建设服务。追求良好的浏览体验,以探求精品塑造与理念升华,设计最适合用户的网站页面。 合作只是第一步，服务才是根本,我们始终坚持讲诚信，负责任的原则，为您进行细心、贴心、认真的服务,与众多客户在蓬勃发展的市场环境中,互促共生。
代码如下:
?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;
//
如果只有一个数据的数组直接返回
$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++;
}
}
//
合并数组
$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、顺序表（数组）
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组 地址连续的存储单元 依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
数组在内存中是连续的存储的，所以索引速度很快（ 根据 Loc(ai)=Loc(a1)+(i-1)w,(1=i=n) ,其中Loc(a1) 是基地址既第一个元素地址，i是索引数，w是存储单元，每个元素的存储单元都是相同的，所以只要知道了基地址和存储单元，就能查询到任意索引的值；例如 索引为4，查第4个值，假如w=1, Loc(4)=Loc(1)+(4-1)1 ,既首个地址加上索引减一再乘以存储单元就找到索引的地址了，从而直接访问到该元素的值，时间复杂度O(1),所以比较快），而且赋值与修改元素也很简单。可以利用地址访问元素，时间复杂度为O(1);可以用二分法查找元素、效率高。
但是，在对顺序表进行插入和删除时，需要通过移动数据元素来实现(比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序，C#中如ArrayList ,List 等)，比较影响效率。
2、链表
2.1、 单链表
链表中的数据是以节点来表示的，每个节点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个节点的地址数据。
个人理解：链表实际上是把一些具有相同类型的元素(节点)通过其存储的地址信息连接起来。例如：某个(节点)元素中除了存储数据信息外，还保存了另外一个同种类型元素的引用地址A，在访问该引用地址A时，就会访问到A的内容，也就是下个节点的内容，同理，A也存储了另外的同种类型元素的引用地址B,以此类推，形成一个链表。
大白话可以说是有一个普通平常的类Node，由于该类有个属性next也是Node引用类型的，既该属性next存的是Node类型的引用地址，所以该类在调用next的时候，就会访问到next存放的地址所指向内容，也就是下一个节点的内容。
b、然后建立一个链表节点类NodeT，使用泛型
然后由链表类LinkListT 实现ILstDST接口，下面只写了Add方法
2.2、 双向链表
2.3、 循环链表
//用vc调试过了有问题可以提出
#includestdio.h
#define listsize 100
typedef struct
{
int data[listsize];
int length;
}sqlist;//顺序表的类型
void createtsqlist(sqlist L,int a[],int n)//用数组创建顺序表
{
L.length=0;
for(int i=0;in;i++)
{
L.data[L.length++]=a[i];
}
}
void findvalue(sqlist L,int x) //查找x是否在顺序表内
{
for(int i=0;iL.length;i++)
{
if(L.data[i]==x)
{
printf("%d是第%d个元素\n",x,i+1);return;
}
}
printf("%d不在顺序表内\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",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创建为有序表
createtsqlist(L1,a,10);
findvalue(L1,45);//查找45是否在表内可以换成其他数
createtsqlist(L2,b,10);
search_bin(L2,14);//查找14是否在表内可以换成其他数
}
没错。确实是这样。这里有一段我写的顺序链表源代码、代码分俩个文件：Node、List
节点类模板
#ifndef NODE_H
#define NODE_H
using namespace std;
templateclass T
class Node
{
private:
NodeT *Next;//节点指针域，指向下一个节点
public:
T data;//数据存储域
Node();//无参构造函数
Node(NodeT n);
Node(const T data,NodeT *ptrNext=NULL);//有参构造函数
void insertAfter(NodeT *p);//往后插入
NodeT *insertH(NodeT *p);//往头部插入
NodeT *deleteAfter();//删除后一个节点
NodeT *NextNode();//返回指针域，即指向下一个节点的指针
};
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;//当前表的长度，元素个数
NodeT *NewNode(const T item,NodeT*ptrNext=NULL);//建立新的节点，指针域默认为空
void freeNode(NodeT *p){delete p;};
public:
List();//无参构造函数
List(const ListT l);//复制构造函数
//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();//访问数据域
const T Data()const;//数据域的常引用
};
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
顺序表的优点是便于随机存储，缺点是不便于插入删除等操作，因为插入删除一个元素需要移动其后的所有元素，但是链表不存在这个问题，链表只要改变指针就行，时间复杂度小，所以链表于顺序表恰恰相反，优点是便于插入删除等操作，缺点是随机存储没有顺序表方便。