使用顺序统计算法从给定列表中查找第 i 个最大数的 C++ 程序

2023-06-20 10:00:05 81

算法

Begin function Insert() to insert nodes into the tree: Arguments: root, d. Body of the function: If tree is completely null then insert new node as root. If d = tmp->data, increase the count of that particular node. If d < tmp->data, move the tmp pointer to the left child. If d > tmp->data, move the tmp pointer to the right child. End Begin function AssignRank() to assign rank to each node of the tree: Arguments: Root. Body of the function: If left child of the root is not null. Then assign rank to the left child of the root. Increase the rank count. If right child of the root is not null. then assign rank to the right child of the root. End Begin function Select() to search Kth smallest element from the data stored in the tree: Arguments: Root, searched element k. Body of the function: If found to be equal, return to main and print the result. Else If it is greater then shift the temporary variable to the right child. Else shift the temporary variable to the left child. End

示例

#include using namespace std; static int cnt = 0; struct nod //节点声明 { int data; int rank; nod *l; nod *r; }; nod* CreateNod(int d) //创建新节点 { nod *newnod = new nod; newnod->data = d; newnod->rank = 0; newnod->l = NULL; newnod->r = NULL; return newnod; } nod* Insert(nod* root, int d) //执行插入 { nod *tmp = CreateNod(d); nod *t = new nod; t = root; if(root == NULL) root = tmp; else { while(t != NULL) { if(t->data < d ) { if(t->r== NULL) { t->r = tmp; break; } t = t->r; } else if(t->data > d) { if(t->l == NULL) { t->l= tmp; break; } t = t->l; } } } return root; } void AssignRank(nod *root) //为节点分配等级 { if(root->l!= NULL) AssignRank(root->l); root->rank = cnt; cnt++; if(root->r != NULL) AssignRank(root->r); } int Select(nod* root, int k) //选择第k个最大的元素 { if(root->rank == k) return root->data; else if(root->rank > k) return Select(root->l, k); else return Select(root->r, k); } void display(nod *root) //显示树。 { if(root->l != NULL) display(root->l); cout<<"\n data: "<data<<" rank: "<rank; if(root->r != NULL) display(root->r); } int main() { char c; int n, i, k, a[10]={4,7,6,1,10,3,2,15,16,20}; nod *root = new nod; root = NULL; for(i = 0; i < 10; i++) root = Insert(root, a[i]); //调用函数插入() cout<<"输入k的值： "; cin>>k; AssignRank(root); //调用函数Assignrank() cout<<"\nRank associated to each node:-"; display(root); //调用函数display() cout<<"\n\nThe kth Largest element is: "<输出结果

输入k的值： 7
Rank associated to each node:-
data: 1 rank: 0
data: 2 rank: 1
data: 3 rank: 2
data: 4 rank: 3
data: 6 rank: 4
data: 7 rank: 5
data: 10 rank: 6
data: 15 rank: 7
data: 16 rank: 8
data: 20 rank: 9
The kth Largest element is: 4

使用顺序统计算法从给定列表中查找第 i 个最大数的 C++ 程序

算法

示例

热门推荐

随机推荐