中国地质大学(武汉)信息工程学院 数据结构实习报告.docx

《中国地质大学(武汉)信息工程学院 数据结构实习报告.docx》由会员分享，可在线阅读，更多相关《中国地质大学(武汉)信息工程学院 数据结构实习报告.docx（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、?数据结构?课程设计学生姓名： 占 昭 班 学 号： 20211003494 指导教师： 吴 亮 中国地质大学武汉信息工程学院 2021 年 11 月1.题目:n nn20的阶乘n 【问题描述】n 大数运算计算n的阶乘n=20。n 【根本要求】n 1数据的表示和存储；n 累积运算的中间结果和最终的计算结果的数据类型要求是整型这是问题本身的要求；n 试设计适宜的存储结构，要求每个元素或结点最多存储数据的3位数值。 n 2数据的操作及其实现：n 基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。n 【测试数据】n 1n20，n！2432902021176640000n

2、 2n30，n！v 【实现提示】v 1设计数据的存储结构：v 介于阶乘运算的精确性以及实型数据表示的不精确性，此题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个适宜的数据结构实现对数据的存储，例如可以让每个元素或结点存储数据的假设干位数值。v 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构【可采用的数据结构】 1采用链式存储结构实现普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构。 2采用动态数组实现。设计思路：此题思路较为简单,将大

3、数数存于一个数组里,每个元素存一个3位数,然后设计好数与数之间的乘法,已经将数存入数组的函数即可;n 输入：1n20，n 输出：n！2432902021176640000n 输入：2n30，n 输出：n！/源码：/ test21.cpp : Defines the entry point for the console application./#include stdafx.h#include iostreamusing namespace std;int trans(int b,int a);int mult(int *b,int l,int *c,int n);void OutPut(i

4、nt b,int k);int add(int b,int k);int main(int argc, char* argv)int c60;memset(c,0,60);int i(1);int L=trans(c,i);/将i存入c中int b60;memset(b,0,60);int sum(1);int k=trans(b,sum);/把sum存入b中int n;cinn;while(n-)k=mult(b,k,c,L);/sum=i*sumL=add(c,L);/i+OutPut(b,k);return 0;int trans(int b,int a)/把a存入b中int i=0;m

5、emset(b,0,60);while(a!=0)bi+=a%1000;a=a/1000;/每三位存入数组b中return i;/b的位数3个3个的int mult(int *b,int l,int *c,int n)/l为b的长度int s60;memset(s,0,60);for(int j=0;jn;j+)/cfor(int i=0;il;i+)/bsi+j+=bi*cj;/s【k】：b中第i+j位的数之和int max=n+l-1;/当前长度for(int i=0;imax;i+)bi=si;for (int k=0;k999)int s=bk/1000;bk%=1000;bk+1+=

6、s;if(bmax!=0) +max;return max;void OutPut(int b,int k)/输出结果for(int i=0;ik;i+)if(i=0) cout=100) coutbk-i-1;/三位数else if(bk-i-19) cout0bk-i-1;/两位数else cout00bk-i-1;/一位数cout999)/进位,注意进位后b【i】=0的情况int s=btemp/1000;btemp+%=1000;btemp+=s;+temp;return (ktemp? k:temp);/题目2:题目：表达式求值v 要求：实现关键 栈的使用 两位数以上、负数、小数点？

7、v 实现方式 控制台程序 MFC对话框设计思路：参照课本上把中缀表达式改为后缀表达式输出的方法，略作改良，运用两个栈，一个符号栈char型，存储运算符，一个数字栈，存储数字设为double型；接着解决输入的问题，本程序运用了一个二维数组，以便暂时存储double型数字和运算符刚开始二者均为char型，主要是为了方便解决浮点中小数点的输入以及存储问题，然后取每次输入的第一个字符，假设为数字，那么运用atof函数将字符串转换为浮点数，将其压人数字栈中；假设为运算符，那么根据isp函数和icp函数进行判断是将其压人字符栈中还是进行运算从数据栈中退出2个数据，根据运算符进行运算，然后将运算结果压人栈中

8、；重复以上步骤，直至字符栈为空，最后取数据栈内数据，此即为最终的运算结果，输出即可。测试数据：*6/5=;逐个输入字符，如下列图输出结果：运行正确！源码/r.cpp#include stdafx.h#include LinkedStack.h#include iostreamusing namespace std;int isp(char ch);int icp(char ch);int main(int argc, char* argv)char p2030;/二维数组，p【i】i20表示一个字符串cout请输入要计算的算式：p0;int i(0);while(pi0!= & ip+i;co

9、ut中缀表示为：endl;for(int j=0;ji;j+)coutpj;coutendl;LinkedStack s1;/char型栈，储存运算符LinkedStack s2;/double型栈，储存数字char ch=;/相当于一个输入的终止符s1.Push(ch); char ch1,op;int k=0;while(s1.IsEmpty()=false )ch=pk0;/取输入字符串的数字符，以便判断它是数字还是运算符if(isdigit(ch)/如果是数字，那么压人double栈s2double x=atof(pk);s2.Push(x);k+;/进入下一个字符串的判断else/如

10、果是运算符s1.getTop(ch1);if(isp(ch1)icp(ch) s1.Pop(op);s2.DoOperator(op);elses1.Pop(op);if(op=() k+;double x;s2.getTop(x);cout最终结果为：xendl;return 0;int isp(char ch)if(ch=)return 0;else if(ch=() return 1;else if(ch=* | ch=/ | ch=%) return 5;else if(ch=+ |ch=-) return 3;else if(ch=) return 6;else coutch;int

11、 icp(char ch)if(ch=)return 0;else if(ch=() return 6;else if(ch=* | ch=/ | ch=%) return 4;else if(ch=+ |ch=-) return 2;else if(ch=) return 1;else coutch;/注意到以上程序的输入比拟麻烦,每输入一个数都要换行,可做一些改良,改良后运行如下:改良后的代码如下:/ test12.cpp : Defines the entry point for the console application./#include stdafx.h#include ios

12、treamusing namespace std;#include LinkedStack.hint isp(char ch)if(ch=)return 0;else if(ch=() return 1;else if(ch=* | ch=/ | ch=%) return 5;else if(ch=+ |ch=-) return 3;else if(ch=) return 6;else coutch;int icp(char ch)if(ch=)return 0;else if(ch=() return 6;else if(ch=* | ch=/ | ch=%) return 4;else i

13、f(ch=+ |ch=-) return 2;else if(ch=) return 1;else coutch;int main(int argc, char* argv)char ch50;char ch1=,op;LinkedStack s1;/char型栈，储存运算符LinkedStack s2;/double型栈，储存数字coutch;s1.Push(ch1);while(!s1.IsEmpty()intn=strlen(ch);/为字符时可能还要用到nif (isdigit(ch0)double x=atof(ch);s2.Push(x);int i(0);while(isdigi

14、t(chi) | chi=.)/是数字就被后面的覆盖for(int j(0);jn;j+)chj=chj+1;n-;else/如果是运算符s1.getTop(ch1);if(isp(ch1)icp(ch0) s1.Push(ch0);for(int j(0);jicp(ch0) s1.Pop(op);s2.DoOperator(op);elses1.Pop(op);if(op=() for(int j(0);jn;j+)chj=chj+1;n-;double x;s2.getTop(x);cout最终结果为：xLoadIcon(IDR_MAINFRAME);void CTestDlg:DoDa

15、taExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CTestDlg)/ NOTE: the ClassWizard will add DDX and DDV calls here/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CTestDlg, CDialog)/AFX_MSG_MAP(CTestDlg)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERYDRAGICON()ON_BN_CLICKED(IDC_BUTTON1, OnButton1)ON_W

16、M_CTLCOLOR()ON_BN_CLICKED(IDC_BUTTON2, OnButton2)ON_BN_CLICKED(IDC_BUTTON3, OnButton3)ON_BN_CLICKED(IDC_BUTTON4, OnButton4)ON_BN_CLICKED(IDC_BUTTON5, OnButton5)ON_BN_CLICKED(IDC_BUTTON6, OnButton6)ON_BN_CLICKED(IDC_BUTTON9, OnButton9)ON_BN_CLICKED(IDC_BUTTON8, OnButton8)ON_BN_CLICKED(IDC_BUTTON7, On

17、Button7)ON_BN_CLICKED(IDC_BUTTON10, OnButton10)ON_BN_CLICKED(IDC_BUTTON11, OnButton11)ON_BN_CLICKED(IDC_BUTTON12, OnButton12)ON_BN_CLICKED(IDC_BUTTON13, OnButton13)ON_BN_CLICKED(IDC_BUTTON14, OnButton14)ON_BN_CLICKED(IDC_BUTTON15, OnButton15)ON_BN_CLICKED(IDC_BUTTON16, OnButton16)ON_BN_CLICKED(IDC_B

18、UTTON17, OnButton17)ON_BN_CLICKED(IDC_BUTTON18, OnButton18)ON_BN_CLICKED(IDC_BUTTON19, OnButton19)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CTestDlg message handlersBOOL CTestDlg:OnInitDialog()CDialog:OnInitDialog();/ Add About. menu item to system menu./ IDM_ABOUTBOX must be in the system command range.ASSERT

19、(IDM_ABOUTBOX & 0xFFF0) = IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX AppendMenu(MF_SEPARATOR);pSysMenu-AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);/ Set the icon for this dialog. The framework does this automatically/ when the applications main window is not a dialogSetIcon(m_hIcon, TRUE);/ Set big ico

20、nSetIcon(m_hIcon, FALSE);/ Set small icon/ TODO: Add extra initialization herereturn TRUE; / return TRUE unless you set the focus to a controlvoid CTestDlg:OnSysCommand(UINT nID, LPARAM lParam)if (nID & 0xFFF0) = IDM_ABOUTBOX)CAboutDlg dlgAbout;dlgAbout.DoModal();elseCDialog:OnSysCommand(nID, lParam

21、);/ If you add a minimize button to your dialog, you will need the code below/ to draw the icon. For MFC applications using the document/view model,/ this is automatically done for you by the framework.void CTestDlg:OnPaint() if (IsIconic()CPaintDC dc(this); / device context for paintingSendMessage(

22、WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);/ Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;GetClientRect(&rect);int x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;/ Draw the icondc.DrawIc

23、on(x, y, m_hIcon);elseCDialog:OnPaint();/ The system calls this to obtain the cursor to display while the user drags/ the minimized window.HCURSOR CTestDlg:OnQueryDragIcon()return (HCURSOR) m_hIcon;/以下是我自己添加的代码，以粗体显示：char ch50;char ch1=,op;LinkedStack s1;/char型栈，储存运算符LinkedStack s2;/double型栈，储存数字voi

24、d CTestDlg:OnButton1() /777777777/ TODO: Add your control notification handler code herestrcat(ch,7);SetDlgItemText(IDC_STATIC1,ch);HBRUSH CTestDlg:OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor) HBRUSH hbr = CDialog:OnCtlColor(pDC, pWnd, nCtlColor);/ TODO: Change any attributes of the DC hereif(nC

25、tlColor=CTLCOLOR_STATIC)pDC-SetTextColor(RGB(0,0,0);pDC-SetBkColor(RGB(247,255,246);/文字背景色HBRUSH b=CreateSolidBrush(RGB(247,255,246);/控件背景色return b;/ TODO: Return a different brush if the default is not desiredreturn hbr;void CTestDlg:OnButton2() /888888888/ TODO: Add your control notification handl

26、er code herestrcat(ch,8);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton3() /9999999999/ TODO: Add your control notification handler code herestrcat(ch,9);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton4() /44444444444/ TODO: Add your control notification handler code herestrcat(ch,4);Se

27、tDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton5() /555555555/ TODO: Add your control notification handler code herestrcat(ch,5);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton6() /66666666/ TODO: Add your control notification handler code herestrcat(ch,6);SetDlgItemText(IDC_STATIC1,ch);vo

28、id CTestDlg:OnButton9() /11111111/ TODO: Add your control notification handler code herestrcat(ch,1);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton8()/2222222222 / TODO: Add your control notification handler code herestrcat(ch,2);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton7() /33333

29、3333/ TODO: Add your control notification handler code herestrcat(ch,3);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton10() /000000000/ TODO: Add your control notification handler code herestrcat(ch,0);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton11() /./ TODO: Add your control notific

30、ation handler code herestrcat(ch,.);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton12() /+/ TODO: Add your control notification handler code herestrcat(ch,+);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton13() /- -/ TODO: Add your control notification handler code herestrcat(ch,-);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton14() / */ TODO: Add your control notification handler code herestrcat(ch,*);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton15() / /