南京XX大学 数据结构 课程设计 堆排序 二叉排序树
XX
课 程 设 计 总 结 报 告
课程名称: 《数据结构 –使用C语言》
课设题目: 堆排序，二叉排序树 班级: 姓名: 学号:
指导教师: 课设成绩:
1
目 录
1 堆排序….............................................................................................. 3 1.1. 题目….......................................................................................... 3 1.2. 功能要求….................................................................................. 3 1.3. 算法设计
1.4. 算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1.5. 算法
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
1.6. 算法程序
1.7. 编译运行结果
2 二叉排序树查找
2.1. 题目….......................................................................................... 2.2. 功能要求….................................................................................. 2.3. 算法设计
2.4. 算法流程
2.5. 算法程序
2.6. 编译运行结果
3 认识(收获)与体会
2
1堆排序
1.1. 题目
堆排序(针对大根堆)
1.2. 功能要求
输入一组正整数关键字,20个以内，以-1结束,
将输入数据存入数组,
调用初始堆构造函数，建立初始堆,
调用堆排序函数进行堆排序，结果仍在数组中,
调用输出函数输出数组中的结果排序值。
1.3. 算法设计
* 大根堆的定义
若完全二叉树中任一结点的关键字值均大于等于孩子(若存在的话)结点的关键字值,则称此完全二叉树为大根堆。
* 算法思想,利用堆排序,
? 将欲排序的序列构造成一个大根堆顺序存储结构的序列,按完全二叉树的存储结构,,
? 删除此完全二叉树的根结点并输出,该结点关键字的值一定是最大,或最小,的,
? 针对第?步操作的剩余结点组成的子序列，将其重新构造成一个新的大根堆,
? 重复?、?的操作，直到删除输出所有的结点，由此得到的输出序列一定是有序序列。
主要操作:建立初始堆、重构堆
* 初始堆的构造
若完全二叉树是堆?则其所有子树均应是堆.
由于叶结点为根的子树一定是堆，因此构造堆可从倒数第一的内结点为根的子树开始逐步将其构造成堆，直到将树根结点为根的整个子树构造成堆为止。
? 若某子树已是堆,则无须重新构造;
3
? 若某子树还不是堆,则需调整结点的位置,使其成为堆;
用根结点的关键字与左、右孩子的关键字进行比较，如果根结点的大，说明其位置正确，则不调整,否则让根结点与左、右孩子中大的一个交换，交换后再从新的位置继续上述比较调整，直到位置正确或调整到叶结点为止。
* 堆的重构
原理与初始建堆子树的构造相同
* 实例解析
例a[]:0 1 2 3 4 5 6 7 8
24 10 90 77 16 25 33 89 67
? 构造初始堆(大根堆,
0 1 2 3 4 5 6 7 8
90 89 33 77 16 25 24 10 67
? 删除根,放在
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
尾,
? 重构堆
0 1 2 3 4 5 6 7 8
89 77 33 67 16 25 24 10 90
结果:0 1 2 3 4 5 6 7 8
10 16 24 25 33 67 77 89 90
1.4. 算法分析
时间复杂度:;(n*log2n)
空间复杂度:;,,,
4
稳 定 性:不稳定排序
1.5.算法流程
输入20个以内的正整数
将输入的数据存入数组，形成堆的初始状态
创建堆并重构，使得满足大根堆定义
大根堆排序，反复调用重构堆函数
输出堆排序后的结
果 1.6.算法程序
#include "stdio.h"
#include "stdlib.h"
int i,n;
int a[20];
typedef int DataType;
/*5.调用输出函数输出数组中的结果排序值*/
void PrintHeap(DataType a[],int n) {
int i;
printf("\nThe OriginHeap is:\n");
for(i=0;i
a[j])
flag=1;
else
{
a[i]=a[j];
i=j;
j=2*i+1;
}
}
a[i]=temp;
}
/*2.调用初始堆构造函数*/
void InitCreatHeap(DataType a[],int n)
{
int i;
for(i=(n-2)/2;i>=0;i--)
{
CreatHeap(a,n,i);
if(i==0) PrintHeap(a,n);
}
}
/*4.调用堆排序函数进行堆排序，结果仍在数组中*/ void HeapSort(DataType a[],int n)
{
int i;
DataType temp;
InitCreatHeap(a,n);
printf("\n");
for(i=n-1;i>0;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
CreatHeap(a,i,0);
}
}
6
/*1.输入一组正整数关键字,20个以内，以-1结束,,将输入数据存入数组*/ main()
{
printf("Please enter some integer , ended by -1 . \n");
for(i=0;i<20;i++)
{
scanf("%d",&a[i]);
if(a[i]==-1)
{
n=i;
break;
}
else if(a[i]<=0)
{
printf("Number must >0.\n");
i--;
}
if(i==19)
{
printf("Touch the Max.\n");
n=20;
break;
}
}
printf("The number you entered are:\n");
for(i=0;idata.key==item.key) return 1;
if(item.key>p->data.key) p=p->rightChild;
else p = p->leftChild;
}
}
return 0;
}
if(num==1)/**/
{
for(i=0;idata.key==item.key) return 0; /*数据元素已 if(current-
存在*/
parent=current;
if(current->data.keyrightChild;
else current=current->leftChild;
}
p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
if(p==NULL)
{
printf("Lack of space!");
exit(1);
}
p->data=item;
p->leftChild=NULL;
p->rightChild=NULL;
12
if(parent==NULL) *root=p;
else if(item.keydata.key) parent->leftChild=p;
else parent->rightChild=p;
return 1;
}
/*插入数组*/
void InsertN()
{
for(i=0;i<20;i++)
{
scanf("%d",&a[i]);
if(a[i].key==-1)
/*判断是否非数字*/
{
n=i;
break;
}
else if(a[i].key<=0)
{
printf("Number must >0.\n");
i--;
13
}
if(i==19)
{
printf("Touch the Max.\n");
n=20;
break;
}
}
printf("\nThe number you entered are:\n");
for(i=0;ileftChild!=NULL) InTraverse(root->leftChild);
printf("%d ",root->data.key);
if(root->rightChild!=NULL) InTraverse(root->rightChild);
}
/*y删除*/ /*删除
数组中a[i]往后的元素 重建二叉树 实现删除*/
BiTreeNode *Destroy(BiTreeNode *bt,DataType item) {
BiTreeNode *p,*q;
if(bt->data.key==item.key)
{
if(bt->leftChild==NULL&&bt->rightChild==NULL)
{
free(bt);
return NULL;
}
else if(bt->rightChild==NULL)
{
p=bt->leftChild;
free(bt);
return p;
}
15
else if(bt->leftChild==NULL)
{
p=bt->rightChild;
free(bt);
return p;
}
else
{
p=q=bt->rightChild;
while(p->leftChild!=NULL) p=p->leftChild;
p->leftChild=bt->leftChild;
free(bt);
return q;
}
}
if(bt->data.key>item.key&&bt->leftChild!=NULL)
bt->leftChild=Destroy(bt->leftChild,item.key);
if(bt->data.keyrightChild!=NULL)
bt->rightChild=Destroy(bt->rightChild,item.key);
return bt;
}
16
/*打印二叉树*/
void PrintBiTree(BiTreeNode *bt,int n) {
if(bt==NULL)return;
PrintBiTree(bt->rightChild,n+1); for(i=0;i=0)
{
printf("---");
printf("%d\n",bt->data);
}
PrintBiTree(bt->leftChild,n+1); }
/*主函数*/
void main()
{
int d,m,t=0;
do
{
printf("\n");
printf(" 1. Insert\n");
17
printf(" 2. Search\n");
printf(" 3. Destroy\n");
printf(" 4. Print\n");
printf(" 5. InTraverse\n");
printf(" 6. Exit!\n\n");
printf("Input command number:\n");
scanf("%d",&d);
switch(d)
{
case 1: InsertN(); break;
case 2:
{
printf("\n Search number:\n");
scanf("%d",&item.key);
m=Search(root,item);
if(m==1)
printf("\n Element exists!\n");
else
printf("\n Didn't find it!\n");
break;
}
case 3:
18
{
printf("Destroy number:\n");
scanf("%d",&item.key);
Destroy(root,item);
break;
}
case 4: PrintBiTree(root,0); break;
case 5: InTraverse(root); break;
case 6: t=1; break;
default: printf("The number should between 1 and 6.\n");
}
} while(!t);
}
19
浙公网安备 33021202002483