班號: 116112
姓名: 李旭
學號: 20111003534
實習報告
【實習一】 線性表及其應用
n(n>20)的階乘
【問題描述】
大數運算——計算n的階乘(n>=20)。
【基本要求】
(1)資料的表示和儲存:
(1.1) 累積運算的中間結果和最終的計算結果的資料型別要求是整型——這是問題本身的要求;
(1.2)試設計合適的儲存結構,要求每個元素或結點最多儲存資料的3位數值。
(2)資料的操作及其實現:
基於設計的儲存結構實現乘法操作,要求從鍵盤上輸入n值,在螢幕上顯示最終計算結果。
【問題分析】
(1)設計資料的儲存結構:
介於乘運算的精確性以及實型資料表示的不精確性,本題不能採用實型表示累積運算的中間結果和最終的計算結果,而只能用整型。然而由於普通整型和長整型所能表述數的範圍受其字長的限制,不能表示大數階乘的累積結果,故必須設計乙個合適的資料結構實現對資料的儲存,例如可以讓每個元素或結點儲存資料的若干位數值。
從問題描述不難看出n值為任意值,故為使程式盡量不受限制,應採用動態儲存結構。
累積運算的特點是當前的計算結果是下次乘法運算的乘數。
實現兩個數的乘法運算須考慮:
(1)乘數的各位數都要與被乘數進行乘法運算;
(2)乘法過程中的進製問題及其實現;
(3)因每個元素或結點最多儲存資料的3位數值,故當元素或結點中的數值大於999,需向前乙個元素或結點進製。
綜合以上幾點,我採用了單鏈表的儲存結構形式。
(2)階乘演算法的實現:
1. 鏈表型資料乘法的具體實現描述:
(1)初始演算法
順序訪問對每個節點上的資料乘以要乘的數後在順序訪問檢視是否需要進製,大於999則向前進製,如果前面沒有節點則新增新節點儲存進製的數
(2)改進演算法
將原始演算法的乘操作和進製操作合在一起進行,提高程式效率.
2. 資料輸出演算法具體實現描述
從高位向低位順序輸出節點上儲存的資料,注意補零,最高位的節點不補,其它節點要補。對於最後的結果,因為我採用的是普通的單鏈表演算法,因此我新增了乙個逆置的演算法。
【演算法實現的源**】
1. 鏈表型資料乘法
void faclist::fac(int n)//階乘操作
}output(first);
}2. 資料輸出演算法
void faclist::output(linknode *current)//輸出函式
}3. 逆置演算法
linknode *faclist::reverselist()
else
此時q指向原始鍊錶最後乙個元素,也是逆轉後的鍊錶的表頭元素
first->link->link = null; //設定鍊錶尾
first->link = p調整煉表頭
return first->link;
}}【測試資料】
(1)n=20,n!= 2432902008176640000
(2)n=25,n!=15511210043330985984000000
(3)n=30,n!=265252859812191058636308480000000
(4)n=40,n!=815915283247897734345611269596115894272000000000
【測試截圖】
【實習二】 棧及佇列的應用
棧及佇列的應用
【問題描述】
表示式求值。
【基本要求】
實現關鍵
棧的使用;
兩位數以上、負數、小數點;
實現方式
控制台程式;
mfc對話方塊;
【問題分析】
要實現表示式運算,有兩個問題需要解決,首先是如何得到表示式,然後是怎樣進行計算 。對於計算,我們可以考慮用棧來實現,根據書上的內容,我決定用字尾輸入表示式,然後計算。通過順序讀取字串,遇到數字直接輸出,遇到運算子,先和運棧的最上面的乙個運算子比較優先順序,如果比其大就壓入棧,比其小則彈出棧頂元素。
如果相等則彈出棧的第乙個元素不進行操作。
對於字尾表示式,由於我們習慣使用字首輸入,定義乙個轉換函式即可將字尾表示式轉換為字首。
【演算法實現的源**】
(1)計算器演算法**:
void calculator::dooperator(char op)
//沒有除零,做運算
break;
}else clear();
};bool calculator::get2operand(double &left,double &right)
s.pop(right); //取右運算元
if (s.isempty()==true檢查棧空否
s.pop(left);//取左運算元
return true;
};void calculator::addoperand(double value)
;void calculator::run()
}cout<};
void calculator::clear()
;(2)轉換字尾演算法:
int isp(char ch棧內優先數的定義
{ switch(ch)
{case'#':return 0;break;
case'(':return 1;break;
case'*':return 5;break;
case'/':return 5;break;
case'%':return 5;break;
case'+':return 3;break;
case'-':return 3;break;
資料結構上機報告 迷宮
迷宮求解 小組成員 1 問題提出 利用棧結構實現迷宮求解問題。迷宮求解問題如下 心理學家把乙隻老鼠從乙個無頂蓋的大盒子的入口趕進迷宮,迷宮中設定很多隔壁,對前進方向形成了多處障礙,心理學家在迷宮的唯一出口放置了一塊乳酪,吸引老鼠在迷宮中尋找通路以到達出口,測試演算法的迷宮如下圖所示 2 問題分析及演...
資料結構上機實驗報告
一 實驗目的 文學研究人員需要統計某篇英文 中某些形容詞的出現次數和位置,試寫出乙個實現這一目標的文字統計系統,成為 文學研究助手 二 實驗內容 英文 存放在乙個文字檔案中 帶統計的額詞彙集合要以此輸入完畢,即統計工作必須在程式的以此執行後全部完成 程式的輸出結果是每個詞的出現次數和出現位置所在的行...
資料結構上機實驗報告
1.實習題目 問題描述 假設某銀行有四個視窗對外置待客戶,從早晨銀行開門起不斷有客戶進入銀行。由於每個視窗在某個時刻只能接待乙個客戶,因此在客戶人數眾多時需在每個視窗前順次排隊,對於剛進入銀行的客戶,如果某個視窗的業務員正空閒,則可上前辦理業務,反之,若四個視窗均有客戶所佔,他便會排在人數最少的隊伍...