【正确答案】(1)分析
   可以证明满M又树的性质：叶结点的个数=分支结点数×(M-1)+1。任意给定N个叶结点的权，构造最优M叉树可能不是满的M叉树，如果(N-1)/(M-1)不是整数，最优M叉树的分支结点数c应该是取不小于它的最小整数。
   根据这个c的值可以计算出将要构造的最优满M叉树叶结点的个数d=c×(M-1)+1。其中d-N个叶结点是虚构的，它们的权可以用0标记，这样构造M叉树的算法比较简单，而且可以保证构造出的M叉树是最优的。
   根据上面的思想，下面的main()函数把对于构造N个叶结点的最优M叉树的要求，转换成构造d个叶结点的最优M叉树。它的分支结点数为c，总结点数total=c+d=c×M+1。通过调用mhuffman()函数完成题目的要求。
   在算法中的另外一个难点是：如何选择M个最小的权?mhuffman算法中采用了一个用小根堆记录的权的集合，初值存放全部已知的叶结点权。根据优先队列的原理，连续从堆中取出M个最小的权，构造一个新的分支结点，计算出它的权，再插入堆中，然后参加下一个分支结点的构造。如此反复，直到全部构造完成。
   (2)数据结构
   stmct mHtNode{    /*M叉最优树结点的结构*/
       intww:
       int parent:
       int*link:    /*存放子结点的数组*/
   };
   Typedef struct mHtNode*pmHtNode;
                      /*M又最优树结点类型的指针类型*/
   struct mHtTree{    /*M叉最优树结构*/
       int m:        /*外部结点的个数*/
       int M:        /*M叉树*/
           int root: /*M叉最优树根的下标*/
           pmHtNode mht;    /*存放结点的数组*/
   };
   typedef struct mHtnee*pmHtTree;  /*M叉最优树类型的指针类型*/
   typedef struct{    /*堆中的元素*/
       int w;        /*元素的值*/
       int pos;    /*元素在mht数组中的下标*/
   }Record;
   typedef struct Record*precord;
   struct mPriorityQueue{
       int MAXNUM;     /*堆中的元素个数的上限*/
       intn;           /*堆中的实际元素个数*/
       precordpq;      /*堆中元素的顺序表示*/
   };                  /*优先队列类型*/
   typedef struct mPriorityQueue*pmPriorityQueue;
                        /*指向优先队列的指针类型*/
   (3)优先队列的实现
   /*创建空的优先队列。时间代价为O(1)*/
   pmPriorityQueue createEmptyPriorityQueue_heap(int m){
   pmPriorityQueue papq=(pmPriorityQueue)malloc(sizeof(stmct mPriorityQueue));
   if(papq!=NULL){
       papq-＞pq=(precord)malloc(sizeof(Record)*m);
       if(papq-＞pq!=NULL){
           papq-＞MAXMUM=m;
           papq-＞n=0:
           return papq;
           }
       else free(papq);
       }
   printf("out of space!in");
   return NULL;
   }
   /*判断一个优先队列是否为空*/
   int isEmptyPriorityQueue_heap(pmPriorityQueue papq){
       return papq-＞n==0;
       }
   /*向优先队列中加入一个元素,保持堆的性质*/
   void add heap(pmPriorityQueue papq,Record R){
       int i;
   if(papq-＞n＞=papq-＞MAXNUM){
       printf("Full!\n");
       return;
       }
   for(i=papq-＞n;i＞0&&papq-＞pq[(i-1)/2].w＞R.w;i=(i-1)/2)
       papq-＞pq[i]=papq-＞pq[(i-1)/2];
   papq-＞pq[papq-＞i]=R;
       papq-＞n++:
   }
   /*从优先队列中输出并删除一个元素(最小元素)*/
   Record removeMin_heap(pmPriorityQueue papq){
       Record temp,min;
       int i,child;
       if(isEmptyPriorityQueue heap(papq)){printf("Empty!\n");return;}
       temp=papq-＞pq[--papq-＞n];
       min=papg-＞pq[0];
       i=0:
       child=1:
       while(child＜papq-＞n){
           if(child＜papq-＞n-1&＆
             papq-＞pq[child].w＞papq-＞pq[child+1].w)child++;
           if(temp.w＞papq-＞pq[child].w){
             papq-＞pq[i]=papq-＞pq[child];
             i=child;
             child=2*i+1:
           }
           else break;
   }
   papq-＞pq[i]=temp;
   return min;
   }
   (4)核心构造函数
   int mhuffman(int m,int M,int c,int*ww,pmHtTree pmht){
   /*构造具有m个外部结点,c个内部结点的M叉最优树pmht*/
   pmHtTree pmht;
   pmHtNode pmhn;
   Record R,min;
   int i,k,total,tempW;
   pmPriorityQueue papq;
   if(M＜2)  return 0;
   if(m!=c*(M-1)+1)return 0;    /*参数错*/
   total=m+c;
   for(i=0;i＜total;i++){    /*置结点数组初态*/
       for(k=0;k＜M;k++)pmht-＞mht[i]-＞link[k]=-1;
       pmht-＞mht[i].parent=-1;
       if(i＜m)pmht-＞mht[i].ww=ww[i];
       else pmht-＞mht[i].ww=0:
   }
   papq=createEmptyPriorityQueue_heap(m);    /*创建空的优先队列*/
   for(i=0;i＜m;i++){    /*建初始的优先队列*/
       R.w=ww[i];
       R.pos=i;
       add_heap(papq,R);
   }
   for(i=0;i＜c;i++){
   /*每循环一次构造一个内部结点,c为内部结点的个数*/
       tempW=0:
       for(k=0;k＜M;k+T){    /*找M个较小值*/
           min=removeMin_heap(papq);
           tempW+=min.w:
           pmht-＞mht[min.pos].parent=m+i;
           pmht-＞mht[m+i]-＞link[k]=min.pos;
           /*内部结点的子结点下标*/
       }
       pmht-＞mht[m+i].ww=tempW;
       R.w=pmht-＞mht[m+i].ww:
       R.pos=m+i:
       add_heap(papq,R);
   }
       return 1;
   }
   main(){
       int m,M,*ww,c,d,total;
       int i,j;
       floattmp;
       pmHtTree pmht;
       printf("kn Please input the value of M=");
       scanf("/%d",&M);
       printf("\n Please input the value of m=");
       scanf("/%d",&m);
       /*计算满M叉树的叶结点数目*/
       tmp=(m-1)/(M-1);
       c=(float)(tmp-fint)tmp)＞0?((int)tmp+1):tmp;  /*分支结点数*/
       d=c*(M-1)+1;    /。需要的叶结点数*/
       total=M*c+1:    /。需要的总结点数*/
           WW=(int*)malloc(sizeof(int)*d);    /*分配权数组空间*/
       if(ww==NULL){printf("Out ofspace!kn");return NULL;)
       printf("\n Please input the values of ww");
       for(i=0;i＜m;i++)scanf("god",&ww[i]);
       for(i=m;i＜d;i++)ww[i]=0;    /*虚构叶结点的权值置0*/
       pmht=(pmHtTree)malloc(sizeof(struct mHtTree));  /*分配M叉最优树结构空间*/
       if(pmht==NULL){printf("Out of space!\n");return NULL;}
       pmht-＞M=M:
       pmht-＞m=d:
       pmht-＞root=total-1:
       pmht-＞mht=(pmHtNode)malloc(sizeof(struct pmHtNode)*total);
       /*分配结点数组空间*/
       if(pmht-＞mht==NULL){
       printf(1. Out of space!in");free(pmht);return NULL;
       }
       /*分配结点数组空间*/
       for(i=0;i＜total;i++){
       pmht-＞mht[i]-＞link=(int*)malloc(sizeof(int)*M);
                                    /*分配所有的子结点下标数组空间*/
       if(pmht-＞mht[i]-＞link==NULL){
           printf("Out of space!\n");
           for(j=0;j＜i;j++)free(pmht-＞mht[j]-＞link);
           free(pmht-＞mht):
           free(pmht);
           return 0;
           }
         }
       If(mHuffman(d,M,c,*ww,pmht)){/*(根据需要处理)*/};
       return;
   }
   (5)代价分析
   引入优先队列，增加的空间大小为O(m)，使得mHuffman算法的时间代价从O(m²)降低到O(mlogm)。具体分析方法可以参考堆排序。