清华大学-数据结构课后答案.docx

1-4.什么是抽象数据类型？试用C+的类声明定义“复数”的抽象数据类型。要求(1)在复数内部用浮点数定义它的实部和虚部。(2)实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋 给复数的实部，虚部置为0:第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚 部。(3)定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。(4)定义重载的流函数来输出一个复数。【解答】抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基 本的数据类型构成，并包括一组相关的服务。在头文件complex.h中定义的复数类#ifndef _complex_h_#define _complex_h_#include <iostream.h>class coinlex 不带参数的构造函数只置实部的构造函数分别置实部、虚部的构造函数取复数实部取复数虚部修改复数实部修改复数虚部public:complex () Re = Im = 0; complex ( double r) Re = hn = 0; complex ( double r, double i) Re = r; Im = /; double getReal () return Re; double gelhnag () return hn; void setReal ( double r) Re - r void setlmag ( double i) bn = z; complex& operator = ( complex& ob) Re - ob.Re; hn = ob.hn; 复数赋值重载函数：复数四则运算complex& operator + ( complex& ob );coniplex& operator - ( complex&. ob );complex& operator * ( contplex& ob );complex, operator / ( complex& oh );friend ostream& operator « ( ostream& os, complex& c ); 友元函数：重载vv private:double Re, bn;复数的实部与虚部)；#endif复数类complex的相关服务的实现放在C+源文件complex.cpp中#include <iostream.h>#include <math.h>#include "complex.h"complex& complex : operator + ( complex & ob) 重载函数：复数加法运算。complex * result = new complex (Re + ob.Re, bn + ob.lin ); return *result;complex& complex : operator - ( complex& ob) 重载函数：复数减法运算complex * result = new complex ( Re - ob.Re, Im - ob.bn ); return * result;co nip I ex & complex : operator * ( complex& oh ) 重载函数：复数乘法运算complex * result =new complex (Re * ob.Re - Im * ob.Im, Im * oh. Re Re * ob.lm );return *result;)complex& complex : operator / ( complex& ) 重载函数：复数除法运算double d = ob.Re * ob.Re + ob.lm * ob.lm;complex * result = new complex ( Re * ob.Re + Im * ob.lm ) / d,(Im * ob. Re - Re * ob.bn )/</);return * result)friend ostream& operator «( ostream& os, complex & ob) 友元函数：重载,将复数ob输出到输出流对象心中。return os « ob.Re « ( ob.lm >= 0.0 ) ? “+” ："-"<< fabs ( ob.lm ) « "i"11-7试编写一个函数计算"!*2"的值，结果存放于数组4arraySize的第个数组元素中，0 4 n < arraySize0若设计算机中允许的整数的最大值为maxlnt,则当n > arraySize或者对于某一个k (0 4% 4)，使得A!*2*>znox/W时,应按出错处理。可有如下三种不同的出错处理方 式：(1)用cerrvv及exit (1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置-个引用型的整型变量来区别是正常返回还是某种错误返回。 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include "iostream.h'1#define arraySize 100#define Maxlnt Ox7fffffffint calc (int T , int n ) int i, value = 1;if(w !=0)int edge = Maxlnt / n / 2;for (i = 1; / < /i; /+ ) value *= /*2;if ( value > edge ) return 0;value *= * 2;)Tn = value;cout « MAH « n « M=H « Tn « endl;return 1;void main () int AarraySize;int i;for (/ = 0; / < array Size; /+ )if ( lealc (A, /) cout « "failed at"«i« "vv endl;break;)1-9(1)在下面所给函数的适当地方插入计算count的语句：void d (ArrayElement x , int n ) int i = 1;do xi += 2; i +=2; while (i <= n );； <=1；while (i <= (n/2) x/ += x/+l; /+;)(2)将由(1)所得到的程序化简使得化筒后的程序与化简前的程序具有相同的count值。(3)程序执行结束时的co”"值是多少？(4)使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。【解答】(1)在适当的地方插入计算以"皿语句void d (ArrayElement x , int n ) int i = 1;count +;do xi += 2; count +;i += 2; count +;count +;针对 while 语句 while (i <= n );/=1；count +;/针对while语句while (i<=(n/2)count +;xi +=x/+l;count +;i +;count +;count +;针对最后一次while语句)(2)将由所得到的程序化简。化简后的程序与原来的程序有相同的cam，值: void d (ArrayElement x , int n ) int / = 1;docount += 3； i += 2; while (/ <= n );i=l；while (/ <= ( n / 2 ) count += 3; i -H-;)count += 3;(3)程序执行结束后的值为3n + 3o当 n 为偶数时.count = 3*(n/2) + 3*(n/2) + 3 = 3*n + 3当 n 为奇数时，count = 3 * ( n + 1 )/2) + 3*(n-l)/2) + 3 = 3*n + 3(4)使用执行频度的方法计算程序的执行步数，画出程序步数统计表:行号程序语句一次执行步数执行频度程序步数1void d (ArrayElement x , int )0102int / = 1;1113do0L(n+l)/2j04xi+=2;1L(n+l)/2jL(n+l)/2j5i+=2;1L(n+l)/2jL(n+l)/2j6 while ( / <= n );1L(n+l)/2jL(n+l)/2j7i=l；1118while (/ <= ( n / 2 ) ILn/2+lJLn/2+lJ9xi +=x/+l;1Ln/2jLn/210I+;1Ln/2jLn/2110Ln/2j012010(nO)3n + 32-1设“个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局; 然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到 所有的人全部出局为止。卜面要解决的Josephus问题是：对于任意给定的”,s和求出这 个人的出局序列。请以 = 9,s=l,机=5为例，人工模拟Josephus的求解过程以求得问题 的解。【解答】出局人的顺序为5, 1,7,4, 3, 6, 9, 2, 8。2-2试编写一个求解Josephus问题的函数。用整数序列1,2, 3,，"表示顺序围坐在圆桌 周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用 = 9,s=1,/m = 5, 以及"=9, s = 1, m = 0,或者 =9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健 壮性。最后分析所完成算法的时间复杂度。【解答】函数源程序清单如下：void Josephus int A , int n, s,m)int i、j, k, tmp;if( m = = 0 ) coutvv"/n = 0 是无效的参数！ "vvendl;return;)for (/ = 0; i < n; /+ )Ai = i+ 1;i = s- 1;for (k = n; k> 1; i) if(i=L)i = O； i = (i + m - 1 )%;if(i!=I ) tmp = Ai;/*初始化，执行次*/*报名起始位置*/*逐个出局，执行nT次*/*寻找出局位置*/*出局者交换到第&T位置*/for (7 = i;i< I; j+) A/ =A/+11;Ak- = tmp;)for (& = 0;攵 v / 2;"+ ) /*全部逆置，得到出局序列*/tmp = A 伙;Ak =An-jt+l = imp;)逆置829634715第8人出局,i 二 0 最终出局顺序517436928例：n = 9, 5 = 1, /n = 0报错信息 m=0是无效的参数!例：W = 9, 5 = 01, m = 10 12345678k = 9女二8k = 7k = 6k = 5k = 4k = 3k = 2逆置当阳=1123456789第1人出局,i = 0 第3人出局,，=1 第6人出局,i 二 3 第2人出局,i = 0 第9人出局,i = 4 第5人出局,i = 1 第7人出局,i=l 第4人出局,i = 0 第8人出局,i = 0 最终出局顺序1 =n(n-l)/2»O(n2)o234567891245678931245789631457892631457892631478592631487592631847592631136295748时，时间代价最大。达到(-1 ) + (-2) +2-3设有一个线性表(小约，呢2存放在一个一维数组4arm)0ze中的前个数组 元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前个原址内容置换为(部”, 呢-2, * *» e , e。) °【解答】templatecclass Type> void inverse ( Type A , int n ) Type imp;for (int i = 0; / <= (“T ) / 2; /+ ) tmp - 4|/； Ai = An-i- ; An-i- = tmp2-7设有一个二维数组4刈川，假设*OHO存放位置在644(10)，M2n2存放位置在676(10), 每个元素占一个空间，问433k0)存放在什么位置？脚注(|0)表示用10进制表示。【解答】设数组元素存放在起始地址为Loc (i, j )的存储单元中。Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676./. n = ( 676-2-644 )/2 = 15Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.2-9设有一个x”的对称矩阵4,如图(a)所示。为了节约存储，可以只存对角线及对角线以 上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩 阵。我们把它们按行存放于一个一维数组8中，如图(b)和图(c)所示。并称之为对称矩阵4 的压缩存储方式。试问：(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 为在只存上三角部分的情形下(图(b)应存于一维数组的什么下标位置？给出计算公式。(3)若在一维数组8中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素劭在只存下三角部分的情形下(图)应存于一维数组的什么下标位置？给出计算公式。 【解答】(1)数组 B 共有 n + ( nT ) + + 1= n * ( n+l ) / 2 个元素。ran aiz am)azi azz az»Idnl Gnz dnnj(a)对称矩阵an aiz - flw'iazz 八 azn(b)只存上三角黝ail 012 am azz can Onn严cazi azz、z潺余然勰滁3Omi制i麻射。刈(0只存下三角黝Oil azi Ozz Cmm Oni anM dnn(2)只存上三角部分时，若i4j,则数组元素AiH前面有iT行(1i-1,第0行第0 列不算)，第1行有n个元素，第2行有nT个元素，第iT行有n-i+2个元素。在第 i行中，从对角线算起，第j号元素排在第j-i+1个元素位置(从1开始)，因此，数组元素 在数组B中的存放位置为n + (nT) + (n-2) +(n-i+2) + j-i+1= (2n-i+2)*(i-1)/2+j-i+1= (2n-i)*(i-l)/2+j若i>j,数组元素在数组B中没有存放，可以找它的对称元素AUHi。在数组B的第(2n-j)*(j-l)/2 + i位置中找到。如果第0行第0列也计入，数组B从。号位置开始存放，则数组元素在数组B 中的存放位置可以改为当 i4j 时，=(2n-i+l)*i/2+j- i = ( 2n - i - 1 ) * i / 2 + j当 i>j 时，=(2n-j- l)*j/2 + i(3)只存下三角部分时，若i2j,则数组元素前面有iT行(1i-1,第0行第0 列不算)，第1行有1个元素，第2行有2个元素，第i-1行有iT个元素。在第i行 中，第j号元素排在第j个元素位置，因此，数组元素在数组B中的存放位置为1 +2 + (i-l) + j = (i-l)*i/2+j若i<j,数组元素在数组B中没有存放，可以找它的对称元素在数组B的第(j-l)*j / 2 + i位置中找到。如果第0行第0列也计入，数组B从。号位置开始存放，则数组元素在数组B 中的存放位置可以改为当 i2j 时，=i*(i+l)/2+j当 i<j 时，=j*0+l)/2 + i2-10设4和8均为下三角矩阵，每一个都有"行。因此在下三角区域中各有0(+1 )/2个元 素。另设有一个二维数组C,它有n行n+l歹试设计一个方案，将两个矩阵4和8中的 下三角区域元素存放于同一个C中。要求将4的下三角区域中的元素存放于C的下三角区 域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元 素旬和B的矩阵元素与在C中的存放位置下标的公式。【解答】c =a 00a 10a 20b ooa 11a 21b ioa 22b n-20216 一22b n - io、-11b n-12t " n-10an-a n-12*a n-ln-ln-ln-l )计算公式Rr.ir . Jc4i + 1, B/ j= <lC/j + l.当i>当i<，时 j时rfC« j,Aij = 1 Jl7J， Cji,当i>当i<j时 ，时2-14字符串的替换操作replace (String &s, String &/, String &p)是指：若f是s的子串，则用 串v替换串t在串s中的所有出现；若，不是s的子串，则串s不变。伊IJ如，若串s为 “aabbabcbaabaaacbab”,串/为"bab”,串v为"abdc”,则执行rep/ace操作后，串$中的结果 为“aababdccbaabaaacabdc"。试利用字符串的基本运算实现这个替换操作。【解答】String & Siring : Replace ( String & t, Siring &v) if(int/W = F/W(/)=-1)没有找到，当前字符串不改，返回 cout« "The (replace) operation failed." « endl; return *this; String temp( ch );用当前串建立一个空的临时字符串c/!0 = AO' curLen = 0;当前串作为结果串，初始为空intj,k = O, /;存放结果率的指针while (id != -1 ) for (j = O;j< id; j+) chk+ = temp.chj;摘取力中匹配位置id前面的元素到结果串chocurLen += id + v.curLen;修改结果串连接后的长度if ( curLen <= maxLen )1= v.curLen;确定替换串 v 传送字符数 /else / = curLen -maxLen curLen = maxLen for (J = O;j </; j+ ) chk+ = v.chj;连接替换串V到结果串ch后面if (curLen = maxLen ) break;字符串超出范围for (j = id + t.curLen; j < ternp.curLen; j+ )temp.chj-id -t.curLen = temp.chj;删改原来的字符串temp.curLen -= (id + t.curLen );id = temp.Find (t);)return *this;2-15编写一个算法加g“ecy,统计在一个输入字符串中各个不同字符出现的频度。用适当 的测试数据来验证这个算法。【解答】统计算法include <iostream.h>include "string.h"void frequency( Strin& s、char& A |, int& C| 1, int &k ) s是输入字符串，数组用中记录字符串中有多少种不同的字符，Q中记录每 一种字符的出现次数。这两个数组都应在调用程序中定义。攵返网不同字符数。int i,j, len = s.lenglh();if ( Men ) ( cout« "The string is empty." « endl; k = 0; return;else A0=i0; C0= 1;后=1;/*语句 是串的重载操作*/for(i= 1;/< len; i+ ) Ci = 0;/* 初始化*/for(i= l;/< len; i+ ) /*检测串中所有字符*/j = 0；while (j<k && A/ !=si)J+;/* 检查 si是否已在 中*/if(j=k)= s|/; CR+; k+ /*si从未检测过*/else C/+;/*si已经检测过*/测试数据 s = "cast cast sat at a tasa0"测试结果一S一a一§一?一C 27455【另一解答】include <iostream.h>include "string.h"const int charnumber = 128;/*ASCII 码字符集的大小*/void frequency( Strin& s, int& C ) (5是输入字符串，数组C中记录每一种字符的出现次数。for (int / = 0; i < charnumber; i+ ) Ci = 0;/*初始化*/for (/ = 0; / < s.length (); /+ )/*检测串中所有字符*/C atoi(5/) +；/*出现次数累加*/for (i = 0; i < chamumber; /+ )/*输出出现字符的出现次数*/if( Ci > 0 ) cout« H(" «i« M): tH « Ci « "tH;3-2试编写一个算法，在带表头结点的单链表中寻找第i个结点。若找到，则函数返回第i 个结点的地址；若找不到，则函数返回0。【解答】template <class Type>ListNode <Type> * List <Type> : Get AN ode (int i) 取得单链表中第i个结点地址,i从0开始计数,i v 0时返回指针0, i = 0时返回表头结点地址。if(/< 1 ) return NULL;ListNode <Type> * p = first; int 左=0;while (p != NULL && k < i) p = p-link; k+； return /?;3-3设布和协分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存 储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】#include <iostream.h>template <class Typo class List;template <class Typo class ListNode friend class Lz.vr<Type>public:ListNode ();构造函数ListNode ( const Type& item );构造函数private:Type data;ListNode<Type> *link;I；template <class Typo class List public:List ( const Type finishied);建立链表void Browse ();打印链表void Merge ( L/57<Type> &hb );连接链表private:LislNode<Type> *first9 *last;)；各成员函数的实现template <class l pe>ListNode<Type>:ListNode (): link ( NULL ) 构造函数，仅初始化指针成员。template <class Trpe>ListNode<Type> : ListNode ( const Type & item ): data (item ), link ( NULL ) 构造函数，初始化数据与指针成员。template <class l pe>List<Type> : List ( const Type finis hied ) 创建一个带表头结点的单链表，finished是停止建表输入的标志，是所有输入值中不可能出现的数值。first = last = new ListNode<Type>();创建表头结点Type value; ListNode<Type> *p, *q, *s;cin » value;while ( value !=finished) 循环建立各个结点s = new ListNode<Type>( value );q = first; p = first-link;while (p != NULL && p-data <= value )夕=P； p = p7ik;寻找新结点插入位置q-link = s； sfink = p；在 q, p 间插入新结点if(p= NULL) last = s;cin » value;)template <class Typovoid Lis/<lype> : Browse () 浏览并输出链表的内容cout«"nThe List is : nM;ListNode<Type> *p =firsLlink;while (p != NULL ) cout« p-data;if (p != last) cout «else cout« endl;p pfink;template <class Typo void List <Type> : Merge ( List<Type>& hb) 将当前链表this与链表汕按逆序合并，结果放在当前链表this中。LislNode<Type> *pa,*pb,*q,*p;检测指针跳过表头结点结果链表初始化当两链表都未结束时从pa链中摘F从P8链中摘F链入结果链的链头处理未完链的剩余部分pa = first f ink; pb = hb.first-link;first-*-link = NULL;while ( pa != NULL && pb != NULL )if (pa-*'data <= ph-*-data )q-pa; pa = palink; else 4 = pb; pb = pbfink; qfink =fir$Llink; first-link =p = (p。！= NULL )? pa : pb;while ( p != NULL ) q = p; p = p-link;qflink = firsLlink; first-*-link = <7;)3-6设有一个表头指针为人的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有 结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针人指向原链表的最后一个 结点。P.h Pi Ii-h i "I i"'i i J i i si【解答1】template<class Typo void Lisi<Type> : Inverse () if (first = NULL ) return;ListNode<Type> *p = first-*-link;, *pr = NULL;while (p != NULL )first-link = pr;逆转 first 指针pr = first; first = p; p = p-link;指针前移)【解答2】template<class Typo void List<Type> : Inverse () Lis【Node<Type> *p, "head = new ListNode<Type> ();while (first != NULL ) p = first; first = first-link;摘下 first 链头结点p-link = head flink; head f link = p; 插入 head 链前端 1 first = headlink; delete head;重置3-7从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连 接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p 所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。(1)编写一个算法，从任一给定的位置p)开始，将指针0右移出个结点。如果p移 出链表，则将p置为0,并让“停留在链表最右边的结点上。(2)编写一个算法，从任一给定的位置(pr, p)开始，将指针。左移/个结点。如果p移 出链表，则将p置为0,并让pr停留在链表最左边的结点上。pr Pni rfl ni rn-ni-rToi【解答】(i)指针右移上个结点template<class Type> void List<Type> :siftToRight ( ListNode<Type> *& p, Lis iNode vType> *& pr, int A ) if(p= NULL && pr !=first)已经在链的最右端cout vv "已经在链的最右端，不能再右移。"<vendl;return;int /; ListNode<Type> *q;if (p = NULL )/ = 1; pr = NULL; p - first; else i = 0;/从链头开始重置p到链头也算次右移while (p != NULLq = pfink; p flink = pr;pr = p； P = q； /+；右移k个结点链指针pfIink逆转指向pr指针pr,p右移cout « "右移了" << i« "个结点."« endl;)(2)指针p左移k个结点template<class Type> void List<Vype> :siftToLeft ( ListNode<Ty pe> *& p, ListNode<Type> *& int k ) if ( p = NULL && pr =first) 已经在链的最左端cout vv”已经在链的最左端，不能再左移。"vvendl;return;）int / = 0; ListNode<Jype> *q; while ( pr != NULL && i<k) q - pr-link; pLlink = p; P = pr； pr = q; /+；)左移k个结点链指针plink逆转指向p指针尸八尸左移cout« "左移 T" «i« "个结点。" endl;if(ivQpr = p; p = NULL;)指针p移出表外，重置p, pr3-9试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以 及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员 函数。要求每个字符串结点中只存放一个字符。【解答】用单链表表示的字符串类string 1的头文件stringl.h#include <iostream.h>const int maxLen - 300;字符串最大长度为300 （理论上可以无限长）class string public:string!();string 1 ( char * obstr );加gl ();int Length () const return curLen; string 1 & operator = ( string 1 & ob );int operator = ( string 1 & ob );char& operator (int /);构造空字符串从字符数组建立字符中析构函数求字符串长度串赋值