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

（完整版）数据结构经典题目及c语言代码《数据结构》课程设计题目（程序实现采用C语言）题目1:猴子选王（学时：3）一堆猴子都有编号，编号是1,2,3.。5，这群猴子（m个）按照1-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二（RingNodePtr）malloc（sizeof（RingNode））;i++；（完整版）数据结构经典题目及c语言代码pCurr—〉pos=i;pPrev-〉next=pCurr;pPrev=pCurr;)pCurr-〉next二pHead;//构成环状链表}voidKickFromRing(RingNodePtrpHead,intn)(RingNodePtrpCurr,pPrev;inti=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("\nKingis%d",pCurr一〉pos); //显示出圈循序free(pCurr);break;)i++;（完整版）数据结构经典题目及c语言代码intmain(){intn二0,m=0;RingNodePtrpHead二NULL;printf("M(personcount)二”)；scanf("%d",&m);printf("N(outnumber)=");scanf(”%d”,&n);if(m〈二0||n<=0){printf("InputError\n")；return0;)//建立链表pHead二(RingNodePtr)malloc(sizeof(RingNode));pHead->pos=1;pHead->next=NULL;CreateRing(pHead,m);//开始出圈printf("\nKickOrder: ");KickFromRing(pHead,n);printf("\n");system(”pause”);return0;)〃数组做：#include<stdio。h〉#include〈stdlib。h〉（完整版）数据结构经典题目及c语言代码#include<string.h>voidSelectKing(intMonkeyNum,intCallNum)；voidmain()(intMonkeyNum；intCallNum；/*输入猴子的个数大/printf("MonkeyNum=")；scanf("%d",&MonkeyNum);/*输入M的值*/printf("CallNum=")；scanf("%d",&CallNum)；SelectKing(MonkeyNum,CallNum)；}voidSelectKing(intMonkeyNum,intCallNum)(int*Monkeys;//申请一个数组，表示所有的猴子；intcounter=0；//计数，当计数为猴子个数时表示选到最后一个猴子了；intposition=0；//位置，数组的下标，轮流遍历数组进行报数；inttoken=0；//令牌，将报数时数到M的猴子砍掉；//申请猴子个数大小的数组，把桌子摆上。Monkeys=(int*)malloc(sizeof(int)*MonkeyNum)；if(NULL=Monkeys)(printf("Somanymonkeys,systemerror.\n")；(完整版)数据结构经典题目及c语言代码return;)//将数组的所有内容初始化为0,被砍掉的猴子设置为1memset(Monkeys，0，sizeof(int)*MonkeyNum);//循环，直到选中大王while(counter!=MonkeyNum)(//如果这个位置的猴子之前没有砍掉，那么报数有效if(Monkeys[position]=0){token++;//成功报数一个,令牌+1,继续报数直到等于M〃如果报数到凶，那么将这个猴子砍去if(token二二CallNum){Monkeys[position]=1；//设置为1,表示砍去counter++;//计数增加token=0;//设置为0,下次重新报数//如果是最后一个猴子，把它的位置打印，这个就是大王了if(counter=MonkeyNum)(printf("Thekingisthe%dmonkey.\n",position+1);}))//下一个猴子报数position二(position+1)%MonkeyNum;（完整版）数据结构经典题目及c语言代码//释放内存,开头为所有猴子创建的桌子free(Monkeys)；return；)题目2:字符逆转(学时：3)从键盘读入一个字符串，把它存入一个链表(每个结点存储1个字符)，并按相反的次序将字符串输出到显示屏。#include<stdiooh>#include<stdlib.h〉structnode(structnode*prev;charc;structnode*next;)；structnode*input(structnode*top);intmain(void){structnodeT,*top=&T,*bottom=&T,*p=NULL；Toprev=NULL；T.next=NULL;T.c二,\0'；bottom=input(top);p=bottom—>prev;while(p!=NULL)(printf("%c”,p->c);p=p一〉prev;return0;（完整版）数据结构经典题目及c语言代码}structnode*input(structnode*top){structnode*t;charx;while((x二getchar())!=’\n')top->c=x;t=(structnode*)malloc(sizeof(structnode));top->next=t;t->prev=top;t->next=NULL；t—>c='\0'；top=top—〉next;)returntop;}题目3:工资核算(学时：3)设有一个单位的人员工资有如下信息：name、department、basepay、allowance、totalo现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的basepay增加100元，增加后将工资数据显示于屏幕(每行1人)。#include〈stdio。h〉#include<stdliboh〉#defineSIZE2#defineLENTHsizeof(structstuff)structstuff（完整版）数据结构经典题目及c语言代码charname[100];chardepartment[100];intbasepay;intallowance;inttotal;}stuff[SIZE]；main()(FILE*fp；inti;printf("Pleaseenternamedepartmentbasepayallowance:\n");for(i=0;i〈SIZE;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'topenfile\n");return0;}for(i=0;i〈SIZE;i++)if(fwrite(&stuff[i],LENTH,1,fp)!=1)printf("文件写入出错\门");fclose(fp);if((fp=fopen("paydata.dat","rb"))==NULL)(printf("Can'topenfile\n");}printf("修改过后的结果：\n");for(i=0;i<SIZE;i++)(fread(&stuff[i],LENTH,1,fp)；stuff[i].total二stuff[i].basepay+100+stuff[i].allowance;(完整版)数据结构经典题目及c语言代码printf(" ％—10s%—10s %f%f%f\n”,stuff[i] .name,stuff[i].department,stuff[i].basepay+100,stuff[i].allowance,stuff[i]ototal);}fclose(fp);return0;}题目4:满足条件的有序表生成(学时：3)已知三个有序表A、B、。，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表0:排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。#include<stdio。h>voidmain()(inta[7],b[5],c[6],d[7];inti,j,k,t,m;printf("\nPleaseenter7numbersofA:“)；for(i=0；i<7；i++)scanf("%d",&a[i]);for(j=0;j<6;j++)for(i=0;i<6-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}printf("thesortednumbers:\n")；for(i=0;i〈7;i++)printf("%5d",a[i]);printf("\nPleaseenter5numbersofB:");for(i=0;i<5;i++)scanf("%d",&b[i]);printf("\n");for(j=0;j<4;j++)for(i=0;i<4-j;i++)（完整版）数据结构经典题目及c语言代码if(b[i]>b[i+1]){t=b[i];b[i]=b[i+l];b[i+1]=t;}printf("thesortednumbers:\n")；for(i=0;i〈5；i++)printf("%5d",b[i]);printf("\nPleaseenter6numbersofC:");for(i=0;i〈6；i++)scanf("%d”,&c[i]);for(j=0;j<5;j++)for(i=0;i〈5-j；i++)if(c[i]>c[i+1]){t=c[i];c[i]=c[i+l];c[i+1]=t；}printf("thesortednumbers:\n")；for(i=0;i〈6；i++)printf("%5d",c[i]);printf("\n");for(i=0；i<5;i++)(for(j=0；j<6；j++){if(b[i]=c[j]){for(k=0；k〈7;k++){if(b[i]==a[k])a[k]=m;}}}printf("\n");（完整版）数据结构经典题目及c语言代码k=0；for(i=0;i〈7；i++)if(a[i]!=m)(d[k]=a[i];k++;)printf("生成的有序表d为")；for(i=0;i〈k;i++)printf("％4d",d[i]);printf("\n")；)题目5:一元多项式的减法(学时：6)设有两个一元多项式A(x),B(x),请完成运算A(x)+B(x)、A6)—8a)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能.#include〈stdio。h>structPolynode(intcoef;intexp;Polynode*next;}Polynode,*Polylist;voidPolycreate(Polylisthead){Polynode*rear,*s;intc,e;rear=head;printf(”请输入多项式的系数项和指数项”)；scanf("%d,%d",&c,&e);while(c!=0){（完整版）数据结构经典题目及c语言代码s二(Polynode*)malloc(sizeof(Polynode));s-〉coef=c;s―〉exp=e；rear-〉next=s；rear二s；scanf("％d，%d",&c,&e);)rear-〉next=NULL;}voidPolyadd(Polylistpolya,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){sum=p-〉coef+q一〉coef;if(sum!=0){p一〉coef=sum;tail一>next=p;tail=p;（完整版）数据结构经典题目及c语言代码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;elsetail-〉next=q；}voidPolysubstract(Polylistpolya,Polylistpolyb){Polylisth=polyb;Polylistp=pb一>next;Polylistpd；while(p)（完整版）数据结构经典题目及c语言代码{p—〉coef*二一1;p=p->next;)pd二Polyadd(pa,h);for(p=h—>next;p;p=p->next)p->coef*=-1;returnpd;)voidPrintPolyn(PolynP)voidprintfPolyn(Polynode*head){Polynode*p=head一〉next;while(p){printf("%dx^%d",p一〉coef,p->exp);if(p-〉next)printf(”+");p=p一>next;}}intmain(){Polynode*La,Lb;La二Polycreate();Lb二Polycreate();PrintPolyn(La);printf("/n”)；PrintPolyn(Lb);printf("/n”);Polyadd(polya,polyb);printPolyn(polya);return0;(完整版)数据结构经典题目及c语言代码题目6:床位分配(学时：6)某客店有N个等级的房间，第k级客房有A(k)个，每个房间有B(k)个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。#include〈stdio。h>#include<stdliboh〉#include<conio.h〉#include〈string。h>#defineN3typedefstructRoom{introomlevel;introomnum;intbednum;intpeoplenum;intbed[N]；intsex;charname[10];structRoom*next;}Room;Room*creat(introomlevel,introom[],intbed[])(Room*head,*p,*q;（完整版）数据结构经典题目及c语言代码inti=1,j,h,num=1;head=(Room*)malloc(sizeof(Room));head—>peoplenum=0；q=head；while(i<=roomlevel){for(j=1;j〈=room[i];j++){p=(Room*)malloc(sizeof(Room));P-〉roomlevel=i;p—>roomnum=num++; p—>peoplenum=0;p—>sex=-1;for(h=0;h<bed[i];h++) p—>bed[h]=0;q—>next=p;q=p;}i++;}p—>next=NULL;return(head);}voidInit(Room*head)(Room*p;inti;p=head;while(p!=NULL)(p—>peoplenum=0;p—>sex=-1;（完整版）数据结构经典题目及c语言代码for(i=0；i〈N；i++)p—>bed[i]=0;p=p->next;}printf("\n\n操作成功\n”);)voidGetin(Room*head)(Room*p;inti,s,lev,age;charname[10];intnumber=0;intbednumber=0;printf(”\n\n欢迎使用订房系统\n\n");printf(“请输入性别(1为男，2为女)：”)；scanf("%d",&s);printf("\n\n请输入想入住的房间等级：”)；scanf("%d",&lev);p=head-〉next;while(p!=NULL)(if((p-〉roomlevel==lev)&&((p->sex=s)||(p-〉sex==-1)))(for(i=0;i〈lev;i++)if(p—>bed[i]=0)(number=p-〉roomnum;bednumber=i+1;p—>bed[i]=1;（完整版）数据结构经典题目及c语言代码p->sex=s;p―〉peoplenum++;break;)if(number！=0)break;}p=p->next;}if(number=0&&bednumber=0)printf("\n满客\n”)；else(head-〉peoplenum++;printf("\n订单已下，请输入客人信息：\n”)；printf("g字：\n");scanf("%s"，name);printf("年龄：\n”)；scanf("%d",&age);printf("您的订单3:\n");printf("名字 年龄性别到达时间 房间等级 房间号床位号5”)；if(s==1)printf("％s %d male 11-19 %d %d %d\n"，name,age,p-〉roomlevel,p->roomnum,bednumber);elseprintf( "％s %d formale11-19 %d %d %d\n"，name,age,p一)roomlevel,p->roomnum,bednumber);printf("\n");)（完整版）数据结构经典题目及c语言代码voidCheckout(Room*head){Room*p；intnumber，bednumber，i，s；printf("欢迎使用退房系统：”)；printf(”\n\n请输入房间号：”)；scanf("%d",&number)；printf(”\n\n请输入性别(1为男，0为女)：”)；scanf("%d",&s);printf("请输入床位号：“)；scanf(”%d”,&bednumber)；p=head->next；while(p!=NULL)(if(p-〉roomnum==number)for(i=0；i<p->roomlevel；i++)

if(i+1==bednumber){p->bed[i]=0；p-〉peoplenum ；if(p->peoplenum〈0)p-〉peoplenum=0；if(p->peoplenum==0)p->sex=-1;printf("您已退房，欢迎下次光临”)；break;)p=p->next；)（完整版）数据结构经典题目及c语言代码voidDisplay(Room*head)(Room*p;inti=0；p=head—>next;printf("\n\n已订房间查询“)；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);elseprintf("\n房间号：％d，房间等级:％d,已住人^^%d,住房人性别：女"，p->roomnum,p一〉roomlevel,p->peoplenum);while(i<p->peoplenum)if(p-〉bed[i]==1){printf(",已住床位号：％d",i+1);i++；}printf("\n");p=p—>next;（完整版）数据结构经典题目及c语言代码)voidmain(){intn,k=1,i,roomlevel,room[10],bed[10],sum=0;Room*head；printf("请输入房间等级数:5");printf(”Roomlevel：")；scanf("％d"，&roomlevel)；for(i=1;i<=roomlevel； i++)(printf(”\n%d等级房间数："，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:查询\门4:退出系统\n");printf("请输入您的选择：\n")；scanf("％d",&n);switch(n)(case1：Getin(head);break;case2：Checkout(head);break;case3：Display(head);break；case4：k=0;break；default:printf("Error!!pleaseinputagain:")；break；)(完整版)数据结构经典题目及c语言代码题目7：文本文件单词的检索及计数(学时：6)要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。#include〈stdio。h>#include<stdliboh〉#include〈string.h〉typedefstructStringWord(charch[100];}SW；voidCreatTextFile(){charfilename[10],ch;FILE*fp；printf("请输入所用的文件名：”)；scanf("\n%s"，filename);fp=fopen(filename,\”);printf("请输入一段文字，以$号结束:\n")；scanf("%s",&ch);while(ch!='$')(fwrite(&ch,sizeof(ch),1,fp);scanf("%c”，&ch);（完整版）数据结构经典题目及c语言代码fclose(fp);)voidCountWord(){FILE*fp;SWS，T；charch；charfilename[10];inti=0,number=0;printf("输入文本文件名：”)；scanf("%s"，filename);fp=fopen(filename,"r")；printf("输入要统计计数的单词：”)；scanf("%s",Toch);while(!feof(fp))(ch=fgetc(fp);if(ch=='')(if(i!=0){Soch[i]='\0’;i=0；if(strcmp(Soch,Toch)==0)number++;))elseif(ch=='\n?)（完整版）数据结构经典题目及c语言代码if(i!=0){S.ch[i]='\0’;i=0;if(strcmp(S。ch,Toch)==0)number++;})else{Soch[i]=ch；i++;}}if(number==0)printf("单词不在文本中\n");elsenumber);printf("单词％$在文件％s中共出现了％d次："，T.ch,filename,fclose(fp);number);)voidSearchWord(){FILE*fp；SWS,T;charfilename[10];inti,i_r,line,flag=0；charch;printf("\n输入文本文件名：”)；scanf("%s",filename);fp=fopen(filename,"r");printf("输入要统计计数的单词：”)；scanf("%s",Toch);（完整版）数据结构经典题目及c语言代码i=i_r=0；line=1；while(!feof(fp))(ch二fgetc(fp);if(ch==’'){if(i!=0){i_r++；S.ch[i]二'\0';i=0；if(strcmp(T。ch,S。ch)==0)(printf("％s单词第一次出现是在%d行,％d列\n",T.ch,line,i_r);flag=1;break;}))elseif(ch二二'\n?){if(i!=0)(i_r++;Soch[i]='\0’;if(strcmp(T.ch,Soch)==0){printf("%s单词第一次出现是在％d行,％d列\n”,T.ch,line,i_r);flag=1;break;)i=0;i_r=0;line++;)(完整版)数据结构经典题目及c语言代码else{line++；i_r=0;})else(Soch[i]=ch; i++；})if(flag==0)printf("%s单词不在文本中\n”，Toch);fclose(fp);)intmain()(CreatTextFile();CountWord();SearchWord();)题目8:二叉树的遍历(学时：6)二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。#include〈stdio.h〉#include〈stdlib。h>#defineM100typedefstructnode〃定义二叉树结点(（完整版）数据结构经典题目及c语言代码chardata;structnode*lchild,*rchild;}BTNode;BTNode*CreatBTree()〃创建二叉树(先序递归){charch;BTNode大b;scanf("%c",&ch);if(ch='#')//递归结束控制符b=NULL;else{b=(BTNode*)malloc(sizeof(BTNode))；b-〉data=ch;b一〉lchild二CreatBTree();//递归先序建立左子树b-〉rchild二CreatBTree();//递归先序建立右子树}returnb;}voidPreOrder(BTNode*b)〃递归先序遍历二叉树函数{if(b!=NULL){printf("%c",b-〉data);PreOrder(b->lchild);PreOrder(b-〉rchild);})voidInOrder(BTNode*b)//非递归中序遍历二叉树函数{BTNode*stack[M],*p;inttop=一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];//出栈访问结点(完整版)数据结构经典题目及c语言代码top ；printf("%c",p-〉data);p=p->rchild;//扫描p的右结点))printf("\n")；}}voidPostOrder(BTNode*b)//非递归后序遍历二叉树函数{BTNode*stack[M],*p；intsign,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”)；}}voidchange(BTNode*b) 〃左右子树交换(递归)(BTNode*r；r=(BTNode*)malloc(sizeof(BTNode))；intf1=0,f2=0；

if(b==0)return;if(b-〉Ichild)if(b==0)return;if(b-〉Ichild)(change(b—〉Ichild);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(fl|If2){b->rchild=r->lchild;b一〉lchild=r->rchild；})intmax(intm,intn){if(m>n)returnm;elsereturnn;)//树为空时，跳出//有左子树，符号位不为空//有右子树，符号位不为空//否则，给中间变量赋空值intcount(BTNode*b)//计算树高（递归）intcount(BTNode*b)//计算树高（递归）{if(b==NULL)return0;elsereturn(1+max(count(b->lchild),count(b->rchild)));}intmain()(BTNode*root=NULL；printf(" 二叉树的遍历 \n\n”)；printf("请按先序递归顺序创建二叉树(结束符#):\n");root=CreatBTree()；printf("\n递归先序遍历结果：\n”)；PreOrder(root);printf("\n非递归中序遍历结果:\n")；InOrder(root)；printf("非递归后序遍历结果:\n")；PostOrder(root)；printf("\n树高：％d\n",count(root))；(完整版)数据结构经典题目及c语言代码printf("\n左右子树交换位置：”)；change(root);printf(”\n递归先序遍历结果：\n");PreOrder(root)；printf(”\n非递归中序遍历结果:\n”)；InOrder(root)；printf("非递归后序遍历结果:\n");PostOrder(root)；return0；题目9：创建二叉排序树(学时:3)二叉排序树以lson—rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。#include〈stdio.h〉#include<stdliboh〉typedefstructnode{intdata；structnode*lchild,*rchild;}BSTNode,*BSTTree；//二叉排序树的插入(递归算法)voidInsertBST(BSTTree*BST,intkey)(if((*BST)==NULL){(*BST)=(BSTNode*)malloc(sizeof(BSTNode));(*BST)->data=key;(*BST)—〉lchild=NULL;(*BST)—>rchild二NULL;}elseif((*BST)->data〉卜6丫)//如果待插入的元素比根结点元素值小InsertBST(&((*BST)—>lchild),key)；//插入在根结点的左子树（完整版）数据结构经典题目及c语言代码elseInsertBST(&((*BST)—〉rchild),key);//插入在根结点的右子树上)〃创建一棵二叉排序树BSTTreeCreateBSTTree(){BSTTreebst二NULL;intx；while(1){scanf("%d",&x);if(x==00)break；InsertBST(&bst,x);}returnbst;}//中序遍历voidInOrder(BSTTreeBST){if(BST!=NULL)(InOrder(BST—〉lchild);printf(”%5d”,BST->data)；InOrder(BST-〉rchild)；)(完整版)数据结构经典题目及c语言代码voidmain(){BSTTreeBST;printf("建立二叉排序树，请输入序列：\n");BST二CreateBSTTree()；printf("中序遍历后输出的该序列为：")；InOrder(BST)；printf(“\n”)；}题目10：霍夫曼编码应用(学时：3)假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。#include<stdiooh>#include<malloc.h>#include<string.h>#definen100#definem2*n-1typedefstruct{intweight；charch；intparent,lchild,rchild；}HTNode；typedefstruct{charch；

（完整版）数据结构经典题目及（完整版）数据结构经典题目及c语言代码charbits[n+1];}CodeNode；typedefstruct(charcha;intnumber;}COUNTER；intInit（HTNodehtintInit（HTNodeht口）〃初始化函数，为每一个字母信息赋权值（inti,s=1；COUNTERcounter[27]；charch;printf（"请输入字符：\n"）;scanf("%c”,&ch);counter[l].cha='A'；counter[2]ocha='B';counter[31°cha二'C';counter[4].cha='D';counter[5]°cha='E';counter[6].cha='F';counter[7].cha='G';counter[81°cha='H';counter[9]ocha='I';counter[10]ocha='Jcounter[1l1°cha='K'counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16]ocha='P'（完整版）数据结构经典题目及c语言代码counter[I7]°cha='Q';counter[18]。cha='R';counter[19]ocha='S';counter[201°cha='T';counter[21]ocha='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〈=26;i++)counter[i]onumber=0;while(ch!二’’){switch(ch){case'A':counter[1].number++;break;case'B':counter⑵.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;（完整版）数据结构经典题目及c语言代码case’Q’：counter[l7]。number++;break;case'R':counter[18]onumber++;break;case'S':counter[19]onumber++;break;case'T':counter[20].number++;break;case'U':counter[21]onumber++;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<=26;i++)(if(counter[i]onumber!=0)(ht[s]。weight=counter[i].number;ht[s]och=counter[i].cha;s++;)}s=s-1;returns;)voidselect(HTNodeht[],intq,int*p1,int*p2)//select函数{inti,j,x=0,y=0;（完整版）数据结构经典题目及c语言代码for(j=1;j<=q;++j){if(ht[j].parent=0){x二j；break；))for(i=j+1;i<=q；++i){if(ht[i].weight<ht[x].weight&&ht[i]。parent==0){x=i; //选出最小结点})for(j=1;j〈=q;++j)(if(ht[j]。parent=0&&x!二j){y=j;break；))for(i=j+1;i<=q;++i)(if(ht[i].weight〈ht[y].weight&&ht[i].parent=0&&x!二i)(y=i; //选出第二小结点)}if(x〉y)(（完整版）数据结构经典题目及c语言代码*p1=y;*p2=x;)else{大pl二x;大p2二y;}}voidhuffman_setup(HTNodeht口,ints){inti,a；intp1,p2；a=2*s—1；for(i=1;i<=a；i++)(if(i〈=s){ht[i].weight=ht[i].weight；}else{ht[i]oweight=0;}ht[i]。parent=ht[i]。Ichild=ht[i]。rchild=0;}for(i=s+1；i<=a；++i) //建立赫夫曼树{select(ht,i一1,&p1,&p2);ht[p1].parent二i；ht[p2].parent二i；（完整版）数据结构经典题目及c语言代码ht[i]olchild=p1；ht[i].rchild=p2；ht[i].weight=ht[pl]。weight+ht[p2].weight;}}voidhuffman_show(CodeNodehc口，HTNodeht口，ints)〃给字符编码{charq[n];inti,p,c,f;q[s-1]='\0'；for(i=1;i〈二s;i++){p=s-1;for(c二i,f=ht[i]。parent;f;c=f,f=ht[f]。parent)(if(ht[f]olchild==c){q[--p]='0';)else(q[-p]二'1'；)strcpy(hc[i]。bits,&q[p]);}hc[i]och=ht[i]。ch;}}// 编码voidhuffman_code(CodeNodehc[])（完整版）数据结构经典题目及c语言代码inti=1;charch,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;))// 解码voidhuffman_read(HTNodeht口，ints)//根据编码来返回字母信息{inti,j,t;charb；t=2*s—1;i=t;printf("进行解码\n");fflush(stdin);scanf("%c",&b);printf("解码后的信息是:\n");while(b!二’‘){if(b='0')（完整版）数据结构经典题目及c语言代码i=ht[i]oIchild;elsei=ht[i].rchild;if(ht[i]oIchiId==0)(printf("%c”,ht[i]och);j=i；i二t；)scanf("%c",&b);})intmain(){intflag=1,choice;ints,i;HTNodeht[m];CodeNodehc[n];printf("霍夫曼树：\n");s=Init(ht);huffman_setup(ht,s);huffman_show(hc,ht,s);for(i=1;i〈二s;i++)(printf(“％c >%s\n",hc[i].ch,hc[i]obits);)while(flag)(printf("请输入您想要进行的操作：\n1编码\n2解码\n3退出5”);fflush(stdin);（完整版）数据结构经典题目及c语言代码scanf("%d",&choice);switch(choice){case1:huffman_code(hc);printf(“\n”)；break;case2:huffman_read(ht,s);printf("\n")；break;case3:flag=0;)}return0;}题目11:关键路径寻找(学时:6)对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。#include〈malloc。h>#include〈stdio.h〉structNode〃邻接点(intvex;//顶点信息intweight;//权值structNode*next;｝；（完整版）数据结构经典题目及c语言代码structHnode//头结点(intvex2；intid；//入度structNode*link;}A[20]；voidcreate(structHnodeA[20],intn,inte){inti,j,k,l;structNode*p;for(i=1;i<=n；i++)//建立顶点表(A[i]ovex2=i；A[i]oid=0；A[i].link二NULL；}for(k=1;k<=e；k++)//建图{printf("\n请输入边及其权值：\n");scanf("%d",&i)；scanf("%d",&j);scanf("%d”,&l)；p=(structNode*)malloc(sizeof(structNode))；p->vex=j；p-〉weight=l；p一〉next=A[i]。link;A[i]。link=p;(完整版)数据结构经典题目及c语言代码for(i=1;i<=n;1++)//完善入度(p=A[i].link;while(p!=NULL){k=p->vex；A[k].id=A[k].id+1；p=p->next;}}}voidfind(structHnodeA