📄 archivecontent.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0050)http://bbs.kaoyan.com/archivecontent.asp?id=190377 -->
<HTML><HEAD><TITLE>清华数据结构题解答案!!c++!! - 考研论坛</TITLE><LINK
href="archivecontent.files/DEFAULT.css" type=text/css rel=stylesheet>
<META http-equiv=Expires content=0>
<META http-equiv=Cache-Control content=no-cache>
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 5.50.4134.100" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#000066 link=#000066 bgColor=#ffffff>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD>
<DIV align=right><A target=_blank
href="http://www.kaoyan.com/">kaoyan.com首页</A> | <A
href="http://bbs.kaoyan.com/default.asp">论坛总览</A> | <A
href="http://bbs.kaoyan.com/archive.htm">精华区</A> | <A
href="http://bbs.kaoyan.com/search.asp">论坛搜索</A> | <A
href="javascript:location.reload()">刷新本页</A> | <A
href="http://bbs.kaoyan.com/signup.asp">注册</A> | <A target=_blank
href="http://www.kaoyan.com/guestbook">批评建议</A> | <A target=_blank
href="http://shop.kaoyan.com/">书店</A> | <A
href="mailto:news@kaoyan.com">投稿</A> | <A target=_blank
href="http://chat.kaoyan.com/">聊天</A></DIV></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD bgColor=#3399cc height=1></TD></TR></TBODY></TABLE></CENTER>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD>
<CENTER><IFRAME marginWidth=0 marginHeight=0
src="archivecontent.files/bbsadtop.htm" frameBorder=0 width=468
scrolling=no height=60
bordercolor="#000000"></IFRAME></CENTER><BR><BR><BR><IMG
src="archivecontent.files/ubbfriendminiicon.gif" border=0> <B>论坛信使：</B><A
href="http://bbs.kaoyan.com/ubbmisc.asp?action=sendthread&Subject=%C7%E5%BB%AA%CA%FD%BE%DD%BD%E1%B9%B9%CC%E2%BD%E2%B4%F0%B0%B8%21%21c%2B%2B%21%21">发送本页给您的朋友！</A></TD>
<TD vAlign=top>
<P align=left><IMG src="archivecontent.files/open.gif"
align=absMiddle> <A
href="http://bbs.kaoyan.com/default.asp"><ACRONYM title=返回讨论区总页.><SPAN
class=smallFont>考研论坛</SPAN></ACRONYM></A> <BR><IMG
src="archivecontent.files/tline.gif" align=absMiddle border=0><IMG
src="archivecontent.files/open.gif" align=absMiddle border=0><SPAN
class=smallFont> <A
href="http://bbs.kaoyan.com/archivelist.asp?archiveid=8">计算机</A></SPAN><BR><IMG
src="archivecontent.files/tline3.gif" align=absMiddle border=0><IMG
src="archivecontent.files/open.gif" align=absMiddle border=0><SPAN
class=smallFont> 清华数据结构题解答案!!c++!!</SPAN></P>
<P><SPAN class=smallFont><IFRAME marginWidth=0 marginHeight=0
src="archivecontent.files/newarchive.htm" frameBorder=0 width=150
scrolling=no height=19
BORDERCOLOR="#000000"></IFRAME></SPAN></P></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD colSpan=2>注意：这是一个归档主题。它是只读的。 <BR>此主题先前所在的论坛：计算机</TD></TR>
<TR>
<TD colSpan=2></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=1 cellPadding=4 width="100%" border=0>
<TBODY>
<TR bgColor=#3399cc>
<TD vAlign=center width="18%"><FONT color=#ffffff><B>发表人</B></FONT></TD>
<TD vAlign=center><FONT
color=#ffffff><B>主题: 清华数据结构题解答案!!c++!!</B></FONT></TD></TR>
<TR bgColor=#dcdcdc>
<TD vAlign=top noWrap width="18%">neasemy<BR><IMG
src="archivecontent.files/Image15.gif"
vspace=5><BR><B>一般站友</B><BR>积分：231<BR>发贴：37<BR>来自：<BR>资格：2001-02-23<BR></TD>
<TD vAlign=top><IMG src="archivecontent.files/icon1.gif" align=absMiddle
border=0> 发表于 2001-05-13 <FONT
color=#000000>08:32:43</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=neasemy"><IMG
alt=按此观看neasemy的个人资料 src="archivecontent.files/profile.gif"
align=absMiddle border=0></A> <A href="mailto:neasemy@sohu.com"><IMG
alt=按此发邮件给neasemy src="archivecontent.files/email.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/pm.asp?action=newpm&recipient=neasemy&subject=%C7%E5%BB%AA%CA%FD%BE%DD%BD%E1%B9%B9%CC%E2%BD%E2%B4%F0%B0%B8%21%21c%2B%2B%21%21"><IMG
alt=发送悄悄话给neasemy src="archivecontent.files/pm.gif" align=absMiddle
border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=neasemy"><IMG
height=16 alt=搜索neasemy的所有帖子 src="archivecontent.files/find.gif" width=16
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=8&Topic=190377&TopicSubject=%C7%E5%BB%AA%CA%FD%BE%DD%BD%E1%B9%B9%CC%E2%BD%E2%B4%F0%B0%B8%21%21c%2B%2B%21%21&action=editarchive"><IMG
alt=编辑/删除帖子 src="archivecontent.files/edit.gif" align=absMiddle border=0
?></A>
<HR>
1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求<BR>(1) 在复数内部用浮点数定义它的实部和虚部。<BR>(2)
实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。<BR>(3)
定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。<BR>(4)
定义重载的流函数来输出一个复数。<BR>【解答】<BR>抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务。
<P>//在头文件complex.h中定义的复数类<BR>#ifndef _complex_h_<BR>#define
_complex_h_<BR>#include <iostream.h>
<P>class comlex {<BR>public:<BR> complex ( ){ Re = Im = 0; }
//不带参数的构造函数<BR> complex ( double r ) { Re = r; Im =
0; } //只置实部的构造函数<BR> complex ( double r, double i ) { Re =
r; Im = i; } //分别置实部、虚部的构造函数<BR> double getReal ( )
{ return Re; } //取复数实部<BR> double getImag ( ) { return Im; }
//取复数虚部<BR> void setReal ( double r ) { Re = r; }
//修改复数实部<BR> void setImag ( double i ) { Im = i; }
//修改复数虚部<BR> complex& operator = ( complex& ob) { Re =
ob.Re; Im = ob.Im; } //复数赋值<BR> complex&
operator + ( complex& ob ); //重载函数：复数四则运算<BR> complex&
operator - ( complex& ob );<BR> complex& operator * (
complex& ob );<BR> complex& operator / ( complex&
ob );<BR> friend ostream& operator << ( ostream&
os, complex& c ); //友元函数：重载<<<BR>private:<BR> double
Re, Im; //复数的实部与虚部<BR>};<BR>#endif
<P> //复数类complex的相关服务的实现放在C++源文件complex.cpp中<BR>#include
<iostream.h><BR>#include <math.h><BR>#include
“complex.h”<BR>complex& complex :: operator + ( complex & ob )
{<BR>//重载函数：复数加法运算。<BR>complex * result = new complex ( Re +
ob.Re, Im + ob.Im );<BR>return *result;<BR>
}<BR>complex& complex :: operator - ( complex& ob )
{<BR>//重载函数：复数减法运算<BR>complex * result = new complex ( Re -
ob.Re, Im - ob.Im );<BR>return * result;<BR>}<BR>complex&
complex :: operator * ( complex& ob ) {<BR>//重载函数：复数乘法运算<BR>complex *
result = <BR>new complex ( Re * ob.Re - Im * ob.Im, Im * ob.Re
+ Re * ob.Im );<BR>return *result;<BR>}<BR>complex& complex ::
operator / ( complex& ) {<BR>//重载函数：复数除法运算<BR>double d = ob.Re * ob.Re
+ ob.Im * ob.Im;<BR>complex * result = new complex ( ( Re * ob.Re + Im *
ob.Im ) / d,<BR>( Im * ob. Re - Re * ob.Im ) / d );<BR>return *
result;<BR>}<BR>friend ostream& operator << ( ostream& os,
complex & ob )
{<BR>//友元函数：重载<<，将复数ob输出到输出流对象os中。<BR> return os
<< ob.Re << ( ob.Im >= 0.0 ) ? “+” : “-” << fabs (
ob.Im ) << “i”;<BR>}
<P>1-7 试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0 &pound; n
&pound; arraySize。若设计算机中允许的整数的最大值为maxInt，则当n > arraySize或者对于某一个k (0
&pound; k &pound; n)，使得k!*2k >
maxInt时，应按出错处理。可有如下三种不同的出错处理方式：<BR>(1) 用cerr<<及exit
(1)语句来终止执行并报告错误；<BR>(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；<BR>(3)
在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。<BR>试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。<BR>【解答】<BR>#include
"iostream.h"<BR>#define arraySize 100<BR>#define MaxInt 0x7fffffff
<P>int calc ( int T[ ], int n ) {<BR>int i, value = 1;<BR>if ( n != 0 )
{<BR>int edge = MaxInt / n / 2;<BR>for ( i = 1; i < n; i++ ) {<BR>value
*= i*2;<BR>if ( value > edge ) return 0;<BR>}<BR>value *= n *
2;<BR>}<BR>T[n] = value;<BR>cout << "A[" << n << "]="
<< T[n] << endl;<BR>return 1;<BR>}
<P>void main ( ) {<BR>int A[arraySize];<BR>int i;<BR>for ( i = 0; i <
arraySize; i++ )<BR>if ( !calc ( A, i ) ) {<BR>cout << "failed at "
<< i << " ." << endl;<BR>break;<BR>}<BR>}
<P>1-9 (1) 在下面所给函数的适当地方插入计算count的语句：<BR>void d (ArrayElement x[ ], int n )
{<BR> int i = 1;<BR> do {<BR> x[i] +=
2; i +=2;<BR> } while (i <= n );<BR>;
i = 1;<BR> while ( i <= (n/2) )
{<BR> x[i] += x[i+1]; i++;<BR>
}<BR>}<BR>(2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。<BR>(3)
程序执行结束时的count值是多少？<BR>(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。 <BR>【解答】<BR>(1)
在适当的地方插入计算count语句<BR>void d ( ArrayElement x [ ], int n )
{<BR>int i = 1;<BR> count ++;<BR> do {<BR>x[i] +=
2; count ++;<BR>i += 2; count
++; <BR>count ++; //针对while语句<BR> } while ( i <=
n );<BR> i = 1;<BR> count ++;<BR>
while ( i <= ( n / 2 ) ) {<BR> count ++;
//针对while语句<BR>x[i] += x[i+1];<BR>count ++;<BR>i ++;<BR>count
++;<BR> }<BR> count ++;
//针对最后一次while语句<BR>}<BR>(2) 将由(1)所得到的程序化简。化简后的程序与原来的程序有相同的count值：<BR>void
d ( ArrayElement x [ ], int n ) {<BR> int i =
1;<BR>do {<BR>count += 3; i += 2;<BR> } while ( i
<= n );<BR> i = 1;<BR>while ( i <= ( n / 2 ) )
{<BR> count += 3; i ++; <BR>
}<BR> count += 3; <BR>}<BR>(3) 程序执行结束后的count值为 3n +
3。<BR>当n为偶数时，count = 3 * ( n / 2 ) + 3 * ( n / 2 ) + 3 = 3 * n +
3<BR>当n为奇数时，count = 3 * ( ( n + 1 ) / 2 ) + 3 * ( ( n - 1 ) / 2 ) + 3 = 3
* n + 3<BR>(4) 使用执行频度的方法计算程序的执行步数，画出程序步数统计表：<BR>行 号
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -