《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目 1 一元多項(xiàng)式計(jì)算*題目 2 迷宮求解題目 3 翻牌游戲題目 4 作業(yè)調(diào)度姓名：*班級：*計(jì)科（1）班學(xué)號：200310610*題目1 一元多項(xiàng)式計(jì)算1 需求分析1）、能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；2）、能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入。2 算法描述分析任意一元多項(xiàng)式的描述方法可知，一個(gè)一元多項(xiàng)式的每一個(gè)子項(xiàng)都是由“系數(shù)指數(shù)”兩部分來組成的，所以可以將它抽象成一個(gè)由“系數(shù)指數(shù)對”構(gòu)成的線形表，由于對多項(xiàng)式中系數(shù)為0的子項(xiàng)可以不記錄它的指數(shù)值，對于這樣的情況就不再付出存儲(chǔ)空間來存放它了。基于這樣的分析，我們可以采用一個(gè)帶有頭結(jié)點(diǎn)的單鏈表來表示一個(gè)一元多項(xiàng)

2、式。（1）具體數(shù)據(jù)類型如下： typedef struct node float coef; /系數(shù)域 int expn; /指數(shù)域 struct node * next; /指針域，指向下一個(gè)系數(shù)不為0的子項(xiàng) polynode;（2）輸入并建立多項(xiàng)式的功能模塊要求按照指數(shù)遞減的順序和一定的輸入格式輸入各個(gè)系數(shù)不為0的子項(xiàng)的“系數(shù)指數(shù)對”，輸入一個(gè)子項(xiàng)建立一個(gè)相關(guān)結(jié)點(diǎn)，當(dāng)遇到輸入結(jié)束的標(biāo)志的時(shí)候就停止輸入，而轉(zhuǎn)去執(zhí)行程序的下面部分。例如：polynode * create_poly(char ch) /輸入多項(xiàng)式 polynode * p, *s,*r; float x; int y; p=(

3、polynode *)malloc(sizeof(polynode); p-next=null; printf(請輸入一元多項(xiàng)式%c:(格式:系數(shù) 指數(shù),指數(shù)遞減,以0 0結(jié)束.)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）多項(xiàng)式相加的功能模塊此模塊根據(jù)在

4、（1）中建立的兩個(gè)多項(xiàng)式進(jìn)行相加的運(yùn)算，并存放在以c為頭指針的一個(gè)新鏈表中。 polynode * add_poly(polynode * f,polynode * g)/多項(xiàng)式相加 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)/指數(shù)相等時(shí)系數(shù)相加 m=t-coef+q-coef; if(m!=0)/系數(shù)為不0時(shí)加到結(jié)果中去 s=(polyno

5、de *)malloc(sizeof(polynode); s-coef=m; s-expn=t-expn; s-next=null; t=t-next; q=q-next; else/指數(shù)小的加到結(jié)果中去再后移 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）多項(xiàng)式顯示的功能模塊此模塊用于多項(xiàng)式的顯示，程序可以使用圖形界面，通過調(diào)整指數(shù)應(yīng)該出現(xiàn)的坐標(biāo)位置來表示指數(shù)形式，如：x+2x2-3x100；也可以使用文本界面，用“系數(shù)指數(shù)對”的形式表示表達(dá)式，如：(1,1),(2,2),(-3,100)。本程序采用第一種方式，如下：void out_poly(polynode * f)/輸出多項(xiàng)式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 運(yùn)行結(jié)果 題目2 迷宮求解1 需求分析 可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。2 算法描述（1） 輸出相關(guān)參數(shù) for (char ch=y;ch=y|ch=y;cinch)int m,n,prec;cout 請輸入二維迷宮的兩個(gè)維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 初始狀態(tài)：n; showmaze(a,m,n); / start.row=1;start.col=1;/end.row=8;end.col=8; if (mazepath(s,start,end,a) coutn 最后狀態(tài)：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) /當(dāng)前位置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) /留死胡同標(biāo)記apost.rowpost.col=4;bool mazepath(struct sstack &s,struct postype start,struct postype end,int ammnn)/在迷宮a中找出路, 用棧來記錄走的路徑，start、end分別為入、出口坐標(biāo)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） 產(chǎn)生一個(gè)隨機(jī)迷宮void random_creat_maze(int ammnn,int m,int n,int prec) /產(chǎn)生隨機(jī)迷宮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 坐標(biāo)從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 運(yùn)行結(jié)果題目3 翻牌游戲*1需求分析 編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過，輸出：這時(shí)正面向上的牌有哪些？2算法描述（1）采用數(shù)組存儲(chǔ)，循環(huán)嵌套實(shí)現(xiàn) int i,j;

15、int a53;/*定義數(shù)組大小*/ 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 運(yùn)行結(jié)果 題目4 作業(yè)調(diào)度1 需求分析 一個(gè)公司的職員可分為經(jīng)理、部門主管和職工。公司的服務(wù)支持由一個(gè)共同的秘書處承擔(dān)，每一個(gè)職員都可以提出服務(wù)請求（諸如企劃及建議、指示及批復(fù)等），只要填寫一張包括該職員的職位、任務(wù)號、任務(wù)內(nèi)容的表格即可。這張表格內(nèi)的信息存儲(chǔ)在

16、一個(gè)作業(yè)請求記錄jobrequest隊(duì)列中，并根據(jù)時(shí)間將作業(yè)加入到對應(yīng)的優(yōu)先級隊(duì)列中。初始作業(yè)隊(duì)列存放于一個(gè)作業(yè)隊(duì)列文件中，作業(yè)隊(duì)列文件中存放有一批將被加入到優(yōu)先級隊(duì)列的作業(yè)。每個(gè)作業(yè)請求都以記錄的形式存放在“job.dat”文件中。記錄中記載著職員的職位、作業(yè)標(biāo)識(shí)號和工作時(shí)間。所有作業(yè)在讀入后都加入到一個(gè)名為“jobpool-作業(yè)池”的優(yōu)級隊(duì)列中，然后，按其所具有的優(yōu)先級逐個(gè)進(jìn)行處理，并將處理結(jié)果打印出來。程序最后打印為每一類人的總服務(wù)時(shí)間。2 算法描述（1）定義一個(gè)結(jié)構(gòu)體 struct jcb char name10; /* 作業(yè)名 */ char state; /* 作業(yè)狀態(tài) */ in

17、t ts; /* 提交時(shí)間 */ float super; /* 優(yōu)先權(quán) */ int tb; /* 開始運(yùn)行時(shí)間 */ int tc; /* 完成時(shí)間 */ float ti; /* 周轉(zhuǎn)時(shí)間 */ float wi; /* 帶權(quán)周轉(zhuǎn)時(shí)間 */ int ntime; /* 作業(yè)所需運(yùn)行時(shí)間 */ char resource10; /* 所需資源 */ struct jcb *link; /* 結(jié)構(gòu)體指針 */ *p,*q,*head=null;typedef struct jcb jcb;（2）初始化結(jié)構(gòu)體 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）打開文件函數(shù) 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）打印作業(yè)信息 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