《數(shù)據(jù)結(jié)構(gòu)》課件附錄A

附錄A課程設(shè)計(jì)指導(dǎo)問題1：設(shè)計(jì)一程序，要求從鍵盤上輸入一個(gè)只含加、減、乘、除等四種運(yùn)算符的算術(shù)表達(dá)式，便可計(jì)算表達(dá)式的結(jié)果。

解：本題的求解如下。

1.相關(guān)知識(shí)要對一個(gè)表達(dá)式求值，首先要了解算術(shù)四則運(yùn)算的規(guī)則。即：

(1)先乘除，后加減。

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

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

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

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

=4?+?20?+?8

=24?+?8

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

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

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

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

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

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

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

3.程序?qū)崿F(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]; /*定義一個(gè)全程變量，用以存放輸入的表達(dá)式*/intflag=1; /*標(biāo)志變量值為0則說明表達(dá)式已求解完畢*/voidpush_r(chare) /*算符進(jìn)棧函數(shù)*/{if(tr.top==MAX){printf("內(nèi)存不夠!\n");exit(-2);}else{tr.top=tr.top+1;tr.elem[tr.top]=e;

}}

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

if(nd.top==2*MAX-1){printf("內(nèi)存不夠!\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() /*運(yùn)算函數(shù)*/{floatn1,n2;charop;/*取得兩操作數(shù)*/n2=pop_d();n1=pop_d();op=pop_r(); /*取得運(yùn)算符*/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); /*將運(yùn)算的中間結(jié)果進(jìn)棧保存*/}voidstch(char*bb,charitem)

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

/*測試運(yùn)算是否結(jié)束，并顯示最終結(jié)果*/{

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

/*顯示最后的計(jì)算結(jié)果*/flag=0; /*修改標(biāo)志變量，以結(jié)束程序的運(yùn)行*/}main(){intyy=0;charch,bb[10]="",*sp,*qq;/*設(shè)置兩個(gè)棧為空*/tr.top=0;nd.top=0;sp=aa; /*讓字符指針sq指向表達(dá)式的第一個(gè)字符*/printf("請輸入表達(dá)式：\n");gets(sp); /*接收表達(dá)式*/for(;flag!=0;sp++){yy=0; if(*sp=='') /*去除表達(dá)式中的空格*/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ù)字字符串轉(zhuǎn)換為數(shù)值后進(jìn)操作數(shù)棧*/bb[0]='\0';if(test(qq))

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

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

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

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

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

count();

/*則去計(jì)算原來?xiàng)Ｖ械倪\(yùn)算*/qq=sp;push_r(ch);

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

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

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

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

(1)用頂點(diǎn)表示選手。

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

2.算法設(shè)計(jì)

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

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

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

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

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

3.程序?qū)崿F(xiàn)為上機(jī)實(shí)現(xiàn)