数据结构实战

    返回首页    发表留言
本文作者:李德强
          第六节 树形选择排序
 
 

        树形选择排序是将待排序数组的每一个元素做为一棵满二叉树的叶子节点,每个非叶子节点中的最小关键字等于其左右孩子节点中较小报关键字,则根结点中的关键字即为最小关键字。在选定了最小关键字之后,如果想要选出次小关键字,仅需将叶子结点中的最小关键字设置为“最大值”,然后按其所在位置再做最小关键字选择算法即可:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define SIZE	(10)
#define MAX		(99)

typedef struct
{
	int key;
	int index;
} s_tree;

//创建一棵满二叉树
s_tree** create_tree(int *array, int size, int *ms)
{
	//计算阶数
	int m = (int) log2(size) + 1;
	if (pow(2, m - 1) < size)
	{
		m++;
	}
	//计算叶子节点数
	int c = pow(2, m - 1);

	//申请内存
	s_tree **tree = malloc(sizeof(s_tree *) * m);
	for (int i = 0; i < m; i++)
	{
		//申请内存
		tree[i] = malloc(sizeof(s_tree) * (int) pow(2, i));
	}

	//初始化二叉树的叶子节点数据,不足的补MAX
	for (int j = 0; j < c; j++)
	{
		if (j < size)
		{
			tree[m - 1][j].key = array[j];
		}
		else
		{
			tree[m - 1][j].key = MAX;
		}
		tree[m - 1][j].index = j;
	}
	//返回阶数
	*ms = m;
	//返回满二叉树
	return tree;
}

//销毁满二叉树
void destory_tree(s_tree **tree, int m)
{
	for (int i = 0; i < m; i++)
	{
		free(tree[i]);
	}
	free(tree);
}

//找到最小值
int min_ind_tree(s_tree **tree, int m)
{
	//从最大阶开始
	for (int i = m - 1; i > 0; i--)
	{
		//每两个兄弟节点比较大小
		for (int j = 0; j + 1 < (int) pow(2, i); j += 2)
		{
			//将值大的兄弟节点的值向上赋值给其父节点
			if (tree[i][j].key < tree[i][j + 1].key)
			{
				tree[i - 1][j / 2].key = tree[i][j].key;
				tree[i - 1][j / 2].index = tree[i][j].index;
			}
			else
			{
				tree[i - 1][j / 2].key = tree[i][j + 1].key;
				tree[i - 1][j / 2].index = tree[i][j + 1].index;
			}
		}
	}
	//显示二叉树
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < (int) pow(2, i); j++)
		{
			printf("%02d ", tree[i][j].key);
		}
		printf("\n");
	}
	//最后这个满二叉树的根节点即为最小的关键字
	tree[m - 1][tree[0][0].index].key = MAX;
	//返回根节点关键字
	return tree[0][0].key;
}

//选择排序
void select_sort(int*array, int size)
{
	int m = 0;
	//创建满二叉树
	s_tree **tree = create_tree(array, size, &m);
	//循环数组
	for (int i = 0; i < size; i++)
	{
		//找到最小的关键字
		array[i] = min_ind_tree(tree, m);
		printf("%d times the selection result %d.\n\n", i + 1, array[i]);
	}
	//销毁满二叉树
	destory_tree(tree, m);
}

//显示数组
void display(int *array, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

int main(int argc, char **args)
{
	int array[SIZE] =
	{ 5, 3, 7, 2, 9, 8, 1, 0, 6, 4 };
	display(array, SIZE);
	select_sort(array, SIZE);
	display(array, SIZE);

	return 0;
}

        运行结果:

5 3 7 2 9 8 1 0 6 4 

00 
00 04 
02 00 04 99 
03 02 08 00 04 99 99 99 
05 03 07 02 09 08 01 00 06 04 99 99 99 99 99 99 
1 times the selection result 0.

01 
01 04 
02 01 04 99 
03 02 08 01 04 99 99 99 
05 03 07 02 09 08 01 99 06 04 99 99 99 99 99 99 
2 times the selection result 1.

02 
02 04 
02 08 04 99 
03 02 08 99 04 99 99 99 
05 03 07 02 09 08 99 99 06 04 99 99 99 99 99 99 
3 times the selection result 2.

03 
03 04 
03 08 04 99 
03 07 08 99 04 99 99 99 
05 03 07 99 09 08 99 99 06 04 99 99 99 99 99 99 
4 times the selection result 3.

04 
05 04 
05 08 04 99 
05 07 08 99 04 99 99 99 
05 99 07 99 09 08 99 99 06 04 99 99 99 99 99 99 
5 times the selection result 4.

05 
05 06 
05 08 06 99 
05 07 08 99 06 99 99 99 
05 99 07 99 09 08 99 99 06 99 99 99 99 99 99 99 
6 times the selection result 5.

06 
07 06 
07 08 06 99 
99 07 08 99 06 99 99 99 
99 99 07 99 09 08 99 99 06 99 99 99 99 99 99 99 
7 times the selection result 6.

07 
07 99 
07 08 99 99 
99 07 08 99 99 99 99 99 
99 99 07 99 09 08 99 99 99 99 99 99 99 99 99 99 
8 times the selection result 7.

08 
08 99 
99 08 99 99 
99 99 08 99 99 99 99 99 
99 99 99 99 09 08 99 99 99 99 99 99 99 99 99 99 
9 times the selection result 8.

09 
09 99 
99 09 99 99 
99 99 09 99 99 99 99 99 
99 99 99 99 09 99 99 99 99 99 99 99 99 99 99 99 
10 times the selection result 9.

0 1 2 3 4 5 6 7 8 9 

        本例代码:

code path   chapter.08/e.g.8.6/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号