数据结构实验之修理牧场

数据结构与算法实验报告

修理牧场

      姓名: 孙瑞霜  

一、实验目的

1、熟练掌握学习的每种结构及其相应算法;

2、理论联系实际,会对现实问题建模并设计相应算法。

3、优化算法,使得算法效率适当提高

二、 实验要求

1. 认真阅读和掌握教材上和本实验相关的内容和算法;

2. 上机将各种相关算法实现;

3. 实现上面实验目的要求的功能,并能进行简单的验证。

、实验内容

认真学习 学习通->数据结构->资料->数据结构实验指导书--陈越版,从第二章进阶实验1~10中任选一个来实现,编写程序,输入给定的数据,能得到给定的输出。总结算法思想、画出流程图,并思考程序有无改进空间,如何改进。

三、算法描述

(采用自然语言描述)   

选择了修理牧场

改进后方法二:我们将木头的长度看成树的节点,每切割一次木头就相当与把节点分为两个子节点,每个节点的权值就相当于分的的木头长度。那么最后这棵树的总权值就相当于切割的代价。问题就变成求这棵树的最小权值,这不就是Hoffman树的作用嘛。所以这道题目就变成了求一棵Hoffman树的权值。(选用两种方法)

四、详细设计

(画出程序流程图)

五、程序代码

(给出必要注释)

(方法一)复杂代码

#include<stdio.h>

#include<stdlib.h>

#define MinData 0

//#define M 10000

#define MaxData 100

typedef struct TreeNode *HuffmanTree;

struct TreeNode{

//char Data;

int Weight;

HuffmanTree Left;

HuffmanTree Right;

};

typedef HuffmanTree ElementType;

typedef  struct  HeapStruct  *MinHeap;

struct  HeapStruct {

ElementType *Elements; /* 存储堆元素的数组 */

int Size; /* 堆的当前元素个数 */

int Capacity; /* 堆的最大容量   */

};

// 函数声明

MinHeap Create( int MinSize );

void Insert( MinHeap H, ElementType item );

ElementType DeleteMin( MinHeap H );

MinHeap BuildMinHeap( MinHeap H );

int IsFull( MinHeap H );

int IsEmpty( MinHeap H );

void printfHeap( MinHeap H);

HuffmanTree Huffman( MinHeap H );

int PreOrderTraversal( HuffmanTree H,int sum );

MinHeap Create( int MaxSize )

{   /* 创建容量为 MinSize 的空的最小堆 */

HuffmanTree ht0;

MinHeap H =( MinHeap)malloc( sizeof( struct HeapStruct ) );

H->Elements =( ElementType *) malloc( (MaxSize+1) * sizeof( ElementType ) );

H->Size = 0;

H->Capacity =MaxSize;

/* 定义 " 哨兵 " 为小于堆中所有可能元素的值 */

ht0 = (HuffmanTree)malloc( sizeof( struct TreeNode) );

ht0->Left = NULL;

ht0->Right = NULL;

ht0->Weight = 0;

H->Elements[0] = ht0;

return H;

}

void printfHeap( MinHeap H)

{   

int i;

for(i=1;i<=H->Size;i++)

printf("%d ",H->Elements[i]->Weight);

}

void Insert( MinHeap H, ElementType item )

{ /* 将元素 item 插入最小堆 H ,其中 H->Elements[0] 已经定义为哨兵 */

int i;

HuffmanTree hti;

if ( IsFull(H) ) {

printf(" 最小堆已满 ");

return;

}

hti = (HuffmanTree)malloc( sizeof( struct TreeNode) );

hti->Left = item->Left;

hti->Right =  item->Right;

hti->Weight = item->Weight;

i = ++H->Size; /* i 指向插入后堆中的最后一个元素的位置 */

for ( ; H->Elements[i/2]->Weight > item->Weight; i/=2 )

H->Elements[i] = H->Elements[i/2]; /* 向下过滤结点 */

H->Elements[i] = hti; /* item 插入 */

}

ElementType DeleteMin( MinHeap H )

{   /* 从最大堆 H 中取出键值为最大的元素,并删除一个结点 */

int Parent, Child;

ElementType MinItem, temp;

if ( IsEmpty(H) ) {

printf(" 最大堆已为空 ");

return H->Elements[0];

}

MinItem = H->Elements[1]; /* 取出根结点最小值 */

/* 用最小堆中最后一个元素从根结点开始向上过滤下层结点 */

temp = H->Elements[H->Size--];

for( Parent=1; Parent*2<=H->Size; Parent=Child ) {

Child = Parent * 2;

if( (Child!= H->Size) && (H->Elements[Child]->Weight > H->Elements[Child+1]->Weight) )

Child++;  /* Child 指向左右子结点的较小者 */

if( temp->Weight <= H->Elements[Child]->Weight ) break;

else  /* 移动 temp 元素到下一层 */

H->Elements[Parent] = H->Elements[Child];

}

H->Elements[Parent] = temp;

return MinItem;

}

MinHeap BuildMinHeap( MinHeap H )

{   /* 这里假设所有 H->Size 个元素已经存在 H->Elements[] 中      */

/* 本函数将 H->Elements[] 中的元素调整,使满足最小堆的有序性 */

int Parent, Child, i;

ElementType temp;

for( i = H->Size/2; i>0; i-- ){ /* 从最后一个结点的父结点开始 */

temp = H->Elements[i];

for( Parent=i; Parent*2<=H->Size; Parent=Child ) { /* 向下过滤 */

Child = Parent * 2;

if( (Child!= H->Size) && (H->Elements[Child]->Weight > H->Elements[Child+1]->Weight) )

Child++;  /* Child 指向左右子结点的较小者 */

if( temp->Weight <= H->Elements[Child]->Weight ) break;

else  /* 移动 temp 元素到下一层 */

H->Elements[Parent] = H->Elements[Child];

} /* 结束内部 for 循环对以 H->Elements[i] 为根的子树的调整 */

H->Elements[Parent] = temp;

}

return H;

}

int IsFull( MinHeap H )

{

if(H->Size == H->Capacity -1)

return 1;

else

return 0;

}

int IsEmpty( MinHeap H )

{

if(H->Size == 0)

return 1;

else

return 0;

}

int main()

{

MinHeap h1;

int i;

int num;

HuffmanTree ht;

int M;

scanf("%d",&M);

h1=Create(M);

//printf(" 请输入序列: \n");

for(i=1;i<=M;i++)

{

scanf(" %d",&num);

ht = (HuffmanTree)malloc( sizeof( struct TreeNode) );

ht ->Left = NULL;

ht->Right = NULL;

ht->Weight = num;

h1->Elements[i]=ht;

h1->Size++;

}

ht=Huffman(h1);

printf("%d\n",PreOrderTraversal(ht,0));

}

HuffmanTree Huffman( MinHeap H )

{   /* 假设根据 H->Size 个权值所生成的跟结点已经存在 H->Elements[] */

int i,m;

HuffmanTree  T;

BuildMinHeap(H); /* H->Elements[] 按权值调整为最小堆 */

m=H->Size;

for (i = 1; i < m; i++) { /* H->Size -1 次合并 */

T = (HuffmanTree)malloc( sizeof( struct TreeNode) ); /* 建立一个新的根结点 */       

T->Left = DeleteMin(H);/* 从最小堆中删除一个结点,作为新 T 的左子结点 */        

T->Right = DeleteMin(H); /* 从最小堆中删除一个结点,作为新 T 的右子结点 */       

T->Weight = T->Left->Weight+T->Right->Weight; /* 计算新权值 */

Insert( H, T ); /* 将新 T 插入最小堆 */

}

T=DeleteMin(H);// 取合并后的树根

return T;

}

// 递归先序求哈夫曼树的非叶子结点的权重和

int PreOrderTraversal(HuffmanTree T,int sum)

{

if(T)

{

if(T->Left&&T->Right)

sum+=T->Weight;

sum= PreOrderTraversal(T->Left,sum);

sum=PreOrderTraversal(T->Right,sum);

}

return sum;

}

(方法二)优化后代码

#include<stdio.h>

#define swap(a,b) a=a^b,b=a^b,a=a^b

int tail=0;     // 堆的最后一个元素的下一个位置

void Insert(int *length,int temp);

int GetHeap(int *length);

int Solve(int *length);

int main(void)

{

int N;

int i;

scanf("%d",&N);

int length[N];

int temp;

for(i=0;i<N;i++){

scanf("%d",&temp);

Insert(length,temp);      // 构造一个小顶堆

}

printf("%d",Solve(length));

return 0;

}

void Insert(int *length,int temp)

{

int son,father;

son=tail;

length[tail++]=temp;

father=(son+(son&1))/2-1;

if(!son)

return ;

while(length[son]<length[father]&&father>=0){

swap(length[son],length[father]);    // 交换两节点位置

son=father;

father=(father+(father&1))/2-1;

}

return ;

}

int GetHeap(int *length)

{

int result=length[0];

int father=0;

int son=1;

length[0]=length[--tail];

while(son<tail){

if(length[son]>length[son+1])

son++;                      // 如果左孩子节点的数值更大

if(length[father]>length[son]){

swap(length[father],length[son]);

father=son;

son=2*son+1;

}

else

break;

}

return result;

}

int Solve(int *length)

{

int min1,min2;

int result=0;

if(tail==1)

return 0;

while(1!=tail){

min1=GetHeap(length);

min2=GetHeap(length);   // 找打最小的两块板子

result+=min1+min2;      // 将其合为一块板子

Insert(length,min1+min2);     // 继续排序

}

return result;

}

六、测试和结果

(给出测试用例以及测试结果)

输入样例 :

8

4 5 1 2 1 3 1 1

输出样例 :49

 

七、用户手册

首先打开 Dev, 然后将代码粘贴到上面,先编译看是否编译成功,再根据下面测试的数据将代码运行后依次填入,便能得出相应的结果,当然也可以尝试用其他测试数据来测验一下,看看最后结果如何。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章