數據結構實驗之修理牧場
- 2020 年 5 月 24 日
- 筆記
數據結構與算法實驗報告
修理牧場
姓名：孫瑞霜
一、實驗目的
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,然後將代碼粘貼到上面，先編譯看是否編譯成功，再根據下面測試的數據將代碼運行後依次填入，便能得出相應的結果，當然也可以嘗試用其他測試數據來測驗一下，看看最後結果如何。
