最受欢迎的3种水果(综合应用)
程序员文章站
2022-05-26 18:29:26
...
该代码的大体思路:先把所有的水果(及其受欢迎度即就是有几个人喜欢count)插入到一棵二叉搜索树中,在进行二叉树的中序 遍历,最后进行建立小堆的操作,即就可以找出最受欢迎的3种水果。主要操作:二叉搜索树的插入,中序遍历,建堆时条件(叶子结点的处理,已经满足堆的情况),向下调整的操作。具体代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
typedef struct {
char fruit[20]; // 水果
int count; // 出现次数
} Report;
typedef struct TreeNode {
char fruit[20]; // Key
int count;
struct TreeNode *pLeft;
struct TreeNode *pRight;
} TreeNode;
int Insert(TreeNode **ppRoot, const char *fruit)
{
if (*ppRoot == NULL) {
*ppRoot = (TreeNode *)malloc(sizeof(TreeNode));
assert(*ppRoot);
strncpy((*ppRoot)->fruit, fruit, 20);
(*ppRoot)->count = 1;
(*ppRoot)->pLeft = (*ppRoot)->pRight = NULL;
return 0;
}
int r = strncmp((*ppRoot)->fruit, fruit, 20);
if (r == 0) {
return -1;
}
if (r < 0) {
return Insert(&(*ppRoot)->pLeft, fruit);
}
return Insert(&(*ppRoot)->pRight, fruit);
}
TreeNode * Search(TreeNode *pRoot, const char *fruit)
{
if (pRoot == NULL) {
return NULL;
}
int r = strncmp(pRoot->fruit, fruit, 20);
if (r == 0) {
return pRoot;
}
if (r < 0) {
return Search(pRoot->pLeft, fruit);
}
return Search(pRoot->pRight, fruit);
}
void InOrder(TreeNode *pRoot, Report array[], int *i, int max)
{
assert(*i < max);
if (pRoot == NULL) {
return;
}
InOrder(pRoot->pLeft, array, i, max);
strncpy(array[*i].fruit, pRoot->fruit, 20);
array[*i].count = pRoot->count;
(*i)++;
// 遍历根结点
InOrder(pRoot->pRight, array, i, max);
}
// 1. 建什么堆 小堆
// 2. 向下调整: 1) 叶子结点 2)已经满足堆
void AdjustDown(Report array[], int size, int parent)
{
int left = parent * 2 + 1;
int right = parent * 2 + 2;
if (left >= size) {
return;
}
int min = left;
if (right < size && array[right].count < array[left].count) {
min = right;
}
if (array[parent].count < array[min].count) {
return;
}
Report t = array[parent];
array[parent] = array[min];
array[min] = t;
AdjustDown(array, size, min);
}
void CreateHeap(Report array[], int size)
{
for (int i = (size - 2) / 2; i >= 0; i--) {
AdjustDown(array, size, i);
}
}
void App2()
{
const char * fruits[] = {
"Apple", "Banana", "Watermelon", "Pineapple",
"Apple", "Apple", "Apple", "Banana", "Pear", "Pear",
"Orange"
};
TreeNode *pRoot = NULL;
for (int i = 0; i < sizeof(fruits) / sizeof(char *); i++) {
const char * fruit = fruits[i];
TreeNode *pFound = Search(pRoot, fruit);
if (pFound) {
pFound->count++;
}
else {
Insert(&pRoot, fruit);
}
}
Report array[100];
int size = 0;
InOrder(pRoot, array, &size, 100);
Report heap[3];
int i;
for (i = 0; i < 3; i++) {
heap[i] = array[i];
}
CreateHeap(heap, 3);
for (i = 3; i < size; i++) {
if (array[i].count > heap[0].count) {
heap[0] = array[i];
AdjustDown(heap, 3, 0);
}
}
// 构建堆,数组(顺序表)
// 建堆
printf("插入成功\n");
}
上一篇: oh-my-zsh 显示执行时间
下一篇: spring自定义属性编辑器