目录实验——元稀疏多项式的计算 (2)实验三停车场管理 (11)实验四算术表达式求值 (18)实验七哈夫曼编/译码器实验指导书 (25)实验八最短路径实验指导书 (36)实验十部排序算法比较实验指导书 (45)实验——元稀疏多项式的计算#include <stdio.h>#include <stdlib.h>#include vconio.h〉typedef struct ltem{ double coef;int expn;struct Item *next;Jltem/Polyn;#define Createltem(p) p=(ltem *)malloc(sizeof(ltem));#define Deleteltem(p) free((void *)p);判断选择函数/******京******車************車**********末木*****京******拿*****京**/int Select(char *str){char ch; printf(,,%s\n,,/str);printf("lnput Y or N:'1)；do{ ch=getch();}while(ch!='Y,&&ch!='y‘&&ch!='N'&&ch!—rV);printfCXn");if(ch==,Y,||ch==,y,) return(l);else return(O);}/*******************************京************球************* 4K/* 插入位星定位函数 /********************車****************京************孚*********** int InsertLocate(Polyn h/nt expnjtem **p){Item 床pr已*q;pre=h;q=h->n ext;while(q&&q・> exp nvexpn){ Pre=q；q 二q.>n ext;}if(!q){ *P=pre;return 仕)；}else if(q->expn==expn) {*p=q；return(O);}插入结点函数 ****京******京*****)|(4|******41****京*拿4[**京************ 京***定*京**void insert(ltem *prejtem *p) { p ・> next 二 pre ・ >n ext;pr/>n ext=p;}/拿*****京******車************車**********末木***«******沐牛拿*****京**/ /* 输入多项式 *//******京** ******** ***4t******************4t4t** ****** ********京** / Polyn Input(void){double coef;int expnjlag;Item *h /*p /*q,*pp;Createltem(h);// 产生头结点 h->next=NULL;printf("input coef and expn(if end ,expn=・l)\n”)；while(l){ printf(,,coef=,')；scanf(”％lf ：&coef);printf(,,expn=")；scanf("%d",&expn); 〃输入多项式的系数和指数 if(expn==-l) break; 〃若指数为一1，表示输入结朿if(lnsertLocate(h,expn,&pp))//返回值非0表示插入新结点{Createltem(p);p->coef=coef;p->expn=exp n;insert(pp,p); 〃按顺序在插入}else if(Select("has the same expr\Replace older value?")) pp->coef=coef; 〃指数相同，替换系数}return h;}/拿 *****京******車***********************木木**********沐牛拿*****京**/ /* 撤消多项式 */y****)«(>)( *«♦♦♦♦****♦♦****♦♦ ***♦♦♦♦****♦**♦**♦♦♦♦**♦♦ ♦**♦♦♦♦**** /{ *P=pre;return(-l);}}車**********京車****案******承******************承****水4(*車***未** */void Destroy(Polyn h)Item *p=h/q; while(p!=NULL) {q=p;p=p->n ext;Deleteltem(q);}/*****4t*4t****4c4t4t***4t4K************4(拿4t***4t *************** 定**#*卓/ /* 输岀多项式♦//****木京************京************京************球*********/ void Output(Polyn h z char *title)int flag=l;Item *p=h・>next;printf(,,%s=,,/title);while(p){if(flag) 〃表示是否是多项式的第一项{flag=O;if(p->expn==O) printf(,,%.2lf,,/p->coef);else printf(l,%.2lfx A%d,,/p->coef/p->expn);}else{if(p->coef>0) printf(,,+H);if(p->expn==0) printf("%.2lf,/p->coef);else printf(H%.2lfx A%d,,/p->coef/p->expn);p=p->next;} printfCV)；/*******************************束*******車****京************京拿*/ /*判断两个多项式项的关系*//************京*************************京*****4(車******** / int ltemComp(ltem xjtem y){if(x.expn<y.expn)return(-l);else iffx.expn二二y.expn)return(O);else return(l);int menu(void){int num; system(,,cls H);printf(N now the choice you can make:\n H);printf(" (l)create P(x)\n u)；printf(H (2)create Q(x)\n")；printf(" (3)p(x)+Q(x)\n");printf(" (4)P(x)-Q(x)\n“)；printf(" (5)p(x)*Q(x)\n")；printf("⑹print P(x)\n u);printf(" (7)print Q(x)\n H)；printf("⑻print P(x)+Q(x)\n n);printf(M⑼print P(x)-Q(x)\n H);printf(H (lO)print P(x)*Q(x)\n u);print:f(”(ll)Quit\n");printf(H please select 1,2,3,4,5,6,7,8,94041：")；do{scanf("%dj&num);}while(num<l | | num>ll);return(num);}/*****床******京*****案*************************京*****4(車******** / /* 判断多项式是否存在*//****** 案******車車***4( ******* 車**********>k*******4t****4t4i4t****i|(4t*/ int PolynNotEmpty(Polyn h,char *p) {if(h==NULL){ printf(H%s is not exist'Xn'^p);getchar();return 0;else return(l);}/*4c***>)ciK4t************4t4i*****************4t4t** ****** ********京**/ /* 两多项式多项式相加*//*******************************束*******車****京************京拿*/ Polyn AddPolynfPolyn hl,Polyn h2)Item *head/*last/*pa=hl->next,*pb=h2->next/*s;Createltem(head); 〃头结点，不动last=head;while(pa&&pb){ switch{ltemComp(*pa/*pb))case -1:Createltem(s); s->coef=pa->coef;s->expn=pa->expn; last->next=s;last=last-> next;pa=pa->n ext;break;case 1:Createltem(s);s->coef=pb->coef;s->expn=p b・>expn;last->n ext=s;last=last-> next;pb=pb->next;break;case 0: if(pa->coef+pb->coef) 〃相加不为0,写入{Createltem(s); s->coef=pa->coef+pb->coef;s->expn=pa->expn;last- >n ext=s; last=last-> next;}pa=pa->n ext;pb=pb->next; break;}}if(pa) //a未到尾last- >n ext=pa;else if(pb)last- >n ext=pb;else 〃两者皆到尾last->next=NULL;return head;}Polyn SubtractPolyn(Polyn hl,Polyn h2){Item *head/*last/*lastl,*pa=hl->next,*pb=h2->next,*s;Createltem(head);last=head;while(pa&&pb){ switch(ltemComp(*pa,*pb)){ case -1:Createltem(s);s->coef=pa->coef;s->expn=pa->expn;last->n ext=s;last=last- >n ext;pa=pa->n ext;break;case 1:Createltem(s); s->coef=pb->coef*(-l); s->expn=p b・>expn; last->next=s; last=last- >n ext; pb=pb->next;break;case 0: if(pa->coef-pb->coef) 〃相加不为0,写入{Createltem(s); s->coef=pa->coef-pb->coef;s->expn=pa->exp n; last- >n ext=s;last=last-> next;}pa=pa->n ext; pb=pb->next; break;}}if(pa) //a未到尾last ext=pa;else if(pb) 〃pb未到尾，后面附负值{while(pb){Createltem(s); s->coef=pb->coef*(-l); s->expn=p b・>expn; last->n ext=s;last=last- >n ext; pb=pb->next;} last->next=pb;}else 〃两者皆到尾last->next=NULL;return head;}/************** *****車*****************京************扌*****未*/* 两多项式多项式相乘/拿 *****京******車************車**********末木************拿*****京* Polyn MultPolyn(Polyn hl,Polyn h2) 〃两个多项式相乘{int expn;Item *head/*pa,*pb=h2->next,*s/*pp;double coef;Createltem(head);head->next=NULL;while(pb) 〃双层循环，每项都乘到{ pa=hl->n ext;while(pa){ expn=pa->expn+pb->expn;coef=pa coef*pb->coef;if(lnsertLocate(head,expn/&pp))//返回值非0 表示插入新结点{ Createltem(s);s->coef=coef;s->expn=expn;insert(pp,s); 〃按顺序在插入}elsepp->coef=pp->coef+coef; 〃找到有相同指数，直接加上去pa=pa->next; }pb=pb->n ext;return head;*/主函数*******************車*****************************孚******** */ void main(){int num;Polyn hl=NULL;//p(x)Polyn h2 二NULL; 〃Q(x)Polyn h3=NULL;//P(x)+Q(x)Polyn h4=NULL;//P(x)-Q(x)Polyn h5=NULL;//P(x)*Q(x)while(l){num=menu(); getchar();switch(num){ case 1: 〃输入第一个多项式，若多项式存在，首先撤消然后再输入if(hl!=NULL){if(Select(H P(x) is not Empty,Create P(x) again?")){ Destroy(hl);hl=lnput();}else hl=lnput();break;case 2: 〃输入第二个多项式，若多项式存在，首先撤消然后再输入if(h2!=NULL){if(Select("Q(x) is not Empty z Create Q(x) again?11)){ Destroy(h2);h2=lnput();}}else h2=lnput();break;case 3: 〃两多项式相加if(PolynNotEmpty(hl/p(x)")&&PolynNotEmpty(h2/Q(X)”)){ h3=AddPolyn(hl/h2);Outputfhl/Tfx)11);Output(h2/Q(x)");Output(h3；,P(x)+Q(X)n);printf("P(x)+Q(x) has finished !\n")；getchar();}break;case 4: 〃两多项式相减if(PolynNotEmpty(hl/p(x)")&&PolynNotEmpty(h2「Q(X)J){ h4=SubtractPoly n(hl,h2);Output(hl/,,P(x),,);Output(h2/Q(x)”)；Output(h4「Px)・Q(x)”)；printf(,,P(x)-Q(x) has finished !\n H);getchar();}break;case 5: 〃两多项式相乘if(PolynNotEmpty(hl/,p(x)n)&&PolynNotEmpty(h2/Q(X)")){ h5=MultPolyn(hl/h2);Output(hl/,,P(x),,);Output(h2,'Q(x)”)；Output(h5「P(x 广Q(x)”);printf(H P{x)*Q(x) has finishedgetchar();}break;case 6: //显示第一个多项式if(PolynNotEmpty(hl/,p(x)u)){Output(hl；,P(x)l,);getchar();实验三停车场管理#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>#define STACKSIZE 3typed ef struct{int Bno;int type; 〃小车1,客车2,货车3int arrivetime;int pushtime;int departuretime;}CAR;〃链队结构左义（临时车道）typedef struct QNODE{CAR elm;struct QNODE *next;}QNODE;〃链队结构左义（注意申明方法，相当全局变量）struct LinkQueuefQNODE *front;QNODE *rear;}Queue;〃顺序栈结构立义（停车场）struct SqStack{CAR elm[STACKSIZE];int top;}stack;〃收费标准int pay［卜{0,235}; //每小时小车2元,客车3元，货车5元〃判栈空int StackEmpty{)if（stack.top==0）return 1;elsereturn 0;}〃判栈满int StackFull(){if(stack.top==STACKSIZE)return 1;else return 0;}〃顺序栈入栈void push(struct SqStack *stack,CAR car){ if(!StackFull()) stack->elm[stack->top++]=car;}〃顺序栈岀栈(CAR用了引用，不知为啥指针不管用)void pop(struct SqStack * stack,CAR &car){ if(!StackEmpty()){ stack->top-; car=stack->elm[stack->top);}}〃链栈入栈函数void LPush(QNODE *stack z QNODE *p){ p・>n ext=stack->next;stack->next=p;}〃链栈出栈函数(去掉了stack卜•一位的结点)void LPop(QNODE *stack,QNODE **p){ (*p)=stack->next;stack->next=(*p)->next;}〃链队初始化void InitQueue(){ Queue.front=Queue.rear=(QNODE *)malloc(sizeof(QNODE));Queue.fr on t->next=NULL;}〃判队列空int QueueEmpty{){ if(Queue.front->next==NULL&&Queue.front==Queue.rear) return 1;else return 0;}〃入队操作void EnQueue(CAR car){ QNODE *p;p=(QNODE *)malloc(sizeof(QNODE));p->elm=car;p->n ext=NULL;Queue.rear- >n ext=p;Queue.rear=p;}〃出队操作(队列带头结点，才方便岀)void DeQueue(CAR *car){ int flag=O;QNODE *p;if(Queue.front->next==Queue.rear)flag=l；p=Queue.fr on t->next;Queue.front->next=p->n ext;*car=p->elm;if(flag) 〃一泄要在减到空时重新置rear,不然rear没有了，无法判空Queue.rear=Queue.fr ont;free(p);}〃栈数据查找(返回査找失败)int SearchStack(int BusNo){ int k;k=stack.topwhile(k>=0&&BusNo !=stack.elm[k].Bno)k-;return k;}〃队数据查找(返回NULL,查找失败)QNODE *SearchQueue(int BusNo){ QNODE *p;p二Queue.fr on t->next;while(p!二NULL&&p・>Glm.Bno!=BusNo)p=p->n ext;return p;}〃收费计算与显示函数(0表示未干此事，时间按24小时制，一旦不等0,必有arrive<=push<=departure)void CalcultPay(CAR car){ int payment;if(car.arrivetime!= 0&&car.pushtime==0)payme nt=(car.departuretime-car.arrivetime)*pay[car.type]^.O;else if(car.arrivetime!= 0&&car.pushtime!=O)payme ntNcar.pushtime-car.aiTivGtimG^paylcar.typel/S.O+Yar.departiirGtimicar.pushtime)3* pay[car.type];elsepayme nt=(car・departurGtime・car・pushtime)Say[car・type];printfCXn");printf(" 收费二％4d \n", payment);printf(”\n“)；getch();}〃进场车数据的录入与管理void lnputArrialData(){ CAR arrive;printf(”请输入车辆信息\n“)；printf(l,Bno:")；scanfC^d'^&arrive.Bno);printf ("type:")；scanfC%cT：&arrive.type);prin tfC^rrivetime:")；sea nf(”％d‘：&airivG・arrivetime);while(!StackFull()&&arrive.Bno>0&&arrive.type>O&&arrive.arrivetime>0){ arrive.push t:ime 二arrive, arrivetime;push(&stack,arrive);printf(,,Bno:,,); scan &airive.Bno); printfCtype:"); scan f(ll%d"/&arrive・type)；printfCarrivetime:")；sea nf("%cT,&arTive・arTivetime);} while(arrive.Bno>0&&arrive.type>0&&arrive.arrivetime>0){ arrive.pushtime=O;En Queue(arrive);printf(,,Bno:,,)；scanf(,,%d,：&arrive.Bno);printf(,,type:N); scanf(,,%d,,/&arrive.type);printf("arrivetime:u)；sea nf("%cT,&arTive・arrivGtime);}}〃离场车数据录入与管理void lnputDepartData(){ int BusNo^eparttime^os;CAR depart,temp;QNODE *p,*pri/q;QNODE*LStack;LStack=(QNODE *)malloc(sizeof(QNODE));LStack->next= NULL;printf(”请输入车辆离开信息\n“);printfC'departtime:")； scanf「％cT：&departtirne);printfCBusNo:")； sea nf ("%d BusNo);while(BusNo>0&&departtime>0){ pos=SearchStack(BusNo);if(pos>=0){ while(stack.top-l!=pos){ pop(&stack z temp);p==(QNODE *)malloc(sizeof(QNODE));p・ >elm 二temp;LPush(LStack/p);}pop(&stack’temp);temp.departuretime=departtime;printf("车辆离开的信息:\n“)；printf(“Bno:%d Type:%d arrivetime:%d pushtime:%d departtime^dXn'^temp.BnoAemp.type^emp.arrivetime,temp.pushtime,temp.departuretime);CalcultPay(temp);while(LStack->next!=NULL){ LPop(LStack z&q);push(&stack z q->elm);free(q);}if(!QueueEmpty()){ DeQueue(&depart);printf("There is new space in STACK! please input pushtime:");scanff^d'^&depart. pushtime);push(&stack,depart);printf("A car get into the STACK successfully!\n\n")；}}pri=SearchQueue(BusNo);if(pri){ while(pri !=Queue.fr on t->next){ DeQueue(&depart);p==(QNODE *)malloc(sizeof(QNODE));p・ >elm二depart;LPush(LStack/p);}DeQueue(&depart);depart.departuretime=departtime;printf("车辆离开的信息为:\n");printf(“Bno:%d Type:%d arrivetime:%d pushtime:%d departtime:%d\n 舄depart. B no,depart, typ 巳depart, arrivetim 已depart, push 廿me,depart・d€partureti me);CalcultPay(depart);while(LStack->next!=NULL)LPop(LStack,&q);LPush(Queue.front,q);}if(pos==-l&&pri==NULL)printf(M there is no this CAR! Please input again:\n N)；elseprintf(H the other departure CAR:\n");printf(,,departtime:,,)； scanf(,,%d,,/&departtime); printfCBusNo:")；scanff%d'^&BusNo);}}〃列表显示车场数据void OutputBusData(){ int i；QNODE *p;printf("\n 停车场:\n");printf(" CarNo Type Arrive Push\n,,)；printf(" stack top=%d\n 舄stack, top);for(i=0;i<stack.top;i++)printf(,,%10d%10d%13d%12d\n',/stack.elm[i].Bno/stack.elm[i].type/stack.elm[i].arrivetime/st ack.elm[i).pushtime);if(Queue.front->next){ printf(H\n 便道:\n");p=Queue.front->n ext;printf(" CarNo Type Arrive\n u)；while(p){ printf(,,%10d%10d%13d\n,,/p->elm.Bno/p->elm.type,p->elm.arrivetime); p=p->n ext;}}getch();}〃撤销队列函数void DestroyQue(){QNODE *p/q;p=Queue.fr ont;while(p){q二p;p=p->n ext;free(q);}do{ scanf 「％cT,&rn);}while(m<l| |m>3);return m;〃主函数void main(){stack.top=0;lnitQueue();while(l){ //system (” cis");switch( nemu()){case 1:lnputArrialData();OutputBusData(); break;case 2:lnputDepartData();OutputBusData(); break;case 3:OutputBusData();DestroyQue(); return;}printf(M \n printf(" printf("printf(" *41***沐4(************ CAR Man age1.Arrival \n M ); 2. D eparture \n H )；〃菜单选择int nemu(){ int m;printf(" *定**京***********孚孚************拿*****卓****球******京*\n")・ printf('Pease select 1,2,3:'');实验四算术表达式求值#include<stdio.h> #include<stri ng・h> #include<conio.h> #include<stdlib.h> #definePLUS 0 #define MINUS 1 #define POWER 2 #define DIVIDE 3 #define LEFT 4 #defineRIGHTS #define STARTEND 6 #define DIGIT 7 #define POINT 8 #define NUM 7 #defineNO -100 #define STACKSIZE 20 chara[]=f<'-7*7/7(7)7#-}；〃优先级矩阵int PriorityTable[7][7]={{l,—1,1,1},{1,1,-1,-1,-1,1,1}, {1,1,1,1,-144}, {1,1,1,1,-144}, {-1,-1,-1,-1,-1AN0}, {1,1,1,1,NO,14Lint menu() {int num;system(,,cls H);printf("\n Expressi on Calculation 水案京****常京京**********、n‘‘)・printf(" --------------------- 1.input expression ------------------------------ \n");prirrtf(” -------------------- 2.calculation expression ----------------------- \n H);printf(" --------------------- 3.print result --------------------------------- \n H);printf(" --------------------- 4.Quit ------------------------------------------ \n");printf("***********車孚*******************車****************************車孚*\n")・printf("Please select 1,23/4:")； do{scanf(,,%d,,/&num);}while(num<l| |num>4);return num;〃输入表达式void In putExpressi on (char str[]){int len;printf("lnput expression string:\n N)； scanf("%s 舄str);len=strle n(str);str[len]=,#1;str[len+l]=,\O,;}〃确泄当前字符类型int GetCharType(char ch){int i;for(i=0;i<NUM;i++) if(ch==a[i]) return i;if(ch>=l O,&&ch<=,9,)return DIGIT;if(ch==1.1)return POINT;return -1;}〃表达式计算(1表示正确，0表达式有误)int EXCUTE(char *str,double *Result){int pp,topTr，topNd,CharTyp巳OPTR[STACKSIZE]; double numbeGtemp^PNDlSTACKSIZE];OPTR[0]=STARTEND;topTr=l;topNd=0;PP=O;while((str[pp])){CharType=GetCharType(str[pp]);switch(CharType){case -1:return 0;case DIGIT:number=0;while(str[pp]>='0,&&str[pp]<='9,)number=number*10+(str[pp]-48);pp++；}if(str[pp]==7) 〃遇小数点{temp=10.0;PP++；while(str[pp]>='O l&&str[pp]v=9) {num ber 二number+(str[pp 卜48)/temp;temp=temp*10;pp++;}}OPND[topNd++]=number; break;case POINT: 〃以小数点开始的实数number=0;temp=10.0;PP++；while{str[pp]>='O'&&str[pp]<='9,){number=nu mber+(str[pp]-48)/temp;temp=temp*10;pp++;}OPND[topNd 卄]二number; break;case PLUS:if(PriorityTable[OPTR[topTr-l]][PLUS]==-l){OPTR[topTr++]=PLUS;pp++;}else{switch(OPTR[topTr-l]) {case PLUS:OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-l];break;case MINUS:OPND[topNd.2]=OPND[topNd-2]-OPND[topNd-l];break;case POWER:OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-l];break;case DIVIDE:OPND(topNd-2]=OPND[topNd-2]/OPND(topNd-l];break;}topNd—;topTr—;break;case MINUS:if(PriorityTable[OPTR[topTr-l]][MINUS]==-l){OPTR[topTr++]=MINUS;pp++;}else{switch(OPTR[topTr-l]) {case PLUS:OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-l];break;case MINUS:OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-l];break;case POWER:OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-l];break; case DIVIDE:OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-l];break; } topNd-;topTr-;}break;case POWER:if(PriorityTable[OPTR[topTr-l]][POWER]==-l){OPTR[topTr++]二POWER;PP++；}else{ switch(OPTR[topTr-l]){case PLUS:OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-l];break;case MINUS:OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-l];break;case POWER:OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-l];break;case DIVIDE:OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-l];break; } topNd—;topTr—;break;case DIVIDE:if(PriorityTable[OPTR[topTr-l]][DIVIDE]==-l){OPTR[topTr++]二DIVIDE;pp++;}else{switch(OPTR[topTr-l]) {case PLUS:OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-l];break;OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-l];break;case POWER:OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-l];break;case DIVIDE:OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-l];break;}topNd—;topTr—;}break;case LEFT:OPTR[topTr++]=LEFT;pp++;break;case RIGHT:if(OPTR[topTr-l]==LEFT){ topTr-;pp++;}else{while(OPTR[topTr-l]==PLUS| |OPTR[topTr-l]==MINUS| |OPTR[topTr-l]==POWER| |OPTR[top Tr-1]==DIVIDE){switch(OPTR[topTr-l]){case PLUS:OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-l];break;case MINUS:OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-l];break;case POWER:OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-l];break;case DIVIDE:OPND(topNd-2]=OPND[topNd-2]/OPND(topNd-l];break;topNd-;topTr-;}if(OPTR[topTr-l]==STARTEND)return 0;if(OPTR[topTr-l]==LEFT){topTr-;pp++；}}break;case STARTEND:while(OPTR[topTr-l]!=STARTEND){switch(OPTR[topTr-l]){OPND[topNd-2]=OPND[topNd-2]+OPND[topNd-l];break; caseMINUS:OPND[topNd-2]=OPND[topNd-2]-OPND[topNd-l];break; casePOWER:OPND[topNd-2]=OPND[topNd-2]*OPND[topNd-l];break; caseDIVIDE:OPND[topNd-2]=OPND[topNd-2]/OPND[topNd-l];break; }topNd—;topTr—;}if(topNd==l){*Result=OPND[0];return 1;}else return 0;}}return 1;}void main(){ int numjlag^;double result;char str[256];str[O]=,\O,;while(l){ num=me nu();switch(num)case 1: 〃输入表达式InputExpressio n(str);flag 二0;printf(n the Expression is:")； printf("%s\n 舄str);getch();break;case 2: 〃讣算表达式if(str[O]==,\O,){ printf(H Expression is Empty! Again!\n“)；InputExpression(str);flag=0;printf(u the Expression is:11); printf(”％s\n 舄strj;getch();}else if(!EXCUTE(str;&result)){ printf(H The expression has error! Again! \n")；InputExpression(str);flag 二0;printf(u the Expression is:H); printf(”％s\rV：strj;getch();}else {printf(n calculation has finished!\n u)；getch();flag=l；}break;case 3: 〃打印计算结果if(flag){ printf(,,#%s=%lf\n,,/str/result); getch();}else{ printf(H You had not did the calculation!\n")； getch();}break;case 4:return;实验七哈夫曼编/译码器实验指导书#include<stdio.h> /* for size_t/ printf() */#include<conio.h> /* for getch()#include<ctype.h> /* for tolower() */#include<malloc.h> /* for mallocO, callocf), free() */#include<string.h> /* for memmove(), strcpy()#include<stdlib.h>#define NODENUM 26〃最大编码长度/* ----- 哈夫曼树结点结构 -------- */struct node{char ch;int weight;int pare nt;int Ichildjchild;} *ht; 〃指向哈夫曼树的存储空间的指针变量/*树结构和全局结构指针*//* ----- 字符编码结点结构 -------- */struct HuffmanCoding{char ch;char coding[NODENUM];};/* ---- 哈夫曼树遍历时栈的结点结构*/struct stack no de{int NodeLevel;int NodeElem;};/* -------- 常量文件爼--------- */const char *TableFileName = ,,d://HfmTbl.txt,1; 〃哈夫曼树数拯文件const char *CodeFileName = ”d:〃CodeFile.txt”；〃字符编码数据文件const char *SourceFileName = ”d://SrcText・txt”；〃需编码的字符串文件const char *EnCodeFileName = ,,d://EnCodeFile.txt u; //编码数据文件const char *DecodeFileName = "dy/DecodeFile.txt"; //译码字符文件*****京******************************末未*****京***************/释放哈夫曼树数据空间函数void free_ht()if(ht != NULL) {free(ht);ht = NULL;}}***********京******京********************************專****京**** 判是否为可译码字符串*************************************************4(孚**********int JudgeStr(char str[])for(int i=O;str[i]!=l\O,;i++) if(str[i]!=,0•&&str[i]!=T) return 0;return 1;/****** 案******車車***4( ******* 車**********>k*******4t****4t4i4t****i|(4t*/从文件读取哈夫曼树数据函数*/int ReadFromFile()int i;int m; FILE *fp;if((fp=fopen(TableFileName/,rb,,))==NULL){printf("cannot open %s\n,,/ TableFileName);getch();return 0;}freadf&m^izeoffin^lJp)； //m为数据个数(文本中第一个就是结点个数)free_ht();ht=(struct node *)malloc(m*sizeof(struct node));fread(ht,sizeof(struct node),m,fp);fclose(fp);return m;}void EatCharsUntilNewLine()while(getchar()!=,\n')con tinue;/******************************* 束 ******* 車****京************京拿 ***4(******>k/*/void Select(struct node ht[]Jnt n, int *sl,int *s2) {int i,j;〃寻找第一个根结点 *sl=0;while esl<=n&&ht[*sl].parent!=.l) ++(*sl);//父亲为 1 无父亲，为根，在森林中 i=(*sl)+l ； while(i< 二n){if(ht[i].parent==-l&&ht[i].weight<ht[*sl].weight) *sl=i; 〃比较后面所有根结点,寻找 第一个权值最小的根结点++i ； }〃开始左s2・先寻找第一个根结点，如果是si,跳过 *s2=0;while(*s2<=n&&(ht[*s2].parent!=-l 11 *s2==*sl)) ++(*s2); 〃寻找第二个权值最小的根结点 j=*s2+l; while(j<=n){if(j!=*sl&&ht[j].parent==-l&&ht[j].weight<ht[*s2].weight) *s2=j; //不等于 si ++j; } return;/4t****4t*4t******車********* *******束*******車****京***********京京拿* / /* 创建哈夫曼树和产生字符编码的函数 */ /************京*****寧***************************************** / void Initialization() {int i,n /m,j /f r sl /s2/start; charcd[NODENUM];struct HuffmanCoding code[NODENUM]; 〃为数组，长度已上，不可再改(如用 malloc, new 之类)FILE *fp;printfC*输入字符总数n:")； scanf("%d"，&n);EatCharsllntilNewLine{);// 除 了数字只能输回车了 m=2*n-l; 〃总结点数选择权值最小的两个根结点函数（重0到n 找）ht=(struct node *)malloc(m*sizeof(struct node));//申诘哈夫曼树的存储空间printf("请输入字符和权值:\n”);//记录并初始化for(i=0;i<n;i++){printf(”第％d 组：0+1);scanf("%c %d l,/&ht[i].ch/&ht[i].weight);EatCharsUntilNewLine(); 〃至关重要ht[i].parent=-l;ht[i].lchild=-l;ht[i].rchild=-l;}for(i=n ;i<m;i++){ht[i].ch=l#,;ht[i].weight=O;ht[i].parent=ht[i].lchild=ht[i].rchild=-l;**京* 拿******** 开始彳:**♦♦♦****♦♦♦***♦♦♦***♦♦♦♦♦*for(i=n;i<m;i++)Select(ht,i-l,&sl,&s2);// 找到最小两结点ht[sl].pare nt 二i;ht[s2].pare nt 二i;ht[i].lchild=sl;ht[i].rchild=s2;ht[i].weight=ht[sl].weight+ht[s2].weight;}〃把哈夫曼树的数拯存储到文件中if((fp=fopen(TableFileName/,,wb,,))==NULL){printf(u cannot open %s\n,,/ TableFileName);getch();return;}fwrite(&m,sizeof(int)丄fp);fwrite(ht,sizeof(struct node^mjp);fclose(fp);cd[n-l]=,\O,;for(i=0;i<n;i++){start=n-l;for(j=i,f=ht[i].parent;f!=-l;j=f,仁ht[f].parent)//沿着父亲上去，直到根if(ht[f].lchild==j)cd[-.start]=I O,; 〃若沿父结点的左分支上升，则得编码字符“0”elsecd[..start]=i r；〃若沿父结点的右分支上升，则得编码字符a r code[i].ch=ht[i].ch;strcpy(code[i].coding,&cd[start]);//从start的这个地址处开始赋值，前而的位可能用不到}〃把字符编码数据存储到文件中iffSffp^openfCodeFileName/'wb")))printf("cannot open %s\n"/ CodeFileName); getch();return;}fwrite(&n/sizeof(int)/l/fp); 〃先写有几组编码fwritefcode^izeoffstruct HuffmanCoding),njp);fclose(fp);free_ht();printf(H\nlnitial successful!\n u)；getch();/****木京************京************京************球*********/哈夫曼编码的函数void Encode(void)int i,j,n;char Encodestr[256);struct HuffmanCoding code[NODENUM];FILE *fpl;if((fpl=fopen(CodeFileName/,,rb,,))==NULL) {printf("cannot open %s\n,,/ CodeFileName); getch();return;}fread(&n,sizeof(int)丄fpl);fread(code,sizeof(struct HuffmanCoding^nJpl);//读字符编码数据printf("请输入需编码的文本串：“)；scanfC^s^Encodestr); 〃读需编码的字符串fclose(fpl);if((fpl=fopen{SourceFileName,,,wb,,))==NULL)printf("cannot open %s\n”，SourceFileName );getch();return;}fputs(Encodestr,fpl);//存储被编码的字符串数据到文件中// fwritefEncodestGsizeoffchar^sizeoffEncodestrJJpl);后而会读出乱码fclose(fpl);if((fpl=fopen(EnCodeFileName/,,wb"))==NULL){printf(N cannot open %s\n舄EnCodeFileName );getch();return;}printf("编码结果为:\n u);for(i=0;Encodestr[i] !='\0';i++){for(j=0;j<n;j++)if(code[j].ch==Encodestr[i]){printfC^s'^codeO).coding);fputs(code[j].coding,fpl);break; 〃编码结果写入文件}if(j==n){ printf("\nWrong string,there is a unknow ChariCan not Encode!")； //出现没有的字符，显示出错return;}}printf("\nEnCode Succeedfclose(fpl);return;*/哈夫曼译码的函数*******************車*****************************孚********void Decode()FILE *CFI> *TFP;char DeCodeStr[256];char ch;intm=ReadFromFile();//读哈夫曼树数据,已进入ht。
