《数据结构》课程设计

1、数据结构课程设计题目 1 一元多项式计算*题目 2 迷宫求解题目 3 翻牌游戏题目 4 作业调度姓名：*班级：*计科（1）班学号：200310610*题目1 一元多项式计算1 需求分析1）、能够按照指数降序排列建立并输出多项式；2）、能够完成两个多项式的相加、相减，并将结果输入。2 算法描述分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都是由“系数指数”两部分来组成的，所以可以将它抽象成一个由“系数指数对”构成的线形表，由于对多项式中系数为0的子项可以不记录它的指数值，对于这样的情况就不再付出存储空间来存放它了。基于这样的分析，我们可以采用一个带有头结点的单链表来表示一个一元多项

2、式。（1）具体数据类型如下： typedef struct node float coef; /系数域 int expn; /指数域 struct node * next; /指针域，指向下一个系数不为0的子项 polynode;（2）输入并建立多项式的功能模块要求按照指数递减的顺序和一定的输入格式输入各个系数不为0的子项的“系数指数对”，输入一个子项建立一个相关结点，当遇到输入结束的标志的时候就停止输入，而转去执行程序的下面部分。例如：polynode * create_poly(char ch) /输入多项式 polynode * p, *s,*r; float x; int y; p=(

3、polynode *)malloc(sizeof(polynode); p-next=null; printf(请输入一元多项式%c:(格式:系数 指数,指数递减,以0 0结束.)n,ch); scanf(%f %d,&x,&y); while(x!=0) s=(polynode *)malloc(sizeof(polynode); s-coef=x; s-expn=y; s-next=null; if(p-next=null)p-next=s; r=s; else r-next=s; r=s; scanf(%f %d,&x,&y); return p; （3）多项式相加的功能模块此模块根据在

4、（1）中建立的两个多项式进行相加的运算，并存放在以c为头指针的一个新链表中。 polynode * add_poly(polynode * f,polynode * g)/多项式相加 polynode * fg; polynode *t,*q,*s,*r; float m; t=f-next; q=g-next; fg=r=(polynode*)malloc(sizeof(polynode); fg-next=null; while(t&q) if(t-expn=q-expn)/指数相等时系数相加 m=t-coef+q-coef; if(m!=0)/系数为不0时加到结果中去 s=(polyno

5、de *)malloc(sizeof(polynode); s-coef=m; s-expn=t-expn; s-next=null; t=t-next; q=q-next; else/指数小的加到结果中去再后移 if(t-expnexpn)s=(polynode *)malloc(sizeof(polynode); s-coef=t-coef; s-expn=t-expn; s-next=null; t=t-next; else s=(polynode *)malloc(sizeof(polynode); s-coef=q-coef; s-expn=q-expn; s-next=null;

6、q=q-next; if(fg-next=null) fg-next=s; r=s; elser-next=s; r=s; /while r-next=t?t:q;/把没加完的接上 return fg;（4）多项式显示的功能模块此模块用于多项式的显示，程序可以使用图形界面，通过调整指数应该出现的坐标位置来表示指数形式，如：x+2x2-3x100；也可以使用文本界面，用“系数指数对”的形式表示表达式，如：(1,1),(2,2),(-3,100)。本程序采用第一种方式，如下：void out_poly(polynode * f)/输出多项式polynode *t; t=f-next;if(!f-n

7、ext)printf(0n); return; while(t) if(t-coef0&f-next!=t) printf(+);if(t-expn=0) printf(%f,t-coef); else printf(%f*x%d,t-coef,t-expn); t=t-next; printf(n);3 运行结果 题目2 迷宫求解1 需求分析 可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。2 算法描述（1） 输出相关参数 for (char ch=y;ch=y|ch=y;cinch)int m,n,prec;cout 请输入二维迷宫的两个维m*n（0m,

8、nm;m=50|mm) cout 重输; coutn;n=50|nn) cout 重输; coutprec;prec100|precprec) cout 重输; random_creat_maze(a,m,n,prec); showmaze(a,m,n); coutstart.rowstart.col; coutend.rowend.col; cout 初始状态：n; showmaze(a,m,n); / start.row=1;start.col=1;/end.row=8;end.col=8; if (mazepath(s,start,end,a) coutn 最后状态：n; showmaz

9、e(a,m,n); showpath(s); else coutn= 找不到路径！=n; cout=s.stacksize) s.base=(struct reseach_maze *)realloc(s.base,102*sizeof(struct reseach_maze);s.top=s.base+100;s.stacksize+=2; *s.top+=e;void pop(struct sstack &s,struct reseach_maze &e) /出栈元素，存入eif (s.top!=s.base)e=*-s.top;bool emptystack(struct sstack

10、s) /栈是否空return (s.top=s.base);void footprint(int ammnn,struct postype post) /留足迹apost.rowpost.col=6;struct postype nextpos(struct postype post,int i) /当前位置curpos的下一位置switch (i)case 1:post.col+;break;case 2:post.row+;break;case 3:post.col-;break;default:post.row-;return (post);void markprint(int ammn

11、n,struct postype post) /留死胡同标记apost.rowpost.col=4;bool mazepath(struct sstack &s,struct postype start,struct postype end,int ammnn)/在迷宫a中找出路, 用栈来记录走的路径，start、end分别为入、出口坐标struct postype curpos;int curstep=1; struct reseach_maze e; initstack(s);curpos=start;do if (!acurpos.rowcurpos.col)footprint(a,cu

12、rpos);e.dire=1;e.ord=curstep;e.seat=curpos;push(s,e);if (curpos.col =end.col & curpos.row =end.row ) return (true);curpos=nextpos(curpos,1);curstep+;elseif (!emptystack(s)pop(s,e);while (e.dire=4&!emptystack(s)markprint(a,e.seat);pop(s,e);if (e.dire4)e.dire+;push(s,e);curpos=nextpos(e.seat,e.dire);w

13、hile (!emptystack(s);return(false);（3） 产生一个随机迷宫void random_creat_maze(int ammnn,int m,int n,int prec) /产生随机迷宫int x,i,j;for (i=0;im;i+)for(j=0;jn;j+)if (i=0|i=m-1|j=0|j=n-1) aij=1;elsex=rand();x/=prec*32767/100;aij=x;（4） 显示迷宫矩阵void showmaze(int ammnn,int m,int n) /显示迷宫矩阵cout=n;cout 坐标从0行0列开始 0-可通，1-不

14、通，4-死胡同，6-通路n;cout=n;int i,j;for(i=0;im;i+) cout ;for(j=0;jn;j+)coutaij ;coutendl;3 运行结果题目3 翻牌游戏*1需求分析 编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？2算法描述（1）采用数组存储，循环嵌套实现 int i,j;

15、int a53;/*定义数组大小*/ for(i=1;i=52;i+)ai=i; for(i=1;i=52;i+)（2）整除判断 for(j=2;j=52;j+)if(ai%j=0) ai=-ai;/*整除判断*/（3）输出牌号 printf(正面向上的牌为:n);for(i=1;i0)printf(%dn,ai);/*输出牌号*/4 运行结果 题目4 作业调度1 需求分析 一个公司的职员可分为经理、部门主管和职工。公司的服务支持由一个共同的秘书处承担，每一个职员都可以提出服务请求（诸如企划及建议、指示及批复等），只要填写一张包括该职员的职位、任务号、任务内容的表格即可。这张表格内的信息存储在

16、一个作业请求记录jobrequest队列中，并根据时间将作业加入到对应的优先级队列中。初始作业队列存放于一个作业队列文件中，作业队列文件中存放有一批将被加入到优先级队列的作业。每个作业请求都以记录的形式存放在“job.dat”文件中。记录中记载着职员的职位、作业标识号和工作时间。所有作业在读入后都加入到一个名为“jobpool-作业池”的优级队列中，然后，按其所具有的优先级逐个进行处理，并将处理结果打印出来。程序最后打印为每一类人的总服务时间。2 算法描述（1）定义一个结构体 struct jcb char name10; /* 作业名 */ char state; /* 作业状态 */ in

17、t ts; /* 提交时间 */ float super; /* 优先权 */ int tb; /* 开始运行时间 */ int tc; /* 完成时间 */ float ti; /* 周转时间 */ float wi; /* 带权周转时间 */ int ntime; /* 作业所需运行时间 */ char resource10; /* 所需资源 */ struct jcb *link; /* 结构体指针 */ *p,*q,*head=null;typedef struct jcb jcb;（2）初始化结构体 void inital()int i;printf(ninput jcb numn)

18、;scanf(%d,&n);printf(inputnnamettstntimetresourcen);for(i=0;iname,&p-ts,&p-ntime,&p-resource); p-state=w; p-link=null; if(head=null) head=q=p; else q-link=p; q=p; （3）打开文件函数 void fileinput()file *fp;int i;if(fp=fopen(os2.txt,r)=null) printf( open error!) ; fscanf(fp,%dn,&n);for(i=0;iname,&p-ts,&p-nti

19、me,&p-resource); p-state=w; p-link=null; if(head=null) head=q=p; else q-link=p; q=p; fclose(fp);（4）打印作业信息 void print(jcb *pr,int m)jcb *p; printf(ntime=%d,time); if(m=3) printf(nnametstatettstntimetsupertsourcettbttcttitwin); printf(%st%ct%dt%dt%4.2ft%st%dt%dt%4.2ft%4.2fn, pr-name,pr-state,pr-ts,pr-

20、ntime,pr-super,pr-resource,pr-tb,pr-tc,pr-ti,pr-wi); else printf(nnametstatettstntimetsourcettbttcttitwin); printf(%st%ct%dt%dt%st%dt%dt%4.2ft%4.2fn, pr-name,pr-state,pr-ts,pr-ntime,pr-resource,pr-tb,pr-tc,pr-ti,pr-wi); p=head; do if(p-state=w) if(m=3) printf(%st%ct%dt%dt%4.2ft%sn, p-name,p-state,p-ts,p-n