數(shù)據(jù)結(jié)構(gòu)實驗報告表達式求值、任務(wù)調(diào)度

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

2、時共享計算機系統(tǒng)資源。為了使多個任務(wù)均能夠順利執(zhí)行，操作系統(tǒng)要按一定的原則對它們進行調(diào)度，使它們按一定的次序進行。設(shè)只有一個CPU，現(xiàn)有多個任務(wù)，它們需要CPU 服務(wù)的時間已知。在下列假設(shè)下，按平均等待時間最短為原則，設(shè)計算法求出任務(wù)的執(zhí)行順序。忽略任務(wù)提交的時間差，即認為各任務(wù)同時提交。各任務(wù)不同時提交。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計1. 表達式求值：通過算符優(yōu)先算法來進行表達式求值，為實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧，一個稱為OPTR，用以寄存運算符；另一個稱為OPND，用以寄存操作數(shù)或運算結(jié)果。聲明操作數(shù)棧：typedef struct NumStack / number stack int *b

3、ase; int *top; int stacksize; NumStack;聲明運算符棧：typedef struct SymStack / symbol stack char *base; char *top; int stacksize; SymStack;2. 任務(wù)調(diào)度：用結(jié)構(gòu)體存儲每個任務(wù)的任務(wù)順序，需要時間，提交時間，開始時間，等待時間，結(jié)束時間struct taskint order, need, t,start,wait,end; T100;三、算法設(shè)計1.表達式求值：Precede函數(shù)用以比較運算符的優(yōu)先級，返回，= 或 , -, *, /, %, (, , #, ,=, ;

4、 /優(yōu)先級表格 for(i=0;i9;i+) if(Table0i=a) /縱坐標(biāo)尋找 break; for(j=0;j=49&s=57) /數(shù)字的ASCII碼所在范圍 /這兒決定了本程序只能計算一位數(shù)的四則運算 s-=48; return s; else return 0;/ReadNum求值函數(shù)result, 其基本求值過程為：1. 首先至操作數(shù)棧為空棧，表達式起始符#為運算符的棧底元素；2. 依次讀入表達式中每個字符，若是操作數(shù)則進OPND棧，若是運算符則和OPTR棧的棧頂運算符進行比較優(yōu)先權(quán)后做相應(yīng)的操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為#）int r

5、esult(char *a,NumStack *OPND,SymStack *OPTR) /求值 char theta; int b,c,i=0; IntInitStack(OPND); CharInitStack(OPTR); CharPush(OPTR,#); while(1) if(ReadNum(ai) IntPush(OPND,ReadNum(ai+); else if(ai=+|ai=-|ai=*|ai=/|ai=%|ai=#|ai=(|ai=) switch(Precede(ai,CharGetTop(OPTR) case :theta=CharPop(OPTR); /棧頂元素優(yōu)

6、先權(quán)高 c=IntPop(OPND); b=IntPop(OPND); IntPush(OPND,Operate(b,theta,c); break; /switch /else if if(ai=#&CharGetTop(OPTR)=#) printf(The result is %d.n,IntGetTop(OPND); /打印輸出表達式值 return OK; /while/result將中綴表達式轉(zhuǎn)換為前綴表達式：1）求輸入串的逆序。2）檢查輸入的下一元素。3）假如是操作數(shù)，把它添加到輸出串中。4）假如是閉括號，將它壓棧。5）假如是運算符，則i)假如?？?，此運算符入棧。ii)假如棧頂是

7、閉括號，此運算符入棧。iii)假如它的優(yōu)先級高于或等于棧頂運算符，此運算符入棧。iv)否則，棧頂運算符出棧并添加到輸出串中，重復(fù)步驟5。6）假如是開括號，棧中運算符逐個出棧并輸出，直到遇到閉括號。閉括號出棧并丟棄。7）假如輸入還未完畢，跳轉(zhuǎn)到步驟2。8）假如輸入完畢，棧中剩余的所有操作符出棧并加到輸出串中。9）求輸出串的逆序。char perfix(char *a) /此函數(shù)將中綴表達式轉(zhuǎn)換為后綴表達式 char ch, b100; int j=0; SymStack r, *R; R = &r; CharInitStack(R); /CharPush(R,#); int i = strlen

8、(a)-2; ch=ai; while(i=0) if(ch=49&ch=57) ch-=48; bj+=ch; if(ch=) CharPush(R,ch); while(ch=+|ch=-|ch=*|ch=/|ch=%) if(*R).top=(*R).base|CharGetTop(R) = )|Precede(ch,CharGetTop(R)=0;t-) /打印輸出前綴表達式 if(bt=1&bt=49&ch=57) ch-=48; bj+=ch; ch=a+i; else if(ch=() CharPush(R,ch); ch=a+i; else if(ch=) if(CharGet

9、Top(R)!=() bj+=CharPop(R); else CharPop(R); ch=a+i; else if(ch=+|ch=-|ch=*|ch=/|ch=%) if(Precede(ch,CharGetTop(R)=) / if Top(R) =1&bi=9) printf(%d,bi); else printf(%c,bi); /for printf(.n); return OK;/postfix2任務(wù)調(diào)度：(1). 同時提交獲取每個任務(wù)所需的時間，輸出按順序執(zhí)行時每個任務(wù)的序號，開始時間，等待時間和結(jié)束時間；按所需時間從小到大排序后，依次執(zhí)行即為最短等待時間。int cmp(c

10、onst void *a,const void *b) /相同時間排序, 從小到大return (*(struct task *)a).need-(*(struct task *)b).need;void sametime(int n)double sum,sum2;int i;for(i=0;in;i+)/輸入任務(wù)信息 printf(請輸入第%d個任務(wù)所需要的時間: ,i+1);Ti.t=0;scanf(%d,&Ti.need);Ti.order=i+1;t=0;sum=0; printf(順序執(zhí)行:n);printf(序號 開始時間 等待時間 結(jié)束時間n);for(i=0;in;i+)/順

11、序執(zhí)行任務(wù)，輸出執(zhí)行信息 printf(%-7d,i+1);printf(%-7d,t);printf(%-8d,t);t+=Ti.need;printf(%-8d,t);printf(n);sum+=(n-i-1)*Ti.need);printf(n); printf(平均時間最短:n);printf(序號 開始時間 等待時間 結(jié)束時間n);qsort(T, n, sizeof(T0), cmp);/按最短時間排序 t=0;sum2=0;for(i=0;iT*(int *)b.need;void dele()int i;printf(%-10d%-10d%-10d%-20dnn,Tque0.

12、order,Tque0.start,Tque0.wait,Tque0.end);for(i=0;irear-1;i+)quei=quei+1;rear-;int check(int num1)int i;Tque0.need-;if(Tque0.need=0)Tque0.end=t;dele();for(i=0;irear;i+)Tquei.wait+;return 1;elsefor(i=1;irear;i+)Tquei.wait+;return 0;/時間段移動查尋當(dāng)前隊列 void insert(int n)int i,rec;for(i=0;iTn.need)break;rec=i;f

13、or(i=rear;irec;i-)quei=quei-1;querec=n; rear+;void difftime(int n)/輸入本來按照先后順序 int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;in;i+)/輸入每個任務(wù)信息 printf(請輸入第%d個任務(wù)提交時刻和執(zhí)行時間n,i+1,i+1); printf(提交時刻: ); scanf(%d,&Ti.t); printf(執(zhí)行時間: ); scanf(%d,&Ti.need);Ti.order=i+1;Ti.start=-1;Ti.end=-1;Ti.wait=0;printf

14、(序號 開始時間 等待時間 結(jié)束n);que0=0;rear=1;T0.start=0;i=0;t=0;j=1;while(i=Tj.t&jn)/假入在當(dāng)前任務(wù)執(zhí)行時間內(nèi)有任務(wù)提交 insert(j); /把任務(wù)插入到隊列 j+;qsort(que, rear, sizeof(que0), comp);/按時間長短排序 if(Tque0.start=-1)/給隊列最前點賦起始值 Tque0.start=t;for(i=0;in;i+)/計算出所有等待時間 sum+=Ti.wait;printf(平均等待時間為 %.3lfsnn,sum/n);四、界面設(shè)計1.表達式求值需要輸入以#結(jié)尾的中綴表達

15、式，以提示語句的方式給出。輸出注明是什么結(jié)果。2.任務(wù)調(diào)度需要輸入任務(wù)數(shù)，任務(wù)需要執(zhí)行時間，（不同時需要任務(wù)提交時間），按平均等待時間最短為原則，輸出出任務(wù)的執(zhí)行順序。五、運行測試與分析1.表達式求值1).輸入一個以#結(jié)尾的中綴表達式：2).輸出計算結(jié)果，后綴表達式以及前綴表達式：3.任務(wù)調(diào)度：(1). 同時提交i).輸入:ii).輸出:(2). 不同時間提交i).輸入:ii).輸出:六、實驗收獲與思考1熟練掌握棧的定義及使用。2了解表達式求值的轉(zhuǎn)換算法。設(shè)計前、后綴表達式求值算法。3設(shè)計操作數(shù)為多位實數(shù)，操作符為加、減、乘、除、求模的中綴表達式求值算法。定義算數(shù)符號的優(yōu)先級。4. 從理論到實

16、踐，鞏固了學(xué)過的知識。七、附錄（原程序）1.表達式求值#include #include #include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1typedef struct NumStack / number stack int *base; int *top; int stacksize;NumStack;typedef struct SymStack / symbol stack char *base; char *top; int stacksize;SymStack;

17、void IntInitStack(NumStack *S) S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S-base) exit(ERROR); S-top=S-base; S-stacksize=STACK_INIT_SIZE;/IntInitStackvoid CharInitStack(SymStack *S) S-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S-base) exit(ERROR); S-top=S-base; S-stacksize=STAC

18、K_INIT_SIZE;/CharInitStackint IntGetTop(NumStack *S) /取棧頂元素 int e; if(*S).top=(*S).base) return 0; e=*(*S).top-1); return e;/IntGetTopchar CharGetTop(SymStack *S) /取棧頂元素 char e; if(*S).top=(*S).base) return 0; e=*(*S).top-1); return e;/IntGetTopint IntPush(NumStack *S,int e) *(*S).top+=e; return OK;

19、/IntPushint CharPush(SymStack *S,char e) *(*S).top+=e; return OK;/CharPushint IntPop(NumStack *S) int e; if(*S).top=(*S).base) return 0; e=*-(*S).top; return e;/IntPopint CharPop(SymStack *S) char e; if(*S).top=(*S).base) return 0; e=*-(*S).top; return e;/CharPopchar Precede(char a,char b) int i,j;

20、char Table99= ,+,-,*,/,%,(,),#, +, -, *, /, %, (, , #, ,=, ; /優(yōu)先級表格 for(i=0;i9;i+) if(Table0i=a) /縱坐標(biāo)尋找 break; for(j=0;j=49&s=57) /數(shù)字的ASCII碼所在范圍 /這兒決定了本程序只能計算一位數(shù)的四則運算 s-=48; return s; else return 0;/ReadNumint result(char *a,NumStack *OPND,SymStack *OPTR) /求值 char theta; int b,c,i=0; IntInitStack(OP

21、ND); CharInitStack(OPTR); CharPush(OPTR,#); while(1) if(ReadNum(ai) IntPush(OPND,ReadNum(ai+); else if(ai=+|ai=-|ai=*|ai=/|ai=%|ai=#|ai=(|ai=) switch(Precede(ai,CharGetTop(OPTR) case :theta=CharPop(OPTR); /棧頂元素優(yōu)先權(quán)高 c=IntPop(OPND); b=IntPop(OPND); IntPush(OPND,Operate(b,theta,c); break; /switch /else

22、 if if(ai=#&CharGetTop(OPTR)=#) printf(表達式的結(jié)果是%d.n,IntGetTop(OPND); /打印輸出表達式值 return OK; /while/reslutchar postfix(char *a) /此函數(shù)將中綴表達式轉(zhuǎn)換為后綴表達式 char ch, b100; int i=0, j=0; SymStack r, *R; R = &r; CharInitStack(R); CharPush(R,#); ch=ai; while(ch!=#) if(ch=49&ch=57) ch-=48; bj+=ch; ch=a+i; else if(ch=

23、() CharPush(R,ch); ch=a+i; else if(ch=) if(CharGetTop(R)!=() bj+=CharPop(R); else CharPop(R); ch=a+i; else if(ch=+|ch=-|ch=*|ch=/|ch=%) if(Precede(ch,CharGetTop(R)=) / if Top(R) =1&bi=0) if(ch=49&ch=57) ch-=48; bj+=ch; if(ch=) CharPush(R,ch); while(ch=+|ch=-|ch=*|ch=/|ch=%) if(*R).top=(*R).base|Char

24、GetTop(R) = )|Precede(ch,CharGetTop(R)=0;t-) /打印輸出前綴表達式 if(bt=1&bt=9) printf(%d,bt); else printf(%c,bt); /for printf(.n); return OK;/perfixvoid main() /主函數(shù)，使用自定義函數(shù)完成功能 char a100; NumStack s1,*OPND; SymStack s2,*OPTR; OPND=&s1; OPTR=&s2; printf(請輸入一個以#結(jié)尾的中綴表達式.n); printf(這個表達式:); scanf(%s,&a); result

25、(a,OPND,OPTR); postfix(a); perfix(a);2.任務(wù)調(diào)度1)同時提交#include #include #include int que100,rear=0,t=0;struct taskint order,need,t,start,wait,end;/任務(wù)順序，需要時間，提交時間，開始時間，等待時間，結(jié)束時間 T100;int comp(const void *a,const void *b)/不同時間排序 return T*(int *)a.needT*(int *)b.need;void dele()int i;printf(%-10d%-10d%-10d%

26、-20dnn,Tque0.order,Tque0.start,Tque0.wait,Tque0.end);for(i=0;irear-1;i+)quei=quei+1;rear-;int check(int num1)int i;Tque0.need-;if(Tque0.need=0)Tque0.end=t;dele();for(i=0;irear;i+)Tquei.wait+;return 1;elsefor(i=1;irear;i+)Tquei.wait+;return 0;/時間段移動查尋當(dāng)前隊列 void insert(int n)int i,rec;for(i=0;iTn.need)

27、break;rec=i;for(i=rear;irec;i-)quei=quei-1;querec=n; rear+;void difftime(int n)/輸入本來按照先后順序 int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;in;i+)/輸入每個任務(wù)信息 printf(請輸入第%d個任務(wù)提交時刻和執(zhí)行時間n,i+1,i+1); printf(提交時刻: ); scanf(%d,&Ti.t); printf(執(zhí)行時間: ); scanf(%d,&Ti.need);Ti.order=i+1;Ti.start=-1;Ti.end=-1;Ti.

28、wait=0;printf(序號 開始時間 等待時間 結(jié)束n);que0=0;rear=1;T0.start=0;i=0;t=0;j=1;while(i=Tj.t&jn)/假入在當(dāng)前任務(wù)執(zhí)行時間內(nèi)有任務(wù)提交 insert(j); /把任務(wù)插入到隊列 j+;qsort(que, rear, sizeof(que0), comp);/按時間長短排序 if(Tque0.start=-1)/給隊列最前點賦起始值 Tque0.start=t;for(i=0;in;i+)/計算出所有等待時間 sum+=Ti.wait;printf(平均等待時間為 %.3lfsnn,sum/n);int main()int n;printf(請輸入任務(wù)數(shù): );while(scanf(%d,&n)!=EOF)if(n=0)printf(輸入錯誤,程序結(jié)束);break;difftime(n);return 0;2)不同時提交#include #include #include int que100,rear=0,t