เราได้รับข้อมูลและลำดับความสำคัญเป็นค่าจำนวนเต็ม และภารกิจคือการสร้างรายการที่เชื่อมโยงเป็นสองเท่าตามลำดับความสำคัญที่กำหนดและแสดงผล
คิวเป็นโครงสร้างข้อมูล FIFO ซึ่งองค์ประกอบที่แทรกก่อนเป็นองค์ประกอบแรกที่จะถูกลบออก คิวลำดับความสำคัญเป็นประเภทของคิวที่สามารถแทรกหรือลบองค์ประกอบขึ้นอยู่กับลำดับความสำคัญ สามารถใช้งานได้โดยใช้โครงสร้างข้อมูลคิว สแต็ก หรือรายการลิงก์ คิวลำดับความสำคัญจะดำเนินการตามกฎเหล่านี้ -
- ข้อมูลหรือองค์ประกอบที่มีลำดับความสำคัญสูงสุดจะถูกดำเนินการก่อนข้อมูลหรือองค์ประกอบที่มีลำดับความสำคัญต่ำสุด
- หากองค์ประกอบสองรายการมีลำดับความสำคัญเท่ากันกว่าองค์ประกอบนั้นจะถูกดำเนินการตามลำดับ องค์ประกอบนั้นจะถูกเพิ่มในรายการ
โหนดของรายการที่เชื่อมโยงแบบทวีคูณสำหรับการนำลำดับความสำคัญไปใช้จะมีสามส่วน -
- ข้อมูล - จะเก็บค่าจำนวนเต็ม
- ที่อยู่ถัดไป - จะเก็บที่อยู่ของโหนดถัดไป
- Previous Address - จะเก็บที่อยู่ของโหนดก่อนหน้า
- ลำดับความสำคัญ - จะเก็บลำดับความสำคัญซึ่งเป็นค่าจำนวนเต็ม สามารถอยู่ในช่วงตั้งแต่ 0-10 โดยที่ 0 หมายถึงลำดับความสำคัญสูงสุด และ 10 หมายถึงลำดับความสำคัญต่ำสุด
ตัวอย่าง
ป้อนข้อมูล -
ผลลัพธ์-
อัลกอริทึม
Start Step 1-> Declare a struct Node Declare info, priority Declare struct Node *prev, *next Step 2-> In function push(Node** fr, Node** rr, int n, int p) Set Node* news = (Node*)malloc(sizeof(Node)) Set news->info = n Set news->priority = p If *fr == NULL then, Set *fr = news Set *rr = news Set news->next = NULL Else If p <= (*fr)->priority then, Set news->next = *fr Set (*fr)->prev = news->next Set *fr = news Else If p > (*rr)->priority then, Set news->next = NULL Set (*rr)->next = news Set news->prev = (*rr)->next Set *rr = news Else Set Node* start = (*fr)->next Loop While start->priority > p Set start = start->next Set (start->prev)->next = news Set news->next = start->prev Set news->prev = (start->prev)->next Set start->prev = news->next Step 3-> In function int peek(Node *fr) Return fr->info Step 4-> In function bool isEmpty(Node *fr) Return (fr == NULL) Step 5-> In function int pop(Node** fr, Node** rr) Set Node* temp = *fr Set res = temp->info Set (*fr) = (*fr)->next free(temp) If *fr == NULL then, *rr = NULL Return res Step 6-> In function int main() Declare and assign Node *front = NULL, *rear = NULL Call function push(&front, &rear, 4, 3) Call function push(&front, &rear, 3, 2) Call function push(&front, &rear, 5, 2) Call function push(&front, &rear, 5, 7) Call function push(&front, &rear, 2, 6) Call function push(&front, &rear, 1, 4) Print the results obtained from calling the function pop(&front, &rear) Print the results obtained from calling the function peek(front) Stop
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
//doubly linked list node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
//inserting a new Node
void push(Node** fr, Node** rr, int n, int p) {
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
// if the linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
} else {
// If p is less than or equal front
// node's priority, then insert the node
// at front.
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
} else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
} else {
// Finding the position where we need to
// insert the new node.
Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
//the last value
int peek(Node *fr) {
return fr->info;
}
bool isEmpty(Node *fr) {
return (fr == NULL);
}
int pop(Node** fr, Node** rr) {
Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
// main function
int main() {
Node *front = NULL, *rear = NULL;
push(&front, &rear, 4, 3);
push(&front, &rear, 3, 2);
push(&front, &rear, 5, 2);
push(&front, &rear, 5, 7);
push(&front, &rear, 2, 6);
push(&front, &rear, 1, 4);
printf("%d\n", pop(&front, &rear));
printf("%d\n", peek(front));
return 0;
} ผลลัพธ์
5 3
