对线性表进行二分法查找的前提条件是什么
二分查找又称为折半查找，是一种效率较高的查找方法，其中查找的关键是要求线性表是有序表，即表中的元素按关键字有序。
例如：
int BinSearch(SeqList R,int n, KeyType k)
{
int low=0, high =n-1,mid;
while(low<=high)
{
mid =(low+high)/2;
if(R[mid].key==k)
return mid+1;
if(R[mid].key>k)
return mid-1;
else
low=mid+1;
}
return 0;
}
关于快速排序和归并排序的时间复杂度
首先你说归并排序最坏的情形为O(NlogN)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为O(n^2)，借助的话就是O(nlogn)(O(nlog2n))归并排序 平均复杂度是 O(nlogn) 比较快
快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。
综合来说快速排序速度最快，时间复杂度最小。希望对你有所帮助！
数据结构关于顺序表的问题
没错。确实是这样。这里有一段我写的顺序链表源代码、代码分俩个文件：Node、List
节点类模板
#ifndef NODE_H
#define NODE_H
using namespace std;
template
class Node
{
private:
Node *Next;//节点指针域，指向下一个节点
public:
T data;//数据存储域
Node();//无参构造函数
Node(Node &n);
Node(const T &data,Node *ptrNext=NULL);//有参构造函数
void insertAfter(Node *p);//往后插入
Node *insertH(Node *p);//往头部插入
Node *deleteAfter();//删除后一个节点
Node *NextNode();//返回指针域，即指向下一个节点的指针
};
template
Node::Node()
{
Next=NULL;
}
template
Node::Node(Node &n)
{
Next=n.Next;
}
template
Node::Node(const T &data,Node *ptrNext/*=NULL*/):data(data),Next(ptrNext){}
template
void Node::insertAfter(Node *p)
{
p->Next=Next;
Next=p;
}
template
Node *Node::insertH(Node *p)
{
p->Next=this;
return p;
}
template
Node *Node::NextNode()
{
return Next;
}
template
Node *Node::deleteAfter()
{
Node*p=Next;
Next=p->Next;
return p;
}
#endif
链表类模板
#ifndef LIST_H
#define LIST_H
#include"Node.h"
using namespace std;
template
class List
{
private:
Node *pH,//表头指针
*pE,//表尾指针
*pPre,//前向指针
*pCur;//当前指针域
int nPos,//当前位置
nLength;//当前表的长度，元素个数
Node *NewNode(const T &item,Node*ptrNext=NULL);//建立新的节点，指针域默认为空
void freeNode(Node *p){delete p;};
public:
List();//无参构造函数
List(const List &l);//复制构造函数
//List& operator=(const List &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;//数据域的常引用
};
template
List::List(const List &l)
{
l.Reset();
Clear();
while(!l.isEnd())
{
InsertEnd(l.Data());
l.MoveNext();
}
InsertEnd(l.Data());
}
template
void List::Clear()
{
while(!isEmpty())
{
DeleteCurrent();
}
}
template
void List::DeleteCurrent()
{
if(GetSize()==1)
{
pPre=pCur=pE=pH;
nPos=0;
}
else if(isStart())
{
pH=pH->NextNode();
pPre=pH;
pCur=pH->NextNode();
}
else
{
Node *p=pH;
while(pPre!=p->NextNode())
{
p=p->NextNode();
}
if(isEnd())
{
pPre=pCur=pE=p;
}
else
{
pPre=p->deleteAfter();
}
nPos--;
}
nLength--;
}
template
Node *List::NewNode(const T &item,Node *ptrNext/*=NULL*/)
{
Node *newNode=new Node(item,NULL);
if(newNode==NULL)
{
cout<<"Failed,exiting....";
exit(1);
}
return newNode;
}
template
List::List():pH(NULL),pE(NULL),pPre(NULL),pCur(NULL),nLength(0),nPos(0)
{}
template
int List::GetSize()const
{
return nLength;
}
template
bool List::isEmpty()const
{
return nLength==0;
}
template
bool List::isStart()const
{
return nPos==1;
}
template
bool List::isEnd()const
{
return nPos==nLength;
}
template
void List::Reset(int pos/*=1*/)
{
if(isEmpty())
{
cout<<"^.^是空表噢，游标不能移动啦~"<<endl;
}
else if(pos>GetSize())
{
cout<<"^.^超过链表长度啦，请重新输入试试看~"<<endl;
}
else
{
nPos=1;
pPre=pH;
pCur=pH->NextNode();
for(int p=1;p<pos;p++)
{
MoveNext();
}
}
}
template
void List::InsertHead(const T &item)
{
if(isEmpty())
{
nPos++;
pPre=pCur=pH=pE=NewNode(item,NewNode(item));
}
else
{
pH=pH->insertH(NewNode(item));
}
nLength++;
}
template
void List::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++;
}
template
void List::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++;
Node *p=pH;
while(pPre!=p->NextNode())
{
p=p->NextNode();
}
p->insertAfter(pPre->insertH(NewNode(item)));
}
nLength++;
}
template
int List::CurrentPos()const
{
return nPos;
}
template
void List::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++;
}
template
void List::MoveNext()
{
if(isEmpty())
{
cout<<"^.^是空表噢，游标不能往下移动啦~"<<endl;
}
else if(isEnd())
{
cout<<"^.^到表尾噢，游标不能往下移动啦~"<<endl;
}
else
{
nPos++;
pPre=pCur;
pCur=pCur->NextNode();
}
}
template
T &List::Data()
{
return pPre->data;
}
template
const T &List::Data()const
{
return pPre->data;
}
#endif
