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

1、WORD格式目录实验一一元稀疏多项式的计算. .2实验三停车场管理 . .11实验四算术表达式求值 . .18实验七哈夫曼编 / 译码器实验指导书 . .25实验八最短路径实验指导书 . .36实验十内部排序算法比较实验指导书 . .451专业资料整理WORD格式1专业资料整理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);/*/*判断选择函数*/*/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);/*/*插入位置定位函数*/*/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、专业资料整理WORD格式2专业资料整理WORD格式else *p=pre; return(-1);/*/*插入结点函数*/*/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);/ 产生头结点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); / 输入多项式的系数和指数if(expn=-1) break;/ 假设指数为 1，表示输入完毕if(InsertLocate(h,expn,&pp)/返回值非0 表示插入新结点 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;/ 指数一样，替换系数return h;/*/*撤消多项式*/*/void Destroy(Polyn h)专业资料整理WORD格式3专业资料整理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");/*/*判断两个多项式项的关系*/*/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");专业资料整理WORD格式4专业资

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);/ 头结点，不动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;专业资料整理WORD格式5专业资料整理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;专业资料整理WORD格式6专业资料整理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;专业资料整理WORD格式7专业资料整理WORD格式double coef;CreateItem(head);head->next=NULL;while(pb)/ 双层循环，每项都乘到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);/ 按顺序在插

18、入elsepp->coef=pp->coef+coef; / 找到有一样指数，直接加上去 pa=pa->next;pb=pb->next;return head;/*/*主函数*/*/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: / 输入第一个多项式，假设多项式

19、存在，首先撤消然后再输入if(h1!=NULL) if(Select("P(x) is not Empty,Create P(x) again"") Destroy(h1);h1=Input();else h1=Input();专业资料整理WORD格式8专业资料整理WORD格式break;case 2:/ 输入第二个多项式，假设多项式存在，首先撤消然后再输入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();专业资料整理WORD格式9专业资料整理WORD格式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)");g

24、etchar();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)");O

25、utput(h5,"P(x)*Q(x)");getchar();break;case 11: / 完毕程序运行。完毕前应先撤消已存在的多项式/* 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();专业资料整理WORD格式10专业资料整理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;/ 链队构造定义临时车道typedef struct QNODECAR elm;struct QNODE *next;QNODE;/ 链队构造定义注意申明方法，相当全局变量struct LinkQueueQNODE *front;QNODE *rear;Que

27、ue;/ 顺序栈构造定义停车场struct SqStackCAR elmSTACKSIZE;int top;stack;/ 收费标准int pay=0,2,3,5; / 每小时小车2 元，客车3 元，货车5 元/ 判栈空int StackEmpty()if(stack.top=0)专业资料整理WORD格式11专业资料整理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;/ 链栈入栈函数void LPush(QNODE *stack,QNODE *p)p->next=stack->next; stack->next=p;/ 链栈出栈函数 (去掉了 stack 下一位的结点 ) 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;专业资料整理WORD格式12专业资料整理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;/ 出队操作队列带头结点，才方便出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);/ 栈数据查找返回 -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;

32、 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&&car.pushtime=0)专业资料整理WORD格式13专业资料整理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、);/ 进场车数据的录入与管理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);/ 离场车数据录入与管理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);专业资料整理WORD格式14专业资料整理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)专业资料整理WORD格式15专业资料整理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);/ 列表显示车场数据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();/ 撤销队列函数void DestroyQue()QNODE *p,*q;p=Queue.front;while(p)q=p;p=p->next;free(q);专业资料整理WORD格式16专业资料整理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;/ 主函数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;专业资料整理WORD格式17专业资料整理WORD格式实验四算术表达式求值#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='+','-','*','/','(',')','#'/ 优先级矩阵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