数据结构习题——判断一个数据序列是否构成一个小根堆/编写简单选择排序的单链表版

前言

关于选择排序

正文

题目一

判断一个数据序列是否构成一个小根堆
前提需知，一个“堆”是一颗“完全二叉树”（编号从1…n的完全二叉树存储结构的数列）
故利用以下性质解题：

1. 当i>1时，结点i的双亲结点为i/2（向下取整）
2. 当2i<=n时，结点i的左孩子编号为2i
3. 当2i+1<=n时，结点i的右孩子编号为2i+1

判断是否为小根堆，只要满足双亲结点的左右孩子均小于该结点即可。

//数组a[1...n]
bool judge(int a[],int n){
if(n%2==0){
//len为偶数，有一个单分支
for(A[n/2]>A[n])//判断单分支
return false;
for(i=n/2-1;i>=0;i--)//判断所有双分支
if(A[i]>A[2*i]||A[i]>A[2*i+1])
return false;
}
else{
for(i=len/2;i>=0;i--){//len为奇数，没有单分支结点
if(A[i]>A[2*i]||A[i]>A[2*i+1])//判断所有双分支结点
return false;
}
}
return true;
}

题目二

编写简单选择排序的单链表版（不带头结点）

void sort(linklist *L){
linkNode * p,*pre,*max,*maxpre;
linlist *h=L;
L=NULL;
while(h!=NULL){
//持续扫描原链表
p=max=h;pre=maxpre=NULL;
while(p!=NULL){
if(p->data>max->data){
//找到更大的，记忆它和它的前驱
max=p;
maxpre=pre;
}
pre=p;
//继续寻找
p=p->next;
}
if(s==h)
//最大结点在原链表前段
h=h->next;
else
maxpre->next=max->next;//最大结点在原链表内
max->next=L;//头插	
L=max;
}
}

最后

以上就是怡然白昼为你收集整理的数据结构习题——判断一个数据序列是否构成一个小根堆/编写简单选择排序的单链表版的全部内容，希望文章能够帮你解决数据结构习题——判断一个数据序列是否构成一个小根堆/编写简单选择排序的单链表版所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。