Để sử dụng C ++ priority_queue, chương trình phải bắt đầu bằng mã như:
#bao gồm
#bao gồm
sử dụng không gian têngiờ;
Nó bao gồm thư viện hàng đợi vào chương trình.
Để tiếp tục đọc, người đọc cần phải có kiến thức cơ bản về C ++.
Nội dung bài viết
- Xây dựng cơ bản
- Các chức năng quan trọng của thành viên
- Các chức năng hàng đợi ưu tiên khác
- Dữ liệu chuỗi
- Các cấu trúc hàng đợi ưu tiên khác
- Phần kết luận
Xây dựng cơ bản
Cấu trúc dữ liệu phải được xây dựng trước trước khi nó có thể được sử dụng. Xây dựng ở đây có nghĩa là khởi tạo một đối tượng từ lớp hàng đợi của thư viện. Đối tượng hàng đợi sau đó phải có tên do người lập trình đặt cho nó. Cú pháp đơn giản nhất để tạo hàng đợi ưu tiên là:
hàng đợi ưu tiên<kiểu>queueName;
Với cú pháp này, giá trị lớn nhất sẽ bị loại bỏ trước tiên. Một ví dụ về sự khởi tạo là:
hàng đợi ưu tiên<NS>pq;hoặc
hàng đợi ưu tiên<char>pq;
Vector và deque là hai cấu trúc dữ liệu trong C ++. Một ưu tiên_lệnh có thể được tạo với một trong hai. Cú pháp để tạo hàng đợi ưu tiên từ cấu trúc vectơ là:
hàng đợi ưu tiên<loại, vectơ<cùng loại>, đối chiếu>pq;Một ví dụ về sự thuyết minh này là:
hàng đợi ưu tiên<NS, vectơ<NS>, ít hơn<NS> >pq;Lưu ý khoảng cách giữa> và> ở cuối khai báo. Điều này là để tránh nhầm lẫn với >>. Mã so sánh mặc định ít hơn, có nghĩa là giá trị lớn nhất, và không nhất thiết phải là giá trị đầu tiên, sẽ bị xóa trước. Vì vậy, câu lệnh tạo có thể được viết đơn giản là:
hàng đợi ưu tiên<NS, vectơ<NS> >pq;Nếu giá trị nhỏ nhất cần được loại bỏ trước tiên, thì câu lệnh phải là:
hàng đợi ưu tiên<NS, vectơ<NS>, lớn hơn<NS> >pq;Các chức năng quan trọng của thành viên
Hàm push ()
Hàm này đẩy một giá trị, là đối số của nó, vào giá trị ưu tiên. Nó trả về giá trị vô hiệu. Đoạn mã sau minh họa điều này:
pq.xô(10);
pq.xô(30);
pq.xô(hai mươi);
pq.xô(năm mươi);
pq.xô(40);
Hàng đợi ưu tiên này đã nhận 5 giá trị nguyên theo thứ tự 10, 30, 20, 50, 40. Nếu tất cả các phần tử này được bật ra khỏi hàng đợi ưu tiên, thì chúng sẽ xuất hiện theo thứ tự 50, 40, 30, 20, 10.
Hàm pop ()
Hàm này loại bỏ giá trị có ưu tiên cao nhất khỏi giá trị ưu tiên cao nhất. Nếu mã so sánh lớn hơn, thì nó sẽ loại bỏ phần tử có giá trị nhỏ nhất. Nếu được gọi lại, nó sẽ loại bỏ phần tử tiếp theo có giá trị nhỏ nhất của phần còn lại; được gọi lại, nó loại bỏ giá trị nhỏ nhất tiếp theo hiện tại, v.v. Nó trả về giá trị vô hiệu. Đoạn mã sau minh họa điều này:
pq.xô('đến');pq.xô('NS');pq.xô('NS');pq.xô('Và');pq.xô('NS');
Lưu ý rằng để gọi một hàm thành viên, tên của đối tượng phải được theo sau bởi một dấu chấm, sau đó mới đến hàm.
Hàm trên cùng ()
Các nhạc pop () hàm loại bỏ giá trị tiếp theo của mức độ ưu tiên cao nhất, nhưng không trả lại giá trị đó, như nhạc pop () là một hàm void. Sử dụng đứng đầu() để biết giá trị của mức độ ưu tiên cao nhất phải được loại bỏ tiếp theo. Các đứng đầu() hàm trả về một bản sao của giá trị có mức độ ưu tiên cao nhất trong priority_queue. Đoạn mã sau, trong đó giá trị tiếp theo của mức độ ưu tiên cao nhất là giá trị nhỏ nhất, minh họa điều này
pq.xô('đến');pq.xô('NS');pq.xô('NS');pq.xô('Và');pq.xô('NS');
charch1=pq.đứng đầu();pq.nhạc pop();
charch2=pq.đứng đầu();pq.nhạc pop();
charch3=pq.đứng đầu();pq.nhạc pop();
charch4=pq.đứng đầu();pq.nhạc pop();
charch5=pq.đứng đầu();pq.nhạc pop();
Giá cả<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' ';
Đầu ra là ‘a’ ‘b’ ‘c’ ‘d’ ‘e’.
Hàm rỗng ()
Nếu một lập trình viên sử dụng đứng đầu() trên một hàm ưu tiên trống, sau khi biên dịch thành công, anh ta sẽ nhận được một thông báo lỗi như:
Vì vậy, hãy luôn kiểm tra xem hàng đợi ưu tiên có trống không trước khi sử dụng đứng đầu() hàm số. Các trống() hàm thành viên trả về bool, true, nếu hàng đợi trống và false nếu hàng đợi không trống. Đoạn mã sau minh họa điều này:
hàng đợi ưu tiên<NS>pq;NSi1= 10; NSi2= 30; NSi3= hai mươi; NSi4= năm mươi; NSi5= 40;
pq.xô(i1);pq.xô(i2);pq.xô(i3);pq.xô(i4);pq.xô(i5);
trong khi(!pq.trống())
{
Giá cả <<pq.đứng đầu() << '';
pq.nhạc pop();
}
Giá cả << ' ';
Các chức năng hàng đợi ưu tiên khác
Hàm size ()
Hàm này trả về độ dài của hàng đợi ưu tiên, như đoạn mã sau minh họa:
NSi1= 10; NSi2= 30; NSi3= hai mươi; NSi4= năm mươi; NSi5= 40;
pq.xô(i1);pq.xô(i2);pq.xô(i3);pq.xô(i4);pq.xô(i5);
NSlen=pq.kích thước();
Giá cả <<len<< ' ';
Đầu ra là 5.
Hàm swap ()
Nếu hai dòng hàng ưu tiên có cùng kiểu và cùng kích thước, thì chúng có thể được hoán đổi bằng hàm này, như đoạn mã sau cho thấy:
NSi1= 10; NSi2= 30; NSi3= hai mươi; NSi4= năm mươi; NSi5= 40;
pq1.xô(i1);pq1.xô(i2);pq1.xô(i3);pq1.xô(i4);pq1.xô(i5);
hàng đợi ưu tiên<NS>pqA;
NSit1= 1; NSit2= 3; NSit3= 2; NSit4= 5; NSit5= 4;
pqA.xô(it1);pqA.xô(it2);pqA.xô(it3);pqA.xô(it4);pqA.xô(it5);
pq1.tráo đổi(pqA);
trong khi(!pq1.trống())
{
Giá cả <<pq1.đứng đầu() << '';
pq1.nhạc pop();
} Giá cả<<' ';
trong khi(!pqA.trống())
{
Giá cả <<pqA.đứng đầu() << '';
pqA.nhạc pop();
} Giá cả<<' ';
Đầu ra là:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
The emplace () Fuction
Các emplace () chức năng tương tự như chức năng đẩy. Đoạn mã sau minh họa điều này:
NSi1= 10; NSi2= 30; NSi3= hai mươi; NSi4= năm mươi; NSi5= 40;
pq1.thay thế(i1);pq1.thay thế(i2);pq1.thay thế(i3);pq1.thay thế(i4);pq1.thay thế(i5);
trong khi(!pq1.trống())
{
Giá cả <<pq1.đứng đầu() << '';
pq1.nhạc pop();
} Giá cả<<' ';
Đầu ra là:
50 40 30 20 10
Dữ liệu chuỗi
Khi so sánh các chuỗi, nên sử dụng lớp chuỗi chứ không phải sử dụng trực tiếp các ký tự chuỗi vì nó sẽ so sánh các con trỏ chứ không phải các chuỗi thực. Đoạn mã sau đây cho thấy cách lớp chuỗi được sử dụng:
#bao gồmhàng đợi ưu tiên<dây>pq1;
chuỗi s1=dây('cái bút'), s2=dây('bút chì'), s3=dây('sách bài tập'), s4=dây('sách văn bản'), s5=dây('cái thước kẻ');
pq1.xô(s1);pq1.xô(s2);pq1.xô(s3);pq1.xô(s4);pq1.xô(s5);
trong khi(!pq1.trống())
{
Giá cả <<pq1.đứng đầu() << '';
pq1.nhạc pop();
} Giá cả<<' ';
Đầu ra là:
& emsp; sách văn bản & emsp; thước & emsp; bút chì & emsp; bút & emsp; sách bài tập
Các cấu trúc hàng đợi ưu tiên khác
Sáng tạo rõ ràng từ một vectơ
Một hàng đợi ưu tiên có thể được tạo một cách rõ ràng từ một vectơ như đoạn mã sau cho thấy:
vectơ<NS>vtr= {10,30,hai mươi,năm mươi,40};
hàng đợi ưu tiên<NS>pq(vtr.bắt đầu(), vtr.kết thúc());
trong khi(!pq.trống())
{
Giá cả <<pq.đứng đầu() << '';
pq.nhạc pop();
} Giá cả<<' ';
Đầu ra là: 50 40 30 20 10. Lần này, tiêu đề vectơ cũng phải được đưa vào. Các đối số cho hàm khởi tạo lấy con trỏ bắt đầu và kết thúc của vectơ. Kiểu dữ liệu cho vectơ và kiểu dữ liệu cho priority_queue phải giống nhau.
Để ưu tiên giá trị nhỏ nhất, khai báo cho hàm tạo sẽ là:
hàng đợi ưu tiên<NS, vectơ<NS>, lớn hơn>NS> >pq(vtr.bắt đầu(), vtr.kết thúc()); Sáng tạo rõ ràng từ một mảng
Một hàng đợi ưu tiên có thể được tạo một cách rõ ràng từ một mảng như đoạn mã sau cho thấy:
hàng đợi ưu tiên<NS>pq(arr, arr+5);
trong khi(!pq.trống())
{
Giá cả <<pq.đứng đầu() << '';
pq.nhạc pop();
} Giá cả<<' ';
Kết quả là: 50 40 30 20 10. Các đối số của hàm khởi tạo lấy con trỏ bắt đầu và kết thúc của mảng. arr trả về con trỏ bắt đầu, arr + 5 trả về con trỏ vừa qua mảng và 5 là kích thước của mảng. Kiểu dữ liệu cho mảng và kiểu dữ liệu cho priority_queue phải giống nhau.
Để ưu tiên giá trị nhỏ nhất, khai báo cho hàm tạo sẽ là:
hàng đợi ưu tiên<NS, vectơ<NS>, lớn hơn<NS> >pq(arr, arr+5);Lưu ý: Trong C ++, priority_queue thực sự được gọi là bộ điều hợp, không chỉ là vùng chứa.
Mã so sánh tùy chỉnh
Có tất cả các giá trị trong hàng đợi ưu tiên tăng dần hoặc tất cả giảm dần không phải là tùy chọn duy nhất cho hàng đợi ưu tiên. Ví dụ: danh sách 11 số nguyên cho một heap tối đa là:
88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69
Giá trị cao nhất là 88. Tiếp theo là hai số: 86 và 87, nhỏ hơn 88. Các số còn lại nhỏ hơn ba số này, nhưng không thực sự theo thứ tự. Có hai ô trống trong danh sách. Hai số 84 và 82 nhỏ hơn 86. Số 79 và 74 nhỏ hơn 87. Số 80 và 81 nhỏ hơn 84. Số 64 và 69 nhỏ hơn 79.
Vị trí của các con số tuân theo tiêu chí khối lượng tối đa - xem sau. Để cung cấp một lược đồ như vậy cho priority_queue, lập trình viên phải cung cấp mã so sánh của riêng mình - xem sau.
Phần kết luận
Một hàng đợi ưu tiên trong C ++ là một hàng đợi nhập trước xuất trước. Chức năng thành viên, xô(), thêm một giá trị mới vào hàng đợi. Chức năng thành viên, đứng đầu(), đọc giá trị hàng đầu trong hàng đợi. Chức năng thành viên, nhạc pop (), loại bỏ mà không trả lại giá trị hàng đầu của hàng đợi. Chức năng thành viên, trống(), kiểm tra xem hàng đợi có trống không. Tuy nhiên, priority_queue khác với hàng đợi, ở chỗ, nó tuân theo một số thuật toán ưu tiên. Nó có thể là lớn nhất, từ đầu tiên đến cuối cùng, hoặc ít nhất, từ đầu tiên đến cuối cùng. Các tiêu chí (thuật toán) cũng có thể do người lập trình xác định.