[计算机软件及应用]课程设计实验报告长整型数四则运算.doc

数据结构实验数据结构实验报告报告 题目：题目：长整型数四则运算长整型数四则运算 学 院 计算机学院 专 业 软件工程 年级班别 2010 级 1 班 成 绩 _ 2012 年 7 月 1 日 目录目录 课程设计课程设计实实验报告验报告 .1 一、实验一、实验概概要要.- 1 - 二、实验目的二、实验目的.- 1 - 三、实验环境三、实验环境.- 1 - 四、抽象数据类型的四、抽象数据类型的定义定义.- 1 - 五、存储结构的五、存储结构的定定义义.- 2 - 六、算法设计六、算法设计.- 3 - 六、程序运六、程序运行行情况情况.- 16 - 七、实验总结七、实验总结.- 18 - 实验中遇到的问题：实验中遇到的问题：.- 18 - 实验总结：实验总结：.- 19 - 八、思考题八、思考题.- 19 - 第 - 1 - 页 共 40 页 题目：题目：长整型数四则运算长整型数四则运算 一、实验概要一、实验概要 1、 设计一个实现任意长的整数进行四则运算的程序。 2、 输入和输出形式是按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，长 整数位数没有上限，以分号结束长整型数据的输入。 3、 程序执行的命令包括： 1） 、输入长整数 1；2） 、输入长整数 2；3） 、输入执行的运算符；4） 、计算并输出结果；5） 、 结束。 4、测试数据：（以加法为例） （1） 、0;0;+;应输出“0” 。 （2） 、2345,6789;7654,3211;+;应输出“1,0000,0000” 。 （3） 、9999,9999;1,0000,0000,0000;+;应输出“9999,0000,0001”. （4） 、1,0001,0001;1,0001,0001;+;应输出“0”. （5） 、1,0001,0001;1,0001,0000;+;应输出“1” 。 （6） 、9999,9999,9999;9999,9999,9999;+;应输出“1,9999,9999,9998”. （7）1,0000,9999,9999;1;+;应输出“1,0001,0000,0000”. 二、实验目的二、实验目的 输入和输出形式是按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，长整数 位数没有上限，以分号结束长整型数据的输入，进行计算 三、实验环境三、实验环境 Visual C+6.0 四、抽象数据类型的定义四、抽象数据类型的定义 1、 双向循环链表的数据结构及操作定义如下： typedef short ElemType; /定义基本数据类型，我们采用 short 来表示任意 4 位整 数。 typedef struct DuCiLinkNode / 双向循环链表结点的存储结构 ElemType data; struct DuCiLinkNode *prior;/指向上一结点 struct DuCiLinkNode *next;/指向下一结点 DuCiLinkNode,*DuCiLinkList; /定义双向循环链表结点及链表的类型名 基本操作：基本操作： DuCiLinkNode *MakeNode(ElemType e); /以 4 位整数 e 构造 1 个双向循环链表结点 Status InitList(DuCiLinkList *L); /初始化 1 个双向循环链表，分配 1 个结点 作头结点 /数据域赋初值 0，上下结点指针指向自己 void DestroyList(DuCiLinkList *L); /消毁 1 个双向循环链表，释放它所占用的 第 - 2 - 页 共 40 页 所有内存空间 /并让链表*L 指向 NULL void ClearList(DuCiLinkList L); /清除 1 个双向循环链表，释放数据结点所 占用的内存空间 /保留头结点，并将数据域置为 0，上下结 点指针指向自己 Status InsTail(DuCiLinkList L, ElemType e); /在双向循环链表 L 的尾结点之后 加入 1 个以 e 为 /数据域的新结点,并返回 OK; 否 则返回 ERROR。 Status InsFirst(DuCiLinkList L, ElemType e); /将数据元素 e 插入在线性链表 L 头结点之后,并返回 OK; 否则返回 ERROR。 Status CopyList(DuCiLinkList L, DuCiLinkList C); /将双向循环链表 L 复制到双向循环链表 C 中。 2、 长整数的数据类型和和操作定义为： typedef struct DuCiLinkNode LongIntNode,*LongInt;/采用双向循环链表为实际的 存储结构 void add(LongInt c,LongInt a,LongInt b);/长整型数 c = a + b void sub(LongInt c,LongInt a,LongInt b); /长整型数 c = a - b Status mul(LongInt c,LongInt a,LongInt b);/长整型数 c = a * b void div(LongInt c,LongInt a,LongInt b); /长整型数 c = a / b (整除) void factorial(LongInt c,LongInt a);/长整型数 c = a! (阶乘) void power(LongInt c,LongInt a,int n);/长整型数 c = a n (乘方) CString LongInttoCString(LongInt a);/将 LongInt 型数 a 转化成 CString LongInt CStringtoLongInt(CString a);/将 CString 型数 a 转化成 LongInt 五、存储结构的定义五、存储结构的定义 typedef short ElemType; typedef struct DuCiLinkNode / 双向循环链表结点的存储结构 ElemType data; struct DuCiLinkNode *prior;/指向上一结点 struct DuCiLinkNode *next;/指向下一结点 DuCiLinkNode,*DuCiLinkList; 六、算法设计六、算法设计 1. DuCiLink.cpp #include “DuCiLink.h“ 第 - 3 - 页 共 40 页 DuCiLinkNode *MakeNode(ElemType e) /*e 为数据构造结点*/ DuCiLinkNode *s; s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode); if (s) s-data = e; return s; Status InitList(DuCiLinkList *L) /*初始化双向循环链表*/ (*L) = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode); if (!(*L) return OVERFLOW; /存储分配失败 (*L)-data = 0; (*L)-prior = (*L); (*L)-next = (*L); return OK; void DestroyList(DuCiLinkList *L) /*消毁双向循环链表，释放空间*/ DuCiLinkNode *p,*s; p = (*L)-prior; 第 - 4 - 页 共 40 页 (*L)-prior = NULL; while(p)s = p; p = p-prior; free(s); (*L) = NULL; void ClearList(DuCiLinkList L) /*清除双向循环链表，释放空间，保留头结点*/ DuCiLinkNode *p,*s; p = L-prior; while(p!=L)s = p; p = p-prior; free(s); L-data = 0; L-prior = L; L-next = L; Status CopyList(DuCiLinkList L, DuCiLinkList C) /*将双向循环链表 L 复制到双向循环链表 C 中。*/ DuCiLinkNode *p,*s; C-data = L-data; p = L-prior; while(p!=L) 第 - 5 - 页 共 40 页 s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode); if (!s) return OVERFLOW; /存储分配失败 s-data = p-data; C-next-prior = s; s-next = C-next; s-prior = C; C-next = s; p = p-prior; return OK; Status InsTail(DuCiLinkList L, ElemType e) /*在双向循环链表 L 的尾结点之后加入 1 个以 e 为 数据域的新结点,并返回 OK; 否则返回 ERROR。*/ DuCiLinkNode *s; s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode); if (!s) return OVERFLOW; /存储分配失败 s-data = e; s-prior = L-prior; s-next = L; L-prior-next = s; 第 - 6 - 页 共 40 页 L-prior = s; return OK; / InsTail Status InsFirst(DuCiLinkList L, ElemType e) / 将数据元素 e 插入在线性链表 L 头结点之后,并返回 OK; 否则返 回 ERROR。 DuCiLinkNode *s; s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode); if (!s) return OVERFLOW; /存储分配失败 s-data = e; L-next-prior = s; s-next = L-next; s-prior = L; L-next = s; return OK; / InsTail 2. DuCiLink.h typedef int Status; typedef short ElemType; typedef struct DuCiLinkNode / 双向循环链表结点的存储结 第 - 7 - 页 共 40 页 构 ElemType data; struct DuCiLinkNode *prior; /指向上一结点 struct DuCiLinkNode *next;/指向下一结点 DuCiLinkNode,*DuCiLinkList; DuCiLinkNode *MakeNode(ElemType e); /以 4 位整数 e 构造 1 个双 向循环链表结点 Status InitList(DuCiLinkList *L); /初始化 1 个双向循环链表，分配 1 个结点作头结点 void DestroyList(DuCiLinkList *L); /消毁 1 个双向循环链表，释放 空间并让链表*L 指向 NULL void ClearList(DuCiLinkList L); /清除 1 个双向循环链表，释放 空间，保留头结点 Status InsTail(DuCiLinkList L, ElemType e); /在双向循环链表 L 的尾 结点之后加入 1 个以 e 为数据域的新结点,并返回 OK; 否则返回 ERROR。 Status InsFirst(DuCiLinkList L, ElemType e);/将数据元素 e 插入在线 性链表 L 头结点之后,并返回 OK; 否则返回 ERROR。 Status CopyList(DuCiLinkList L, DuCiLinkList C);/将双向循环链表 L 复制到双向循环链表 C 中。 3.LongInt.cpp #include “LongInt.h“ 第 - 8 - 页 共 40 页 Status UnsignedAdd(LongInt c,LongInt a,LongInt b) /*无符号数相加*/ short sum,carry=0; /进位 LongIntNode *pa,*pb; pa = a-prior;/*pa,pb 分别指两个加数的尾结点*/ pb = b-prior; while(pa!=a carry = sum / 10000; /*进位*/ sum = sum % 10000; /*当前组的数值*/ if (!InsFirst(c,sum) return ERROR;/*加到和长整型数的首位*/ pa = pa-prior; pb = pb-prior; c-data+; while(pa!=a)/* a 中还有没加的组时，补到和上去*/ sum = pa-data + carry; carry = sum / 10000; sum = sum % 10000; 第 - 9 - 页 共 40 页 if (!InsFirst(c,sum) return ERROR; pa = pa-prior; c-data+; while(pb!=b)/* b 中还有没加的组时，补到和上去*/ sum = pb-data + carry; carry = sum / 10000; sum = sum % 10000; if (!InsFirst(c,sum) return ERROR; pb = pb-prior; c-data+; if(carry)/* 如果还有进位*/ if (!InsFirst(c,carry) return ERROR; c-data+; return OK; Status UnsignedSub(LongInt c,LongInt a,LongInt b) 第 - 10 - 页 共 40 页 /*无符号数相减*/ short diff,borrow=0; LongIntNode *pa,*pb,*pc,*s; pa = a-prior; pb = b-prior; while(pa!=a if (diff prior; pb = pb-prior; c-data+; while(pa!=a) diff = pa-data - borrow; if (diff prior; c-data+; 第 - 11 - 页 共 40 页 if(borrow | pb!=b) return PleaseExchange; /* 不够减，提请调用程序交换 a,b */ pc = c-next; while (pc-data = 0 pc = pc-next; c-next = pc; pc-prior = c; free(s); c-data-; return OK; void add(LongInt c,LongInt a,LongInt b) /*加法*/ if (a-data * b-data) 0) /*两数同号，则执行无符号加法，零为当成正数处理*/ UnsignedAdd(c,a,b); c-data *= (a-data=0)?1:-1; 第 - 12 - 页 共 40 页 else/*两数异号，则执行无符号减法*/ /*总是用绝对值大的数减绝对小的数*/ if(UnsignedSub(c,a,b) = PleaseExchange) /* a 不够 b 减，则交换 a,b 的顺序再减*/ ClearList(c); UnsignedSub(c,b,a); c-data *= (b-data=0)?1:-1; else/* a 够 b 减 */ c-data *= (a-data=0)?1:-1; void sub(LongInt c,LongInt a,LongInt b) /*减法*/ b-data *= -1; add(c,a,b); b-data *= -1; 第 - 13 - 页 共 40 页 void mul(LongInt c,LongInt a,LongInt b) long product,carry=0; /进位 short sum; LongIntNode *pa,*pb,*pcend,*pccur,*pc,*s; pa = a-prior;/*从 a 的尾结点，即最后一个 4 位组开始*/ pcend = c;/*记录 a 的每一组与 b 相乘时最低位应加到 积的哪一组之前*/ while(pa!=a)/*只要 a 中还有结点未纳入运算，则循环*/ if (pa-data = 0) /*如果 a 的当前 4 位组为 0，则直接加 0*/ InsFirst(c,0); c-data+; else pccur = pcend-prior;/*记录乘数应加到积的哪一组*/ pb = b-prior; /*取 b 的每组与 a 的当前组相乘*/ while(pb!=b) /*特别注意两个 0-9999 以内的数相乘需要用 long 来记 录，否则会有溢出*/ 第 - 14 - 页 共 40 页 product = carry + (long)pa-data * (long)pb-data; carry = product / 10000;/*进位*/ product = product % 10000;/*余数，也即当前组的值*/ if (pccur = c) /*需要新的结点来存放数据*/ InsFirst(c,(short)product); pccur = c-next; c-data+; else /*以前的运算已经插入过本 4 位组，则增加到当前 组上*/ sum = pccur-data + (short)product; if (sum 9999)carry+; sum -= 10000; pccur-data = sum; pccur = pccur-prior; /*移动乘积数的当前指针*/ pb = pb-prior;/*移动被乘数的当前指针*/ /*如果还有进位，则加上去*/ if(carry0) InsFirst(c,(short)carry); carry = 0;c-data+;/*清空进位器，并将 4 位数组数加 1*/ 第 - 15 - 页 共 40 页 pcend = pcend-prior;/*乘积数的最低位上移一组*/ pa = pa-prior;/*乘数上移一组*/ c-data *= (a-data * b-data)=0)?1:-1; pc = c-next; while (pc-data = 0 pc = pc-next; c-next = pc; pc-prior = c; free(s); c-data-; void Addn(LongInt c, short n) /*一个正的长整型加一个最大为 20000 的正数*/ short carry = n,sum; LongIntNode *pc; pc = c-prior; 第 - 16 - 页 共 40 页 while(carry != 0 carry = sum / 10000; sum = sum % 10000; pc-data = sum; pc = pc-prior; while(carry != 0)/*如果进位不为零说明需要新的结点*/ sum = carry; carry = sum / 10000; sum = sum % 10000; InsFirst(c,sum); c-data+; Status div(LongInt c,LongInt a,LongInt b)/*整除*/ LongInt d,e; short i = 0,EnoughSub; 第 - 17 - 页 共 40 页 short adata = a-data, bdata = b-data; if(b-data = 1 if (a-data data *= -1; if (b-data data *= -1; InitList(InitList( /*使用临时长整型数*/ CopyList(a,e);/* e = a */ EnoughSub = UnsignedSub(d,e,b); /* d = e - b */ while(EnoughSub = OK) i+; if (i = 20000)/*多次相减后再才保存*/ Addn(c,i); i = 0; ClearList(e);CopyList(d,e);ClearList(d); EnoughSub = UnsignedSub(d,e,b); Addn(c,i);/*将最后的尾数补上*/ a-data = adata;b-data = bdata; c-data *= (adata*bdata = 0)?1:-1); DestroyList(DestroyList( 第 - 18 - 页 共 40 页 return OK; void factorial(LongInt c,LongInt a) LongInt b,d,e,start; if (a-data=1|a-data=-1)return; InitList( InitList( InitList( CopyList(CStringtoLongInt(“1“),b); CopyList(CStringtoLongInt(“1“),d); start=a; a=a-prior; while(a!=start) while(a-data0) ClearList(c); mul(c,b,d); ClearList(e); 第 - 19 - 页 共 40 页 CopyList(b,e); ClearList(b); add(b,e,CStringtoLongInt(“1“); ClearList(d); CopyList(c,d); a-data-; a=a-prior; void power(LongInt c,LongInt a,int n) /*乘方运算，变乘方为累乘*/ int i; LongInt b; if (n=0)InsFirst(c,0);return; else if(n=1)CopyList(a,c);return; InitList( CopyList(a,b); for(i=0;idatanext; while(p!=a) temp.Format(_T(“%d“),p-data); 第 - 21 - 页 共 40 页 str+=temp; p=p-next; if(p!=a) str+=“,“; return str; LongInt CStringtoLongInt(CString a) int f=1; int c=0; LongInt l; ElemType e; InitList( if(a.Left(1)=“-“) f=-1; a=a.Right(a.GetLength()-1); for(int i=a.GetLength();i0;i=i-5) 第 - 22 - 页 共 40 页 c+; e=_ttoi(a.Left(4); a=a.Right(a.GetLength()-5); InsTail(l,e); l-data=c*f; return l; 4.LongInt.h #include “DuCiLink.h“ #include “stdafx.h“ typedef struct DuCiLinkNode LongIntNode,*LongInt;/采用双向循环链 表为实际的存储结构 void add(LongInt c,LongInt a,LongInt b);/长整型数 c = a + b void sub(LongInt c,LongInt a,LongInt b); /长整型数 c = a - b void mul(LongInt c,LongInt a,LongInt b);/长整型数 c = a * b Status div(LongInt c,LongInt a,LongInt b); /长整型数 c = a / b (整除) void factorial(LongInt c,LongInt a);/长整型数 c = a! (阶乘) void power(LongInt c,LongInt a,int n);/长整型数 c = a n (乘方) CString LongInttoCString(LongInt a);/将 LongInt 型数 a 转化成 CString 第 - 23 - 页 共 40 页 LongInt CStringtoLongInt(CString a);/将 CString 型数 a 转化成 LongInt 5, NewCountDlg.cpp / NewCountDlg.cpp : implementation file / #include “stdafx.h“ #include “NewCount.h“ #include “NewCountDlg.h“ #include “LongInt.h“ #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE = _FILE_; #endif / / CAboutDlg dialog used for App About class CAboutDlg : public CDialog public: 第 - 24 - 页 共 40 页 CAboutDlg(); / Dialog Data /AFX_DATA(CAboutDlg) enum IDD = IDD_ABOUTBOX ; /AFX_DATA / ClassWizard generated virtual function overrides /AFX_VIRTUAL(CAboutDlg) protected: virtual void DoDataExchange(CDataExchange* pDX); / DDX/DDV support /AFX_VIRTUAL / Implementation protected: /AFX_MSG(CAboutDlg) /AFX_MSG DECLARE_MESSAGE_MAP() ; CAboutDlg:CAboutDlg() : CDialog(CAboutDlg:IDD) 第 - 25 - 页 共 40 页 /AFX_DATA_INIT(CAboutDlg) /AFX_DATA_INIT void CAboutDlg:DoDataExchange(CDataExchange* pDX) CDialog:DoDataExchange(pDX); /AFX_DATA_MAP(CAboutDlg) /AFX_DATA_MAP BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) /AFX_MSG_MAP(CAboutDlg) / No message handlers /AFX_MSG_MAP END_MESSAGE_MAP() / / CNewCountDlg dialog CNewCountDlg:CNewCountDlg(CWnd* pParent /*=NULL*/) 第 - 26 - 页 共 40 页 : CDialog(CNewCountDlg:IDD, pParent) /AFX_DATA_INIT(CNewCountDlg) m_radio = 0; /AFX_DATA_INIT / Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m_hIcon = AfxGetApp()-LoadIcon(IDR_MAINFRAME); void CNewCountDlg:DoDataExchange(CDataExchange* pDX) CDialog:DoDataExchange(pDX); /AFX_DATA_MAP(CNewCountDlg) DDX_Radio(pDX, RADIO_ADD, m_radio); /AFX_DATA_MAP BEGIN_MESSAGE_MAP(CNewCountDlg, CDialog) /AFX_MSG_MAP(CNewCountDlg) ON_WM_SYSCOMMAND() ON_WM_PAINT() 第 - 27 - 页 共 40 页 ON_WM_QUERYDRAGICON() ON_BN_CLICKED(BTN_RESET, OnReset) ON_BN_CLICKED(BTN_OK, OnOk) /AFX_MSG_MAP END_MESSAGE_MAP() / / CNewCountDlg message handlers BOOL CNewCountDlg:OnInitDialog() CDialog:OnInitDialog(); / Add “About.“ menu item to system menu. / IDM_ABOUTBOX must be in the system command range. ASSERT(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 dialog SetIcon(m_hIcon, TRUE);/ Set big icon SetIcon(m_hIcon, FALSE);/ Set small icon / TODO: Add extra initialization here return TRUE; / return TRUE unless you set the focus to a control void CNewCountDlg:OnSysCommand(UINT nID, LPARAM lParam) 第 - 29 - 页 共 40 页 if (nID dlgAbout.DoModal(); else CDialog:OnSysCommand(nID, lParam); / 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 CNewCountDlg:OnPaint() if (IsIconic() CPaintDC dc(this); / device context for painting 第 - 30 - 页 共 40 页 SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); / Center icon in client rectangle int cxIcon = GetSystemMetrics(SM_CXICON); int cyIcon = GetSystemMetrics(SM_CYICON); CRect rect; GetClientRect( int x = (rect.Width() - cxIcon + 1) / 2; int y = (rect.Height() - cyIcon + 1) / 2; / Draw the icon dc.DrawIcon(x, y, m_hIcon); else CDialog:OnPaint(); / The system calls this to obtain the cursor to display while the user drags 第 - 31 - 页 共 40 页 / the minimized window. HCURSOR CNewCountDlg:OnQueryDragIcon() return (HCURSOR) m_hIcon; void CNewCountDlg:OnReset() /* m_editA=“; m_editB=“; m_editRESULT=“; UpdateData(TRUE);*/ SetDlgItemText(EDIT_A,“); SetDlgItemText(EDIT_B,“); SetDlgItemText(EDIT_RESULT,“); void CNewCountDlg:OnOk() UpdateData(TRUE); LongInt A,B,R; InitList( 第 -