整理磁盘时发现考研408时自己的笔记
线性表是具有相同数据类型的n个数据元素的有限序列。 逻辑上,每个元素有且只有一个直接前驱,有且只有一个直接后继(表头表尾元素例外)
使用顺序存储的时候即为顺序表。 使用链式存储即为链表。
线性表的顺序存储又称为顺序表,是一组地址连续的存储单元。特点是表中元素的逻辑顺序与物理顺序相同。 PS:动态分配并不是链式存储,同样属于顺序存储结构,只是分配的空间大小可以在运行时决定。 最主要的特点是随机访问,而且逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量的元素。
错题:线性表的顺序存储结构是一种顺序存取的存储结构。 这个是错误的,是随机存取的存储结构。顺序存取是一种读写方式,不是存储方式,有别于顺序存储。 PPS:表的元素从1开始计数,C中的数组从0开始计算。
题目: [2010真题]1. 设将n(n>1)个整数存放到1维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求: (1)给出算法的基本设计思想 (2)根据设计思想,采用C或C++或java语言描述算法,关键之处给出注释 (3)说明你所设计算法的时间复杂度和空间复杂度 [2011年真题]2.一个长度为L(L>=1)的升序序列S,处在L/2个位置的数被称为中位数。例如,若序列S1=(11,13,15,17,19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。现在由两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求: (1)给出算法的基本思想 (2)根据设计思想,采用C或C++或java语言描述算法,关键之处给出注释 (3)说明你所设计算法的时间复杂度和空间复杂度
[2013年真题]3.已知一个整数序列A=(a0,a1,…,an-1),其中0<=ai<n(0<i<n)。若存在ap1=ap2=…=apm=x且m>n/2(0<=pk<n,1<=k<=m),则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5),则5为主元素;又如A=(0,5,5,3,5,1,5,7),则A中没有主元素。假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素;否则输出-1。要求: (1)给出算法的基本设计思想 (2)根据设计思想,采用C或C++或java语言描述算法,关键之处给出注释 (3)说明你所设计算法的时间复杂度和空间复杂度
注释有感: 读注释的效果应当同读伪代码的效果一样 如果代码的内容无法直观表述,就需要写注释。 题目答案: 1.(1)可以将这个问题看作是把数组ab转换成数组ba(a代表前p个元素,b代表数组余下的n-p个元素),先将a逆置得到a-1b,再将b逆置,最后将ab逆置。 如对abcdefgh左移3个单位 Reverse(0,p-1),得到cbadefgh Reverse(p,n-1),得到cbahgfed Reverse(0,n-1),得到defghabc (2)使用C语言描述算法
void Reverse(int R[],int from,int to){
int i,temp;
for(i=0;i<(to-from+1)/2;i++)
{temp=R[from+i];R[from+i]=R[to-1];R[to-1]=temp}
}//Reverse
void Converse(int R[],int n,int p)
{
Reverse(0,p-1);
Reverse(p,n-1);
Reverse(0,n-1);
}
(3)上述三个Reverse的时间复杂度分别为O(p/2),O((n-p)/2)和O(n/2),故所设计的算法的时间复杂度是O(n),空间复杂度是O(1) 另外,可以使用大小为p的辅助数组,先将左边p个元素导入,再将n-p个元素左移,再放回去。时间复杂度O(n),空间复杂度O(p) 2.(1)算法的基本思想如下: 分别求两个序列的中位数a和b, 若a=b,则算法结束 若a<b,则舍弃A序列小的一半,B序列大的一半,要求两个序列舍弃的长度相等 若a>b,则舍弃A序列大的一半,B序列小的一半,要求两个序列舍弃的长度相等 在保留的升序序列中,重复上述过程直到只含一个元素,较小者即为所求的中位数 (2)代码:
int M_Search(int A[],int B[],int n){
int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
//分别表示序列A和B的首位数、末位数和中位数
while(s1!=d1||s2!=d2){
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]==B[m2])
return A[m1];//满足条件1
if(A[m1]<B[m2]){//满足条件2
if((s1+d1)%2==0){//若元素个数位奇数
s1=m1;//舍弃A中间点以前的部分且保留中间点
d2=m2;//舍弃B中间点以后的部分且保留中间点
}
else{
s1=m1+1;//舍弃A中间点以前及中间点部分
d2=m2;//舍弃B中间点以后部分且保留中间点
}
}
else{//满足条件3
if((s2+d2)%2==0)//若元素个数为奇数
{
d1=m1;//舍弃A中间点以后的部分且保留中间点
s2=m2;//舍弃B中间点以前的部分且保留中间点
}
else{//若元素个数为偶数
d1=m1;//舍弃A中间点以后部分且保留中间点
s2=m2+1;//舍弃B中间点及中间点以前的部分
}
}
}
return A[s1]<B[s2]?A[s1]:B[s2];
}
(3)算法的时间复杂度为O(log2n),空间复杂度为O(1) 3.(1)给出算法的基本设计思想: 算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num。然后重新计数,确认Num是否是主元素。 算法分为以下两步: a.选取候选的主元素:依次扫描所给数组中的每个整数,将第一个遇到的整数Num保存到c中,记录Num的出现次数为1;若遇到的下一个整数仍等于Num,则计数加1,否则计数减1;当计数减到0时,将遇到的下一个整数保存到c中,计数重新记为1,开始新一轮计数,即从当前位置开始重复上述过程,直到扫描完全部数组元素。 b.判断c中元素是否是真正的主元素:再次扫描该数组,统计c中元素出现的次数,若大于n/2,则为主元素;否则,序列中不存在主元素。 (2)算法实现:
int Majority(int A[],int n){
int i,c,count=1;//c用来保存候选主元素,count用来计数
c=A[0];//初始时设置A[0]为候补主元素
for(i=1;i<n;i++){
if(A[i]==c)
count++;//对A中的候选主元素计数
else{
if(count>0)//处理不是候选主元素的情况
count--;
else{//更换候选主元素,重新计数
c=A[i];
count=1;
}
}
}
if(count>0){
for(i=count=0;i<n;i++){//统计候选主元素的实际出现次数
if(A[i]==c)
count++;
}
if(count>n/2) return c;//确认候选主元素
else return -1;//不存在主元素
}
}
(3)实现程序的时间复杂度为O(n),空间复杂度为O(1) PS:对于统考算法题,去花费大量时间思考最优解法是得不偿失的。
结点描述:
typedef struct LNode{
ElemType data;//数据域
struct LNode *next; //指针域
}Lnode,*LinkList;
通常使用头指针来标识一个单链表,第一个结点称为头结点。
结点类型:
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode, *DLinkList;
插入、删除结点的时间为O(1)。(虽然查找依旧是O(n))
循环链表中最后一个结点的指针不是NULL而是指向头结点。
使用数组描述链式结构。
#define MaxSize 50
typedef struct{
ElemType data;//存储数据元素
int next;//下一个数组元素的下标
}
以next=-1作为结束,与动态链表相同,只是不用修改指针。
错题:1.单链表中,增加一个头结点的目的时为了方便运算的实现。主要好处是:第一,有头结点后,插入和删除数据元素的算法统一了,不再需要判断是否在第一个元素之前插入或删除第一个元素;第二,不论链表是否为空,其头指针是指向头结点的非空指针,链表的头指针不变,因此空表和非空表的处理也就统一了。 2. 带头结点的双循环链表为空的条件是:L->prior=L&&L->next=L
编程题: [2009]1.已知一个带表头结点的单链表,结点结构为[data|link]。假设该链表只给出了头指针list,在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1,;否则,只返回0,请问: (1)描述该算法的基本设计思想 (2)描述算法的详细设计步骤 (3)根据设计思想和实现步骤,采用程序设计语言实现算法,关键之处请给出简要注释。
1.(1)程序设计基本思想如下: 问题的关键是设计一个尽可能高效的算法,通过链表的一遍遍历,找到倒数第k个结点的位置。算法的基本设计思想是:定义两个指针变量p和q,初始时均指向头结点的下一个结点(链表的第一个结点),p指针移动到第k个结点时,q指针开始与p指针同步移动;当p指针移动到最后一个结点时,q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一次扫描。 (2)算法的详细实现步骤如下:
typedef int ElemType;//链表数据的类型定义
typedef struct LNode{//链表结点的结构定义
ElemType data;//结点数据
struct LNode *link;//结点链接指针
}
int Search_k(LinkList list,int k){
//查找链表list倒数第k个结点,并输出该结点data域的值
LNode *p=list->link,*q=list->link;//指针p、q指示第一个结点
int count = 0;
while(p!=NULL){ //遍历链表直到最后一个结点
if (count<k) count++;//计数,若count<k只移动p
else q=q->link;
p = p->link;//之后再让p、q同步移动
}
if(count<k)
return 0;//查找失败返回0
else{//否则打印并返回1
printf("%d",q->data);
return 1;
}
}//Search_k
栈:只允许一端进行插入和删除的线性表
#define MaxSize 50
typedef struct{
Elemtype data[MaxSize];
int top;
}SqStack;
typedef struct Linknode{
ElemType data;
struct Linknode *next;
}*LiStack;
队列是一种操作受限制的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。 操作特性是FIFO,故又称为先进先出的线性表。
分配一块连续的存储单元存放队列中的元素,并附设两个指针front和rear分别指示队头和队尾元素的位置。 队列的顺序存储类型描述
#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int front,rear;
}
会出现假溢出,即data数组中仍然有存放元素的空间,但是仍然溢出了。
循环队列:将顺序队列看作是一个环状的空间 入队时少用一个队列单元
(Q.rear+1)%MaxSize==Q.front
Q.front==Q.rear
(Q.rear-Q.front+MaxSize)%MaxSize
后者增设一个表示元素个数的数据成员,或者增设一个tag数据成员。
可以描述为
typedef struct{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *font,*rear;
}LinkQueue;
允许两端都可以进行入队和出队操作的队列
括号匹配 表达式求值(后缀) 递归 二叉树层次遍历
压缩存储:指为多个值相同的元素只分配一个存储空间,对零元素不分配存储空间。其目的时为了节省存储空间 特殊矩阵:指具有许多相同矩阵元素或令元素,并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上/下三角矩阵、对角矩阵等。
稀疏矩阵可以转为表,这时候会失去随机存储特性。
任何一棵非空树应该满足:
树中两个结点之间的路径是由两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过边的个数。
树的性质:
二叉树的性质:
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
层次遍历:需要使用队列,依次将孩子结点加入队列中
由二叉树的先序遍历和中序遍历可以唯一确定一棵二叉树。同理,二叉树的后序遍历和中序遍历也可以唯一确定一棵二叉树。 二叉树的层序序列和中序序列也可以确定一棵二叉树。只有先序序列+后序序列无法确定一棵二叉树。
线索二叉树的实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点都有一个直接前驱和直接后继。 引入线索二叉树的目的是加快查找结点前驱和后继的速度。 在二叉树线索化时,通常规定:若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。同时还需要增加两个标识域来表明当前指针域所指向的对象是指向左(右)子结点还是直接前驱(后继)
线索二叉树的存储结构:
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表。其中指向结点前驱和后继的指针,叫做线索。加上线索的二叉树叫做线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
线索二叉树的构造:对二叉树的线索化,实质上就是遍历一次二叉树,在遍历过程中检查当前结点左、右指针域是否为空,若为空,则将他们改为指向前驱或后继结点的线索。
算法题: [2014年]1.二叉树的带权路径长度(WPL)是二叉树中所有叶节点的带权路径长度之和,给定一棵二叉树T,采用二叉链表存储,结点结构为(left,weight,right)。其中叶节点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: (1)给出算法的基本设计思想 a.基于先序递归遍历的算法思想使用一个static变量记录wpl,把每个结点的深度作为递归函数的一个参数传递,算法步骤如下:(标准答案如下,我个人更倾向于将wpl值作为函数返回值逐层返回)
typedef struct BiTNode{
int weight;
struct BiTNode *lchild,*rchild;
}
(3)算法的代码如下 a. 基于先序遍历的算法
int WPL(BiTree root){
return wpl_PreOrder(root,0);
}
int wpl_PreOrder(BiTree root,int deep){
static int wpl=0;//定义一个static变量存储wpl
if(root->lchild==NULL&&root->rchild==NULL)//若为叶节点,累积wpl
wpl+=deep*root->weight;
if(root->lchild!=NULL)//若左子树不空,对左子树递归遍历
wpl_PreOrder(root->lchild,deep+1);
if(root->rchild!=NULL)//若右子树不空,对右子树递归遍历
wpl_PreOrder(root->rchild,deep+1);
return wpl;
}
b.基于层次遍历的算法
#define MaxSize 100//设置队列的最大容量
int wpl_LevelOrder(BiTree root){
BiTree q[MaxSize]; //声明队列,end1为头指针,end2为尾指针
int end1,end2; //队列最多容纳MaxSize-1个元素
end1=end2=0; //头指针指向队头元素,尾指针指向队尾的后一个元素
int wpl=0,deep=0; //初始化wpl和深度
BiTree lastNode; //lastNode用来记录当前层的最后一个结点
BiTree newlastNode; //newlastNode用来记录下一个层的最后一个结点
lastNode=root; //lastNode初始化为根节点
newlastNode=NULL; //newlastNode初始化为空
q[end2++]=root; //根节点入队
while(end1!=end2){ //层次遍历,若队列不空则循环
BiTree t=q[end1++]; //拿出队列中的头一个元素
if(t->lchild==NULL&&t->rchild==NULL){
wpl+=deep*t->weight;
} //若为叶节点,统计wpl
if(t->lchild!=NULL){ //若非叶节点,把左节点入队
q[end2++]=t->lchild;
newlastNode=t->lchild;
} //并设下一层的最后一个结点为该结点的左结点
if(t->rchild!=NULL){ //处理叶节点
q[end2++]=t->rchild;
newlastNode=t->rchild;
}
if(t==lastNode){ //若该结点为本层最后一个结点,更新lastNode
lastNode=newlastNode;
deep+=1; //层数加1
}
}
return wpl; //返回wpl
}
c.非递归的后序遍历。非递归遍历都需要栈,而后序遍历需要额外保存信息
typedef struct{
BTNode *p;//p是二叉树的结点的指针
int rvisited; //revisited=1代表p所指向的结点的右结点已被访问过
}SNode; //栈中的结点定义
typedef struct{
SNode Elem[maxsize];
int top;
}SqStack;//栈结构体
void PostOrder2(BiTree T){
SNode sn;
BTNode *pt=T;
InitStack(S);//从根节点开始,往左下方走,将路径上的每一个结点入栈
while(T){
Push(pt,0);//Push到栈中的两个信息,一个是结点指针,一个是其右结点是否被访问过
pt=pt->lchild;
}
while(!S.IsEmpty()){//只要S栈非空
sn.s.getTop();//sn是栈顶结点
if(sn.p->rchild==NULL||sn.rvisited){
Pop(S,pt);
visit(pt);
}
else{//若它的右孩子存在且rvisited为0,处理其右孩子
sn.rvisited=1;//往左下方走到尽头,将路径上所有元素入栈
pt=sn.p->rchild;
while(pt!=NULL){
Push(S,pt,0);
pt=pt->lchild;
}
}
}
}
数的存储结构:可以使用顺序存储结构或链式存储结构
typedef struct{
ElemType data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n;
}PTree;
森林的遍历:
错题:
BST左子树非空,则左子树上所有点小于根节点的值;右子树非空,则右子树上所有点大于根节点的值。 查找、插入略 构造:依次输入数据元素,并将它们插入到二叉排序树上适当的位置。 删除(较复杂):删除结点必须维护二叉排序树的性质
显然,对于高度为H的二叉树,插入和删除的运行时间都是O(H),但如果二叉树在最坏的情况,会退化成链表,这时性能会指数增加。 二叉树上的查找与二分查找的性能接近。但是二分查找的判定树是唯一的,二叉排序树是不唯一的,相同的关键字其插入顺序不同可能生成不同的二叉排序树。
为了避免二叉树的高度增长过快,规定在插入和删除二叉树结点的时候,保证任意结点的左、右子树高度的绝对值差不超过1。 平衡因子=左子树高度-右子树高度,显然只能取-1、0、1.
平衡二叉树的插入:插入结点后,要检查其插入路径上的结点是否因为这次操作而导致了不平衡。每次调整的对象都是最小不平衡树,即在插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树
删除相同 查找为log2n
哈夫曼树的带权路径长度最小
前缀编码:如果没有一个编码是另外一个编码的前缀,则称这样的编码为前缀编码。
图G由顶点集V和边集E组成。|V|表示图G中顶点的个数,也称为图G的阶 表可以是空表,树可以是空树,但是图不可以是空图,即图中不能一个顶点都没有。图中至少要有一个点,但是边集可以为空。
#define MaxVertexNum 100//顶点数目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum];//顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵,边表
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;
特点:
当一个图为稀疏图时,使用邻接矩阵表示法显然要浪费大量的存储空间。图的邻接表法结合了顺序存储和链式存储方法。 顶点表:顶点域+边表头指针 边表:邻接点域+指针域
#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点
int adjvex;//该弧所指向的顶点的位置
struct ArcNode *next;//指向下一条弧的指针
//InfoType info;//网的边权值
}ArcNode;
typedef struct VNode{//顶点表结点
VertexType data;//顶点信息
ArcNode *first;//指向第一条依附该结点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices;//邻接表
int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储的图类型
有向图的一种链式存储方式。在十字链表中,有向图的每一条弧有一个结点,对应于每个顶点也有一个结点
#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点
int tailvex,headvex;//该弧的头尾结点
struct ArcNode *hlink,*tlink;//分别指向弧头相同和弧尾相同的结点
//InfoType info;//相关信息指针
}ArcNode;
typedef struct VNode{//顶点表结点
VertexType data;//顶点信息
ArcNode *firstin,*firstout;//指向第一条入弧和出弧
}VNode;
typedef struct{
VNode xlist[MaxVertexNum];//邻接表
int vexnum,arcnum;//图的顶点数和弧数
}GLGraph;//GLGraph是以十字邻接存储的图类型
本质上还是邻接表,但是针对有向图寻找入弧作出了优化,因此很容易可以求得顶点的出度和入度。
邻接多重表是无向图的另一种链式存储结构 邻接表中难以求两个顶点之间是否存在边,以及难以执行删除边的操作。
#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode{//边表结点
bool mark;//访问标记
int ivex,jvex;//分别指向该弧的两个结点
struct ArcNode *ilink,*jlink;//分别指向两个顶点的下一条边
//InfoType info;//相关信息的指针
}ArcNode;
typedef struct VNode{//顶点表结点
VertexType data;//顶点信息
ArcNode *firstedge;//指向第一条依附该结点的边
}VNode;
typedef struct{
VNode adjmulist[MaxVertexNum];//邻接表
int vexnum,arcnum;//图的顶点数和弧数
}AMLGraph;//AMLGraph是以邻接多重表存储的图类型
PS:稀疏矩阵可以使用十字链表和三元组表进行压缩 补充:
BFS:分层遍历,借助辅助队列。 性能分析:空间复杂度O(|V|)(全部入队) 采用邻接表时,每个顶点入队一次,每条边至少访问一次,时间复杂度O(|V|+O|E|)。采用邻接矩阵时,查找每个顶点的邻接点所需时间为O(V),所以总的时间复杂度为O(|V|^2)
使用BFS可以求解非带权图的单源最短路 广度优先生成树对于邻接矩阵而言是唯一的,对于邻接表是不唯一的。
DFS 递归算法,需要借助递归工作栈,空间复杂度为O(|V|) 以邻接矩阵表示时,查找每个顶点的邻接点所需时间为O(|V|),故总的时间复杂度为O(|V|^2)。当以邻接表表示时,查找所有顶点的邻接点所需时间为O(|E|),访问顶点所需时间为O(|V|),总的时间复杂度为O(|V|+|E|) 基于邻接表的深度优先搜索树是不唯一的。
可以用图的遍历算法来判断图的连通性
历年考察重点
一个连通图的最小生成树是图的极小连通子图,它包含图的所有顶点,且边的权值之和最小。 性质:
Dijkstra思路相同。思路如下:
显然,主要开销就是找dist的最小值,可以使用优先队列优化。 dijkstra是基于贪心策略的,在边上带有负权值的时候不适用(准确来说,是对于有负圈的图,dijkstra无法结束) 时间复杂度O(|V|^2)
时间复杂度O(|V|^3),但是很简单。 思路就是使用邻接矩阵来存储任意两个点之间的距离。对于任意两个点,枚举可能的中间结点并更新这个矩阵。
操作:
显然,如果图中存在环,则它不可能有拓扑序列。 如果一个点有多个直接后继,则拓扑排序的结果通常不唯一。
没错,和IT项目管理的关键路径法的那个关键路径是一个东西。 在带权有向图中,以顶点表示事件,有向边表示活动,边上的权值表示活动的开销,这样的网络称为AOE网。 AOE网的性质:
错题:MST的一个限制条件 当带权连通图中的任意一个环中所包含的边的权值均不相同时,其MST是唯一的。
顺序查找,即线性查找。一般分为对无序线性表的查找和按关键字有序的顺序表的顺序查找。
又称二分查找 算法如下:
int Binary_Search(SeqListr L,ElemType key){
int low=0,high=L.TableLen-1,mid;
while(low<=high){
mid=(low+high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]>key)
high=mid-1;
else
low = mid+1;
}
return -1;
}
查找成功的平均查找长度为log2(n+1)-1,时间复杂度O(log2n)
又称索引顺序 查找,既有动态结构,又可以快速查找 基本思想:
设将长度为n的查找表分为b块,每块s个记录。 索引表中顺序查找的平均查找长度=(s^2+2s+n)/(2s) 索引表中二分查找的平均查找长度=ceil((log2(b+1)))+(s+1)/2
PS:表长n个记录,均分成b块,每块记录数为s,则b=n/s。当s=ceil(sqrt(n))的时候,ASL最小为ceil(sqrt(n))+1
B树重点考察,B+树只考察基本概念 王道P263
B树,又称为多路平衡查找树,满足以下特性:
B树是所有结点的平衡因子均等于0的多路查找树 B树的大部分操作所需要的磁盘存取次数与B树的高度成正比。首先要明确,B树的高度不包括最下层叶节点所处的那一层。 对于任意一棵n个关键字,高度为h、阶数为m的B树
5.B+树 B树的一种变形树,m阶的B+树和m阶的B树区别:
在具体应用上,B+树比B树更适用于实际应用中的操作系统的文件索引和数据库索引,因为前者磁盘读写代价更低,查询效率更稳定。
以下用Hi表示第i次探测的散列地址
散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子
串的模式匹配,就是求第一个字符串在第二个字符串中的位置
int Index(SString S,SString T){
int i=1,j=1;
while(i<=S[0]&&j<=T[0]){
if(S[i]==T[j]){
++i;
++j;
}
else{//失败,指针回退
i=i-j+2;
j=1;
}
}
if(j>T[0])
return i-T[0];
else
return 0;
}
时间复杂度为O(nm),n、m分别为主串和模式串的长度
添加了失配函数,如果发生失配,并不直接归位,而是沿着next跳转。
void get_next(char T[],int next[]){
i=1;
next[1]=0;
j=0;
while(i<=T[0]){//T[0]保存字符串的长度
if(j==0||T[i]==T[j]){
++i;++j;next[i]=j;
}
else{
j=next[j];
}
}
}
//王道版本的KMP
int KMP(char S[],char T[],int next[],int pos){
//利用模式串T的next函数在主串S中第pos个位置之后的位置的KMP算法
i=pos;
j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){
++i;
++j;
}
else{
j=next[j];
}
}
if(j>T[0]){
return i-T[0];
}
else
return 0;
}
我更喜欢算法导论版本的伪代码KMP
//匹配串T,模板串P
KMP-MATCHER(T,P){
n=T.length
m=P.length
pi=COMPUTE-PREFIX-FUNCTION(P)//根据模板串计算转移函数pi
q=0
for i=1 to n{
while q>0 && P[q+1]!=T[i]{//如果失配,沿转移函数前进
q=pi[q]
}
if P[q+1]==T[i]{
q = q+1
}
if q==m{
Print i-m
q = pi[q]//寻找下一个匹配
}
}
}
COMPUTE-PREFIX-FUNCTION(P){
m=P.length
let pi[1...m] be a new array
pi[1]=0
k=0
for q=2 to m{
while k>0 && P[k+1]!=P[q]
k=pi[k]
if P[k+1]==P[q]
k=k+1
pi[q]=k
}
return pi
}
排序,就是重新排列表中的元素,使表中的元素按关键字递增或递减的过程。 算法稳定性:如果有两个元素Ri=Rj,其对应的关键字keyi=keyj,且排序时Ri在Rj的前面。如果使用某一排序算法排序后,Ri仍然在Rj前面,该算法是稳定的,否则称排序算法是不稳定的。
某一时刻状态:有序序列L[1…i-1]、L[i]、无序序列L[i+1…n] 为了将L[i]插入,执行以下操作:
void InsertSort(ElemType A[],int n){
int i,j;
for(i=2;i<n;i++)
{
if(A[i].key<A[i-1].key){
A[0]=A[i];//复制为哨兵,A[0]不存放元素
for(j=i-1;A[0].key<A[j].key;--j)//从后往前查找待插入位置
A[j+1]=A[j];//向后挪位
A[j+1]=A[0];//复制到插入位置
}
}
}
效率分析;
查找有序子表的部分用折半查找来实现。在确定出待插入位置后,就可以统一地向后移动元素了。
void InsertSort(ElemType A[],int n){
int i,j,low,high,mid;
for(i=2;i<=n;i++){
A[0]=A[i];
low=1;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid].key>A[0].key) high = mid-1;
else low = mid+1;
}
for(j=i-1;j>=high+1;--j)
A[j+1]=A[j];//统一后移,空出位置
A[high+1]=A[0];
}
}
直接插入排序适用于基本有序的算法和数据量不大的排序表,基于此提出了希尔排序,又称缩小增量排序。 基本思想:先将待排序表分割成若干个形如L[i,i+d,i+2d,…i+kd]的特殊子表,分别进行直接插入排序。党整个表中元素基本有序时,再对全体进行一次直接插入排序。 过程:
void ShellSort(ElemType A[],int n){
/*
修改如下:
1. 前后记录位置的增量是dk,不是1
2. r[0]只是暂存单元,不是哨兵,当j<=0时,插入位置已到
*/
for(dk=n/2;dk>=1;dk/=2){//补偿变化
for(i=dk+1;i<=n;++i){
if(A[i].key<A[i-dk].key){//需将A[i]插入有序增量子表中
A[0]=A[i];
for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk){
A[j+dk]=A[j];//记录后移,查找插入的位置
}
A[j+dk]=A[0];
}
}
}
}
性能分析:
根据序列中两个关键字的比较结果来交换这两个记录在序列中的位置。重点考冒泡排序和快速排序,一般不会单独考察冒泡排序
基本思想:太简单,略。 每趟冒泡的结果都会将一个元素放在最终位置,比如用王道的算法,每次排序之后会将序列中最小的元素放在序列最前面。 记忆:想冒泡泡一样,每次从头撸到尾,最后一个就有序了,然后少撸一截。撸n-1遍。 冒泡有个很好的性质,就是如果撸一遍以后没有可以交换的对象了,那么之后也不再有可以交换的对象,可以提前结束算法。
void BubbleSort(ElemType A[],int n){
//冒泡排序,从小到大
for(i=0;i<n-1;i++){
flag = false;//表示本趟冒泡是否发生交换
for(j=n-1;j>i;j--){
if(A[j-1].key>A[j].key){
swap(A[j-1],A[j]);
flag = true;
}
}
if(!flag){
return;//本趟遍历后没有交换,说明序列已经有序
}
}
}
效率分析;
基本思想是基于分治的。
void QuickSort(ElemType A[],int low,int high){
if(low<high){
int pivotpos=Partition(A,low,high);//划分
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
int Partition(ElemType A[],int low,int high){
//严谨的一趟排序过程
ElemType pivot=A[low];
while(low<high){
while(low<high&&A[high]>=pivot) --high;
A[low]=A[high];//将比枢轴值小的元素移动到左端
while(low<high&&A[low]<=pivot) ++low;
A[high]=A[low];//将比枢轴值大的元素移动到右端
}
A[low]=pivot;//枢轴元素存放到最终位置
return low;
}
也有结合起来的版本,比如我NOIP时期的代码:
#include <stdio.h>
int n,a[100009];
void sort (int a[],int left,int right) {
int low,high,pivot;
int temp;
low=left,high = right;
pivot=a[(left+right)/2];
while (low<=high) {
while (a[low]<pivot) low++;
while (pivot<a[high]) high--;
if (low<=high) {
temp=a[low];
a[low]=a[high];
a[high]=temp;
low++,high--;
}
}
//记忆后面两句话的时候一定要记得,此时low>high
if (left<high) sort(a,left,high);
if (low<right) sort(a,low,right);
}
int main () {
int i,j;
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a,1,n);//从0开始是个好习惯,不过我费事改了
for (i=1;i<=n;i++)
printf("%d ",a[i]);
}
效率分析:
基本思想:每一趟在后面n-i+1个待排序元素中选择关键字最小的元素,作为有序子序列的第i个元素,直到第n-1趟完成。
void SelectSort(ElemType A[],int n){
for(i=0;i<n-1;i++){
min=i;
for(j=i+1;j<n;i++){
if(A[j]<min) min=j;
}
if(min!=i) swap(A[i],A[min])
}
}
效率:
堆排序是一种树形选择排序方式。特点是将L[1..n]看成是一棵完全二叉树的顺序存储结构,以此完成排序。 堆是一种特殊的二叉树,它的根节点的值大于/小于其两个孩子的值,这样根节点就是最大/最小的。通过不断提取最大值,可以得到一个序列,这个序列就是最终的排序结果。
void BuildMaxHeap(ElemType A[],int len){
for(int i=len/2;i>=0;i--)
AdjustDown(A,i,len);
}
void AdjustDown(ElemType A[],int k,int len){
//AdjustDown将元素k向下调整
A[0]=A[k];
for(i=2*k;i<=len;i*=2){//沿key较大的子节点向下筛选
if(i<len&&A[i]<A[i+1]){
i++;//取key较大的子节点的下标
}
if(A[0]>=A[i]) break;//筛选结束
else{
A[k]=A[i];//将A[i]调整到双亲结点上
k=i;//修改k值,以便继续向下筛选
}
}
A[k]=A[0];//被筛选结点的值放入最终位置
}
void HeapSort(ElemType A[],int len){
BuildMaxHeap(A,len);//初始建堆
for(i=len;i>1;i--){//n-1趟的交换和建堆过程
Swap(A[i],A[1]);//输出堆顶元素
AdjustDown(A,1,i-1);//整理,将剩余的i-1个元素整理成堆
}
}
void AdjustUp(ElemType A[],int k){
//参数k为向上调整的结点,也为堆的元素个数
A[0]=A[k];
int i=k/2;
while(i>0&&A[i]<A[0]){
A[k]=A[i];//双亲结点下调
k=i;
i=k/2;
}
A[k]=A[0];
}
将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有n个记录,则可以看成是n个有序子表,然后不断两两归并直到合成一个长度为n的有序表为止,这种排序方法称为2-路归并排序。
递归形式的2-路归并排序算法是基于分治额,对子表递归地排序。
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));//辅助数组B,长度n+1
void Merge(ElemType A[],int low,int mid,int high){
//表A的两端low...mid和mid+1...high各自有序,将它们合并成一个有序表
for(int k=low;k<=high;k++)
B[k]=A[k];//将A中的所有元素复制到B中
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j]){//比较B的左右两段中的元素
A[k]=B[i++];//将较小值复制到A中
}
else{
A[k]=B[j++];
}
}
while(i<=mid) A[k++]=B[i++];
while(j<=high) A[k++]=B[j++];
}
void MergeSort(ElemType A[],int low,int high){
if(low<high){
int mid=(low+high)/2;//从中间划分两个子序列
MergeSort(A,low,mid);
MergeSort(A,mid+1,high);
Merge(A,low,mid,high);
}
}
效率:
它不是基于比较进行排序的,而是采用多关键字排序思想,又分为最高位优先排序和最低位优先排序。 以r为基数的最低位优先基数排序的过程:假设线性表由结点序列a0,a1,…,an-1构成,每个结点的关键字由d元组组成
效率:
省略,看书
在排序过程中需要多次进行内存和主存之间的交换,对外村文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序方法就称为外部排序。
通常根据外存设备的不同分为磁盘文件排序和磁带文件排序两大类。磁盘是直接存取设备,磁带是顺序存取设备。 外部排序通常采用归并排序方法,有两个相对独立的阶段:
一般情况下,外部排序的总时间=内部排序所需的时间+外存信息读写的时间+内部归并所需的时间 即t_ES=rt_IS+dt_IO+S(n-1)t_mg,其中r是初始归并段的个数,t_IS是对每一个初始归并段进行内部排序的时间,d是访问外存块的次数,t_IO是每一个块的存取时间,S是归并趟数,n是每趟参加二路归并的记录个数,t_mg是每作一次内部归并,取得一个关键字最小记录的时间。 显然磁盘存取的时间远远大于内部排序和内部归并的时间,因此要提高外排序的速度,应该着力减少d,即I/O次数。
增大归并路数m,或减少初始归并段数r,都能减少归并趟数S,以减少读写磁盘次数d,达到提高外部排序速度的目的。
上节提到,可以增加归并路数m来减少归并趟数S,进而减少访问外存的次数。然而增加归并路数m又会增加算法内部排序的时间。因此不能使用普通的内部归并排序算法。 为了使内部归并不受m的增大的影响,引入了败者树。可以看作是一棵完全二叉树,每个叶结点存放各归并段在归并过程中参加比较的记录。内部结点用来记录左右子树中的失败者,让胜利者继续向上比较,一直到根节点。 m路归并的败者树深度为ceil(log2m),因此m个记录中选择最小关键字,最少需要ceil(log2(m))次比较,内部归并的比较次数就与m无关了。因此,只要内存空间允许,增大归并路数m可以有效减少归并树的高度,从而减少I/O次数d,提高外部排序的速度。 值得注意的是m并不是越大越好,m增大时要相应地增加输入缓冲区的个数。如果可供使用的内存空间不变,就势必要减少每个输入缓冲区的容量,使得内外存交换数据的次数增大。当m值过大时,虽然归并趟数减少,但读写外存的次数仍会增加。
如果采用前面介绍过的内部排序方法,将得到长度都相同的初始归并段。因此,需要使用新的算法那来生成初始归并段。 设初始待排文件FI,初始归并段文件为FO,内存工作区为WA,内存工作区可容纳w个记录。置换-选择算法的步骤如下: