数据结构经典题目及c语言代码总结_数据结构c语言版习题
数据结构经典题目及c语言代码总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构c语言版习题”。
《数据结构》课程设计题目(程序实现采用C语言)
题目1：猴子选王（学时：3）
一堆猴子都有编号，编号是1，2，3...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。
//链表
#include #include // 链表节点
typedef struct _RingNode
{
int pos;
struct _RingNode *next;}RingNode, *RingNodePtr;
// 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 void CreateRing(RingNodePtr pHead, int count){
RingNodePtr pCurr = NULL, pPrev = NULL;
int i = 1;
pPrev = pHead;
while(--count > 0)
{
pCurr =(RingNodePtr)malloc(sizeof(RingNode));
i++;
pCurr->pos = i;
pPrev->next = pCurr;
pPrev = pCurr;
}
pCurr->next = pHead;// 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n){
RingNodePtr pCurr, pPrev;
int i = 1;
// 计数
pCurr = pPrev = pHead;
while(pCurr!= NULL)
{
if(i == n)
{
// 踢出环
printf(“n%d”, pCurr->pos);
// 显示出圈循序
pPrev->next = pCurr->next;
free(pCurr);
pCurr = pPrev->next;
i = 1;
}
pPrev = pCurr;
pCurr = pCurr->next;
if(pPrev == pCurr)
{
// 最后一个
printf(“nKing is %d”, pCurr->pos);
// 显示出圈循序
free(pCurr);
break;
}
i++;
} }
int main(){
int n = 0, m = 0;
RingNodePtr pHead = NULL;
printf(“M(person count)= ”);
scanf(“%d”, &m);
printf(“N(out number)= ”);
scanf(“%d”, &n);
if(m
{
printf(“Input Errorn”);
return 0;
}
// 建立链表
pHead =(RingNodePtr)malloc(sizeof(RingNode));
pHead->pos = 1;
pHead->next = NULL;
CreateRing(pHead, m);// 开始出圈
printf(“nKick Order: ”);
KickFromRing(pHead, n);
printf(“n”);
system(“pause”);
return 0;}
//数组做：
#include #include #include
void SelectKing(int MonkeyNum, int CallNum);
void main(){
int MonkeyNum;
int CallNum;
/* 输入猴子的个数 */
printf(“Monkey Num = ”);
scanf(“%d”, &MonkeyNum);
/* 输入M的值 */
printf(“Call Num = ”);
scanf(“%d”, &CallNum);
SelectKing(MonkeyNum, CallNum);
}
void SelectKing(int MonkeyNum, int CallNum){
int *Monkeys;// 申请一个数组，表示所有的猴子；
int counter = 0;//计数，当计数为猴子个数时表示选到最后一个猴子了；
int position = 0;// 位置，数组的下标，轮流遍历数组进行报数；
int token = 0;// 令牌，将报数时数到M的猴子砍掉；
// 申请猴子个数大小的数组，把桌子摆上。
Monkeys =(int *)malloc(sizeof(int)* MonkeyNum);
if(NULL == Monkeys)
{
printf(“So many monkeys, system error.n”);
return;
}
// 将数组的所有内容初始化为0，被砍掉的猴子设置为1
memset(Monkeys, 0, sizeof(int)*MonkeyNum);
// 循环，直到选中大王
while(counter!= MonkeyNum)
{
// 如果这个位置的猴子之前没有砍掉，那么报数有效
if(Monkeys[position] == 0)
{
token++;// 成功报数一个，令牌+1，继续报数直到等于M
// 如果报数到M，那么将这个猴子砍去
if(token == CallNum)
{
Monkeys[position] = 1;// 设置为1，表示砍去
counter++;// 计数增加
token = 0;// 设置为0，下次重新报数
// 如果是最后一个猴子，把它的位置打印，这个就是大王了
if(counter == MonkeyNum)
{
printf(“The king is the %d monkey.n”, position+1);
}
}
}
// 下一个猴子报数
position =(position + 1)%MonkeyNum;
}
// 释放内存，开头为所有猴子创建的桌子
free(Monkeys);
return;}
题目2 ：字符逆转（学时：3）
从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。
#include #include
struct node {
struct node *prev;
char c;
struct node *next;};struct node *input(struct node *top);int main(void){ struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c=' ';bottom=input(top);p=bottom->prev;while(p!=NULL){
printf(“%c”,p->c);
p=p->prev;} return 0;}
struct node *input(struct node *top){
struct node *t;char x;while((x=getchar())!='n'){ top->c=x;t=(struct node *)malloc(sizeof(struct node));top->next=t;t->prev=top;t->next=NULL;t->c=' ';top=top->next;
} }
return top;题目3 ：工资核算（学时：3）
设有一个单位的人员工资有如下信息：name、department、base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。
#include #include #define SIZE 2 #define LENTH sizeof(struct stuff)struct stuff {
char name[100];char department[100];
int basepay;
int allowance;
int total;}stuff[SIZE];main(){ FILE *fp;
int i;
printf(“Please enter name department basepay allowance：n”);
for(i=0;i
scanf(“%s %s %f %f”,&stuff[i].name,&stuff[i].department,&stuff[i].basepay,&stuff[i].allowance);
if((fp=fopen(“paydata.dat”,“wb”))==NULL)
{
printf(“Can't open filen”);
return 0;}
for(i=0;i
if(fwrite(&stuff[i],LENTH,1,fp)!=1)
printf(“文件写入出错n”);
fclose(fp);
if((fp=fopen(“paydata.dat”,“rb”))==NULL)
{ } printf(“Can't open filen”);
printf(“修改过后的结果：n”);
for(i=0;i
{ fread(&stuff[i],LENTH,1,fp);
stuff[i].total=stuff[i].basepay+100+stuff[i].allowance;
printf(“%-10s%-10s %f %f %fn”,stuff[i].name,stuff[i].department,stuff[i].basepay+100,stuff[i].allowance,stuff[i].total);
}
fclose(fp);return 0;} 题目4：满足条件的有序表生成（学时：3）
已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。
#include void main(){
int a[7],b[5],c[6],d[7];
int i,j,k,t,m;printf(“nPlease enter 7 numbers of A:”);for(i=0;i
for(i=0;i
if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers：n”);for(i=0;i
printf(“nPlease enter 5 numbers of B:”);
for(i=0;i
if(b[i]>b[i+1]){t=b[i];b[i]=b[i+1];b[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i
printf(“nPlease enter 6 numbers of C:”);
for(i=0;i
for(j=0;j
for(i=0;i
if(c[i]>c[i+1]){t=c[i];c[i]=c[i+1];c[i+1]=t;} printf(“the sorted numbers：n”);for(i=0;i
for(i=0;i
for(j=0;j
if(b[i]==c[j]){
for(k=0;k
if(b[i]==a[k])
}
}
} }
a[k]=m;
printf(“n”);k=0;for(i=0;i
if(a[i]!=m){
} printf(“生成的有序表d为 ”);for(i=0;i
printf(“%4d”,d[i]);d[k]=a[i];k++;printf(“n”);}
题目5：一元 多项式的减法（学时：6）
设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。
#include
struct Polynode {
int coef;int exp;Polynode *next;}Polynode,*Polylist;void Polycreate(Polylist head){
} void Polyadd(Polylist polya,Polylist polyb){
Polynode *p,*q,*tail,*temp;int sum;p=polya->next;Polynode *rear,*s;int c,e;rear=head;printf(“请输入多项式的系数项和指数项”);scanf(“%d,%d”,&c,&e);while(c!=0){
} rear->next=NULL;s=(Polynode*)malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf(“%d,%d”,&c,&e);
q=polyb->next;tail=polya;while(p!=NULL&&q!=NULL){
if(p->expexp){ tail->next=p;tail=p;p=p->next;} else if(p->exp=q->exp){
sum=p->coef+q->coef;if(sum!=0){
} else { temp=p;p->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next;free(temp);
}
}
}
} p=p->next;free(temp);q=q->next;free(temp);else {
} tail->next=q;tail=q;q=q->next;if(p!=NULL)tail->next=p;else tail->next=q;void Polysubstract(Polylist polya,Polylist polyb){ Polylist h=polyb;Polylist p=pb->next;Polylist pd;while(p){p->coef*=-1;p=p->next;} pd=Polyadd(pa,h);for(p=h->next;p;p=p->next)p->coef*=-1;return pd； }
void PrintPolyn(Polyn P)
void printfPolyn(Polynode *head){ Polynode *p=head->next;while(p){printf(“%dx^%d”,p->coef,p->exp);if(p->next)printf(“+”);p=p->next;} } int main(){
Polynode *La,Lb;La=Polycreate();Lb=Polycreate();PrintPolyn(La);printf(“/n”);PrintPolyn(Lb);
} printf(“/n”);Polyadd(polya,polyb);printPolyn(polya);return 0;
题目6：床位分配（学时：6）
某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。
#include #include #include #include #define N 3
typedef struct Room {
int roomlevel;int roomnum;int bednum;int peoplenum;int bed[N];int sex;char name[10];struct Room *next;}Room;Room *creat(int roomlevel,int room[],int bed[]){ Room *head,*p,*q;
int i=1,j,h,num=1;
head=(Room *)malloc(sizeof(Room));head->peoplenum=0;q=head;while(i
{
for(j=1;j
{
p=(Room *)malloc(sizeof(Room));
p->roomlevel=i;p->roomnum=num++;
p->sex=-1;
for(h=0;hbed[h]=0;
q->next=p;
q=p;}
i++;}
p->next=NULL;
p->peoplenum=0;
return(head);}
void Init(Room *head){ Room *p;int i;p=head;while(p!=NULL){
p->peoplenum=0;
p->sex=-1;
for(i=0;i
p->bed[i]=0;
p=p->next;} printf(“nn
操作成功}
void Getin(Room *head){ Room *p;n”);
int i,s,lev,age;char name[10];int number=0;int bednumber=0;printf(“nn 欢迎使用订房系统
nn”);
printf(“请输入性别（1为男，2为女）：”);
scanf(“%d”,&s);printf(“nn 请输入想入住的房间等级：”);scanf(“%d”,&lev);p=head->next;while(p!=NULL){
if((p->roomlevel==lev)&&((p->sex==s)||(p->sex==-1))){
} for(i=0;i
if(p->bed[i]==0){
} if(number!=0)break;number=p->roomnum;bednumber=i+1;p->bed[i]=1;p->sex=s;p->peoplenum++;break;
} p=p->next;if(number==0&&bednumber==0)
else
{
head->peoplenum++;
printf(“n订单已下，请输入客人信息: n”);printf(“n 满客 n”);
printf(“名字:n”);scanf(“%s”,name);
printf(“年龄 :n”);scanf(“%d”,&age);
printf(“您的订单3:n”);
printf(“名字
年龄
性别
到达时间
房间等级
房间号
床位号n”);
if(s==1)
printf(“%s
%d
male
11-19
%d
%d
%dn”,name,age,p->roomlevel,p->roomnum,bednumber);
else
printf(“%s
%d
formale
11-19
%d
%d
%d n”,name,age,p->roomlevel,p->roomnum,bednumber);
}
printf(“n”);
}
void Checkout(Room *head){
Room *p;int number,bednumber,i,s;printf(“欢迎使用退房系统：”);printf(“nn 请输入房间号：”);scanf(“%d”,&number);printf(“nn 请输入性别（1为男，0为女）：”);scanf(“%d”,&s);printf(“请输入床位号：”);scanf(“%d”,&bednumber);p=head->next;while(p!=NULL){
if(p->roomnum==number)
for(i=0;i
roomlevel;i++)
if(i+1==bednumber){
p->bed[i]=0;p->peoplenum--;if(p->peoplenum
p->peoplenum=0;
}
}
}
if(p->peoplenum==0)
p->sex=-1;
printf(“您已退房，欢迎下次光临”);break;p=p->next;void Display(Room *head){
Room *p;int i=0;p=head->next;printf(“nn已订房间查询”);if(head->peoplenum==NULL){ printf(“所有等级房间空房”);
return;}
while(p->peoplenum!=NULL){ if(p->sex==1)
printf(“n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：男”,p->roomnum,p->roomlevel,p->peoplenum);
else
printf(“n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：女”,p->roomnum,p->roomlevel,p->peoplenum);
} void main(){
int n,k=1,i,roomlevel,room[10],bed[10],sum=0;
Room *head;
printf(“请输入房间等级数:n”);printf(“Roomlevel:”);scanf(“%d”,&roomlevel);for(i=1;i
{
printf(“n %d等级房间数:”,i);
} printf(“n”);p=p->next;
while(i
peoplenum)
if(p->bed[i]==1)
{
printf(“，已住床位号：%d”,i+1);
i++;
}
}
scanf(“%d”,&room[i]);printf(“n %d房间内床位数:”,i);
scanf(“%d”,&bed[i]);sum+=room[i]*bed[i];head=creat(roomlevel,room,bed);
while(k==1)
{
printf(“ n欢迎光临
:n”);
printf(“1:订房n2:退房n3:查询n4:退出系统n”);
printf(“请输入您的选择:n”);
scanf(“%d”,&n);
switch(n)
{
case 1: Getin(head);break;
case 2: Checkout(head);break;
case 3: Display(head);break;
case 4: k=0;break;
default : printf(“Error！please input again:”);break;
}
} }
题目7：文本文件单词的检索及计数（学时：6）
要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。
#include #include #include typedef struct StringWord { char ch[100];
}SW;
void CreatTextFile(){
char filename[10],ch;
FILE*fp;
printf(“请输入所用的文件名:”);scanf(“n%s”,filename);fp=fopen(filename,“w”);
printf(“请输入一段文字，以$号结束:n”);scanf(“%s”,&ch);
while(ch!='$'){
fwrite(&ch,sizeof(ch),1,fp);
} scanf(“%c”,&ch);
} fclose(fp);void CountWord(){
FILE *fp;SW S,T;char ch;char filename[10];
int i=0,number=0;
printf(“输入文本文件名：”);
scanf(“%s”,filename);fp=fopen(filename,“r”);
printf(“输入要统计计数的单词：”);
scanf(“%s”,T.ch);
while(!feof(fp)){ ch= fgetc(fp);
if(ch==' ')
{
if(i!=0){ S.ch[i]=' ';i=0;
}
}
} if(strcmp(S.ch,T.ch)==0)number++;else if(ch=='n'){
if(i!=0)
} else { }
S.ch[i]=ch;i++;{
S.ch[i]=' ';
i=0;
} if(strcmp(S.ch,T.ch)==0)number++;if(number==0)printf(“单词不在文本中 n”);else printf(“单词%s在文件%s中共出现了%d次:”,T.ch,filename,number);
fclose(fp);} void SearchWord(){ FILE*fp;SW S,T;char filename[10];
int i,i_r,line,flag=0;char ch;printf(“n输入文本文件名：”);
scanf(“%s”,filename);fp=fopen(filename,“r”);printf(“输入要统计计数的单词：”);
scanf(“%s”,T.ch);
i=i_r=0;line=1;while(!feof(fp)){ ch=fgetc(fp);
if(ch==' ')
{
if(i!=0)
{
i_r++;S.ch[i]=' ';
i=0;
if(strcmp(T.ch,S.ch)==0){
printf(“%s单词第一次出现是在n”,T.ch,line,i_r);
%d 行,%d列
flag=1;
break;
}
} }
else if(ch=='n')
{
if(i!=0)
{
i_r++;S.ch[i]=' ';
if(strcmp(T.ch,S.ch)==0){
printf(“%s单词第一次出现是在n”,T.ch,line,i_r);
flag=1;
break;
}
i=0;i_r=0;line++;
}
else
{
line++;i_r=0;
} }
else
{
%d 行,%d列
S.ch[i]=ch;i++;}
} if(flag==0)
printf(“%s单词不在文本中n”,T.ch);
fclose(fp);}
int main(){
} CreatTextFile();CountWord();SearchWord();
题目8：二叉树的遍历（学时：6）
二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。
#include #include #define M 100 typedef struct node//定义二叉树结点 { char data;struct node *lchild,*rchild;}BTNode;BTNode *CreatBTree()//创建二叉树(先序递归){ char ch;BTNode *b;scanf(“%c”,&ch);if(ch=='#')//递归结束控制符
b=NULL;else {
b=(BTNode *)malloc(sizeof(BTNode));
b->data=ch;
b->lchild=CreatBTree();//递归先序建立左子树
b->rchild=CreatBTree();//递归先序建立右子树
} return b;} void PreOrder(BTNode *b)//递归先序遍历二叉树函数 {
if(b!=NULL)
{
printf(“%c ”,b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
} } void InOrder(BTNode *b)//非递归中序遍历二叉树函数 { BTNode *stack[M],*p;int top=-1;if(b!=NULL){
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)//扫描p的所有左结点并入栈
{
top++;
stack[top]=p;
} p=p->lchild;if(top>-1){ p=stack[top];//出栈访问结点
top--;printf(“%c ”,p->data);
p=p->rchild;//扫描p的右结点
}
}
printf(“n”);} } void PostOrder(BTNode *b)//非递归后序遍历二叉树函数 { BTNode *stack[M],*p;int sign,top=-1;if(b!=NULL){
do
{
while(b!=NULL)// b所有左结点入栈
{
top++;
stack[top]=b;
b=b->lchild;
}
p=NULL;// p指向栈顶前一个已访问结点 sign=1;
//置b为已访问 while(top!=-1 && sign){ b=stack[top];//取出栈顶结点
if(b->rchild==p)//右孩子不存在或右孩子已访问则访问b {
printf(“%c ”,b->data);
top--;p=b;//p指向被访问的结点
} else {
b=b->rchild;//b指向右孩子结点
sign=0;//置未访问标记
}
}
}while(top!=-1);
printf(“n”);} } void change(BTNode *b)
//左右子树交换(递归){ BTNode *r;r=(BTNode *)malloc(sizeof(BTNode));int f1=0,f2=0;if(b==0)return;
//树为空时，跳出
if(b->lchild){
change(b->lchild);
r->lchild=b->lchild;
f1++;
//有左子树，符号位不为空
}
if(b->rchild){
change(b->rchild);
r->rchild=b->rchild;
f2++;
//有右子树，符号位不为空
} if(f1==0)r->lchild=NULL;
//否则，给中间变量赋空值
if(f2==0)r->rchild=NULL;if(f1||f2){
b->rchild=r->lchild;
//左右子树交换
b->lchild=r->rchild;} } int max(int m,int n){
} if(m>n)return m;else return n;int count(BTNode *b)
//计算树高(递归){
if(b==NULL)
return 0;else return(1+max(count(b->lchild),count(b->rchild)));}
int main()
{
BTNode *root = NULL;
printf(“-----------------二叉树的遍历-----------------nn”);
printf(“请按先序递归顺序创建二叉树(结束符 #):n”);
root = CreatBTree();
printf(“n递归先序遍历结果:n”);
PreOrder(root);
printf(“n非递归中序遍历结果:n”);
InOrder(root);
printf(“非递归后序遍历结果:n”);
PostOrder(root);
printf(“n树高: %dn”,count(root));printf(“n左右子树交换位置:”);
change(root);
printf(“n递归先序遍历结果:n”);
PreOrder(root);
printf(“n非递归中序遍历结果:n”);
InOrder(root);
printf(“非递归后序遍历结果:n”);
PostOrder(root);
return 0;
题目9：创建二叉排序树（学时：3）
二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。
#include #include
typedef struct node { int data;struct node *lchild ,*rchild;}BSTNode,*BSTTree;
//二叉排序树的插入（递归算法）void InsertBST(BSTTree *BST , int key){
} if((*BST)==NULL){
} else if((*BST)->data>key)//如果待插入的元素比根结点元素值小 InsertBST(&((*BST)->lchild),key);//插入在根结点的左子树(*BST)=(BSTNode*)malloc(sizeof(BSTNode));(*BST)->data=key;(*BST)->lchild=NULL;(*BST)->rchild=NULL;else InsertBST(&((*BST)->rchild),key);//插入在根结点的右子树上
//创建一棵二叉排序树 BSTTree CreateBSTTree(){
}
//中序遍历
void InOrder(BSTTree BST){
if(BST!=NULL){
} InOrder(BST->lchild);printf(“%5d”,BST->data);InOrder(BST->rchild);BSTTree bst=NULL;int x;while(1){
} return bst;
scanf(“%d”,&x);if(x==00)break;InsertBST(&bst,x);}
void main(){ BSTTree BST;
printf(“建立二叉排序树，请输入序列:n”);
BST=CreateBSTTree();
printf(“中序遍历后输出的该序列为:”);InOrder(BST);
printf(“n”);
}
题目10：霍夫曼编码应用（学时：3）
假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。
#include #include #include #define n 100 #define m 2*n-1 typedef struct { int weight;
char ch;
int parent,lchild,rchild;}HTNode;
typedef struct{ char ch;
char bits[n+1];
}CodeNode;
typedef struct { char cha;int number;}COUNTER;
int Init(HTNode ht[])//初始化函数，为每一个字母信息赋权值 {
int i,s=1;COUNTER counter[27];char ch;printf(“请输入字符：n”);scanf(“%c”,&ch);counter[1].cha='A';counter[2].cha='B';counter[3].cha='C';counter[4].cha='D';
counter[5].cha='E';counter[6].cha='F';counter[7].cha='G';counter[8].cha='H';counter[9].cha='I';counter[10].cha='J';counter[11].cha='K';counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16].cha='P';counter[17].cha='Q';
counter[18].cha='R';
counter[19].cha='S';counter[20].cha='T';counter[21].cha='U';counter[22].cha='V';counter[23].cha='W';counter[24].cha='X';counter[25].cha='Y';counter[26].cha='Z';for(i=1;i
switch(ch){ case 'A':counter[1].number++;break;case 'B':counter[2].number++;break;case 'C':counter[3].number++;break;case 'D':counter[4].number++;break;case 'E':counter[5].number++;break;case 'F':counter[6].number++;break;case 'G':counter[7].number++;break;case 'H':counter[8].number++;break;case 'I':counter[9].number++;break;case 'J':counter[10].number++;break;case 'K':counter[11].number++;break;case 'L':counter[12].number++;break;case 'M':counter[13].number++;break;case 'N':counter[14].number++;break;case 'O':counter[15].number++;break;
case 'P':counter[16].number++;break;
case 'Q':counter[17].number++;break;case 'R':counter[18].number++;break;case 'S':counter[19].number++;break;case 'T':counter[20].number++;break;case 'U':counter[21].number++;break;case 'V':counter[22].number++;break;case 'W':counter[23].number++;break;case 'X':counter[24].number++;break;
}
} case 'Y':counter[25].number++;break;case 'Z':counter[26].number++;break;} scanf(“%c”,&ch);for(i=1;i
} s=s-1;return s;if(counter[i].number!=0){
} ht[s].weight=counter[i].number;ht[s].ch=counter[i].cha;s++;
void select(HTNode ht[],int q,int *p1,int *p2)//select函数 {
int i,j,x=0,y=0;for(j=1;j
} if(ht[j].parent==0){
} x=j;break;for(i=j+1;i
} for(j=1;j
} for(i=j+1;i
if(ht[i].weight
//选出第二小结点 if(ht[j].parent==0&&x!=j){
} y=j;break;if(ht[i].weight
//选出最小结点
} } } if(x>y){
} else {
} *p1=x;*p2=y;*p1=y;*p2=x;void huffman_setup(HTNode ht[],int s){
int i,a;int p1,p2;a=2*s-1;for(i=1;i
if(i
}
} } ht[i].weight=0;ht[i].parent=ht[i].lchild=ht[i].rchild=0;for(i=s+1;i
//建立赫夫曼树 {
} select(ht,i-1,&p1,&p2);ht[p1].parent=i;ht[p2].parent=i;ht[i].lchild=p1;ht[i].rchild=p2;ht[i].weight=ht[p1].weight+ht[p2].weight;void huffman_show(CodeNode hc[],HTNode ht[],int s)//给字符编码 {
char q[n];int i,p,c,f;q[s-1]=' ';for(i=1;i
{
p=s-1;for(c=i,f=ht[i].parent;f;c=f,f=ht[f].parent){
}
}
if(ht[f].lchild==c){ } else { } q[--p]='1';q[--p]='0';strcpy(hc[i].bits,&q[p]);} hc[i].ch=ht[i].ch;//-----------------编码
void huffman_code(CodeNode hc[]){
int i=1;char ch,ah;printf(“请输入编码的信息：n”);scanf(“%c”,&ch);printf(“编码是：n”);while(ch!=' '){
ah=hc[i].ch;while(ch!=ah){
} i++;ah=hc[i].ch;printf(“%s”,hc[i].bits);scanf(“%c”,&ch);i=1;
} } //-----------------解码
void huffman_read(HTNode ht[],int s)//根据编码来返回字母信息 {
int i,j,t;char b;t=2*s-1;i=t;printf(“进行解码n”);fflush(stdin);scanf(“%c”,&b);printf(“解码后的信息是：n”);while(b!=' '){
if(b=='0')i=ht[i].lchild;else i=ht[i].rchild;if(ht[i].lchild==0){
}
}
} printf(“%c”,ht[i].ch);j=i;i=t;scanf(“%c”,&b);int main(){
int flag=1,choice;int s,i;HTNode ht[m];CodeNode hc[n];printf(“霍夫曼树：n”);s=Init(ht);huffman_setup(ht,s);huffman_show(hc,ht,s);for(i=1;i %sn“,hc[i].ch,hc[i].bits);
}
} printf(”请输入您想要进行的操作：n 1 编码n 2 解码n 3 退出n“);fflush(stdin);scanf(”%d“,&choice);switch(choice){
case 1:
huffman_code(hc);printf(”n“);break;
case 2:
}
huffman_read(ht,s);printf(”n");break;
case 3:
flag=0;return 0;题目11：关键路径寻找（学时：6）
对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。
#include #include
