《數(shù)據(jù)結構》課件附錄A

附錄A課程設計指導問題1：設計一程序，要求從鍵盤上輸入一個只含加、減、乘、除等四種運算符的算術表達式，便可計算表達式的結果。

解：本題的求解如下。

1.相關知識要對一個表達式求值，首先要了解算術四則運算的規(guī)則。即：

(1)先乘除，后加減。

(2)同級運算，從左到右。

(3)先括號內，后括號外。因此，例如求解表達式4?+?5?×?(6-2)?+?8，根據(jù)運算規(guī)則，這個表達式的計算順序應為

4?+?5?×?(6-2)?+?8

=4?+?5?×?4?+?8

=4?+?20?+?8

=24?+?8

=32這種根據(jù)運算符的優(yōu)先關系來實現(xiàn)對表達式求值的方法稱為“算符優(yōu)先法”。任何一個表達式都是由操作數(shù)、算符組成的。一般地，操作數(shù)既可以是常數(shù)也可以是被說明為變量或常量的標識符。算符包括運算符和界符兩種，其中運算符又可以分為算術運算符、關系運算符和邏輯運算符等三類，基本界符有左右括號和表達式結束符等。為了敘述的簡潔，我們僅討論簡單算術表達式的求值問題。這種表達式只含加、減、乘、除等四種運算符。根據(jù)上述的三條運算規(guī)則，我們可以把算符的優(yōu)先級從高到低排列出來為：左括號→乘、除→加、減→右括號。因此，在運算的每一步中，任意兩個相繼出現(xiàn)的算符a和b，至多是下面三種關系之一：

a＜ba的優(yōu)先級低于b

a＝ba的優(yōu)先級等于b

a＞ba的優(yōu)先級高于b

2.算法分析為實現(xiàn)算符優(yōu)先算法，使用兩個工作棧。一個稱做算符棧tr，用以存放算符；另一個稱做操作數(shù)棧nd，用以存放操作數(shù)或運算結果。

(1)首先置操作數(shù)棧和算符棧為空棧。

(2)讀入表達式，用一個指針指向該表達式的每個字符，若是操作數(shù)，則進nd棧，若是算符，則與tr棧的棧頂算符比較優(yōu)先級后做相應操作，直到整個表達式求值完畢(即tr棧為空)。

3.程序實現(xiàn)

#include<stdio.h>

#include<stdlib.h>

#include<io.h>

#include<string.h>

#defineMAX20

structst_optr /*算符棧的描述*/{charelem[MAX+1];inttop;};structst_opnd /*操作數(shù)棧的描述*/{floatelem[2*MAX];inttop;};structst_optrtr;structst_opndnd;charaa[30]; /*定義一個全程變量，用以存放輸入的表達式*/intflag=1; /*標志變量值為0則說明表達式已求解完畢*/voidpush_r(chare) /*算符進棧函數(shù)*/{if(tr.top==MAX){printf("內存不夠!\n");exit(-2);}else{tr.top=tr.top+1;tr.elem[tr.top]=e;

}}

voidpush_d(floatm) /*操作數(shù)進棧函數(shù)*/{

if(nd.top==2*MAX-1){printf("內存不夠!\n");exit(-2);}else{nd.top=nd.top+1;nd.elem[nd.top]=m;}}charpop_r() /*算符出棧函數(shù)*/{

chare; if(tr.top>0) {

e=tr.elem[tr.top];

tr.top=tr.top-1;returne;}elsereturnNULL;}chargettop_r() /*取算符棧棧頂元素的函數(shù)*/{ chare; if(tr.top>0){

e=tr.elem[tr.top];

returne;}elsereturnNULL;}floatpop_d() /*操作數(shù)出棧函數(shù)*/{ floatm; if(nd.top>0){m=nd.elem[nd.top];nd.top=nd.top-1;returnm;}elsereturnNULL;}voidcount() /*運算函數(shù)*/{floatn1,n2;charop;/*取得兩操作數(shù)*/n2=pop_d();n1=pop_d();op=pop_r(); /*取得運算符*/switch(op){case'+':n1=n1+n2;break;case'-':n1=n1-n2;break;case'*':n1=n1*n2;break;case'/':n1=n1/n2;break;}push_d(n1); /*將運算的中間結果進棧保存*/}voidstch(char*bb,charitem)

/*數(shù)值型字符串形成函數(shù)*/{char*ee;ee=bb+strlen(bb);*ee=item,ee++;*ee='\0';}inttest(char*qq)

/*測試運算是否結束，并顯示最終結果*/{

intkk;kk=strlen(aa);if((qq<aa+kk)) /*若還未掃描完畢*/return1; /*返回1，表示應繼續(xù)掃描*/while(tr.top!=0) /*若表達式已全部掃描完，并且算符棧中還有運算符*/count(); /*則執(zhí)行最后一次運算*/printf("數(shù)學表達式%s==%f\n",aa,nd.elem[1]);

/*顯示最后的計算結果*/flag=0; /*修改標志變量，以結束程序的運行*/}main(){intyy=0;charch,bb[10]="",*sp,*qq;/*設置兩個棧為空*/tr.top=0;nd.top=0;sp=aa; /*讓字符指針sq指向表達式的第一個字符*/printf("請輸入表達式：\n");gets(sp); /*接收表達式*/for(;flag!=0;sp++){yy=0; if(*sp=='') /*去除表達式中的空格*/continue; while(*sp>='0'&&*sp<='9')

/*若掃描到的是數(shù)字字符*/{yy=1;stch(bb,*sp);

/*則去形成數(shù)字字符串*/ sp++;}/*while*/if(yy==1) /*如果剛處理的是數(shù)字字符串*/{

qq=sp;sp--;push_d(atoi(bb));

/*將數(shù)字字符串轉換為數(shù)值后進操作數(shù)棧*/bb[0]='\0';if(test(qq))

/*測試表達式是否掃描完畢*/continue;}

if(*sp<‘0’||*sp>‘9’) /*若掃描到的字符不是數(shù)字，則進行判斷*/ch=*sp;switch(ch){case'(':qq=sp; /*若是'('算符*/push_r(ch); /*則進算符棧保存*/test(qq);break;case'*':case'/':while(gettop_r()=='*'||gettop_r()=='/')

/*若棧中有乘或除運算符*/count();

/*則先去計算棧中的乘法或除法*/qq=sp;push_r(ch);

/*將這次掃描得到的運算符進棧，以便下次運算*/test(qq);break;case'+':case'-':while(gettop_r()!='('&&tr.top>0)/*若是加法或減法運算符，則只要算符棧中有運算符，并已不是'('運算符。*/

count();

/*則去計算原來棧中的運算*/qq=sp;push_r(ch);

/*保存這次的運算符*/test(qq);break;case')':while(gettop_r()!='(')

/*若掃描到的是')'，且算符棧中有其他運算符*/count(); /*則去計算原來棧中的運算*/pop_r(); /*消去一對括號*/qq=sp+1;test(qq);break;default:printf("輸入錯誤！\n");exit(-1);

/*中斷程序的執(zhí)行*/}/*switch*/}/*for*/}/*main*/問題2：在有n個選手P1，P2，P3，…，Pn參加的單循環(huán)賽中，每對選手之間非勝即負?，F(xiàn)要求求出一個選手序列，，，…,，，使其滿足勝(i?=?1，…，n-1)。解：本題的求解如下：

1.模型表示由于僅涉及到n個選手，并且這些選手之間的關系僅是勝負關系，因此可用圖來表示。

(1)用頂點表示選手。

(2)用弧表示選手之間的勝負關系：當且僅當Pi勝Pj時，有從頂點i到j的一條弧。在這種表示下，本題變成了在有向圖中求解出一條包含所有頂點的簡單路徑的問題。附圖1所示為一個有8個選手的問題的一個示例，其中的一個解為1,2,3,4,8,6,5,7。附圖18個選手比賽情況示例

2.算法設計

(1)設計本題算法的構思：為搜索出符合條件的簡單路徑，需按深度優(yōu)先搜索方式進行遍歷。因此求解算法應是深度遍歷算法的變形形式，也應是遞歸形式的算法。由于要求遍歷序列中的各結點按次序構成一條簡單路徑，因此算法與深度遍歷算法有明顯的不同：并非任意選擇的起點和訪問次序都能得到解。而這些又是事先難以確定的。這就要求在求解過程中進行試探：試探起點以及訪問次序。既然要在求解過程中進行試探，則需要記錄試探的中間狀態(tài)：某頂點是否在當前試探的路徑中，已經(jīng)試探的各頂點的次序，當前正在試探的頂點等。

(2)將所用到的變量及有關參數(shù)設置如下：①設圖為g。②設當前試探路徑中最后的頂點號為v。③?v在試探路徑中的序號為k。④用int型數(shù)組visited[n+1]表示各頂點是否在當前試探的路徑中(初值為全0)。⑤用數(shù)組B[n+1]存儲當前路徑中的各頂點(在前k個元素中，事實上應是棧)。

(3)可能情況的處理：既然是試探型求解，則需對當前頂點v的每個鄰接點(不妨用w表示)進行試探，試探由v經(jīng)w往下是否可以得到解。每個w都可能有成功(指現(xiàn)在可以將該頂點放在路徑上，這包括暫時的和最終的)與失敗(指此路不通)兩種情況，對此應分別作不同的處理：①若試探成功，則應將w放入路徑中，并置相應的狀態(tài)值。然后再由w往下求解。②若不成功，則應恢復w的有關信息，以使w在試探其它路徑時成為可選頂點。為了能求出解以及所有可能的解，需要做如下兩方面的工作：①選擇起點：應以每個頂點為起點進行搜索。②搜索路徑：在從v往下搜索時，應依次選擇v的所有不在當前試探路徑中的鄰接點往下搜索。為此，需要有這方面的保證：應在試探某頂點w后并在換下一個試探頂點前恢復w的有關狀態(tài)，以使其仍為可選擇的頂點。

(4)本算法的基本思想：①若k?=?n，則說明已經(jīng)求得一解，因此可輸出結果，并結束本次調用。②若k＜n，則依次選擇v的所有不在當前試探路徑中的鄰接點w往下搜索，這包括以下的操作：試探：將w放到B[k?+?1]中，并置visited[w]為1，然后以w為起點往下搜索?；謴停簩恢復為不在當前路徑中，以使其在試探其它路徑時可用。

(5)有關算法中的變量設置：可將上述討論中所提及的變量k、v作為參數(shù)(僅提供值而不返回值)，將g作為地址傳送型參數(shù)(雖然不會改變其值，但這種形式更節(jié)省時間和空間)，將數(shù)組B和visited作為全程變量，以便各調用層能共享，并節(jié)省時間、空間，同時使程序更清晰。

3.程序實現(xiàn)為上機實現(xiàn)