公告:本站提供编程开发方面的技术交流与分享,打造最佳教程网,希望能为您排忧解难!

C语言教程数据结构C语言实现系列[6]——堆

数据结构C语言实现系列[6]——堆

更新时间:2013-04-02 12:31:26 |
#include <stdio.h>
#include <stdlib.h>

typedef int elemType;
/************************************************************************/
/*                    以下是关于堆顺序存储操作的5种算法                 */
/************************************************************************/
/* 定义堆的顺序存储类型 */
struct heap{
    elemType 
*heap;        /* 定义指向动态数组空间的指针 */
    int len;            /* 定义保存堆长度的变量 */
    int maxSize;        /* 用于保存初始化时所给的动态数组空间的大小 */
};


/* 1.初始化堆 */
void initHeap(struct heap *hbt, int ms)
{
    
/* 检查ms的值是否有效 */
    if (ms <= 0){
        printf(
"数组长度参数非法!");
        exit(
1);
    }
    
    
/* 动态分配存储的数组空间 */
    hbt->heap = malloc(ms * sizeof(elemType));
    
    
if (hbt->heap == NULL){
        printf(
"空间分配失败!");
        exit(
1);
    }

    
/* 设置maxSize域和len域的值 */
    hbt->maxSize = ms;
    hbt
->len = 0;

    
return;
}


/* 2.清除堆 */
void clearHeap(struct heap *hbt)
{
    
if (hbt->heap != NULL){
        free(hbt
->heap);
        hbt
->heap = NULL;
        hbt
->len = 0;
        hbt
->maxSize = 0;
    }

    
return;
}


/* 3.检查一个堆是否为空 */
int emptyHeap(struct heap *hbt)
{
    
if (0 == hbt->len){
        
return 1;
    }
else{
        
return 0;
    }
}


/* 4.向堆中插入一个元素 */
void insertHeap(struct heap *hbt, elemType x)
{
    
int i;
    
/* 堆满时数组空间扩展为原来的2倍,
       原内容被自动拷贝到p所指向的存储空间中
*/
    if (hbt->len == hbt->maxSize){
        elemType 
*p;
        p 
= realloc(hbt->heap, 2 * hbt->maxSize * sizeof(elemType));
        
if (p == NULL){
            printf(
"存储空间分配失败!");
            exit(
1);
        }

        hbt
->heap = p;        /* 堆数组空间指向新空间 */
        hbt->maxSize = 2 * hbt->maxSize;        /* 修改数组空间的大小 */
    }

    
/* 向堆尾添加新元素 */
    hbt->heap[hbt->len] = x;
    hbt
->len++;

    
/* 用i指向待调整元素的位置,初始指向新元素所在的堆尾位置 */
    i = hbt->len - 1;

    
/* 寻找新元素的最终位置,每次使双亲元素下移一层 */
    while (0 != i){
        
int j = (i - 1/ 2;        /* j指向下标为i的元素的双亲 */
        /* 比较调整结束退出循环 */
        if (x >= hbt->heap[j]){        
            
break;
        }
        hbt
->heap[i] = hbt->heap[j];        /* 双亲元素下移 */
        i = j;
    }
    hbt
->heap[i] = x;        /* 把新元素调整到最终位置 */

    return;
}


/* 5.从堆中删除元素 */
elemType deleteHeap(struct heap *hbt)
{
    elemType temp, x;
    
int i, j;
    
    
/* 若为空堆,则显示出错信息并退出运行 */
    if (0 == hbt->len){
        printf(
"堆已空,退出运行!");
        exit(
1);
    }
    
    
/* 将堆顶元素暂存在temp中以便返回 */
    temp = hbt->heap[0];
    hbt
->len--;

    
/* 若删除操作后变为空堆则返回 */
    if (0 == hbt->len){
        
return temp;
    }

    
/* 将待调整的堆尾元素暂存在x中,以便放入最终位置 */
    x = hbt->heap[hbt->len];
    
/* 用i指向待调整元素的位置,初始指向堆顶位置 */
    i = 0;
    
/* 用j指向i的左孩子位置,初始指向下标1的位置 */
    j = 2 * i + 1;
    
/* 寻找待调整元素的最终位置,每次使孩子元素上移一层 */
    while (j <= hbt->len - 1){        /* 调整到孩子为空时止 */
        /* 若右孩子存在并且较小,应使j指向右孩子 */
        if ((j < hbt->len - 1&& (hbt->heap[j] > hbt->heap[j+1])){
            j
++;
        }
        
/* 若条件成立则调整结束,退出循环 */
        if (x <= hbt->heap[j]){
            
break;
        }
        
/* 孩子元素上移到双亲位置 */
        hbt->heap[i] = hbt->heap[j];
        
/* 使i和j分别指向下一层结点 */
        i = j;
        j 
= 2 * i + 1;
    }
    
/* 把待调整元素放到最终位置 */
    hbt->heap[i] = x;
    
    
return temp;
}


/************************************************************************/

int main(void)
{
    
int i, x;
    
int a[8= {2356406238551016};
    
struct heap b;

    initHeap(
&b, 5);
    
/* 向堆b中依次插入数组a中的每一个元素 */
    for (i = 0; i < 8; i++){
        insertHeap(
&b, a[i]);
    }

    
while (!emptyHeap(&b)){
        x 
= deleteHeap(&b);
        printf(
"%d", x);
        
if (!emptyHeap(&b)){
            printf(
",");
        }
    }

    printf(
"");
    clearHeap(
&b);

    
return 0;
}
最佳教程网

最大的技术交流平台 www.goodxyx.com© CopyRight 2011-2013, All Rights Reserved

浙ICP备11033019号