1、WORD格式目錄實驗一一元稀疏多項式的計算. .2實驗三停車場管理 . .11實驗四算術(shù)表達式求值 . .18實驗七哈夫曼編 / 譯碼器實驗指導(dǎo)書 . .25實驗八最短路徑實驗指導(dǎo)書 . .36實驗十內(nèi)部排序算法比較實驗指導(dǎo)書 . .451專業(yè)資料整理WORD格式1專業(yè)資料整理WORD格式實驗一一元稀疏多項式的計算#include <stdio.h>#include <stdlib.h>#include <conio.h>typedef struct Itemdoublecoef;intexpn;struct Item *next;Item,*Polyn;#

2、define CreateItem(p) p=(Item *)malloc(sizeof(Item);#define DeleteItem(p) free(void *)p);/*/*判斷選擇函數(shù)*/*/int Select(char *str) char ch;printf("%sn",str);printf("Input Y or N:");do ch=getch();while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n&

3、#39;);printf("n");if(ch='Y'|ch='y') return(1);else return(0);/*/*插入位置定位函數(shù)*/*/int InsertLocate(Polyn h,int expn,Item *p) Item *pre,*q;pre=h;q=h->next;while(q&&q->expn<expn) pre=q;q=q->next;if(!q) *p=pre; return(1);else if(q->expn=expn) *p=q; return(0);

4、專業(yè)資料整理WORD格式2專業(yè)資料整理WORD格式else *p=pre; return(-1);/*/*插入結(jié)點函數(shù)*/*/void insert(Item *pre,Item *p) p->next=pre->next; pre->next=p;/*/*輸入多項式*/*/Polyn Input(void)doublecoef;intexpn,flag;Item *h,*p,*q,*pp;CreateItem(h);/ 產(chǎn)生頭結(jié)點h->next=NULL;printf("input coef and expn(if end ,expn=-1)n")

5、;while(1) printf("coef="); scanf("%lf",&coef); printf("expn=");scanf("%d",&expn); / 輸入多項式的系數(shù)和指數(shù)if(expn=-1) break;/ 假設(shè)指數(shù)為 1，表示輸入完畢if(InsertLocate(h,expn,&pp)/返回值非0 表示插入新結(jié)點 CreateItem(p);p->coef=coef;p->expn=expn;insert(pp,p);/ 按順序在插入else if(Se

6、lect("has the same expn,Replace older value"")pp->coef=coef;/ 指數(shù)一樣，替換系數(shù)return h;/*/*撤消多項式*/*/void Destroy(Polyn h)專業(yè)資料整理WORD格式3專業(yè)資料整理WORD格式Item *p=h,*q;while(p!=NULL) q=p;p=p->next;DeleteItem(q);/*/*輸出多項式*/*/void Output(Polyn h,char *title)int flag=1;Item *p=h->next;printf(&q

7、uot;%s=",title);while(p) if(flag)/ 表示是否是多項式的第一項 flag=0;if(p->expn=0)printf("%.2lf",p->coef);else printf("%.2lfx%d",p->coef,p->expn);else if(p->coef>0) printf("+");if(p->expn=0)printf("%.2lf",p->coef);else printf("%.2lfx%d"

8、;,p->coef,p->expn);p=p->next;printf("n");/*/*判斷兩個多項式項的關(guān)系*/*/int ItemComp(Item x,Item y) if(x.expn<y.expn) return(-1);else if(x.expn=y.expn)return(0);else return(1);int menu(void) int num; system("cls");printf("now the choice you can make:n");專業(yè)資料整理WORD格式4專業(yè)資

9、料整理WORD格式printf(" (1)create P(x)n");printf(" (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(" (6)print P(x)n");printf(" (7)print Q(x)n");printf(" (8)print P(x)+Q(x)n")

10、;printf(" (9)print P(x)-Q(x)n");printf(" (10)print P(x)*Q(x)n");printf(" (11)Quitn");printf("please select 1,2,3,4,5,6,7,8,9,10,11:");doscanf("%d",&num);while(num<1 | num>11);return(num);/*/*判斷多項式是否存在*/*/int PolynNotEmpty(Polyn h,char *p) i

11、f(h=NULL) printf("%s is not exist!n",p); getchar();return 0;else return(1);/*/*兩多項式多項式相加*/*/Polyn AddPolyn(Polyn h1,Polyn h2)Item *head,*last,*pa=h1->next,*pb=h2->next,*s;CreateItem(head);/ 頭結(jié)點，不動last=head;while(pa&&pb)switch(ItemComp(*pa,*pb)case -1: CreateItem(s); s->coe

12、f=pa->coef; s->expn=pa->expn; last->next=s;專業(yè)資料整理WORD格式5專業(yè)資料整理WORD格式last=last->next;pa=pa->next;break;case 1:CreateItem(s);s->coef=pb->coef;s->expn=pb->expn;last->next=s;last=last->next;pb=pb->next;break;case 0:if(pa->coef+pb->coef)/ 相加不為0，寫入CreateItem(s)

13、;s->coef=pa->coef+pb->coef;s->expn=pa->expn;last->next=s;last=last->next;pa=pa->next;pb=pb->next; break;if(pa)/a 未到尾last->next=pa;else if(pb)last->next=pb;else/ 兩者皆到尾last->next=NULL;return head;Polyn SubtractPolyn(Polyn h1,Polyn h2)Item *head,*last,*last1,*pa=h1-&

14、gt;next,*pb=h2->next,*s;CreateItem(head);last=head;while(pa&&pb)switch(ItemComp(*pa,*pb)case -1:CreateItem(s);s->coef=pa->coef;s->expn=pa->expn;last->next=s;last=last->next;專業(yè)資料整理WORD格式6專業(yè)資料整理WORD格式pa=pa->next;break;case 1:CreateItem(s);s->coef=pb->coef*(-1);s-&

15、gt;expn=pb->expn;last->next=s;last=last->next;pb=pb->next;break;case 0:if(pa->coef-pb->coef)/ 相加不為 0，寫入CreateItem(s);s->coef=pa->coef-pb->coef;s->expn=pa->expn;last->next=s;last=last->next;pa=pa->next;pb=pb->next; break;if(pa)/a 未到尾last->next=pa;else i

16、f(pb)/pb 未到尾，后面附負值while(pb)CreateItem(s);s->coef=pb->coef*(-1);s->expn=pb->expn;last->next=s;last=last->next;pb=pb->next;last->next=pb;else/ 兩者皆到尾last->next=NULL;return head;/*/*兩多項式多項式相乘*/*/Polyn MultPolyn(Polyn h1,Polyn h2)/ 兩個多項式相乘 int expn;Item *head,*pa,*pb=h2->nex

17、t,*s,*pp;專業(yè)資料整理WORD格式7專業(yè)資料整理WORD格式double coef;CreateItem(head);head->next=NULL;while(pb)/ 雙層循環(huán)，每項都乘到pa=h1->next; while(pa)expn=pa->expn+pb->expn;coef=pa->coef*pb->coef;if(InsertLocate(head,expn,&pp)/返回值非0 表示插入新結(jié)點CreateItem(s);s->coef=coef;s->expn=expn;insert(pp,s);/ 按順序在插

18、入elsepp->coef=pp->coef+coef; / 找到有一樣指數(shù)，直接加上去 pa=pa->next;pb=pb->next;return head;/*/*主函數(shù)*/*/void main() int num;Polynh1=NULL; /p(x)Polynh2=NULL; /Q(x)Polynh3=NULL; /P(x)+Q(x)Polynh4=NULL; /P(x)-Q(x)Polynh5=NULL; /P(x)*Q(x)while(1) num=menu();getchar();switch(num) case 1: / 輸入第一個多項式，假設(shè)多項式

19、存在，首先撤消然后再輸入if(h1!=NULL) if(Select("P(x) is not Empty,Create P(x) again"") Destroy(h1);h1=Input();else h1=Input();專業(yè)資料整理WORD格式8專業(yè)資料整理WORD格式break;case 2:/ 輸入第二個多項式，假設(shè)多項式存在，首先撤消然后再輸入if(h2!=NULL) if(Select("Q(x) is not Empty,Create Q(x) again"") Destroy(h2);h2=Input();else

20、 h2=Input();break;case 3:/ 兩多項式相加if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)") h3=AddPolyn(h1,h2); Output(h1,"P(x)");Output(h2,"Q(x)");Output(h3,"P(x)+Q(X)");printf("P(x)+Q(x) has finished!n");getchar();break;case 4:/ 兩多項式相減

21、if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)")h4=SubtractPolyn(h1,h2); Output(h1,"P(x)");Output(h2,"Q(x)");Output(h4,"Px)-Q(x)");printf("P(x)-Q(x) has finished!n");getchar();break;case 5:/ 兩多項式相乘if(PolynNotEmpty(h1,"p(x)

22、")&&PolynNotEmpty(h2,"Q(X)")h5=MultPolyn(h1,h2);Output(h1,"P(x)");Output(h2,"Q(x)");Output(h5,"P(x)*Q(x)");printf("P(x)*Q(x) has finished!n");getchar();break;case 6: / 顯示第一個多項式if(PolynNotEmpty(h1,"p(x)") Output(h1,"P(x)&qu

23、ot;); getchar();專業(yè)資料整理WORD格式9專業(yè)資料整理WORD格式break;case 7: / 顯示第二個多項式if(PolynNotEmpty(h2,"Q(x)") Output(h2,"Q(x)"); getchar();break;case 8: / 顯示相加結(jié)果多項式if(PolynNotEmpty(h3,"P(x)+Q(x)")Output(h1,"P(x)"); Output(h2,"Q(x)");Output(h3,"P(x)+Q(x)");g

24、etchar();break;case 9: / 顯示相減結(jié)果多項式if(PolynNotEmpty(h4,"P(x)-Q(x)")Output(h1,"P(x)");Output(h2,"Q(x)");Output(h4,"P(x)-Q(x)");getchar();break;case 10: / 顯示相乘結(jié)果多項式if(PolynNotEmpty(h5,"P(x)*Q(x)")Output(h1,"P(x)");Output(h2,"Q(x)");O

25、utput(h5,"P(x)*Q(x)");getchar();break;case 11: / 完畢程序運行。完畢前應(yīng)先撤消已存在的多項式/* if(h1!=NULL) Destroy(h1);if(h2!=NULL) Destroy(h2);if(h3!=NULL) Destroy(h3);if(h4!=NULL) Destroy(h4);if(h5!=NULL) Destroy(h5);*/return;getch();專業(yè)資料整理WORD格式10專業(yè)資料整理WORD格式實驗三停車場管理#include<stdio.h>#include<stdlib

26、.h>#include<string.h>#include<conio.h>#define STACKSIZE 3typedef structint Bno;int type; / 小車 1，客車 2，貨車 3int arrivetime;int pushtime;int departuretime;CAR;/ 鏈隊構(gòu)造定義臨時車道typedef struct QNODECAR elm;struct QNODE *next;QNODE;/ 鏈隊構(gòu)造定義注意申明方法，相當全局變量struct LinkQueueQNODE *front;QNODE *rear;Que

27、ue;/ 順序棧構(gòu)造定義停車場struct SqStackCAR elmSTACKSIZE;int top;stack;/ 收費標準int pay=0,2,3,5; / 每小時小車2 元，客車3 元，貨車5 元/ 判棧空int StackEmpty()if(stack.top=0)專業(yè)資料整理WORD格式11專業(yè)資料整理WORD格式return 1;elsereturn 0;/ 判棧滿int StackFull()if(stack.top=STACKSIZE)return 1;else return 0;/ 順序棧入棧void push(struct SqStack *stack,CAR ca

28、r)if(!StackFull()stack->elmstack->top+=car;/ 順序棧出棧 (CAR用了引用，不知為啥指針不管用 ) void pop(struct SqStack *stack,CAR &car)if(!StackEmpty() stack->top-;car=stack->elmstack->top;/ 鏈棧入棧函數(shù)void LPush(QNODE *stack,QNODE *p)p->next=stack->next; stack->next=p;/ 鏈棧出棧函數(shù) (去掉了 stack 下一位的結(jié)點 ) v

29、oid LPop(QNODE *stack,QNODE *p)(*p)=stack->next; stack->next=(*p)->next;/ 鏈隊初始化void InitQueue()Queue.front=Queue.rear=(QNODE *)malloc(sizeof(QNODE); Queue.front->next=NULL;/ 判隊列空int QueueEmpty()if(Queue.front->next=NULL&&Queue.front=Queue.rear) return 1;專業(yè)資料整理WORD格式12專業(yè)資料整理WOR

30、D格式else return 0;/ 入隊操作void EnQueue(CAR car)QNODE *p;p=(QNODE *)malloc(sizeof(QNODE); p->elm=car;p->next=NULL; Queue.rear->next=p;Queue.rear=p;/ 出隊操作隊列帶頭結(jié)點，才方便出void DeQueue(CAR *car)int flag=0; QNODE *p;if(Queue.front->next=Queue.rear) flag=1;p=Queue.front->next; Queue.front->next=

31、p->next;*car=p->elm;if(flag)/ 一定要在減到空時重新置rear，不然 rear 沒有了，無法判空Queue.rear=Queue.front;free(p);/ 棧數(shù)據(jù)查找返回 -1，查找失敗int SearchStack(int BusNo)int k;k=stack.top-1; while(k>=0&&BusNo!=stack.elmk.Bno)k-;return k;/ 隊數(shù)據(jù)查找返回 NULL，查找失敗QNODE *SearchQueue(int BusNo)QNODE *p;p=Queue.front->next;

32、 while(p!=NULL&&p->elm.Bno!=BusNo)p=p->next;return p;/ 收費計算與顯示函數(shù)0 表示未干此事，時間按 24 小時制,一旦不等 0，必有arrive<=push<=departure void CalcultPay(CAR car)int payment; if(car.arrivetime!=0&&car.pushtime=0)專業(yè)資料整理WORD格式13專業(yè)資料整理WORD格式payment=(car.departuretime-car.arrivetime)*paycar.type/

33、3.0; else if(car.arrivetime!=0&&car.pushtime!=0)payment=(car.pushtime-car.arrivetime)*paycar.type/3.0+(car.departuretime-car.pushtime)*paycar.type;elsepayment=(car.departuretime-car.pushtime)*paycar.type; printf("n");printf("收費 =%4dn",payment);printf("n");getch(

34、);/ 進場車數(shù)據(jù)的錄入與管理void InputArrialData()CAR arrive;printf(" 請輸入車輛信息 n");printf("Bno:");scanf("%d",&arrive.Bno);printf("type:");scanf("%d",&arrive.type);printf("arrivetime:"); scanf("%d",&arrive.arrivetime); while(!StackFu

35、ll()&&arrive.Bno>0&&arrive.type>0&&arrive.arrivetime>0) arrive.pushtime=arrive.arrivetime; push(&stack,arrive);printf("Bno:");scanf("%d",&arrive.Bno);printf("type:");scanf("%d",&arrive.type);printf("arrivetime:

36、");scanf("%d",&arrive.arrivetime);while(arrive.Bno>0&&arrive.type>0&&arrive.arrivetime>0)arrive.pushtime=0;EnQueue(arrive);printf("Bno:");scanf("%d",&arrive.Bno);printf("type:");scanf("%d",&arrive.type);print

37、f("arrivetime:");scanf("%d",&arrive.arrivetime);/ 離場車數(shù)據(jù)錄入與管理void InputDepartData()int BusNo,departtime,pos; CAR depart,temp; QNODE *p,*pri,*q; QNODE *LStack;LStack=(QNODE *)malloc(sizeof(QNODE); LStack->next=NULL;printf(" 請輸入車輛離開信息 n");printf("departtime:&qu

38、ot;); scanf("%d",&departtime); printf("BusNo:"); scanf("%d",&BusNo);專業(yè)資料整理WORD格式14專業(yè)資料整理WORD格式while(BusNo>0&&departtime>0)pos=SearchStack(BusNo); if(pos>=0)while(stack.top-1!=pos) pop(&stack,temp);p=(QNODE *)malloc(sizeof(QNODE); p->elm=t

39、emp;LPush(LStack,p);pop(&stack,temp);temp.departuretime=departtime;printf(" 車輛離開的信息:n");printf("Bno:%d Type:%d arrivetime:%d pushtime:%d departtime:%dn",temp.Bno,temp.type,temp.arrivetime,temp.pushtime,temp.departuretime);CalcultPay(temp);while(LStack->next!=NULL)LPop(LSta

40、ck,&q);push(&stack,q->elm);free(q);if(!QueueEmpty()DeQueue(&depart);printf("There is new space in STACK! please input pushtime:");scanf("%d",&depart.pushtime);push(&stack,depart);printf("A car get into the STACK successfully!nn");pri=SearchQueue(B

41、usNo);if(pri)while(pri!=Queue.front->next) DeQueue(&depart);p=(QNODE *)malloc(sizeof(QNODE); p->elm=depart;LPush(LStack,p);DeQueue(&depart);depart.departuretime=departtime;printf(" 車輛離開的信息為:n");printf("Bno:%dType:%darrivetime:%dpushtime:%ddeparttime:%dn",depart.Bno,

42、depart.type,depart.arrivetime,depart.pushtime,depart.departureti me);CalcultPay(depart);while(LStack->next!=NULL)專業(yè)資料整理WORD格式15專業(yè)資料整理WORD格式LPop(LStack,&q);LPush(Queue.front,q);if(pos=-1&&pri=NULL)printf("there is no this CAR!Please input again:n");elseprintf("the other

43、departure CAR:n");printf("departtime:");scanf("%d",&departtime);printf("BusNo:");scanf("%d",&BusNo);/ 列表顯示車場數(shù)據(jù)void OutputBusData()int i; QNODE *p;printf("n停車場 :n");printf("CarNoTypeArrivePushn");printf("stacktop=%dn",

44、stack.top);for(i=0;i<stack.top;i+)printf("%10d%10d%13d%12dn",stack.elmi.Bno,stack.elmi.type,stack.elmi.arrivetime,stack.elmi.pushtime);if(Queue.front->next)printf("n便道 :n");p=Queue.front->next;printf("CarNoTypeArriven");while(p)printf("%10d%10d%13dn",

45、p->elm.Bno,p->elm.type,p->elm.arrivetime); p=p->next;getch();/ 撤銷隊列函數(shù)void DestroyQue()QNODE *p,*q;p=Queue.front;while(p)q=p;p=p->next;free(q);專業(yè)資料整理WORD格式16專業(yè)資料整理WORD格式/ 菜單項選擇擇int nemu()int m;printf("n* CARManage *n");printf("1.Arrivaln");printf("2.Departuren&

46、quot;);printf("3.Quitn");printf("*n");printf("Please select 1,2,3:");doscanf("%d",&m);while(m<1|m>3);return m;/ 主函數(shù)void main()stack.top=0;InitQueue();while(1)/system("cls");switch(nemu()case 1:InputArrialData();OutputBusData();break;case 2:

47、InputDepartData();OutputBusData();break;case 3:OutputBusData();DestroyQue();return;專業(yè)資料整理WORD格式17專業(yè)資料整理WORD格式實驗四算術(shù)表達式求值#include<stdio.h>#include<string.h>#include<conio.h>#include<stdlib.h>#define PLUS 0#define MINUS 1#define POWER 2#define DIVIDE 3#define LEFT 4#define RIGHT

48、 5#define STARTEND 6#define DIGIT 7#define POINT 8#define NUM 7#define NO -100#define STACKSIZE 20char a='+','-','*','/','(',')','#'/ 優(yōu)先級矩陣int PriorityTable77=1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1,1,1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,-1,-1,-1,-1,0,NO,1,1,1,1,NO,1,1,-1,-1,-1,-1,-1,NO,0;int menu()int num;system("cls");print