分治法求解递归问题算法的一般形式:
void p(参数表){
if (递归结束条件) 可直接求解步骤;---基本型
else p(较小的参数);---归纳项
}
队列:只能在表的一端进行插入运算,在表的另-端进行删除运算的线性表(头删尾插)
队列的顺序表示——用一维数组base[MAXQSIZE]
#define MAXQSIZE 100//最大队列长度
Typedef struct{
QElemType *base;//初始化动态分配存储空间
int front;//头指针
int rear;//尾指针
}SqQueue;
解决假上溢的方法——引入循环队列
插入元素:Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)% MAXQSIZE;
删除元素:x=Q.base[s.front]
Q.front=(Q.front+1)% MAXQSIZE
队满:(rear+1)% MAXQSIZE==front
循环队列的操作一队列的初始化:
Status lnitQueue (SqQueue &Q){
Q.base = new QElemType[MAXQSIEZE] //分配数组空间
//Q.base = (QElemType*)
//malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base) exit*(OVERFLOW);//存储分配失败
Q.front=Q.rear=0; //头指针尾指针置为0,队列为空
return OK;
}
求队列的长度
int QueueLength(SqQueue Q){
return((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
}
循环队列入队:
Status EnQueue(SqQueue &Q,QElemType &e){
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;//队满
Q.base[Q.rear]=e; //新元素加入队尾
Q.rear=(Q.rear+1)&MAXQSIZE;//队尾指针+1
return OK;
}
循环队列出队:
Status DeQueue(SqQueue &Q,QElemType &e){
if(Q.front == Q.rear) return ERROR;//队空
e=Q.base[Q.front];//保存队头元素
Q.front=(Q.front+1)%MAXQSIZE;//队头指针+1
return OK;
}
取队头元素:
SElemType GetHead(SqQuere Q){
if(Q.front!=Q.rear)//队列不为空
return Q.base[Q.front];//返回队头指针元素的值,队头指针不变
链队列的初始化:
Status linitQueue(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
销毁链队列:
Status DestroyQueue(LinkQueue &Q){
while(Q.front){
p=Qmfront->next; free(Q.front); Q.fornt=p;
}
return OK;
//Q.rear= Q.front-> next; free(Q.front); Q.front=Q.rear;
}
链队列的操作——将元素e入队:
链队列的操作——链队列出队:
链队列的操作一 求链队列的队头元素