数据结构经典习题目及c语言代码

精心整理

《数据结构》课程设计题目

（程序实现采用C语言）

题目1：猴子选王（学时：3）

一堆猴子都有编号，编号是L2,这群猴子（m个）按照-m的顺序围坐一圈，从第

1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，

则该猴子为大王。

要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。

〃链表

#include<stdio.h>

#include<stdlib.h>

〃链表节点

typedefstruct.RingNode

（

intpos;

struct_RingNode*next;

}RingNode,*RingNodePtr;

〃创建约瑟夫环，pHead:链表头指针，count:链表元素个数

voidCreateRing（RingNodePtrpHead,intcount）

（

RingNodePtrpCurr=NULL,pPrev=NULL;

-来源网络

inti=1;

pPrev=pHead;

while(-count>0)

(

pCurr^fRingNodePtrlmallocfsizeoffRingNode));

i++；

pCurr->pos=i;

pPrev->next=pCurr;

pPrev=pCurr;

)

pC<iir>next=pHeacQ/7构成环状链表

)

voidKickFromRing(RingNodePtrpHead,intn)

(

RingNodePtrpCurr,pPrev;

pCurr=pPrev=pHead;

while(pCurr!=NULL)

if(i==n)

〃踢出环

prirrtf「\n%d”,pCiir2pos);〃显示出圈循序

pPrev->next=pCurr->next;

free(pCurr);

pCurr=pPrev->next;

i=1;

)

pPrev=pCurr;

pCurr=pCurr>next;

if(pPrev==pCurr)

(

〃最后一个

prifitf「YiKingls%cF,pCtim>po$);/7显示出圈循序

free(pCurr);

break;

)

I++;

)

)

intmainf)

(

111^=0,111=0;

RingNodePtrpHead-NULL;

printf(l>M(personcount)=N);

a>M

scanf(%dr&in);

printf(nN(outnumber)-N);

scanf(N%dN,&nJ;

if(m<=0||n<=0)

(

printf("lnputError\nM);

returnO;

)

〃建立链表

pHead=(RingNo<fePtr)malloc(sizeof(RingNode)J;

pHead->pos=1;

pHead->next=NULL;

CreateRing(pHead,m);

〃开始出圈

printf(N\nKickOrder:");

KickFromRing(pHead,n);

system(Mpausen);

returnO;

)

〃数组做：

#indude<stdio.h>

#include<stdlib.h>

#include<string.h>

voidSelectKing(intMonkeyNum,intCallNum);

voidmainf)

(

in*MonkeyNum;

intCallNum;

/*输入猴子的个数*/

printf(NMonkeyNum=M);

scanf(ai%dN,&MonkeyNum);

/*输入M的值*/

printf(NCallNum=H);

scanf(n%dN,&CallNum);

SelectKing(MonkeyNum,CallNum);

)

voidSelectKing(intMonkeyNum,intCallNum)

(

int*Monkey$/申请一个数组，表示所有的猴子；

irrtcoimter=0/计数，当计数为猴子个数时表示选到最后一

个猴子了；

位置，数组的下标，轮流遍历数组进行报数;

inttoken=O^JS,将报数时数到M的猴子砍掉；

〃申请猴子个数大小的数组，把桌子摆上。

Monkeys=(int*Jmalloc(sizeof(int)*MonkeyNum);

if(NULL==MonkeysJ

(

printf("Somanymonkeys,systemerror.\n"J;

return;

)

"I各数组的所有内容初始化为0,被砍掉的猴子设置为1

memset(Monkeys,0,sizeof(int)*MonkeyNum);

〃循环，直到选中大王

while(counter!=MonkeyNum)

(

〃如果这个位置的猴子之前没有砍掉，那么报数有效

if(Monkeys[position]=-0]

(

token++〃成功报数一个，令牌+1,继续报数直到等于M

〃如果报数到M,那么将这个猴子砍去

if(token==CallNum)

(

M。nkey$[p。$iti<m]=1;//设置为1,表示砍去

coimter++以计数增加

token=0；/7设置为0,下次重新报数

〃如果是最后一个猴子，把它的位置打印，这个就是大王了

if(counter==MonkeyNum)

printf(NThekingisthe%clmonkey.\nn,position+1);

)

)

)

〃下一个猴子报数

position=(position+1)%MonkeyNum;

)

〃释放内存，开头为所有猴子创建的桌子

free(Monkeys);

return;

)

题目2：字符逆转(学时：3)

从键盘读入一个字符串，把它存入一个链表(每个结点存储1

个字符)，并按相反的次序将字符串输出到显示屏。

#include<stdio.h>

#include<stdlib.h>

structnode

structnode*prev;

chare;

structnode*next;

);

structnode*input(structnode*top|;

intmain(void)

(

structnodeT,*top=&T,*bottom=&T,*p=NULL;

T.prev=NULL;

T.next=NULL;

TcfCT;

bottom=input(top);

p=bottom->prev;

while(p!=NULL)

(

printf("%c"rp->c);

p=p->prev;

returnO;

structnode*input(structnode*top)

structnode**;

charx;

whileffx=getcharOJi=Vi1)

(

top->c=x;

t=(structnode*)malloc(sizeof(structnode));

top->next=t;

t->prev=top;

t->next=NULL;

top=top->next;

)

returntop;

)

题目3：工资核算(学时：3)

设有一个单位的人员工资有如下信息：name、departmentsbasepay、allowance^totalo现

从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数

据并给每个人的basepay增加100元，增加后将工资数据显示于屏幕(每行1人)。

#include<stdio.h>

#include<stdlib-h>

#defineSIZE2

#defineLENTHsizeof(structstuff)

structstuff

(

charnamef100];

chardepartmentf100];

intbasepay;

intallowance;

inttotal;

}stuff[SIZE];

main()

(

FILE*fp;

inti;

printf("Pleaseentemamedepartmentbasepayallowan

ce：\n"J;

for(i=0;i<SIZE;i++)

scanf(N%s%s%f%f>a,&stuff[i].name,&stuff[i].departmen

tr&stuff[i].basepayr&stuff[i].allowance);

if((fpsfopenfpaydata.clat11,"wb11))==NULL)

(

printf(MCanltopenfile\nM);

returnO;

)

for(i=0;i<SIZE;i++)

if(fwrite(&stuff[i]rLENTHr1,fp)!=1)

printf「文件写入出错\rH：

fclose(fp);

n>>nl>

if((fp=fopen(paydata.datrrb))==NULL)

(

printf(iaCanRtopenfile\nn);

)

prhitf「修改过后的结果：\n"J;

for(i=0;i<SIZE;i++|

fread(&stuff[i],LENTH,1,fp);

stuff[i].total=stuff[i].basepay+100+stuff[i].allowance;

printff"%-10s%-10s%f%f%f\nll,stuff[i].name,stuff[i].de

partment,stuff[i].basepay+100,stuff[i].allowance,stuff[i

J.total);

)

ffclose(fp);

returnO;

)

题目4：满足条件的有序表生成(学时：3)

己知三个有序表A、B、C,它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序

表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输

出有序表到屏幕的功能。

#include<stdio.h>

voidmainf)

(

inta[7],b[5]rc[6],d[7];

intijXVm;

printff^nPleaseenterZnumbersofA:11);

for(i=0;i<7;i++)

scanf(N%clN,&a[i]);

for(j=0J<6J++)

for(i=0;i<6v；i++)

lf(a[l]>a[l+lj)

{t=a[i];a[i]=a[i+l];a[i+

printf("thesortednumbers：\pn);

for(i=0;i<7;i++)

R

printf(%5d"ra[i]);

printf("\nPleaseenter5numbersofB:n);

for(i=0;i<5;i++)

scanf(n%dM,&b[i]|;

for(j=0J<4j++)

for(i=0;i<4j;i++)

if(b[i]>b[i+1])

{t=b[i];b[i]=b[i+1];b[i+

printfCthesortednumbersiXn");

for(i=0;i<5;i++)

printf(N%5dn,b[i]J;

printf("\nPleaseenter6numbersofC:");

for(i=0;i<6;i++)

scanf("%dN,&c[i]);

for(j=0J<5J++)

for(i=0;i<5-j;i++)

lf(C[l]>C[l+1]J

{t=c[i];c[i]=c[i+1];c[i+

printf("thesortednumbers：\nw);

for(i=0;i<6;i++)

printf「%5cT,c[iD：

for(i=0;i<5;i++)

(

for(j=0J<6J++)

(

if(b[i]==c[j])

(

for(k=0;k<7;k++)

(

if(b[i]==a[k]J

a[k]=m;

printf("\nBi);

k=0;

for(i=0;i<7;i++)

if(a[i]!=m)

(

d[K]=a[i];

k++;

)

print，「生成的有序表d为力

for(i=0;i<k;i++)

printf(N%4dR,d[i]);

printf("\n"J;

题目5：一元多项式的减法(学时：6)

设有两个一元多项式A(x),B(x),请完成运算A(x)+B(x)、A(x)-B(x),要求多项式采用链表进行

存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。

#include<stdio.h>

structPolynode

(

intcoef;

intexp;

Polynode*next;

}Polynode,*Polylist;

voidPolycreate(Polylisthead)

(

Polynode*rear,*s;

intc,e;

「请输入多项式的系数项和指数项

NM

scanf(%d,%dr&cr&e);

while(c!=O)

(

s=(Polynode*)malloc(sizeof(Polynode));

s->coef=c;

s->exp=e;

rear->next=s;

NN

scanf(%dr%<i,&c,&e);

)

rear->next=NULL;

)

voidPolyadd(PolylistpoIya,Polylistpolyb)

(

Polynode*p,*q,*tail,*temp;

intsum;

p=polya->next;

q=polyb->next;

tail=polya;

while(p!=NULL&&q!=NULL)

(

if(p>>exp<q->exp)

(

tail->next=p;

tail=p;

p=p->next;

elseif(p->exp=q->exp)

sumsp->coef+q->coef;

if(sum!=O)

(

p->coef=sum;

taik>next=p;

tail=p;

p=p->next;

temp=q;

q=q->next;

free(temp);

)

else

temp=p;

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;

voidPolysubstract(Polylistpolya,Polylistpolyb)

Polylisth=polyb;

Polylistp=pb->next;

Polylistpd;

while(pj

{p->coef*=-l;

p^p^next;

)

pd=Polyadd(parh);

for(p=h->next;p;p=p->next)

p->coef*=-1;

returnpd；

)

voidPrintPolyn(PolynP)

voidprintfPolyn(Polynode*head)

(

Polynode*p=head->next;

while(p)

{printf(ia%dxA%dN,p->coef,p->exp);

if(p->next)

printf(w+ii);p=p->next:}

intmainf)

Polynode*La,Lb;

LasPolycreate();

LbBPolycreate();

PrintPolyn(La);

printf(7n-J;

PrintPolyn(Lb);

printf(7nn);

Polyadd(polyarpolyb);

printPolyn(polya);

returnO;

题目6：床位分配(学时：6)

某客店有N个等级的房间，第k级客房有A(k)个，每个房间有B(k)个单人床，以菜单调

用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、

年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不

更改等级，印出“满客”提示。

#indude<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<string.h>

#defineN3

typedefstructRoom

(

introomlevel;

introomnum;

intbednum;

intpeoplenum;

intbed[N];

intsex;

charnamef10];

structRoom*next;

}Room;

Room*creat(introomlevel,introom[],intbed[])

(

Room*head,*p,*q;

inti=1j,h,num=1;

head=(Room*)malloc(sizeof(Room));

head->peoplenum=0;

q=head;

while(i<=rooinlevel)

for(j=1J<=room[i]a++)

(

p=(Room*)malloc(sizeof(Room));

p->roomlevel=i;p->roomnum=num++；p->peoplenuin=

for(h=O;h<bed[i];h++)p->bed[h]=O;

q->next=p;

q=p；

i++；

p->next=NULL;

return(head);

voidlnit(Room*head)

Room*p;

inti;

p=head;

while(p!=NULL|

p->peoplenum=0;

for(i=0;i<N;i++)

p->bed[i]=O;

p=p->next;

printff^nXn操作成功\n-)：

voidGetin(Room*head)

Room*p;

inti,s,lev,age;

charnamef10];

intnumber=0;

intbednumber=O;

printff^nyi欢迎使用订房系统

printf「请输入性别(1为男，2为女)

scanf("%d",&s);

prbrtf("\n\n请输入想入住的房间等级：)

scanf(N%cl",&lev);

p=head->next;

while(p!=NULL)

(

ff((p->roomlevel==lev)&&((p->sex—s)11(p->sex=-1)))

(

for(i=0;i<lev;i++)

if(p->becl[i]==0)

number=p->roomnum;

bednumber=i+1；

p->bed[i]=1;

p->sex=s;

p->peoplenum++;

break;

)

if(number!=0)break;

)

p=p->next;

)

if(number==O&&bednumbers=O)

printf(BI\n满客

else

(

head->peoplenum++;

printf("\n订单已下,请输入客人信息:\fT);

printf名^:\n");scanf(N%sN,name);

printf(N^^:\nu);scanf(n%dN,&age);

prlntf「您的订单3:\n-J;

printf「名字年龄性别到达时间房间等级房间号床位号

\F；

printf("%s%dmale11-19%d%d%d\n",name,age,f»->roo

mlevelrp->roomnum,bednumber);

else

printf("%s%dformale11-19%d%d%d\nR,name^ge,p->r

oomlevel,p->roomnum,bednumber);

printfCXn")；

)

)

voidCheckout(Room*head)

(

Room*p;

intnumber,bednumber,i,s;

prhrtf「欢迎使用退房系统：

printf(N\n\n请输入房间号：

scanf(N%cln,&number);

printf「\n\ii请输入性别(1为男，0为女)：十

scanf(N%dN,&s);

printf「请输入床位号：

scanf(n%dn,&bednumber);

p-head^next;

while(p!=NULL)

(

if(p->roomnum==number)

for(i=0;i<p->roomlevel;i++)

if(i+l==bednumber)

(

p->bed[i]=O;

p->peoplenum-;

if(p->peoplenum<0)

p->peoplenum=0;

if(p->peoplenum==01

printf「您已退房，欢迎下次光临十

break;

p=p->next;

voidDisplay(Room*headJ

(

Room*p;

inti=O;

p=head->next;

prin叫"\n\ri已订房间查询力

if(head->peoplenum==NULLJ

(

pilntf「所有等级房间空房下

return;

)

while(p->peoplenum!=NULL|

if(p>>sex==1)

prhitfr\n房间号：%d,房间等级：%d,已住人

数：%d,住房人性别：男

n

,p->roomnum,p->roomlevelrp->peoplenum);

else

prMtfr\n房间号：%d,房间等级：%d,已住人

数：%d,住房人性别：女

N

,p->roomnumrp->roomlevel,p->peoplenum);

while(i<p->peoplenum)

if(p->bed[i]»1)

(

printf(",已住床位号：

i++；

)

p=p->next;

voidmainf)

intn,k=1,i,roomlevel,room[10],bed[10],sum=O;

Room*head;

prhitf「请输入房间等级数:\n");

nllRn

printf(Roomlevel:);scanf(%dr&roomlevel);

for*1;i<=roomlevel;i++)

(

printf("\n%cl等级房间数

scanf(N%clR,&rooiii[i]);

printf(N\n%d房间内床位数

$canf「%cr,&bed[i])：

sum+=room[i]*bed[i];

)

head=creat(roomlevel,room,becl);

while(k»1)

(

printf("\n欢迎光临

printf("1:订房ViZ:退房\n3:查询退出系统\rT];

printf「请输入您的选择:\n)

scanf(N%dN,&n);

switch(n)

case1:Getin(head);break;

case2:Checkout(head);break;

case3:Display(head);breal<;

case4:k=0;break;

default:printf("Error!!pleaseinputagain:>a);breal<;

题目7：文本文件单词的检索及计数（学时：6）

要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小

写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首

次出现的行号及位置。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedefstructStringWord

（

charch[100];

}SW;

voidCreatTextFilef}

charfilenamef10],ch;

FILE*fp;

printf「请输入所用的文件名:十

scanf(n\n%s",filename);

N

fp=fopen(filenamer"w);

prlntf「请输入一段文字，以$号结束

scanf("%sn,&ch);

while(ch!=$f)

(

fwrite(&ch,sizeof(ch)r1,fp);

nH

scanf(%cr&ch);

)

fclose(fp);

)

voidCountWordfJ

FILE*fp;

SWSrT;

charch;

charfilenamef10J;

inti=O,number=O;

printf「输入文本文件名：

scanf("%s"rfilename);

fp=fopen(filename,"rM);

prhitf「输入要统计计数的单词："];

M

scanf("%srT.ch);

while(!feof(fp))

(

ch=fgetc(fp);

(

S-ch[i尸\p'；

i=0;

iffstrcmp(S.ch,T.ch)==O)

number++;

(

if(i!=O)

(

S.ch[i]='\pK;

1=0;

if(strcmp(S.ch,T.ch)==O)

number++;

else

S.ch[iJ=ch;i++;

if(number==0)

printf「单词不在文本中\n[

else

printf「单词％$在文件%s中共出现了%d

^:",T.ch,filename,nuinber);

fclose(fp);

)

voidSearchWordf)

(

FILE*fp;

SWS.T;

charfilenamef10];

inti,i_r,line,flag=O;

charch;

printf(N\n输入文本文件名：M);

scanff^s^filename);

fp=fopen(filename,"rw);

piintfr输入要统计计数的单词：6

scanff^^T-ch);

l=i_r=O;

Iine=1;

while(!feof(fp)J

ch=fgetc(fp);

if(ch==IB)

(

if(i!=O)

(

Lr++；S-ch[l]='\Oi;

i=0;

if(strcmp(T.ch,S.ch)==O)

(

printf(N%s单词第一次出现是在%d行序d列

\n-zT.chJinerLr);

flag=1;

break;

elseiffchss'Xn1)

if(i!=O)

(

i_r++;S.ch[i]=,\O1;

if(strcmp(T.ch,S-ch)==O)

(

printf("%s单词第一次出现是在%<1行,%d列

\n"rT.chrlineri_r);

flag=1;

break;

)

i=O;i_r=O;line++;

)

else

line++;Lr=O;

else

S.ch[i]=ch;i++;}

)

if(flag==O)

printf(N%s单词不在文本中VCTdi)：

fclose(fp);

)

intmainf)

(

CreatTextFilef);

CountWordf);

SearchWordf);

)

题目8：二叉树的遍历(学时：6)

二叉树以Ison-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出

前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中

序、后序的遍历运算要求采用非递归方式。

#include<stdio.h>

#include<stdlib.h>

#defineM100

typedefstructnodW定义二叉树结点

chardata;

structnode*lchild,*rchild;

JBTNode;

BTNode*CreMBTree(]〃创建二叉树(先序递归)

(

charch;

BTNode*b;

scanf(N%cN,&ch);

jf(ch==#l//递归结束控制符

b=NULL;

else

(

b=(BTNode*)malloc(slzeof(BTNocle));

b->data=ch;

b">lch"d=C：reatBTree0；/7递归先序建立左子树

2rctiilcf=C：reatBTree()；/7递归先序建立右子树

)

returnb;

v。idPre。rde“BTN。d寸bl〃递归先序遍历二叉树函数

if(b!=NULL)

printf("%cN,b->data);

PreOrder(b->lchild);

PreOrder(b->rchild);

)

)

voIdlnOrder(BTNodybl//非递归中序遍历二叉树函数

(

BTNode*stack[M],*p;

inttop=-1;

if(b!=NULL)

(

p=b；

whlle(top>-1||p!=NULL)

(

whilHpyNULL]//扫描p的所有左结点并入栈

(

top++;

stack[top]=p;

p=p->lchild;

)

if(top>-1>

pnstack[top]；/7出栈访问结点

top";

printf("%cn,p->data);

p=p»>rchiW〃扫描p的右结点

)

)

printfC\n");

)

)

丫。1<«>06*。「€15伸1^。<1。*1>]〃非递归后序遍历二叉树函数

(

BTNode*stack[M],*p;

intsign,top="1;

lf(b!=NULL)

(

do

(

while(b!=N<JLL)//b所有左结点入栈

(

top++;

stack[top]=b;

b=b->lchild;

p=NULI^/7p指向栈顶前一个已访问结点

sign=1/置b为已访问

while(top!=-1&&sign)

(

b=stack[top]^y^出栈顶结点

ff(l>>rchikl==p)/7右孩子不存在或右孩子已访问则访

问b

printf(R%cN,b->data);

top-;

P=b;〃p指向被访问的结点

b=b->rchild^yb指向右孩子结点

sign=O〃置未访问标记

)

}while(top!=-f);

printff-Xn");

)

voidchange(BTNode*bl/7左右子树交换(递归)

BTNode*r;

r»(BTNode*)malloc(sizeof(BTNode));

intf1=0,f2=0;

if(b==OWetum/树为空时，跳出

if(b-»child|

(

change(b->lchild);

r>lchild=b->lchil<l:

□++;〃有左子树，符号位不为空

)

if(b->rchild)

(

change(b->rchlld);

r->rchild=b->rchild;

f2++"右子树，符号位不为空

)

if伊1==012Ich"cf=NULL"否则，给中间变量赋空值

if(f2==0)r>rchild=NULL;

»(«!!«)

加＞rchi1d=2JcliAd;〃左右子树交换

b->lchild=r>rchild;

intmax(intm,intn)

(

returnm;

elsereturnn;

)

irrtcotirrt(BTNo<le*bl/7计算树高(递归)

(

if(b==NULL)

returnO;

elsereturnf1+max(count(b->lchild),count(b->rchilcl)));

)

intmainf)

(

BTNode*root=NULU

printf("------------二叉树的遍历---------\n\n"J;

prhitf「请按先序递归顺序创建二叉树［结束符川:

root=CreatBTree();

printf("\n递归先序遍历结果

PreOrder(root);

printf("\n非递归中序遍历结果

InOrderfrootJ;

printfr啡递归后序遍历结果zn：

PostOrder(root);

printf("\nWiW：%d\nn,count(root));

printf("\n左右子树交换位置门；

change(root);

prlntf(N\n递归先序遍历结果:'n1');

PreOrder(root);

printf("\n非递归中序遍历结果

InOrder(root);

prbitf「非递归后序遍历结果:

PostOrder(root);

returnO;

题目9：创建二叉排序树(学时：3)

二叉排序树以l$omr$on链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立

完立即在屏幕显示中序遍历结果的程序。

#include<stdio.h>

#include<stdlib.h>

typedefstructnode

(

intdata;

structnode*lchild,*rchild;

}BSTNoder*BSTTree;

〃二叉排序树的插入(递归算法)

voidlnsertBST(BSTTree*BST,intkey)

if((*BST)==NULL)

(

(*BST)=(BSTNode*)malloc(sizeof(BSTNode));

(*BST)->data=key;

(*BST)->lchild=NULL;

(*BST)->rchild=NULL;

)

如果待插入的元素比根结点元

素值小

lnsertBST(&(「B$T)OIchi呵Jcey)力插入在根结点的

左子树

else

lnsertBST(&(「B$T)Orchild),key);/7插入在根结点的

右子树上

〃创建一棵二叉排序树

BSTTreeCreateBSTTreef)

BSTTreebst=NULL;

intx;

whilefl)

(

scanf(N%dN,&x);

if(x==OO)break;

InsertBSTf&bst,x);

)

returnbst;

)

〃中序遍历

voidlnOrder(BSTTreeBST)

(

if(BST!=NULL)

lnOrder(BST->lchild);

printf(n%5clN,BST->data);

lnOrder(BST->rchild);

)

)

voidmainf)

(

BSTTreeBST;

prkitfE建立二叉排序树，请输入序列:

BST=CreateBSTTree();

printf「中序遍历后输出的该序列为"

InOrder(BST);

printf(-yi-);

}

题目10：霍夫曼编码应用(学时：3)

假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功

能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。

#indude<stdio.h>

#include<malloc.h>

#include<string.h>

#definen100

#definem2*n-1

typedefstruct

(

intweight;

charch;

intparent,lchildrrchild;

JHTNode;

typedefstruct{

charch;

charbits[n+l]；

}CodeNode;

typedefstruct

(

charcha;

intnumber;

JCOUNTER;

imirm(HTNodehq]l/7初始化函数，为每一个字母信息赋权

值

intirs=1;

COUNTERcounter[27J;

charch;

prirrtf「请输入字符：\nM);

scanf(n%c\&ch);

counterf1J.cha='A';

counter[2].cha=tBK;

counter[3].cha=>Ca;

counter[4].cha="D>;

counterfSJ.cha='E1;

KK

counter[6]acha=F;

counter[7].cha=>Gl;

counter[8].cha=BHv;

counter[9].cha=T;

counter[10].cha=lJv;

counter[11].cha='K';

counter[12].cha='L';

counter[1刃

counter[14]acha="N";

counterf15].cha='O";

counter[16].cha=>PR;

counterf1ZJ.cha='Q1;

counter[18].cha='R';

counterf19].cha='Si;

counter[20].cha=lTa;

counter[2IJ.chas'U1;

counter[22].cha=tV;

counter[23].cha=KWK;

cotmter[24]・ctia='X'：

counterfZSJ.chasY;

counter[26].cha=aZ";

for(i=1;i<=26;i++)

counter[i].number»0;

while(ch!=v>)

(

switch(ch)

case'A^counterf1].number++；break;

caseaBB:counter[2].number++；breal<;

caseaC>:counter[3].number++；break;

caseaDv:counter[4].number++；brealc;

case>El:counter[5].number++;break;

case>Fl:counter[6].number++;break;

case'G>:counter[7].number++；breal<;

case"Hl:counter[8].number++；break;

case>ll:counter[9].number++；break;

caseU'scounterf10].number++；break;

case'K'zcounterf11].number++；break;

caseX^counterf12].number++；break;

case'M'xounterf13].number++；break;

case'N'zcounterf14].number++；break;

caseaOR:counter[15].number++；break;

caseP'zcounterf16].number++；break;

case'Q^counterf17].number++;break;

caseaRB:counter[18].number++；breal<;

case'S'zcounterf19].number++；break;

case>T>:counter[20].number++；break;

caseaUR:counter[21].number++；break;

caseVl:counter[22].number++；brealc;

caselW>:counter[23].number++；break;

case>Xl:counter[24].number++;break;

caselY1:counter[25].number++;brealc;

case>Z>:counter[26].number++；break;

)

scanf("%cai,&ch);

)

for(i=1;i<=26;i++)

(

if(counter[i].number!=OJ

(

ht[s].weight=counter[i].number;

ht[s].ch=counter[i].cha;

s++；

returns;

voidselect(HTNodeht[],intq,int*p1,int*p2]//select函

数

(

intij,x=O,y=O;

for(j=1j<=q;++j)

(

if(ht[j].parent==O)

(

X寸

break;

)

)

for(i=^j+1;i<=q;++i)

(

if(ht[i].weight<ht[x].weight&&ht[i].parentssO)

选出最小结点

for(j=1a<=q;++j)

if(ht[j].parent==O&&x!寸

(

y寸

break;

)

)

for(i^j+1;i<=q;++i)

(

if(ht[i].weight<ht[y].weight&&ht[i].parent==O&&x!=i)

(

选出第二小结点

*pi=y;

else

(

*pl=X；

*p2=y;

)

)

voidhuffman_setup(HTNodeht[],ints)

(

intLa：

intp1rp2;

a=2*s-l;

ffor(i=1;K=a;l++)

if(i<=s)

ht[i].weight=ht[i].weight;

else

(

ht[i].weight=O;

)

ht[i].parent=ht[i].lchild=ht[i].rchild=O;

)

建立赫夫曼树

(

select(htrM,&p1,&p2);

ht[p1].parent=i;

ht[p2].parent=i;

ht[i].lchild=p1;

ht[i].rchild=p2;

ht[l].weight=ht[p1].weight+ht[p2].weight;

voidhuffman_show(CodeNodehc[],HTNodeht[],ints]/

/给字符编码

(

charqfn];

q[s-1J=\0';

for(i=l;i<=s;i++)

(

P=S-1；

for(c=i,f=ht[i].parent;f;c=f,f=ht[f].parent)

(

lf(ht[q.lchlld»c)

(

q[-p]='O';

)

else

q[-p]=T：

strcpy(hc[i].bits,&q[p]J;

hc[i].ch=ht[i].ch;

)

)

//---------编码

voidhuffman.code(CodeNodehc[J)

(

inti=1;

charcti,ah;

print,「请输入编码的信息：\n"j;

NH

scanf(%cr&ch);

printf「编码是：'ll11);

while(ch!=ia)

(

ah=hc[l].ch;

while(ch!sah)

i++；

ah=hc[i].ch;

)

printf("%s",hc[i].bits);

scanf("%c>B,&ch);

i=1;

)

)

//---------解码

voidhiiffinan_roacl(HTNocfeti肛ints]〃根据编码来返回

字母信息

(

intij,t；

charb;

t=2*s-1;

i=t；

进行解码\116

ffflush(stdin);

print,「解码后的信息是：

while(b!=vl)

涮b=='(H

i=ht[i].lchild;

elsei-htfij.rchild;

if(ht[i].lchild=»O)

(

printf(a%cn,ht[i].ch);

j=i；

i=t;

)

a>

scanf("%cr&b);

)

)

intmainf)

(

intflag=1,choice;

ints,i;

HTNodeht[m];

CodeNodehc[n];

printf「霍夫曼树:\n"J;

huffman.setup(ht,s);

huffman_show(hc,ht,s);

for(i=1;i<=s;i++)

(

)

while(flag)

(

printer请输入您想要进行的操作：\n1编码中2解码\n3

退出\iT)；

fflushfstdin);

scanf(N%dN,&choice);

switch(choice)

(

easel:

huffman.code(hc);

printf("\n"J;

break;

easel:

huffman_read(ht,s);

printf("\n"J;

break;

case3:

flag=O;

)

)

returnO;

)

题目11：关键路径寻找(学时：6)

对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程

序。

#indude<malloc.h>

#include<stdio.h>

stnictNodW邻接点

Intvex”顶点信息

Mtweigh场7权值

structNode*next;

);

stnictHn。。旬/头结点

(

intvex2;

Mti%/入度

structNode*link;

}A[20J;

voidcreate(structHnodeA[20],intnrinte)

(

inti^KI;

structNode*p;

for(i=1：i<=n：i++j/7建立顶点表

(

A[i].vex2=l;

A[i].id=O;

A[i].link=NULL;

for(k=1;k<=e;k++l//建图

printf("\n请输入边及其权值:\11力

scanf(N%d",&i);

scanf(N%d",&j);

scanf("%dN,&l);

p=(structNode*)malloc(sizeof(structNode)J;

p->vex^j;

p->weight=l;

p->next=A[i].link;

A[i].link=p;

)

fo