1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：表達(dá)式求值問題、任務(wù)調(diào)度實驗類型：綜合性實驗班級：學(xué)號：姓名：李曉彬?qū)嶒炄掌冢?0121.問題描述（1）表達(dá)式求值問題表達(dá)式是數(shù)據(jù)運算的基本形式。人們的書寫習(xí)慣是中綴式，如：11+22*(7-4)/3。中綴式的計算按運算符的優(yōu)先級及括號優(yōu)先的原則，相同級別從左到右進(jìn)行計算。表達(dá)式還有后綴式（如：22 7 4 - * 3 / 11 +）和前綴式（如：+ 11 / * 22 7 4 3）。后綴表達(dá)式和前綴表達(dá)式中沒有括號，給計算帶來方便。如后綴式計算時按運算符出現(xiàn)的先后進(jìn)行計算。本設(shè)計的主要任務(wù)是進(jìn)行表達(dá)式形式的轉(zhuǎn)換及不同形式的表達(dá)式計算。（2）任務(wù)調(diào)度多用戶多任務(wù)操作系

2、統(tǒng)中，多個任務(wù)同時共享計算機(jī)系統(tǒng)資源。為了使多個任務(wù)均能夠順利執(zhí)行，操作系統(tǒng)要按一定的原則對它們進(jìn)行調(diào)度，使它們按一定的次序進(jìn)行。設(shè)只有一個CPU，現(xiàn)有多個任務(wù)，它們需要CPU服務(wù)的時間已知。在下列假設(shè)下，按平均等待時間最短為原則，設(shè)計算法求出任務(wù)的執(zhí)行順序。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計（1）表達(dá)式求值問題typedef struct node char name10; /*進(jìn)程標(biāo)識符*/ int prio; /*進(jìn)程優(yōu)先數(shù)*/ int round; /*進(jìn)程時間輪轉(zhuǎn)時間片*/ int cputime; /*進(jìn)程占用CPU時間*/ int needtime; /*進(jìn)程到完成還要的時間*/ int coun

3、t; /*計數(shù)器*/ char state; /*進(jìn)程的狀態(tài)*/ struct node *next; /*鏈指針*/PCB;（2）任務(wù)調(diào)度typedef struct node char name10; /*進(jìn)程標(biāo)識符*/ int prio; /*進(jìn)程優(yōu)先數(shù)*/ int round; /*進(jìn)程時間輪轉(zhuǎn)時間片*/ int cputime; /*進(jìn)程占用CPU時間*/ int needtime; /*進(jìn)程到完成還要的時間*/ int count; /*計數(shù)器*/ char state; /*進(jìn)程的狀態(tài)*/ struct node *next; /*鏈指針*/PCB;3.算法設(shè)計（1）表達(dá)式求值問

4、題1、算數(shù)表達(dá)式的計算往往是通過棧來實現(xiàn)的。2、讀入或掃描表達(dá)式的同時，完成運算符和操作數(shù)的識別處理。3、識別操作數(shù)時，注意將其字符序列轉(zhuǎn)換成整數(shù)或?qū)崝?shù)形式進(jìn)行存儲。4、可以將表達(dá)式轉(zhuǎn)換成一棵二叉樹，通過先序、中序、后序遍歷得到前綴、中綴、后綴表達(dá)式。（2）任務(wù)調(diào)度1、 為使各任務(wù)平均等待時間最短，如果忽略任務(wù)提交的時間差，調(diào)度時應(yīng)該按短任務(wù)優(yōu)先進(jìn)行調(diào)度，即：按照各任務(wù)需要CPU服務(wù)時間的長短，確定執(zhí)行順序，短的在前，長的在后。2、 根據(jù)上一問題的分析，需要根據(jù)任務(wù)列表，按任務(wù)的CPU服務(wù)時間進(jìn)行排序。3、 如果考慮任務(wù)提交的時間差，應(yīng)該按“最短剩余時間”優(yōu)先進(jìn)行調(diào)度。調(diào)度發(fā)生在每次任務(wù)提交時

5、，從未完成任務(wù)中選擇需要CPU時間最短的任務(wù)。4.界面設(shè)計 程序開始時出現(xiàn)提示漢字：5. 運行、測試與分析1）輸入字符串：2）輸出結(jié)果：6、源代碼：1）后綴表達(dá)式求值：#include stdio.h#include stdlib.h#include string.htypedef struct node char name10; /*進(jìn)程標(biāo)識符*/ int prio; /*進(jìn)程優(yōu)先數(shù)*/ int round; /*進(jìn)程時間輪轉(zhuǎn)時間片*/ int cputime; /*進(jìn)程占用CPU時間*/ int needtime; /*進(jìn)程到完成還要的時間*/ int count; /*計數(shù)器*/ cha

6、r state; /*進(jìn)程的狀態(tài)*/ struct node *next; /*鏈指針*/PCB;PCB *finish,*ready,*tail,*run; /*隊列指針*/int N; /*進(jìn)程數(shù)*/*將就緒隊列中的第一個進(jìn)程投入運行*/firstin() run=ready; /*就緒隊列頭指針賦值給運行頭指針*/ run-state=R; /*進(jìn)程狀態(tài)變?yōu)檫\行態(tài)*/ ready=ready-next; /*就緒對列頭指針后移到下一進(jìn)程*/*標(biāo)題輸出函數(shù)*/void prt1(char a) if(toupper(a)=P) /*優(yōu)先數(shù)法*/ printf( name cputime n

7、eedtime priority staten); else printf( name cputime needtime count round staten);/*進(jìn)程PCB輸出*/void prt2(char a,PCB *q) if(toupper(a)=P) /*優(yōu)先數(shù)法的輸出*/ printf( %-10s%-10d%-10d%-10d %cn,q-name, q-cputime,q-needtime,q-prio,q-state); else/*輪轉(zhuǎn)法的輸出*/ printf( %-10s%-10d%-10d%-10d%-10d %-cn,q-name, q-cputime,q-n

8、eedtime,q-count,q-round,q-state);/*輸出函數(shù)*/void prt(char algo) PCB *p; prt1(algo); /*輸出標(biāo)題*/ if(run!=NULL) /*如果運行指針不空*/ prt2(algo,run); /*輸出當(dāng)前正在運行的PCB*/ p=ready; /*輸出就緒隊列PCB*/ while(p!=NULL) prt2(algo,p); p=p-next; p=finish; /*輸出完成隊列的PCB*/ while(p!=NULL) prt2(algo,p); p=p-next; getch(); /*壓任意鍵繼續(xù)*/*優(yōu)先數(shù)的

9、插入算法*/insert1(PCB *q) PCB *p1,*s,*r; int b; s=q; /*待插入的PCB指針*/ p1=ready; /*就緒隊列頭指針*/ r=p1; /*r做p1的前驅(qū)指針*/ b=1; while(p1!=NULL)&b) /*根據(jù)優(yōu)先數(shù)確定插入位置*/ if(p1-prio=s-prio) r=p1; p1=p1-next; else b=0; if(r!=p1) /*如果條件成立說明插入在r與p1之間*/ r-next=s; s-next=p1; else s-next=p1; /*否則插入在就緒隊列的頭*/ ready=s; /*輪轉(zhuǎn)法插入函數(shù)*/ins

10、ert2(PCB *p2) tail-next=p2; /*將新的PCB插入在當(dāng)前就緒隊列的尾*/ tail=p2; p2-next=NULL;/*優(yōu)先數(shù)創(chuàng)建初始PCB信息*/void create1(char alg) PCB *p; int i,time; char na10; ready=NULL; /*就緒隊列頭指針*/ finish=NULL; /*完成隊列頭指針*/ run=NULL; /*運行隊列指針*/ printf(Enter name and time of processn); /*輸入進(jìn)程標(biāo)識和所需時間創(chuàng)建PCB*/ for(i=1;iname,na); p-cputi

11、me=0; p-needtime=time; p-state=w; p-prio=50-time; if(ready!=NULL) /*就緒隊列不空調(diào)用插入函數(shù)插入*/ insert1(p); else p-next=ready; /*創(chuàng)建就緒隊列的第一個PCB*/ ready=p; clrscr(); printf( output of priority:n); printf(*n); prt(alg); /*輸出進(jìn)程PCB信息*/ run=ready; /*將就緒隊列的第一個進(jìn)程投入運行*/ ready=ready-next; run-state=R;/*輪轉(zhuǎn)法創(chuàng)建進(jìn)程PCB*/void

12、create2(char alg) PCB *p; int i,time; char na10; ready=NULL; finish=NULL; run=NULL; printf(Enter name and time of round processn); for(i=1;iname,na); p-cputime=0; p-needtime=time; p-count=0; /*計數(shù)器*/ p-state=w; p-round=2; /*時間片*/ if(ready!=NULL) insert2(p); else p-next=ready; ready=p; tail=p; clrscr(

13、); printf( output of roundn); printf(*n); prt(alg); /*輸出進(jìn)程PCB信息*/ run=ready; /*將就緒隊列的第一個進(jìn)程投入運行*/ ready=ready-next; run-state=R;/*優(yōu)先數(shù)調(diào)度算法*/priority(char alg) while(run!=NULL) /*當(dāng)運行隊列不空時，有進(jìn)程正在運行*/ run-cputime=run-cputime+1; run-needtime=run-needtime-1; run-prio=run-prio-3; /*每運行一次優(yōu)先數(shù)降低3個單位*/ if(run-ne

14、edtime=0) /*如所需時間為0將其插入完成隊列*/ run-next=finish; finish=run; run-state=F; /*置狀態(tài)為完成態(tài)*/ run=NULL; /*運行隊列頭指針為空*/ if(ready!=NULL) /*如就緒隊列不空*/ firstin(); /*將就緒對列的第一個進(jìn)程投入運行*/ else /*沒有運行完同時優(yōu)先數(shù)不是最大，則將其變?yōu)榫途w態(tài)插入到就緒隊列*/ if(ready!=NULL)&(run-prioprio) run-state=W; insert1(run); firstin(); /*將就緒隊列的第一個進(jìn)程投入運行*/ prt(

15、alg); /*輸出進(jìn)程PCB信息*/ /*時間片輪轉(zhuǎn)法*/roundrun(char alg) while(run!=NULL) run-cputime=run-cputime+1; run-needtime=run-needtime-1; run-count=run-count+1; if(run-needtime=0)/*運行完將其變?yōu)橥瓿蓱B(tài)，插入完成隊列*/ run-next=finish; finish=run; run-state=F; run=NULL; if(ready!=NULL) firstin(); /*就緒對列不空，將第一個進(jìn)程投入運行*/ else if(run-co

16、unt=run-round) /*如果時間片到*/ run-count=0; /*計數(shù)器置0*/ if(ready!=NULL) /*如就緒隊列不空*/ run-state=W; /*將進(jìn)程插入到就緒隊列中等待輪轉(zhuǎn)*/ insert2(run); firstin(); /*將就緒對列的第一個進(jìn)程投入運行*/ prt(alg); /*輸出進(jìn)程信息*/ /*主函數(shù)*/main() char algo; /*算法標(biāo)記*/ clrscr(); printf(type the algorithm:P/R(priority/roundrobin)n); scanf(%c,&algo); /*輸入字符確定算

17、法*/ printf(Enter process numbern); scanf(%d,&N); /*輸入進(jìn)程數(shù)*/ if(algo=P|algo=p) create1(algo); /*優(yōu)先數(shù)法*/ priority(algo); else if(algo=R|algo=r) create2(algo); /*輪轉(zhuǎn)法*/ roundrun(algo); 2）任務(wù)調(diào)度#include stdio.h#include stdlib.h#include string.htypedef struct node char name10; /*進(jìn)程標(biāo)識符*/ int prio; /*進(jìn)程優(yōu)先數(shù)*/ in

18、t round; /*進(jìn)程時間輪轉(zhuǎn)時間片*/ int cputime; /*進(jìn)程占用CPU時間*/ int needtime; /*進(jìn)程到完成還要的時間*/ int count; /*計數(shù)器*/ char state; /*進(jìn)程的狀態(tài)*/ struct node *next; /*鏈指針*/PCB;PCB *finish,*ready,*tail,*run; /*隊列指針*/int N; /*進(jìn)程數(shù)*/*將就緒隊列中的第一個進(jìn)程投入運行*/firstin() run=ready; /*就緒隊列頭指針賦值給運行頭指針*/ run-state=R; /*進(jìn)程狀態(tài)變?yōu)檫\行態(tài)*/ ready=read

19、y-next; /*就緒對列頭指針后移到下一進(jìn)程*/*進(jìn)程PCB輸出*/void prt2(char a,PCB *q) if(toupper(a)=P) /*優(yōu)先數(shù)法的輸出*/ printf( %-10s%-10d%-10d%-10d %cn,q-name, q-cputime,q-needtime,q-prio,q-state); else/*輪轉(zhuǎn)法的輸出*/ printf( %-10s%-10d%-10d%-10d%-10d %-cn,q-name, q-cputime,q-needtime,q-count,q-round,q-state);/*輸出函數(shù)*/void prt(char a

20、lgo) PCB *p; prt1(algo); /*輸出標(biāo)題*/ if(run!=NULL) /*如果運行指針不空*/ prt2(algo,run); /*輸出當(dāng)前正在運行的PCB*/ p=ready; /*輸出就緒隊列PCB*/ while(p!=NULL) prt2(algo,p); p=p-next; p=finish; /*輸出完成隊列的PCB*/ while(p!=NULL) prt2(algo,p); p=p-next; getch(); /*壓任意鍵繼續(xù)*/*優(yōu)先數(shù)的插入算法*/insert1(PCB *q) PCB *p1,*s,*r; int b; s=q; /*待插入的P

21、CB指針*/ p1=ready; /*就緒隊列頭指針*/ r=p1; /*r做p1的前驅(qū)指針*/ b=1; while(p1!=NULL)&b) /*根據(jù)優(yōu)先數(shù)確定插入位置*/ if(p1-prio=s-prio) r=p1; p1=p1-next; else b=0; if(r!=p1) /*如果條件成立說明插入在r與p1之間*/ r-next=s; s-next=p1; else s-next=p1; /*否則插入在就緒隊列的頭*/ ready=s; /*優(yōu)先數(shù)創(chuàng)建初始PCB信息*/void create1(char alg) PCB *p; int i,time; char na10; ready=NULL; /*就緒隊列頭指針*/ finish=NULL; /*完成隊列頭指針*/ run=NULL; /*運行隊列指針*/ printf(Enter name an