如何做好网站的建设与维护,芜湖网站建设推广,做网站傻瓜软件,百度查关键词显示排名概念
不知道你玩过英雄联盟吗#xff1f;英雄联盟里面的防御塔会攻击离自己最近的小兵#xff0c;但是如果有炮车兵在塔内#xff0c;防御塔会优先攻击炮车#xff08;因为炮车的威胁性更大#xff09;#xff0c;只有没有兵线在塔内时#xff0c;防御塔才会攻击英雄。…概念
不知道你玩过英雄联盟吗英雄联盟里面的防御塔会攻击离自己最近的小兵但是如果有炮车兵在塔内防御塔会优先攻击炮车因为炮车的威胁性更大只有没有兵线在塔内时防御塔才会攻击英雄。所以你可以得出优先级距离最近的炮车 炮车 距离最近的小兵 小兵 距离最近的英雄 英雄。 那什么是优先队列首先它是一个队列它的入队顺序没有发生改变但是出队的顺序是根据优先级的高低来实现的遍历队列优先级高的先出队有多个节点具有最高的优先级选取遇到的第一个具有最高的优先级的节点。 空队列 插入一个元素 插入第二个元素 删除一个节点 上列情况是最普通的情况无需多余的操作显然如果删除的是队列中的最后一个节点尾指针需要手动移动如果删除的是队列中的第一个节点头指针会自动移动。如果删除的队列只有一个节点那头尾指针需要手动置空。所以总共有 2 种情况需要考虑。
队列的算法实现
队列的结构体定义
其中优先级的高低是自己定义的你也可以令 0 为最高优先级优先级数也不只有这 9 个。
#define MAX_SIZE 15
typedef int DateElem;typedef struct _QNode
{int priority; //节点的优先级9为最高优先级0为最低优先级优先级相同的取第一个DateElem date;struct _QNode* next;
}QNode;typedef QNode* QueuePtr; //QueuePtr a; 就定义了一个指向结构体QNode的指针typedef struct _Queue
{int length; //队列长度QueuePtr head; //头指针QueuePtr tail; //尾指针
}Queue;
队列的初始化、判空、判满、插入
//队列的初始化初始化为空队列
void initQueue(Queue* q)
{if (!q) //指向队头的指针为空{return;}q-head NULL;q-tail NULL;q-length 0;
}//判断队列是否为空
bool IsEmpty(Queue* q)
{if (!q) return false;if (q-head NULL) //条件用 q-tail NULL 也行{return true;}return false; //不为空
}//判断队列是否为满
bool IsFull(Queue* q)
{if (!q) return false;if (q-length MAX_SIZE) //也可以用 q-length MAX_SIZE{return true;}return false;
}//入队
bool enterQueue(Queue* q, DateElem e, int priority)
{if (!q || IsFull(q)){cout 队列已满 endl;return false;}QNode* p new QNode;//if (!q) return false; 一般不会生成失败p-priority priority;p-date e;p-next NULL;//插入有两种情况if (IsEmpty(q)) //空队列{q-head p;q-tail p;}else //队列中已有元素{q-tail-next p; //队列中的最后一个节点的next指针指向新加节点q-tail p; //更新尾指针}q-length;return true;
}
出队
唯一与普通队列有较大差别的就是队列的出队其他的操作变化很小。
//遍历队列
bool popQueue(Queue* q,DateElem *out)
{if (!q || IsEmpty(q)){cout 队列为空 endl;return false;}if (!out){cout 无法传递删除节点的值 endl;return false;}QNode** prev_node_next NULL; //二级指针指向优先级最高的节点的前一个节点的next指针QNode* prev_node NULL; //指向优先级最高的节点的前一个节点QNode* temp NULL,*last NULL; //temp遍历队列last指向temp指向的前一个节点prev_node_next (q-head); //最开始指向队头指针也就是第一个节点的前一个节点的next指针解引用就是指向第一个节点last q-head; temp last-next; while (temp ! NULL){if (temp-priority (*prev_node_next)-priority){cout 找到了一个更高的优先级 temp-priority endl;prev_node_next (last-next); //指向temp的前一个节点的next指针prev_node last; //指向temp的前一个节点}last temp;temp temp-next;}*out (*prev_node_next)-date; //传递出队元素的值temp *prev_node_next; // temp指向要删除节点*prev_node_next (*prev_node_next)-next; //或者是 prev_node_next (*prev_node_next)-next;delete temp;q-length--;//情况一删除节点后为空队列if (q-length 0){q-head q-tail NULL;}//情况二删除的是尾节点else if ( *prev_node_next NULL prev_node ! NULL){q-tail prev_node;}//情况三删除的是首节点与情况一不同的是删除节点后队列不为空//情况四普通情况//这两种情况遍历结束后的调整中头尾指针就弄好了return true;
}
如果你觉得我这里写得不好嘻嘻因为明明只需要用一级指针我偏要用二级指针这就是我与明明的区别哈哈好了不开玩笑可以看看下图帮助理解。 队列的打印、清空、获取队首元素
//打印队列
bool Print(Queue* q)
{if (!q) return false;if (IsEmpty(q)){cout 队列为空 endl;}QNode* p q-head;cout 队列中的元素;while (p ! NULL){printf(%d[优先级%d] , p-date,p-priority);p p-next;}cout endl;return true;
}
//清空队列
bool ClearQueue(Queue* q)
{if (!q || IsEmpty(q)) return false;QNode* temp q-head, * tmp NULL;while (temp ! NULL){tmp temp-next;delete temp;temp tmp;}q-length 0;q-head NULL;q-tail NULL;return true;
}//获取队头
bool GetHead(Queue* sq, DateElem* date)
{if (!date || !sq || IsEmpty(sq))return false;*date sq-head-date; return true;}
主函数测试代码
int main(void)
{Queue* q new Queue;DateElem e -1;initQueue(q);for (int i 0; i 10; i){enterQueue(q, i 2, i);}printf(队列中有%d个元素\n, q-length);Print(q);for (int i 0; i 5; i){if (popQueue(q, e)){cout 出队的元素是 e endl;}else{cout 出队失败 endl;}}cout 出队后;Print(q);cout 清空队列后;ClearQueue(q);Print(q);//清理资源delete q;return 0;
} 运行结果
