#include"iostream"#include "queue"#include "map"#include "string"#include "iterator"#include "vector"#include "algorithm"using namespace std;#define NChar 8	//suppose use 8 bits to describe all symbols#define Nsymbols 1<<NChar	//can describe 256 symbols totally (include a-z, A-Z)typedef vector<bool> Huff_code;//8 bit code of one charmap<char,Huff_code> Huff_Dic;	//huffman coding dictionary/************************************************************************//* Tree Class elements:*2 child trees*character and frequency of current node*//************************************************************************/class HTree{public :	HTree* left;	HTree* right;	char ch;	int weight;	HTree(){left = right = NULL; weight=0;ch =‘\0‘;}	HTree(HTree* l,HTree* r,int w,char c){left = l;	right = r;	weight=w;	ch=c;}	~HTree(){delete left; delete right;}	bool Isleaf(){return !left && !right; }};/************************************************************************//* prepare for pointer sorting*//*because we cannot use overloading in class HTree directly*//************************************************************************/class Compare_tree{public:	bool operator () (HTree* t1, HTree* t2)	{		return t1->weight> t2->weight;	}};/************************************************************************//* use priority queue to build huffman tree*//************************************************************************/HTree* BuildTree(int *frequency){	priority_queue<HTree*,vector<HTree*>,Compare_tree> QTree;	//1st level add characters	for (int i=0;i<Nsymbols;i++)	{		if(frequency[i])			QTree.push(new HTree(NULL,NULL,frequency[i],(char)i));				}	//build	while (QTree.size()>1)	{		HTree* lc  = QTree.top();		QTree.pop();		HTree* rc = QTree.top();		QTree.pop();		HTree* parent = new HTree(lc,rc,lc->weight+rc->weight,(char)256);		QTree.push(parent);	}	//return tree root	return QTree.top();}/************************************************************************//* Give Huffman Coding to the Huffman Tree*//************************************************************************/void Huffman_Coding(HTree* root, Huff_code& curcode){	if(root->Isleaf())	{		Huff_Dic[root->ch] = curcode;		return;	}	Huff_code lcode = curcode;	Huff_code rcode = curcode;		lcode.push_back(false);	rcode.push_back(true);	Huffman_Coding(root->left,lcode);	Huffman_Coding(root->right,rcode);}int main(){	int freq[Nsymbols] = {0};	char *str = "this is the string need to be compressed";	//statistic character frequency	while (*str!=‘\0‘)		freq[*str++]++;	//build tree	HTree* r = BuildTree(freq);	Huff_code nullcode;	nullcode.clear();	Huffman_Coding(r,nullcode);	for(map<char,Huff_code>::iterator it = Huff_Dic.begin(); it != Huff_Dic.end(); it++)	{		cout<<(*it).first<<‘\t‘;		std::copy(it->second.begin(),it->second.end(),std::ostream_iterator<bool>(cout));		cout<<endl;	}}

/************************************************************************//*	File Name: LZW.cpp*		@Function: Lossless Compression		@Author: Sophia Zhang 		@Create Time: 2012-9-19 10:00		@Last Modify: 2012-9-19 11:10*//************************************************************************/#include"iostream"#include "map"#include "string"#include "iterator"#include "vector"using namespace std;/************************************************************************//*	Compress Module*		input: 			str - the string need to be compressed			result - compress result*//************************************************************************/template<typename TypeIterator>TypeIterator Compress(string str, TypeIterator result){	//Build the dictionary	map<string,int>dictionary;	int Dictsize=256;	for(int i=0;i<Dictsize;i++)		dictionary[string(1,i)]=i;	char z;	string S;	for(string::const_iterator it = str.begin(); it!=str.end(); it++)	{		 z = *it;				 if(dictionary.count(S+z))//can find S			 S+=z;		 else//S is not in dictionary D		 {			 *result++ = dictionary[S];	//output pointer (S,D)			 dictionary[S+z] = Dictsize++; //add to dictionary			 S = z;		 }	}	if(!S.empty())		*result++ = dictionary[S];	return result;}/************************************************************************//*	Decompress Module*		input: 			TypeIterator result - compression result, to be decompressed*//************************************************************************/template<typename TypeIterator>string Decompress(TypeIterator result){	map<int,string>inv_dictionary;	int Dictsize=256;	for(int i=0;i<Dictsize;i++)		inv_dictionary[i] = string(1,i);	char z;	string S;	string entry;	string res;	Dictsize--;//because the first "Dictsize++" make no sense, it has only one char in [0,255]	for(TypeIterator::iterator it = result.begin(); it!=result.end(); it++)	{		int k = *it;		if(inv_dictionary.count(k))			entry = inv_dictionary[k];			else if(k==Dictsize)			entry = S+ S[0];//???		else			throw "Bad compression code";		res += entry;				inv_dictionary[Dictsize++] = S + entry[0];		S = entry;		}	return res;}int main(){	typedef vector<int> TypeIterator;	TypeIterator compress_res;	string S = "the/rain/in/Spain/falls/mainly/on/the/plain";	Compress(S,std::back_inserter(compress_res));// 	copy(compress_res.begin(),compress_res.end(),std::ostream_iterator<int>(std::cout,","));// 	std::cout<<std::endl;	//output the compressed result	for( TypeIterator::iterator it= compress_res.begin(); it!=compress_res.end(); it++)		cout<<(*it)<<endl;	//decompress the compressed result	string decompress = Decompress(compress_res);	cout<<decompress<<endl;}

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<climits>using namespace std; typedef struct BinHeapNode BinNode;typedef struct BinHeapNode * BinHeap;typedef struct BinHeapNode * Position; //结点ADTstruct BinHeapNode {    int key;    int degree;    Position parent;    Position leftChild;    Position sibling;}; //用数组内的值建堆BinHeap MakeBinHeapWithArray(int keys[], int n); //两个堆合并BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2); //将H1, H2的根表合并成一个按度数的单调递增次序排列的链表BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2); //使H2成为H1的父节点void BinLink(BinHeap &H1, BinHeap &H2); //返回最小根节点的指针BinHeap BinHeapMin(BinHeap heap); //减少关键字的值void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key); //删除一个关键字BinHeap BinHeapDelete(BinHeap &heap, int key); //找出一个关键字BinHeap BinHeapFind(BinHeap &heap, int key); //打印输出堆结构void PrintBinHeap(BinHeap heap); //销毁堆void DestroyBinHeap(BinHeap &heap); //用数组内的值建堆BinHeap MakeBinHeapWithArray(int keys[], int n) {    BinHeap heap = NULL, newHeap = NULL;    for (int i = 0; i < n; i++) {        newHeap = (BinHeap) malloc(sizeof(BinNode));                if (newHeap == NULL) {            puts("Out of the Space");            exit(1);        }        memset(newHeap, 0, sizeof(BinNode));        newHeap->key = keys[i];        if (NULL == heap) {            heap = newHeap;        } else {            heap = BinHeapUnion(heap, newHeap);            newHeap = NULL;        }    }    return heap;} //两个堆合并BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2) {    Position heap = NULL, pre_x = NULL, x = NULL, next_x = NULL;    heap = BinHeapMerge(H1, H2);    if (heap == NULL) {        return heap;    }     pre_x = NULL;    x = heap;    next_x = x->sibling;     while (next_x != NULL) {        if ((x->degree != next_x->degree) ||//Cases 1 and 2            ((next_x->sibling != NULL) && (next_x->degree == next_x->sibling->degree))) {                pre_x = x;                x = next_x;        } else if (x->key <= next_x->key) {//Cases 3            x->sibling = next_x->sibling;            BinLink(next_x, x);        } else {//Cases 4            if (pre_x == NULL) {                heap = next_x;            } else {                pre_x->sibling = next_x;            }            BinLink(x, next_x);            x = next_x;        }        next_x = x->sibling;    }    return heap;} //将H1, H2的根表合并成一个按度数的单调递增次序排列的链表BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2) {    //heap->堆的首地址，H3为指向新堆根结点    BinHeap heap = NULL, firstHeap = NULL, secondHeap = NULL,        pre_H3 = NULL, H3 = NULL;     if (H1 != NULL && H2 != NULL){        firstHeap = H1;        secondHeap = H2;        //整个while，firstHeap, secondHeap, pre_H3, H3都在往后顺移        while (firstHeap != NULL && secondHeap != NULL) {            if (firstHeap->degree <= secondHeap->degree) {                H3 = firstHeap;                firstHeap = firstHeap->sibling;            } else {                H3 = secondHeap;                secondHeap = secondHeap->sibling;            }             if (pre_H3 == NULL) {                pre_H3 = H3;                heap = H3;            } else {                pre_H3->sibling = H3;                pre_H3 = H3;            }            if (firstHeap != NULL) {                H3->sibling = firstHeap;            } else {                H3->sibling = secondHeap;            }        }//while    } else if (H1 != NULL) {        heap = H1;    } else {        heap = H2;    }    H1 = H2 = NULL;    return heap;} //使H2成为H1的父节点void BinLink(BinHeap &H1, BinHeap &H2) {    H1->parent = H2;    H1->sibling = H2->leftChild;    H2->leftChild = H1;    H2->degree++;} //返回最小根节点的指针BinHeap BinHeapMin(BinHeap heap) {    Position y = NULL, x = heap;    int min = INT_MAX;     while (x != NULL) {        if (x->key < min) {            min = x->key;            y = x;        }        x = x->sibling;    }    return y;} //抽取有最小关键字的结点BinHeap BinHeapExtractMin(BinHeap &heap) {    BinHeap pre_y = NULL, y = NULL, x = heap;    int min = INT_MAX;    while (x != NULL) {        if (x->key < min) {            min = x->key;            pre_y = y;            y = x;        }        x = x->sibling;    }     if (y == NULL) {        return NULL;    }     if (pre_y == NULL) {        heap = heap->sibling;    } else {        pre_y->sibling = y->sibling;    }     //将y的子结点指针reverse    BinHeap H2 = NULL, p = NULL;    x = y->leftChild;    while (x != NULL) {        p = x;        x = x->sibling;        p->sibling = H2;        H2 = p;        p->parent = NULL;    }     heap = BinHeapUnion(heap, H2);    return y;} //减少关键字的值void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key) {    if(key > x->key) {        puts("new key is greaer than current key");        exit(1); //不为降键    }    x->key = key;     BinHeap z = NULL, y = NULL;    y = x;    z = x->parent;    while(z != NULL && z->key > y->key) {        swap(z->key, y->key);        y = z;        z = y->parent;    }} //删除一个关键字BinHeap BinHeapDelete(BinHeap &heap, int key) {    BinHeap x = NULL;    x = BinHeapFind(heap, key);    if (x != NULL) {        BinHeapDecreaseKey(heap, x, INT_MIN);        return BinHeapExtractMin(heap);    }    return x;} //找出一个关键字BinHeap BinHeapFind(BinHeap &heap, int key) {    Position p = NULL, x = NULL;    p = heap;    while (p != NULL) {        if (p->key == key) {            return p;        } else {            if((x =BinHeapFind(p->leftChild, key)) != NULL) {                return x;            }            p = p->sibling;        }    }    return NULL;} //打印输出堆结构void PrintBinHeap(BinHeap heap) {    if (NULL == heap) {        return ;    }    Position p = heap;     while (p != NULL) {        printf(" (");        printf("%d", p->key);        //显示其孩子        if(NULL != p->leftChild) {            PrintBinHeap(p->leftChild);        }        printf(") ");         p = p->sibling;    }}        int kp1[8] = {12,               7, 25,              15, 28, 33, 41}; int kp2[20] = {18,                3, 37,                6, 8, 29, 10, 44, 30, 23, 2, 48, 31, 17, 45, 32, 24, 50, 55}; int kp4[23] = {37, 41,               10, 28, 13, 77,               1, 6, 16, 12, 25, 8, 14, 29, 26, 23, 18, 11, 17, 38, 42, 27};int main() {    BinHeap H1 = NULL;    H1 = MakeBinHeapWithArray(kp1, 7);    puts("第一个二叉堆H1:");    PrintBinHeap(H1);     BinHeap H2 = NULL;    H2 = MakeBinHeapWithArray(kp2, 19);    puts("\n\n第二个二叉堆H2:");    PrintBinHeap(H2);     BinHeap H3 = NULL;    H3 = BinHeapUnion(H1, H2);    puts("\n\n合并H1,H2后，得到H3:");    PrintBinHeap(H3);     BinHeap H4 = NULL;    H4 = MakeBinHeapWithArray(kp4, 22);    puts("\n\n用于测试提取和删除的二叉堆H4:");    PrintBinHeap(H4);     BinHeap extractNode = BinHeapExtractMin(H4);    if (extractNode != NULL) {        printf("\n\n抽取最小的值%d后：\n", extractNode->key);        PrintBinHeap(H4);    }     extractNode = BinHeapExtractMin(H4);    if (extractNode != NULL) {        printf("\n\n抽取最小的值%d后：\n", extractNode->key);        PrintBinHeap(H4);    }     extractNode = BinHeapExtractMin(H4);    if (extractNode != NULL) {        printf("\n\n抽取最小的值%d后：\n", extractNode->key);        PrintBinHeap(H4);    }     BinHeapDelete(H4, 12);    puts("\n\n删除12后：");    PrintBinHeap(H4);    return 0;}

#include <stdlib.h>typedef struct PairingHeapNode{	int							key;	struct	PairingHeapNode*	child;	struct	PairingHeapNode*	sibling;	struct	PairingHeapNode*	prev;}PairHeap;static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q);static PairHeap* combine_siblings(PairHeap *p);PairHeap* PairHeap_insert(PairHeap *p, int key){	PairHeap *node;	node = (PairHeap*)malloc(sizeof(*node));	if(node == NULL)		return NULL;	node->key = key;	node->child = node->sibling = node->prev = NULL;	if(p == NULL)		return node;	else		return merge_subheaps(p, node);}PairHeap* PairHeap_DecreaseKey(PairHeap *p, PairHeap *pos, int d){	if(d < 0)		return p;	pos->key = pos->key - d;	if(p == pos)		return p;	if(pos->sibling != NULL)		pos->sibling->prev = pos->prev;	if(pos->prev->child = pos)		pos->prev->child = pos->sibling;	else		pos->prev->sibling = p->sibling;	p->sibling = NULL;	return merge_subheaps(p, pos);}PairHeap* PairHeap_DeleteMin(int *key, PairHeap *p){	PairHeap *new_root;	if(p == NULL)		return NULL;	else	{		*key = p->key;		if(p->child != NULL)			new_root = combine_siblings(p->child);		free(p);	}	return new_root;}static PairHeap* combine_siblings(PairHeap *p){	PairHeap *tree_array[1024];	int i, count;	if(p->sibling == NULL)		return p;	for(count = 0; p != NULL; count++)	{		tree_array[count] = p;		p->prev->sibling = NULL;		p = p->sibling;	}	tree_array[count] = NULL;	for(i = 1; i < count; i++)		tree_array[i] = merge_subheaps(tree_array[i-1], tree_array[i]);	return tree_array[count-1];}static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q){	if(q == NULL)		return p;	else if(p->key <= q->key)	{		q->prev = p;		p->sibling = q->sibling;		if(p->sibling != NULL)			p->sibling->prev = p;		q->sibling = p->child;		if(q->sibling != NULL)			q->sibling->prev = q;		p->child = q;		return p;	}	else	{		q->prev = p->prev;		p->prev = q;		p->sibling = q->child;		if(p->sibling != NULL)			p->sibling->prev = p;		q->child = p;		return q;	}}

    //实现对order序(阶)的B-TREE结构基本操作的封装。      //查找：search，插入：insert，删除：remove。      //创建：create，销毁：destory，打印：print。      #ifndef BTREE_H      #define BTREE_H            #ifdef __cplusplus      extern "C" {      #endif            ////* 定义m序(阶)B 树的最小度数BTree_D=ceil(m)*/      /// 在这里定义每个节点中关键字的最大数目为:2 * BTree_D - 1，即序(阶)：2 * BTree_D.      #define BTree_D        2      #define ORDER        (BTree_D * 2) //定义为4阶B-tree,2-3-4树。最简单为3阶B-tree,2-3树。      //#define ORDER        (BTree_T * 2-1)  //最简单为3阶B-tree,2-3树。                typedef int KeyType;          typedef struct BTNode{              int keynum;                        /// 结点中关键字的个数，keynum <= BTree_N              KeyType key[ORDER-1];                /// 关键字向量为key[0..keynum - 1]              struct BTNode* child[ORDER];        /// 孩子指针向量为child[0..keynum]              bool isLeaf;                    /// 是否是叶子节点的标志          }BTNode;                    typedef BTNode* BTree;  ///定义BTree                    ///给定数据集data,创建BTree。          void BTree_create(BTree* tree, const KeyType* data, int length);                ///销毁BTree，释放内存空间。          void BTree_destroy(BTree* tree);                    ///在BTree中插入关键字key。          void BTree_insert(BTree* tree, KeyType key);                ///在BTree中移除关键字key。          void BTree_remove(BTree* tree, KeyType key);                ///深度遍历BTree打印各层结点信息。          void BTree_print(const BTree tree, int layer=1);                    /// 在BTree中查找关键字 key，          /// 成功时返回找到的节点的地址及 key 在其中的位置 *pos          /// 失败时返回 NULL 及查找失败时扫描到的节点位置 *pos          BTNode* BTree_search(const BTree tree, int key, int* pos);                #ifdef __cplusplus      }      #endif            #endif  

    //说明：      //代码中Fibonacci Heap 用变量heap表示      //结点通常用x，y等表示      #include<iostream>      #include<cstdio>      #include<cstdlib>      #include<cmath>      #include<climits>      using namespace std;             //斐波那契结点ADT      struct FibonacciHeapNode {          int key;       //结点          int degree;    //度          FibonacciHeapNode * left;  //左兄弟          FibonacciHeapNode * right; //右兄弟          FibonacciHeapNode * parent; //父结点          FibonacciHeapNode * child;  //第一个孩子结点          bool marked;           //是否被删除第1个孩子      };             typedef FibonacciHeapNode FibNode;             //斐波那契堆ADT      struct FibonacciHeap {          int keyNum;   //堆中结点个数          FibonacciHeapNode * min;//最小堆，根结点          int maxNumOfDegree;   //最大度          FibonacciHeapNode * * cons;//指向最大度的内存区域      };             typedef FibonacciHeap FibHeap;             /*****************函数申明*************************/      //将x从双链表移除      inline void FibNodeRemove(FibNode * x);             //将x堆结点加入y结点之前(循环链表中)      void FibNodeAdd(FibNode * x, FibNode * y);             //初始化一个空的Fibonacci Heap      FibHeap * FibHeapMake() ;             //初始化结点x      FibNode * FibHeapNodeMake();             //堆结点x插入fibonacci heap中      void FibHeapInsert(FibHeap * heap, FibNode * x);             //将数组内的值插入Fibonacci Heap      void FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum);             //将值插入Fibonacci Heap      static void FibHeapInsertKey(FibHeap * heap, int key);             //抽取最小结点      FibNode * FibHeapExtractMin(FibHeap * heap);             //合并左右相同度数的二项树      void FibHeapConsolidate(FibHeap * heap);             //将x根结点链接到y根结点      void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y);             //开辟FibHeapConsolidate函数哈希所用空间      static void FibHeapConsMake(FibHeap * heap);             //将堆的最小结点移出，并指向其有兄弟      static FibNode *FibHeapMinRemove(FibHeap * heap);             //减小一个关键字      void FibHeapDecrease(FibHeap * heap, FibNode * x, int key);             //切断x与父节点y之间的链接，使x成为一个根      static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y);             //级联剪切      static void FibHeapCascadingCut(FibHeap * heap, FibNode * y);             //修改度数      void renewDegree(FibNode * parent, int degree);             //删除结点      void FibHeapDelete(FibHeap * heap, FibNode * x);             //堆内搜索关键字      FibNode * FibHeapSearch(FibHeap * heap, int key);             //被FibHeapSearch调用      static FibNode * FibNodeSearch(FibNode * x, int key);             //销毁堆      void FibHeapDestory(FibHeap * heap);             //被FibHeapDestory调用      static void FibNodeDestory(FibNode * x);             //输出打印堆      static void FibHeapPrint(FibHeap * heap);             //被FibHeapPrint调用      static void FibNodePrint(FibNode * x);      /************************************************/             //将x从双链表移除      inline void FibNodeRemove(FibNode * x) {          x->left->right = x->right;          x->right->left = x->left;      }             /*     将x堆结点加入y结点之前(循环链表中)         a …… y         a …… x …… y     */      inline void FibNodeAdd(FibNode * x, FibNode * y) {          x->left = y->left;          y->left->right = x;          x->right = y;          y->left = x;      }             //初始化一个空的Fibonacci Heap      FibHeap * FibHeapMake() {          FibHeap * heap = NULL;          heap = (FibHeap *) malloc(sizeof(FibHeap));          if (NULL == heap) {              puts("Out of Space!!");              exit(1);          }          memset(heap, 0, sizeof(FibHeap));          return heap;      }             //初始化结点x      FibNode * FibHeapNodeMake() {          FibNode * x = NULL;          x = (FibNode *) malloc(sizeof(FibNode));          if (NULL == x) {              puts("Out of Space!!");              exit(1);          }          memset(x, 0, sizeof(FibNode));          x->left = x->right = x;          return x;      }             //堆结点x插入fibonacci heap中      void FibHeapInsert(FibHeap * heap, FibNode * x) {          if (0 == heap->keyNum) {              heap->min = x;          } else {              FibNodeAdd(x, heap->min);              x->parent = NULL;              if (x->key < heap->min->key) {                  heap->min = x;              }          }          heap->keyNum++;      }             //将数组内的值插入Fibonacci Heap      void FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum) {          for (int i = 0; i < keyNum; i++) {              FibHeapInsertKey(heap, keys[i]);          }      }             //将值插入Fibonacci Heap      static void FibHeapInsertKey(FibHeap * heap, int key) {          FibNode * x = NULL;          x = FibHeapNodeMake();          x->key = key;          FibHeapInsert(heap, x);      }             //抽取最小结点      FibNode * FibHeapExtractMin(FibHeap * heap) {          FibNode * x = NULL, * z = heap->min;         if (z != NULL) {                     //删除z的每一个孩子              while (NULL != z->child) {                  x = z->child;                  FibNodeRemove(x);                  if (x->right == x) {                      z->child = NULL;                  } else {                      z->child = x->right;                  }                  FibNodeAdd(x, z);//add x to the root list heap                  x->parent = NULL;              }                     FibNodeRemove(z);              if (z->right == z) {                  heap->min = NULL;              } else {                  heap->min = z->right;                  FibHeapConsolidate(heap);              }              heap->keyNum--;          }          return z;      }             //合并左右相同度数的二项树      void FibHeapConsolidate(FibHeap * heap) {          int D, d;          FibNode * w = heap->min, * x = NULL, * y = NULL;          FibHeapConsMake(heap);//开辟哈希所用空间          D = heap->maxNumOfDegree + 1;          for (int i = 0; i < D; i++) {              *(heap->cons + i) = NULL;          }                 //合并相同度的根节点，使每个度数的二项树唯一          while (NULL != heap->min) {              x = FibHeapMinRemove(heap);              d = x->degree;              while (NULL != *(heap->cons + d)) {                  y = *(heap->cons + d);                  if (x->key > y->key) {//根结点key最小                      swap(x, y);                  }                  FibHeapLink(heap, y, x);                  *(heap->cons + d) = NULL;                  d++;              }              *(heap->cons + d) = x;          }          heap->min = NULL;//原有根表清除                 //将heap->cons中结点都重新加到根表中，且找出最小根          for (int i = 0; i < D; i++) {              if (*(heap->cons + i) != NULL) {                  if (NULL == heap->min) {                      heap->min = *(heap->cons + i);                  } else {                      FibNodeAdd(*(heap->cons + i), heap->min);                      if ((*(heap->cons + i))->key < heap->min->key) {                          heap->min = *(heap->cons + i);                      }//if(<)                  }//if-else(==)              }//if(!=)          }//for(i)      }             //将x根结点链接到y根结点      void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y) {          FibNodeRemove(x);          if (NULL == y->child) {              y->child = x;          } else {              FibNodeAdd(x, y->child);          }          x->parent = y;          y->degree++;          x->marked = false;      }             //开辟FibHeapConsolidate函数哈希所用空间      static void FibHeapConsMake(FibHeap * heap) {          int old = heap->maxNumOfDegree;          //最大度的计算        heap->maxNumOfDegree = int(log(heap->keyNum * 1.0) / log(2.0)) + 1;          if (old < heap->maxNumOfDegree) {              //因为度为heap->maxNumOfDegree可能被合并,所以要maxNumOfDegree + 1              heap->cons = (FibNode **) realloc(heap->cons,                  sizeof(FibHeap *) * (heap->maxNumOfDegree + 1));              if (NULL == heap->cons) {                  puts("Out of Space!");                  exit(1);              }          }      }             //将堆的最小结点移出，并指向其有兄弟      static FibNode *FibHeapMinRemove(FibHeap * heap) {          FibNode *min = heap->min;          if (heap->min == min->right) {              heap->min = NULL;          } else {              FibNodeRemove(min);              heap->min = min->right;          }          min->left = min->right = min;          return min;      }             //减小一个关键字      void FibHeapDecrease(FibHeap * heap, FibNode * x, int key) {          FibNode * y = x->parent;          if (x->key < key) {              puts("new key is greater than current key!");              exit(1);          }          x->key = key;                 if (NULL != y && x->key < y->key) {              //破坏了最小堆性质，需要进行级联剪切操作              FibHeapCut(heap, x, y);              FibHeapCascadingCut(heap, y);          }          if (x->key < heap->min->key) {              heap->min = x;          }      }             //切断x与父节点y之间的链接，使x成为一个根      static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y) {          FibNodeRemove(x);          renewDegree(y, x->degree);          if (x == x->right) {              y->child = NULL;          } else {              y->child = x->right;          }          x->parent = NULL;          x->left = x->right = x;          x->marked = false;          FibNodeAdd(x, heap->min);      }             //级联剪切      static void FibHeapCascadingCut(FibHeap * heap, FibNode * y) {          FibNode * z = y->parent;          if (NULL != z) {              if (y->marked == false) {                  y->marked = true;              } else {                  FibHeapCut(heap, y, z);                  FibHeapCascadingCut(heap, z);              }          }      }             //修改度数      void renewDegree(FibNode * parent, int degree) {          parent->degree -= degree;          if (parent-> parent != NULL) {              renewDegree(parent->parent, degree);          }      }             //删除结点      void FibHeapDelete(FibHeap * heap, FibNode * x) {          FibHeapDecrease(heap, x, INT_MIN);          FibHeapExtractMin(heap);      }             //堆内搜索关键字      FibNode * FibHeapSearch(FibHeap * heap, int key) {          return FibNodeSearch(heap->min, key);      }             //被FibHeapSearch调用      static FibNode * FibNodeSearch(FibNode * x, int key) {          FibNode * w = x, * y = NULL;          if (x != NULL) {              do {                  if (w->key == key) {                      y = w;                      break;                  } else if (NULL != (y = FibNodeSearch(w->child, key))) {                      break;                  }                  w = w->right;              } while (w != x);          }          return y;      }             //销毁堆      void FibHeapDestory(FibHeap * heap) {          FibNodeDestory(heap->min);          free(heap);          heap = NULL;      }             //被FibHeapDestory调用      static void FibNodeDestory(FibNode * x) {          FibNode * p = x, *q = NULL;          while (p != NULL) {              FibNodeDestory(p->child);              q = p;              if (p -> left == x) {                  p = NULL;              } else {                  p = p->left;              }              free(q->right);          }      }             //输出打印堆      static void FibHeapPrint(FibHeap * heap) {          printf("The keyNum = %d\n", heap->keyNum);          FibNodePrint(heap->min);          puts("\n");      };             //被FibHeapPrint调用      static void FibNodePrint(FibNode * x) {          FibNode * p = NULL;          if (NULL == x) {              return ;          }          p = x;          do {              printf(" (");              printf("%d", p->key);              if (p->child != NULL) {                  FibNodePrint(p->child);              }              printf(") ");              p = p->left;          }while (x != p);      }             int keys[10] = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11};             int main() {          FibHeap * heap = NULL;          FibNode * x = NULL;          heap = FibHeapMake();          FibHeapInsertKeys(heap, keys, 10);          FibHeapPrint(heap);                 x = FibHeapExtractMin(heap);          printf("抽取最小值%d之后：\n", x->key);          FibHeapPrint(heap);                 x = FibHeapSearch(heap, 11);          if (NULL != x) {              printf("查找%d成功,", x->key);              FibHeapDecrease(heap, x, 8);              printf("减小到%d后：\n", x->key);              FibHeapPrint(heap);          }                 x = FibHeapSearch(heap, 7);          if (NULL != x) {              printf("删除%d成功:\n", x->key);              FibHeapDelete(heap, x);              FibHeapPrint(heap);          }                 FibHeapDestory(heap);          return 0;      }