数据结构学习日记(六)

分治法求解递归问题算法的一般形式:

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入队:

数据结构学习日记(六)

 

 

链队列的操作——链队列出队:

数据结构学习日记(六)

 

 

链队列的操作一 求链队列的队头元素

 

数据结构学习日记(六)

 

上一篇:(三)普通队列、循环队列、(循环)链队列


下一篇:队列小哥哥喊你来排队了~(自带循环的那种)