西南交大数据结构实验报告

1、目录实验一 一元稀疏多项式的计算 2实验三 停车场管理11实验四 算术表达式求值18实验七 哈夫曼编/译码器实验指导书25实验八 最短路径实验指导书36实验十 内部排序算法比较实验指导书45实验一 一元稀疏多项式的计算#include <stdio.h>#include <stdlib.h>#include <conio.h>typedef struct Item double coef; int expn; struct Item *next; Item,*Polyn;#define CreateItem(p) p=(Item *)malloc(sizeo

2、f(Item);#define DeleteItem(p) free(void *)p);/*/* 判断选择函数 */*/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'); printf("n"); if(ch=&#

3、39;Y'|ch='y') return(1); else return(0); /*/* 插入位置定位函数 */*/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); else *p=pre; return(-1);

4、/*/* 插入结点函数 */*/void insert(Item *pre,Item *p) p->next=pre->next; pre->next=p; /*/* 输入多项式 */*/Polyn Input(void)double coef; int expn,flag; Item *h,*p,*q,*pp; CreateItem(h);/产生头结点 h->next=NULL; printf("input coef and expn(if end ,expn=-1)n"); while(1) printf("coef=");

5、scanf("%lf",&coef);printf("expn="); scanf("%d",&expn); /输入多项式的系数和指数 if(expn=-1) break; /若指数为1，表示输入结束 if(InsertLocate(h,expn,&pp)/返回值非0表示插入新结点 CreateItem(p); p->coef=coef; p->expn=expn; insert(pp,p); /按顺序在插入 else if(Select("has the same expn,Replac

6、e older value?") pp->coef=coef; /指数相同，替换系数 return h; /*/* 撤消多项式 */*/void Destroy(Polyn h) 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("%s=",title); while(p) if(flag) /表示是否是多项式的

7、第一项 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",p->coef,p->expn); p=p->next; pr

8、intf("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"); printf(" (1)create P(x)n"); printf(&quo

9、t; (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"); printf(" (9)print P(x)-Q(x)n"); printf(

10、" (10)print P(x)*Q(x)n"); printf(" (11)Quitn"); printf("please select 1,2,3,4,5,6,7,8,9,10,11:"); do scanf("%d",&num); while(num<1 | num>11); return(num); /*/* 判断多项式是否存在 */*/int PolynNotEmpty(Polyn h,char *p) if(h=NULL) printf("%s is not exist!n

11、",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); /头结点，不动 last=head; while(pa&&pb) switch(ItemComp(*pa,*pb) case -1:CreateItem(s);s->coef=pa->coef;s->expn=pa->

12、expn;last->next=s;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);s->coef=pa->coef+pb->coef;s->expn=pa->expn;

13、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->next,*pb=h2->next,*s; CreateItem(head); last=hea

14、d; 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;pa=pa->next;break;case 1:CreateItem(s);s->coef=pb->coef*(-1);s->expn=pb->expn;last->next=s;last=last->next;pb=pb->next;brea

15、k;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 if(pb) /pb未到尾，后面附负值while(pb)CreateItem(s);s->coef=pb->coef*(-1);s->

16、;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->next,*s,*pp; double coef; CreateItem(head); head->next=NULL; while(p

17、b) /双层循环，每项都乘到 pa=h1->next; while(pa)expn=pa->expn+pb->expn;coef=pa->coef*pb->coef; if(InsertLocate(head,expn,&pp)/返回值非0表示插入新结点 CreateItem(s);s->coef=coef;s->expn=expn;insert(pp,s); /按顺序在插入 else pp->coef=pp->coef+coef; /找到有相同指数，直接加上去 pa=pa->next; pb=pb->next; ret

18、urn head; /*/* 主函数 */*/void main() int num; Polyn h1=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(1) num=menu(); getchar(); switch(num) case 1: /输入第一个多项式，若多项式存在，首先撤消然后再输入 if(h1!=NULL) if(Select("P(x) is not Empty,Create P(x

19、) again?") Destroy(h1); h1=Input(); else h1=Input(); break; case 2: /输入第二个多项式，若多项式存在，首先撤消然后再输入 if(h2!=NULL) if(Select("Q(x) is not Empty,Create Q(x) again?") Destroy(h2); h2=Input(); else h2=Input(); break; case 3: /两多项式相加 if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h

20、2,"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: /两多项式相减 if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)") h4=Subt

21、ractPolyn(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)")&&PolynNotEmpty(h2,"Q(X)") h5=MultPolyn(h1,h2); Output(h1,

22、"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)"); getchar(); break; case 7: /显示第二个多项式 if(PolynNotEmpty(h2,"Q(x)&quo

23、t;) Output(h2,"Q(x)");getchar(); break; case 8: /显示相加结果多项式 if(PolynNotEmpty(h3,"P(x)+Q(x)") Output(h1,"P(x)");Output(h2,"Q(x)"); Output(h3,"P(x)+Q(x)");getchar(); break; case 9: /显示相减结果多项式 if(PolynNotEmpty(h4,"P(x)-Q(x)") Output(h1,"P(

24、x)");Output(h2,"Q(x)"); Output(h4,"P(x)-Q(x)");getchar(); break; case 10: /显示相乘结果多项式 if(PolynNotEmpty(h5,"P(x)*Q(x)") Output(h1,"P(x)");Output(h2,"Q(x)"); Output(h5,"P(x)*Q(x)");getchar(); break; case 11: /结束程序运行。结束前应先撤消已存在的多项式 /* if(h

25、1!=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(); 实验三 停车场管理#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>#define STACKSIZE 3typedef structint Bno;int type; /小

26、车1，客车2，货车3int arrivetime;int pushtime;int departuretime;CAR;/链队结构定义（临时车道）typedef struct QNODECAR elm;struct QNODE *next;QNODE;/链队结构定义 （注意申明方法，相当全局变量）struct LinkQueueQNODE *front;QNODE *rear;Queue;/顺序栈结构定义（停车场）struct SqStackCAR elmSTACKSIZE;int top;stack;/收费标准int pay=0,2,3,5; /每小时小车2元，客车3元，货车5元/判栈空in

27、t 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->elmstack->top+=car;/顺序栈出栈 (CAR用了引用，不知为啥指针不管用)void pop(struct SqStack *stack,CAR &car)if(!StackEmpty() stac

28、k->top-;car=stack->elmstack->top;/链栈入栈函数void LPush(QNODE *stack,QNODE *p)p->next=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(QNO

29、DE);Queue.front->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->next=NULL;Queue.rear->next=p;Queue.rear=p;/出队操作（队列带头结点，才方便出）void DeQueue(CA

30、R *car)int flag=0;QNODE *p;if(Queue.front->next=Queue.rear)flag=1;p=Queue.front->next;Queue.front->next=p->next;*car=p->elm;if(flag) /一定要在减到空时重新置rear，不然rear没有了，无法判空Queue.rear=Queue.front;free(p);/栈数据查找（返回-1，查找失败）int SearchStack(int BusNo)int k;k=stack.top-1;while(k>=0&&BusN

31、o!=stack.elmk.Bno)k-;return k;/队数据查找（返回NULL，查找失败）QNODE *SearchQueue(int BusNo)QNODE *p;p=Queue.front->next;while(p!=NULL&&p->elm.Bno!=BusNo)p=p->next;return p;/收费计算与显示函数（0表示未干此事，时间按24小时制,一旦不等0，必有arrive<=push<=departure）void CalcultPay(CAR car)int payment;if(car.arrivetime!=0&a

32、mp;&car.pushtime=0)payment=(car.departuretime-car.arrivetime)*paycar.type/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(&quo

33、t;n");printf(" 收费=%4d n",payment);printf("n");getch();/进场车数据的录入与管理void InputArrialData()CAR arrive;printf("请输入车辆信息n");printf("Bno:");scanf("%d",&arrive.Bno);printf("type:");scanf("%d",&arrive.type);printf("arrive

34、time:");scanf("%d",&arrive.arrivetime);while(!StackFull()&&arrive.Bno>0&&arrive.type>0&&arrive.arrivetime>0) arrive.pushtime=arrive.arrivetime;push(&stack,arrive);printf("Bno:");scanf("%d",&arrive.Bno);printf("type:

35、");scanf("%d",&arrive.type);printf("arrivetime:");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

36、);printf("type:");scanf("%d",&arrive.type);printf("arrivetime:");scanf("%d",&arrive.arrivetime);/离场车数据录入与管理void InputDepartData()int BusNo,departtime,pos;CAR depart,temp;QNODE *p,*pri,*q;QNODE *LStack; LStack=(QNODE *)malloc(sizeof(QNODE);LStack->ne

37、xt=NULL;printf("请输入车辆离开信息n");printf("departtime:");scanf("%d",&departtime);printf("BusNo:");scanf("%d",&BusNo);while(BusNo>0&&departtime>0) pos=SearchStack(BusNo);if(pos>=0) while(stack.top-1!=pos) pop(&stack,temp);p=(QNO

38、DE *)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:%dn",temp.Bno,temp.type,temp.arrivetime,temp.pushtime,temp.departuretime);CalcultPay(temp);w

39、hile(LStack->next!=NULL)LPop(LStack,&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 succ

40、essfully!nn");pri=SearchQueue(BusNo);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:%d Type:%d arrivetime:%d pushti

41、me:%d departtime:%dn",depart.Bno,depart.type,depart.arrivetime,depart.pushtime,depart.departuretime);CalcultPay(depart);while(LStack->next!=NULL)LPop(LStack,&q);LPush(Queue.front,q); if(pos=-1&&pri=NULL)printf("there is no this CAR!Please input again:n");else printf(&qu

42、ot;the other departure CAR:n");printf("departtime:");scanf("%d",&departtime); printf("BusNo:");scanf("%d",&BusNo);/列表显示车场数据void OutputBusData()int i;QNODE *p;printf("n 停车场:n");printf(" CarNo Type Arrive Pushn");printf(" st

43、ack top=%dn",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(" CarNo Type Arriven");while(p)printf("

44、;%10d%10d%13dn",p->elm.Bno,p->elm.type,p->elm.arrivetime);p=p->next;getch();/撤销队列函数void DestroyQue()QNODE *p,*q;p=Queue.front;while(p)q=p;p=p->next;free(q);/菜单选择int nemu()int m;printf("n * CAR Manage *n");printf(" 1.Arrival n");printf(" 2.Departure n"

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

46、putDepartData();OutputBusData();break;case 3:OutputBusData();DestroyQue(); return;实验四 算术表达式求值#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 5#define STARTEND 6#defin

47、e DIGIT 7#define POINT 8#define NUM 7#define NO -100#define STACKSIZE 20char a='+','-','*','/','(',')','#'/优先级矩阵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");printf("n* Expre