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

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

2、/*/* 判断选择函数 */*/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=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-expnnext; if(

3、!q) *p=pre; return(1); else if(q-expn=expn) *p=q; return(0); else *p=pre; return(-1); /*/* 插入结点函数 */*/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 exp

4、n(if end ,expn=-1)n); while(1) printf(coef=); 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,Replace older value?)

5、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) /表示是否是多项式的第一项 flag=0; if(p-expn=0) printf(%.2lf,p-coef);

6、 else printf(%.2lfx%d,p-coef,p-expn); else if(p-coef0) printf(+); if(p-expn=0) printf(%.2lf,p-coef); else printf(%.2lfx%d,p-coef,p-expn); p=p-next; printf(n); /*/* 判断两个多项式项的关系 */*/int ItemComp(Item x,Item y) if(x.expny.expn) return(-1); else if(x.expn=y.expn) return(0); else return(1); int menu(void

7、) int num;system(cls);printf(now the choice you can make:n); 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); printf( (9)print P(x)-Q(x)n); print

8、f( (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(num11); return(num); /*/* 判断多项式是否存在 */*/int PolynNotEmpty(Polyn h,char *p) if(h=NULL) printf(%s is not exist!n,p); getchar();return 0; else return(1); /*/* 两多项式多项式相加 */*/Polyn AddPo

9、lyn(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-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=

10、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 if(pb)last-next=pb;else /两者皆到尾 last-next=NULL; return head; Polyn SubtractPolyn(Polyn h1,Po

11、lyn h2) Item *head,*last,*last1,*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-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

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

13、t;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(pb) /双层循环，每项都乘到 pa=h1-next; while(pa)expn=pa-expn+pb-expn;coef=pa-coef*p

14、b-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; return head; /*/* 主函数 */*/void main() int num; Polyn h1=NULL; /p(x) Polyn h2=NULL; /Q(x) Polyn h3=NULL; /P(x)+Q(x) Polyn h

15、4=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) again?) Destroy(h1); h1=Input(); else h1=Input(); break; case 2: /输入第二个多项式，若多项式存在，首先撤消然后再输入 if(h2!=NULL) if(Select(Q(x) is

16、not Empty,Create Q(x) again?) Destroy(h2); h2=Input(); else 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: /两多项式相减 if(PolynNotEmpty(h

17、1,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)&PolynNotEmpty(h2,Q(X) h5=MultPolyn(h1,h2); Output(h1,P(x);Output(h2,Q(x); Output(h5,P(x)*Q(x); printf(P

18、(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) 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);get

19、char(); break; case 9: /显示相减结果多项式 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: /显示相乘结果多项式 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(h1!=NULL)

20、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#include#include#include#define STACKSIZE 3typedef structint Bno;int type; /小车1，客车2，货车3int arrivetime;int pushtime;int departuretime;CAR;/链队结构定义（临时车

21、道）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元/判栈空int StackEmpty()if(stack.top=0)return 1;elsereturn 0;/判栈满int StackFull()i

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

23、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.front-next=NULL;/判队列空int QueueEmpty()if(Queue.front-next=NULL&Queue.front=Queue.rear)return 1;else return 0;/

24、入队操作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(CAR *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，不然r

25、ear没有了，无法判空Queue.rear=Queue.front;free(p);/栈数据查找（返回-1，查找失败）int SearchStack(int BusNo)int k;k=stack.top-1;while(k=0&BusNo!=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小时

26、制,一旦不等0，必有arrive=push0&arrive.type0&arrive.arrivetime0) arrive.pushtime=arrive.arrivetime;push(&stack,arrive);printf(Bno:);scanf(%d,&arrive.Bno);printf(type:);scanf(%d,&arrive.type);printf(arrivetime:);scanf(%d,&arrive.arrivetime);while(arrive.Bno0&arrive.type0&arrive.arrivetime0) arrive.pushtime=0;

27、EnQueue(arrive);printf(Bno:);scanf(%d,&arrive.Bno);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-next=NULL;pri

28、ntf(请输入车辆离开信息n);printf(departtime:);scanf(%d,&departtime);printf(BusNo:);scanf(%d,&BusNo);while(BusNo0&departtime0) pos=SearchStack(BusNo);if(pos=0) while(stack.top-1!=pos) pop(&stack,temp);p=(QNODE *)malloc(sizeof(QNODE);p-elm=temp;LPush(LStack,p);pop(&stack,temp);temp.departuretime=departtime;prin

29、tf(车辆离开的信息: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(LStack,&q);push(&stack,q-elm);free(q);if(!QueueEmpty()DeQueue(&depart);printf(There is new space in STACK! p

30、lease input pushtime:);scanf(%d,&depart.pushtime);push(&stack,depart);printf(A car get into the STACK successfully!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=depart

31、time;printf(车辆离开的信息为:n);printf(Bno:%d Type:%d arrivetime:%d pushtime:%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

32、 input again:n);else printf(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( stack top=%dn,stack.top);for(i=0;inext)printf(n 便道:n);p=Queue.front-n

33、ext;printf( CarNo Type Arriven);while(p)printf(%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);printf( 3.Quit n);printf( *n);printf(Please select 1,2,3:);doscanf(%d,&m);while(m3);return m;/主函数void main()stack.top=0;InitQueue();while(1)/system(cls);switch(nemu()case 1:InputArrialData();OutputBusData();break;case 2:InputDepartData();OutputBusData();break;case 3:OutputBusData();DestroyQue(); return;实验四