資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++雙向連結串列實現優先佇列
給定資料和整數優先順序值，任務是根據給定的優先順序建立一個雙向連結串列並顯示結果。
佇列是一種FIFO(先進先出)資料結構，其中最先插入的元素是最先被移除的。優先佇列是一種佇列，其中元素可以根據優先順序插入或刪除。它可以使用佇列、堆疊或連結串列資料結構實現。優先佇列透過遵循以下規則來實現：
- 具有最高優先順序的數據或元素將優先於具有最低優先順序的數據或元素執行。
- 如果兩個元素具有相同的優先順序，則它們將按照新增到列表中的順序執行。
用於實現優先佇列的雙向連結串列節點將包含三個部分：
- 資料 - 它將儲存整數值。
- 下一個地址 - 它將儲存下一個節點的地址。
- 上一個地址 - 它將儲存上一個節點的地址。
- 優先順序 - 它將儲存優先順序，這是一個整數值。它的範圍可以是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
更新於：2019年12月23日
607 次瀏覽
廣告