立志用最少的代碼做最高效的表達

---

將一系列給定數字順序插入一個初始為空的小頂堆H[]。隨后判斷一系列相關命題是否為真。命題分下列幾種：

x is the root：x是根結點；
x and y are siblings：x和y是兄弟結點；
x is the parent of y：x是y的父結點；
x is a child of y：x是y的一個子結點。

輸入格式：
每組測試第1行包含2個正整數N（≤ 1000）和M（≤ 20），分別是插入元素的個數、以及需要判斷的命題數。下一行給出區間[?10000,10000]內的N個要被插入一個初始為空的小頂堆的整數。之后M行，每行給出一個命題。題目保證命題中的結點鍵值都是存在的。

輸出格式：
對輸入的每個命題，如果其為真，則在一行中輸出T，否則輸出F。

輸入樣例：
5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

輸出樣例：
F
T
F
T

---

三大核心邏輯：建小頂堆、搜索堆中數據、字符串處理(getline+sscanf)

---

#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #define MAXDATA -10001; using namespace std;typedef struct HNode *Heap; //堆的類型定義 struct HNode{int Data[1010]; //存儲元素的數組 int size, Capacity; //堆的當前容量和最大容量 }; typedef Heap MinHeap; //最小堆//開辟空間（堆的空間）、定義哨兵、初始化、定義堆的容量 MinHeap CreateHeap(int MaxSize) {//初始化一個容量為MaxSize的空的最大堆MinHeap H = new HNode(); H->size = 0;H->Capacity = MaxSize;H->Data[0] = MAXDATA;return H; }void Insert(MinHeap H, int x) {int i;//i的起始值為size+1，意思是插入到最后一位，//當遇到第一個大于他的父節點時終止//值的改變范圍為每次一層。 for(i = ++H->size; H->Data[i/2] > x; i /= 2)H->Data[i] = H->Data[i/2];H->Data[i] = x; } int Find(int x, MinHeap H) {for(int i = 0; i < H->size; i++) if(H->Data[i] == x) return i; }int main() {int n,m; //n個節點，m個查詢 cin >> n >> m;MinHeap H; //像樹一樣，需要一個初始節點。 然后開始操作 H = CreateHeap(n); //建立空堆 for(int i = 0; i < n; i++) {int x; cin >> x;Insert(H, x);}getchar();string s;while(m--) {getline(cin, s);int x, x1, x2, pos_1, pos_2, len = s.size();char tmp[10];if(s[len-1] == 't') {sscanf(s.c_str(), "%d", &x);cout << (H->Data[1]==x ? "T\n" : "F\n");}else if(s[len-1] == 's') {sscanf(s.c_str(), "%d %*s %d", &x1, &x2);pos_1 = Find(x1, H);pos_2 = Find(x2, H);cout << ((pos_1/2 == pos_2/2) ? "T\n" : "F\n");}else {sscanf(s.c_str(), "%d %*s %s %*s %*s %d", &x1, tmp, &x2);pos_1 = Find(x1, H);pos_2 = Find(x2, H);if(tmp[0] == 't') //判斷父節點cout << ((pos_1==pos_2/2) ? "T\n" : "F\n");else cout << ((pos_1/2==pos_2) ? "T\n" : "F\n");}} return 0; }

---

耗時

---

?????????——自信的你最可愛

總結

以上是生活随笔為你收集整理的【解析】基础实验4-2.5 关于堆的判断 (25 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。