} ht[p1].parent=i; /* i分别赋给下标为p1、p2的数组中 */ ht[p2].parent=i; ht[i].weight=m1+m2; /* 新结点的的权值为最小权值和次小权值的和 */ ht[i].left=p1; /* p1为新结点的左孩子 */ ht[i].right=p2; /* p2为新结点的右孩子 */ } printf(\哈夫曼树已成功建立！\\n\ return n; /* 返回结点个数 */ }
void Encoding(HuffNode ht[],HuffCode hcd[],int n)/* 哈夫曼编码 */ { HuffCode d; int i,k,f,c; for(i=1;i<=n;i++) /* 对所有结点循环 */ { d.start=n+1; /* 起始位置 */ c=i; /* 从叶结点开始向上 */ f=ht[i].parent; while(f!=0) /* 直到树根为止 */ { if(ht[f].left==c) d.cd[--d.start]='0';/* 规定左树为代码0 */ else d.cd[--d.start]='1';/* 规定右树为代码1 */ c=f; /* c指孩子的位置 */ f=ht[f].parent; /* f指双亲的位置 */ } hcd[i]=d; } printf(\输出哈夫曼编码：\\n\ for(i=1;i<=n;i++) /* 输出哈夫曼编码 */ { printf(\ /* 先输出结点 */ for(k=hcd[i].start;k<=n;k++)/* 再输出其对应的编码 */ printf(\ printf(\ } }
void Decoding(HuffNode ht[],HuffCode hcd[],int n)/* 哈夫曼译码 */ { int f,m,k;
DataType c,ch[200]; /* c接收输入电文，ch存储 */ printf(\请输入电文(0 or 1)，以#为结束标志：\\n\ c=getchar(); k=1; while(c!='#') /* 单个字符循环输入，以'#'结束 */ { ch[k]=c; /* 将单个字符依次存入ch字符串中 */ c=getchar(); k=k+1; /* ch数组下标后移 */ } m=k; /* 标记数组存储末尾位置 */ f=2*n-1; k=1; /* k记录电文字符的个数 */ printf(\输出哈夫曼译码：\\n\ while(k int main(int argc,char* argv[]) { int n,select,flag=FALSE; /* flag为0时标记第一次选择功能 */ HuffNode ht[2*MAXNUM]; /* 定义存放哈夫曼树的数组 */ HuffCode hcd[MAXNUM]; /* 定义存放编码的数组 */ while(TRUE) { printf(\ 请选择您所要实现的功能：（请输入1-4数字）\\n\ printf(\建立哈夫曼树\\n\ printf(\编码\\n\ printf(\译码\\n\ printf(\退出系统\\n\ scanf(\ if(select!=1&&select!=4&&flag==0) { /* 提示先建立哈夫曼树或退出 */ printf(\请先建立哈夫曼树再选择其他功能！\\n\ continue; } flag=TRUE; switch(select) /* 选择功能 */ { case 1: n=HuffmanCreate(ht); break; case 2: Encoding(ht,hcd,n); break; case 3: Decoding(ht,hcd,n); break; case 4: exit(0); } } return 0; } 六、本科生导师制问题 /*研究生及导师关系广义表实现*/ #include\ typedef struct GLNode { char name[100]; /* 教师或学生的姓名 */ char prof[100]; /* 教师结点表示职称，学生结点表示班级 */ int type; /* 结点类型：0--教师，1--研究生，2--本科生 */ struct {struct GLNode *hp,*tp;}ptr;/* hp指向同级的下一结点，tp指向下级的首结点 */ }GList; GList *GListCreate(char *str)/*建立广义表*/ { GList *head,*p,*q,*m,*a;/* 简要介绍：head指向头结点,不变;p指向导师结点;q指向研究生结点;a指向本科生节点; m指向新建立的节点*/ int i = 0,j = 0,flag = 0,flag1 = 0,flag2=0,len = strlen(str); head=p=q=m=a=NULL; while(i < len) { if(str[i] == ')' || str[i] == '(' || str[i] == ','|| str[i] == '）'|| str[i] == '（'|| str[i] == '，') {i++;continue;} else { if(!(m =(GList *)malloc(sizeof(GList)))) exit(1); for(j=0;str[i] != '-';) /* 将字符串中的学生信息转化成学生结点 */ m->name[j++] = str[i++]; m->name[j] = '\\0'; for(j=0,++i;str[i] != '-';) m->prof[j++] = str[i++]; m->prof[j] = '\\0'; m->type = str[++i] - 48; m->ptr.hp=m->ptr.tp=NULL; i++; if(m->type == 0) /* 导师结点的处理 */ { if(flag) { p->ptr.hp=m; /* 非首结点 */ p=m; } else { head=p=m; /* 首结点的处理 */ flag=1; } flag1=0; a=q=m; /* a在此等于m,主要是处理本科生直属于导师的情况 */ } else if(m->type==1) /* 研究生结点 */ { if(flag1) { q->ptr.hp=m; /* 非首结点的处理 */ q=m; } else { q->ptr.tp=m; /* 首结点的处理 */ q=m; flag1=1; } flag2=0; a=m; } else /* 本科生结点 */ { if(flag2) { a->ptr.hp=m; /* 非首结点的处理 */ a=m; } else { a->ptr.tp=m; /* 首结点的处理 */ a=m; flag2=1; } } } } return head; } void GListPrint(GList *head)/*输出广义表*/ { GList *p,*q,*a; /* 与CreatGList函数中的指向一样 */ int flag=0,flag1=0,flag2=0; p = head; printf(\ while(TRUE) /* 导师范畴 */ { if(p == NULL) break; if(flag) printf(\ else {printf(\ flag=1;} q = p->ptr.tp; flag2=flag1=0; while(TRUE) /* 研究生或本科生范畴 */ { if(q == NULL) break; if(flag1) if(q->type==1) printf(\ else printf(\ else