【正文】 。如果想退出計(jì)算機(jī)也可以按鍵退出。 程序的流程圖如下： 22 輸入Cin pP == ‘ 0 ’程序結(jié)束 YChangeN輸入計(jì)算式正確 ？JisuanY輸出N下一次計(jì)算 4) 詳細(xì)的程序清單及程序注釋： include iostream include include string include include define derror 1234567 define Maxlen 400 using namespace std。 double k。 if (strcmp(p,0)==0) return。 cout\t\t **************************************endl。 //初始化運(yùn)算符棧 while (*p!=39。break。 } 。: if (dh==1) // +,是正負(fù)號 { if (*p==39。amp。 p++。*39。 } ++。^39。break。 } ++。 break。I39。[]=39。Q39。amp。 p+=4。C39。s39。 break。a39。N39。 return derror。X39。[]=39。a39。amp。 p+=3。amp。) { q[i]=39。 *p=39。 dh=0。 =1。 case 39。 。break。: 29 []=fmod([],[])。s39。q39。break。break。) //為數(shù)字字符 { d=10*d+(*q39。 while (*q=39。)。 } return []。) //為 數(shù)字字符 { d=d+x*(*q39。.39。 *q=39。a39。e39。break。break。 case 39。 return derror。*39。 。 //給 q 表達(dá)式添加結(jié)束標(biāo)識 return 1。39。 amp。 } if (*p==39。039。[]=39。B39。 return derror。P39。x39。 break。n39。t39。 p+=3。amp。c39。[]=39。R39。q39。N39。i39。 39。 。p++。^39。 。/39。 } ++。 break。: case 39。 。 dh=1。 //i 作為 q 的下標(biāo) int dh=1。 24 meun()。) //循環(huán)執(zhí)行 { cout Input Please:。 }opnd。并將運(yùn)算結(jié)果存入該棧中。 } } 運(yùn)行結(jié)果 ? 不是 二叉排序 樹時(shí)的結(jié)果 ? 是 二叉排序樹時(shí)的結(jié)果 存在的問題 判斷是否 二叉排序樹時(shí)應(yīng)注意 pkeyk 的判定和 k=pkey 的賦值步驟。 實(shí)驗(yàn)十五、判斷二叉排序樹 問題的提出 編寫一個(gè)判別給定的二叉樹是否為二叉排序樹的算法，設(shè)二叉樹以二叉鏈表存儲表示，結(jié)點(diǎn)的數(shù)據(jù)域只存放正整數(shù)。 } } if(lown) { i=idx[low].low。 問題的程序代碼 //分塊查找 int blksearch(record r[],index idx[],keytype k,int n) { int i,low=0,high=n1,mid,bh,find=0。 }//將最大的量進(jìn)行“下沉” for(int k=1。 r[j]=r[j1]。 算法分析 Step1：先設(shè)置交換標(biāo)志為假，進(jìn)行 n1 趟的排序?qū)⒆畲蟮牧窟M(jìn)行“下沉”； Step2：再后移一個(gè)數(shù)，重復(fù) Step1，直到得到的結(jié)果為從小到大排好序的結(jié)果，結(jié)束。 while(r[j].key) { r[j+h]=r[j]。iD1。(visited[j]==0)) dfsa(j)。 算法分析 Step1：確定出發(fā)點(diǎn)為 iv ，開始進(jìn)行深度優(yōu) 先搜索； Step2：當(dāng)被訪問過時(shí)，利用 visited[i]=1 進(jìn)行標(biāo)記； Step3：并從未被訪問的鄰接點(diǎn) jv 出發(fā)進(jìn)行深度優(yōu)先搜索遍歷即可。 if(p!=NULL) { leaf = countleaf( plchild )。 實(shí)驗(yàn)十、統(tǒng)計(jì)二叉樹的結(jié)點(diǎn) 問題的提出 采用二叉鏈表結(jié)構(gòu)存儲一棵二叉樹，編寫一個(gè)算法統(tǒng)計(jì)該二叉樹中結(jié)點(diǎn)總數(shù)及葉子結(jié)點(diǎn)總數(shù)。prchild!=NULL amp。 } pC[i][j]=s。j++) { s=0。 實(shí)驗(yàn)八、對稱矩陣相乘 問題的提出 A 和 B 是兩個(gè) n n階的對稱矩陣，以行為主序輸入對稱矩陣的下三角元素，壓縮存儲存入一維數(shù)組 A 和 B，編寫一個(gè)算法計(jì)算對稱矩陣 A 和 B 的乘積，結(jié)果存入二維數(shù)組 C。 }//分別找出 n行的最大值 for(i=1。j=n。 實(shí)驗(yàn)七、找 馬鞍點(diǎn) 問題的提出 若在矩陣 Amn 中存在一個(gè)元素 A[i][j]，其滿足 A[i][j]是第 i行元素中最小值，且又是第 j 列元素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。 算法分析 Step1：先建立一個(gè)存儲數(shù)組，并將串中的前 i個(gè)字符進(jìn)行復(fù)制到 temp 中； Step2：串 S 中除去要求刪除的 m 個(gè)字符，把后面的字符連接到 temp 中； Step3： 將 temp 中的字符 復(fù)制到 S 中，并修改字符串長度加 1。 j++。 return (temp)。 sqrear=(sqrear+1)%m。 } return 0。 for(i=1。 else insert(other,p)。)) insert(letter,p)。pdata=39。 算法分析 Step1： 將單鏈表中的頭結(jié)點(diǎn)與字母比較，判斷是否在 [A,Z]或者 [a,z]之間； Step2：在 [A,Z]或者 [a,z]之間，則將它寫入字母的單鏈表中 ,否則轉(zhuǎn) Step3； Step3： 將單鏈表中的頭結(jié)點(diǎn)與字母比較，判斷是否在 [0,9]之間； Step4：在 [0,9]之間，則將它寫入數(shù)字的單鏈表中否則轉(zhuǎn) Step5； Step5： 將它寫入其他字符的單鏈表中； Step6：取下一結(jié)點(diǎn)，重復(fù) Step1~ Step5，直到結(jié)點(diǎn)完全進(jìn)入 3 個(gè)新的單鏈表，結(jié)束。//p 指針指向頭結(jié)點(diǎn) q=pnext。 //定義 i和 temp 的類型 for(i=1。 datatype temp。 p=headnext。// 原鏈表最后一個(gè)結(jié)點(diǎn)變?yōu)樾骆湵淼念^結(jié)點(diǎn) } 運(yùn)行結(jié)果 存在的問題 與順序表逆置一樣， 逆置表中的元素只能是單個(gè)元素，不能進(jìn)行多位數(shù)的逆置，如下圖所示 3 實(shí)驗(yàn)二、分解單鏈表 問題的提出 已知由不具有頭結(jié)點(diǎn)的單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（字母、數(shù)字和其他字符），試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間， 頭結(jié)點(diǎn)可另辟空間。amp。z39。) insert(digit,p)。//