工大数据结构第三章作业

{ heap.n=0;}

Bool HeapEmpty(HEAP heap)// 判断堆是否为空 {

If(!(heap.n))return true; Else return false; }

Bool HeapFull(HEAP heap)// 判断堆是否为满

{if(heap.n==Maxsize-1) return true; Else return false; }

Void Insert(HEAP&heap,elementtype element)// 在堆 heap

中插入元素为 element 的结点 { Int I;

If(!HeapFull(heap)){ I=heap.n+1;

While((i!=1)&&(element.data>heap.elements[i/2].data)) {heap.elements[i]=heap.elements[i/2]; i/=2; }

Heap.n++;

Heap.elements[i]=element; } }

Elementtype DeleteMax(HEAP&heap)// 删除堆中最大元素

{int paraent=1,child=2; Elementtype element,tmp; If(!HeapEmpty(heap)){ Element=heap.elements[1]; Tmp=heap.elements[heap.n-]; While(child<=heap.n) {

If((child=heap.elements[child].data)break; Heap.elements[paraent]=heap.elements[child]; Paraent=child; Child*=2;}

Heap.elements[paraent]=tmp; Return element;} }

Int Find(HEAP,datatype x) {int m=1;

While((m=x) m++;

else return 0; else m++;}

if(m<=H.n)return m; else return 0; }

Int main(){ HEAP H;

Elementtype element;

Int data[]={1,3,5,7,9,11,13}; H.n=0;

For(int i=0;i<7;i++) {element.key=i+1; Element.data=data[i]; Insert(H,element);

}for(int i;i<=H.n;i++)

cout<

For(int i=1;i<=H.n;i++)cout<

Cout<<”查找的元素：”; Int x; Cin>>x;

Cout<

十二、给定叶子结点的权值集合{15, 3,14, 2, 6, 9, 16, 17}，构造相应的哈夫曼树，并计算其带权路径长度。

十三、已知n=9和一组等价关系：

1≡5、6≡8、7≡2、9≡8、3≡7、4≡2、9≡3 试应用抽象数据类型MFSET设计一个算法，按输入的等价关系进行等价分类。 #include

#define n 9//MEFSET元素个数 //MFSET抽象数据型 struct mfnode{

int father;//指向父节点的链 int count;//树结点个数 };

typedef mfnode MFSET[n+1]; void Union(int A, int B, MFSET C) //合并A和B {

if(C[A].count>C[B].count) {

C[B].father=A;//B并入A

C[A].count+=C[B].count; } else {

C[A].father=B;//A并入B

C[B].count+=C[A].count; } }

int Find(int x, MFSET C)//求包含元素x的树的根 { int f; f=x;

while(C[f].father!=0)//未到根 f=C[f].father; return f; }

void Initial(int A, MFSET C)//集合A只包含元素A {

C[A].father=0; C[A].count=1; }

// 等价分类

void Equivalence(MFSET S) {

int i, j, m, k;

for(i=1; i<=n; i++) Initial(i, S); cin>>i; cin>>j;

while(!(i==0 && j==0))//输入0,0结束等价分类 {

k=Find(i, S); m=Find(j, S);

if(k!=m)

Union(k, m, S); cin>>i;

cin>>j; } }

void print_MFSET(MFSET S) //输出等价类 {

int r[n+1][n+1]={0}, k; for(int i=1; i<=n; i++)