C++数据结构习题含答案.docx

《C++数据结构习题含答案.docx》由会员分享，可在线阅读，更多相关《C++数据结构习题含答案.docx（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1-4.什么是抽象数据类型?试用C+的类声明定义“复数”的抽象数据类型。要求(1)在复数内部用浮点数定义它的实部和虚部。(2)实现3个构造函数:缺省的构造函数没有参数;第二个构造函数将双精度浮点数赋 给复数的实部,虚部置为:第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚 部。(3)定义获取和修改复数的实部和虚部,以及十、*等运算的成员函数。(4)定义重载的流函数来输出个复数。【解答】抽象数据类型通常是指由用户定义,用以表示应用问题的数据模型。抽象数据类型由基 本的数据类型构成,并包括一组相关的服务。在头文件complex.h中定义的复数类#ifndef _complex_h_#defi

2、ne _complex_h_#include class comlex 不带参数的构造函数只置实部的构造函数分别置实部、虚部的构造函数取复数实部取复数虚部修改复数实部修改复数虚部bn = ob.hn; 复数赋值重载函数:复数四则运算public:complex () Re = Im = 0; complex ( double r)Re = r; hn = 0;complex ( double r, double i) Re = r; bn = z; double getReal ( ) return Re; double getbnag () return bn; void setReal (

3、 double r ) Re = r; void setlmag ( double i) bn = i; complex& operator = ( complex& oh) Re = ob.Re; complex& operator + ( complex& ob );coniplex& operator - ( complex& ob );complex& operator * ( complex& ob );complex& operator / ( complex& ob );friend ostream& operator ( ostream& os, complex& c );友元

4、函数:重载vvprivate:复数的实部与虚部double Re, bn;)；#endif复数类complex的相关服务的实现放在C+源文件complcx.cpp中#include #include #include complex.hMcomplex& complex : operator + ( complex & ob) 重载函数:复数加法运算。complex * result = new complex (Re + ob.Re, bn + ob.bn ); return *result;complexSc complex : operator - ( complex& ob ) 重载函

5、数:复数减法运算complex * result = new complex ( Re - ob.Re, Im - ob.Im );return * result;complex& complex : operator * ( complex& ob ) 重载函数:复数乘法运算complex result =new complex (Re * ob.Re - Im * ob.Im, Im * ob.Re + Re * ob.Im );return *result;)complex& complex : operator / ( complex& ) 重载函数：复数除法运算double d =

6、ob.Re * ob.Re + ob.Im * ob.Im;complex * result = new complex (Re * ob.Re + Im * ob.Im ) / J,(Im * ob. Re - Re * ob.Im )/= 0.0 ) ?“+”：- fabs ( ob.Im ) i;1-7试编写个函数计算!*2的值,结果存放于数组a/roySize的第个数组元素中,0 4 n array Size 若设计算机中允许的整数的最大值为maxlnt,则当arraySize或者对于某 个k (04k 4),使得k!*21ax/，时,应按出错处理。可有如下三种不同的出错处理方 式:(

7、1)用cerrvv及exit (1)语句来终止执行并报告错误;(2)用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回;(3)在函数的参数表设置个引用型的整型变量来区别是正常返回还是某种错误返回。 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include ioslream.h#define arraySize 100#define Maxlnt Ox7fffffffint calc (int T , int n ) int /, value = 1;if(w !=0)int edge = Maxlnt I n 12;for (i = 1; / edge

8、 ) return 0;)value *= n * 2;)Tn = value;cout MAH n Tn endl;return 1;void main () int AarraySize;int i;for (/ = 0; / arraySize; /+ )if ( Icalc (4, i) cout failed at i n .H endl;break;)1-9(1)在下面所给函数的适当地方插入计算count的语句:void d (Array Element x |,int n ) int i = 1;dox/ += 2; i +=2; while (i = n );；i= 1；whi

9、le (/= (n/2) xi +=x/+l; /+;)(2)将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的co“”值。(3)程序执行结束时的值是多少?(4)使用执行频度的方法计算这个程序的程序步数,画出程序步数统计表。【解答】(1)在适当的地方插入计算count语句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 (i=(n/2)count -H-;

10、针对 while 语句xi +=x/+l;count +;i+；count +;)count +;针对最后一次while语句(2)将由(1)所得到的程序化简。化简后的程序与原来的程序有相同的co“”值:void d ( Array Element x , int )int / = 1;docount += 3； i += 2; while (i = n );=1；while (/ = (n / 2 ) count += 3; i +;)count += 3;(3)程序执行结束后的值为3n+ 3。当 n 为偶数时,count = 3*(n/2) + 3*(n/2) + 3 = 3*n + 3当

11、n 为奇数时,count = 3*(n+l)/2) + 3*(n-l)/2) + 3 = 3*n + 3(4)使用执行频度的方法计算程序的执行步数，画出程序步数统计表:行号程序语句一次执行步数执行频度程序步数1void d (Array Element 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 (Z=(n/2)1Ln/2+lJLn/2+lJ9xi +

12、=x/+l；1Ln/2jLn/210+;1Ln/2jLn/211)0Ln/2j012010(n*0)3n + 32-1设个人围坐在个圆桌周围，现在从第s个人开始报数，数到第机个人,让他出局; 然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到 所有的人全部出局为止。下面要解决的Josephus问题是:对于任意给定的s和m,求出这 个人的出局序列。请以 =9,s=l,机=5为例，人工模拟Josephus的求解过程以求得问题 的解。【解答】出局人的顺序为5, 1,7,4,3, 6, 9, 2, 8。2-2试编写个求解Josephus问题的函数。用整数序列1,2, 3,n表示顺

13、序围坐在圆桌 周围的人,并采用数组表示作为求解过程中使用的数据结构。然后使用 = 9,s= 1,5=5, 以及=9, s = I, m = 0,或者=9, s = 1,机=10作为输入数据,检查你的程序的正确性和健 壮性。最后分析所完成算法的时间复杂度。【解答】函数源程序清单如下:void Josephus( int A , int ) int ,k, imp;if(m=0)(:01117 = 0是无效的参数!”!11;return;)for (/ = 0; / 1; i) if(i=k)i = O;i = (i + m- )%k;if(i !=A-1 )tmp = Ai;/初始化,执行“次/

14、报名起始位置/逐个出局,执行T次/*寻找出局位置/出局者交换到第hl位置/for (j = i;j k-l;j+) Aj =A/+1；A 伙-=tmp;)for(k = 0;kn/2; k+ ) /全部逆置,得到出局序列/tmp = Ak;Ak = An-k+; An-k+1 = tmp;)伊:n = 9, 5 = 1, /n = 5012345678 k = 9k = 8k = lk = 6 k = 5k = 4 k = 3k = 2逆置例:n = 9,5 = l,/n = 0报错信息 团=0是无效的参数!例:? = 9,5 = 1,m = 10012345678k = 9234 567 1

15、 819 第 1 人出局,i = 0Jt = 8234567891第3人出局,i=lk = l245678931第6人出局,i = 3k = 6245789631第2人出局,i = 0k = 5457892631第9人出局,i = 4k = 4457892631第5人出局,i= 1k = 3478592631第7人出局,i= 1k = 2487592631第4人出局,i =。847592631第8人出局,i 二 0逆置36295748最终出局顺序当! 二 1时,时间代价最大。达至(T ) + ( “-2 ) + 4-1 = n(n- 1 )/2 0(。2-3设有一个线性表(细约,e.2,“)存

16、放在个维数组Size中的前个数组 元素位置。请编写个函数将这个线性表原地逆置,即将数组的前个原址内容置换为(如, 呢2,白,4)。【解答】templateclass Typo void inverse ( Type A , int n ) Type tmp;for (int i = 0; i j,数组元素在数组B中没有存放，可以找它的对称元素AUHi。在数组B的第(2n-j)*(jT)/2 + i位置中找到。如果第。行第。列也计入,数组B从。号位置开始存放,则数组元素在数组B 中的存放位置可以改为当 i4j 时，=(2n-i+l)*i/2+j- i = ( 2n - i - 1 ) * i /

17、2 + j当 ij 时，=(2n-j- l)*j/2 + i(3)只存下三角部分时，若i2j,则数组元素前面有iT行(1i-1,第。行第。 列不算)，第1行有1个元素，第2行有2个元素，第iT行有i-1个元素。在第1行 中，第j号元素排在第j个元素位置，因此，数组元素在数组B中的存放位置为1 +2 + (i-l) + j = (i-l)*i/2+j若ij,数组元素在数组B中没有存放，可以找它的对称元素AjHi。在数组B的第(j-l)*j/2 + i位置中找到。如果第。行第。列也计入，数组B从。号位置开始存放,则数组元素在数组B 中的存放位置可以改为当 i2j 时，=i*(i+l)/2+j当 i

18、j 时,=j*(j+l)/2 + i2-10设4和8均为下三角矩阵，每一个都有行。因此在下三角区域中各有(+1)/2个元 素。另设有一个二维数组C,它有行+1歹。试设计个方案,将两个矩阵A和B中的 下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区 域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元 素旬和B的矩阵元素与在C中的存放位置下标的公式。【解答】iu11b 1UI I%-10an-an-n-)10n-11 a b b.u 10.b n 一 203-io a 10a ii即 ,bn-2-11C =。!o。2ia 22b n-22b

19、 n-2k n -10iia n-12,a n-In-Ib n计算公式Cii + 1,当，时用1=当i，时Ai i = 当i /时2-14字符串的替换操作刎ace (String &s, String &/, String &v)是指:若是s的子串,则用 串V替换串t在串5中的所有出现;若，不是S的子串,则串S不变。例如,若串S为 “aabbabcbaabaaacbab”,串t为bab”,串v为abdc”,则执行replace操作后,串s中的结果 为“aababdccbaabaaacabdcMo试利用字符串的基本运算实现这个替换操作。【解答】String & String : Replace

20、( String & i, String &v) if(int/W = F/W(r)=-l )没有找到,当前字符串不改,返回 cout The (replace) operation failed/ endl; return *this; String temp( ch );用当前串建立一个空的临时字符串ch0 = AO; curLen = 0;当前串作为结果串,初始为空int j, A = 0, /;存放结果串的指针while (ZJ!=-I )for (j = O;jid; j+) c人伙+ = tenip.chj;摘取temp.ch中匹配位置i前面的元素到结果串chocurLen +=

21、id + v.curLen;修改结果串连接后的长度if ( curLen = niaxLen ) I = v.curLen; 确定替换串 v 传送字符数 /else / = curLen -tnaxLen; curLen = maxLen;for (j = 0;y /;+ ) chk+ = v.chj;连接替换串v到结果串ch后面if ( curLen = = maxLen ) break;字符串超出范围for (j = id +1. curLen; j temp.curLen; j+ )temp.chj- id -t.curLen = temp.chj;删改原来的字符串temp.curLen

22、 -= (/J + t.curLen );id = temp.Find (t);)return *this;2-15编写个算法.“e,统计在个输入字符串中各个不同字符出现的频度。用适当 的测试数据来验证这个算法。【解答】统计算法include include Mstring.hMvoid frequency( String & s, char& A , int& C , int &k ) s是输入字符串,数组中记录字符串中有多少种不同的字符,Q中记录每 种字符的出现次数。这两个数组都应在调用程序中定义。A返回不同字符数。int /, J, len = s.length();if ( lien

23、) cout The string is empty. H endl; & = 0； return; else 40 = 40; C0 = 1; k= I;/语句是串的重载操作/for(i = 1;/ len; i+ ) C = 0;/初始化/for(= l;i len; i+ )/检测串中所有字符/7 = 0；while jk& A/ != s )j+;/检査是否已在ZU 中/if (j = A ) 4因=s0;CJt+; k+/*s/从未检测过/else C/l+;/*s已经检测过/测试数据 s = cast cast sat at a tasa0测试结果 一一5一?一C 27455【另解

24、答】include include string.hconst int charnumber = 128;/*ASCII 码字符集的大小/void frequency( String & s, int& C ) s是输入字符串,数组C中记录每种字符的出现次数。for (int / = 0; / charnumber /+ ) Ci = 0;/初始化/for (/ = 0; / s.length ; /+ )/检测串中所有字符/C atoi (si) +：/出现次数累加/for (/ = 0; i 0 ) cout H( H /H): t Ci tH;3-2试编写个算法,在带表头结点的单链表中寻

25、找第i个结点。若找到,则函数返回第i 个结点的地址;若找不到,则函数返回0。【解答】template ListNode vType* List : GetANode (int r) 取得单链表中第i个结点地址,Z从0开始计数,i v 0时返回指针, i = 0时返回表头结点地址。if (/ 1 ) return NULL;ListNode * p = first; int k = 0;while ( p != NULL & ki) p = p-link; return p;3-3设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计个算法, 将这两个有序链表合并成一个非递增有序的

26、单链表。要求结果链表仍使用原来两个链表的存 储空间,不另外占用其它的存储空间。表中允许有重复的数据。【解答】#include template class List;template class Typo class ListNode friend class List;public:ListNode ();构造函数ListNode ( const Type& item )5构造函数private:Type data;ListNode *link;；template class Typo class List public:List ( const Type finis hied );建立链表

27、void Browse ();打印链表void Merge ( List &hb );连接链表private:ListNode /irsl, *last;)；各成员函数的实现template class TypoListNode: :ListNode (): link ( NULL ) 构造函数,仅初始化指针成员。template class TypoListNode : ListNode ( const Type & item ): data (item ), link ( NULL ) /构造函数,初始化数据与指针成员。template class TypoList : List ( co

28、nst Type finishied) 创建一个带表头结点的单链表,finished是停止建表输入的标志,是所有输入值中不可能出现的数值。first = last = new ListNode();创建表头结点Type value; ListNode *p, *q, *s;cin value;while ( value !=finished) 循环建立各个结点s = new ListNode( value );q = first; p = first-link;while (p != NULL & p-data = value )( q = p； p = p-7/献:；)寻找新结点插入位置q

29、fink = s; s-link = p;在 g, 间插入新结点if (p = NULL ) last = s;cin value;)template class Typovoid sf : Browse () 浏览并输出链表的内容coutnThe List is : n;ListNode *p = first-link;while (p != NULL ) cout p-data;if(p != last) cout v.f ； else cout endl;p = p-link;template class Typo void List : Merge (s/vTypo& hb) 将当前链

30、表this与链表hb按逆序合并,结果放在当前链表this中。检测指针跳过表头结点结果链表初始化当两链表都未结束时/从。链中摘下从独链中摘下链入结果链的链头/处理未完链的剩余部分ListNode *pa, *pb, *q, *p;pa = first-link; pb = hb.fir stlink;first f link = NULL;while ( pa != NULL & pb != NULL )if (padata = pb-data )q = pa; pa = pa-link; else q = pb; pb = pb-link; qf link = firstlink; first

31、link = q;p = (pa != NULL )1 pa * ph;while (p != NULL ) q = p； p = plink;qlink = first-link; firstlink = q;3-6设有一个表头指针为的单链表。试设计个算法,通过遍历趟链表,将链表中所有 结点的链接方向逆转,如下图所示。要求逆转结果链表的表头指针指向原链表的最后一个 结点。pr=O Pprh Pim-ia-LQ-nu d db da【解答template void List : Inverse () if (first = NULL ) return;ListNode *p = first-l

32、ink;, *pr = NULL;while (p != NULL )firsts link = pr;逆转 first 指针pr = first; first = p; p=p-link;指针前移) )【解答2】templateclass Typo void List : Inverse () ListNode *p, *head = newr ListNode ();while (/im != NULL ) p = first; first = first-link;摘下 first 链头结点p-link = head fink; head-link = ; 插入 head 链前端 ) f

33、irst = headlink; delete head;H重置 firsi)3-7从左到右及从右到左遍历个单链表是可能的,其方法是在从左向右遍历的过程中将连 接方向逆转,如右图所示。在图中的指针p指向当前正在访问的结点,指针pr指向指针p 所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。(1)编写个算法,从任一给定的位置0，, p)开始，将指针p右移k个结点。如果p移 出链表,则将p置为0,并让pr停留在链表最右边的结点上。(2)编写个算法,从任一给定的位置p)开始，将指针p左移k个结点。如果移 出链表,则将p置为0,并让“停留在链表最左边的结点上。pr Pe m

34、-na-no【解答】(1)指针p右移k个结点templatevclass Type void Lz5/ :siftToRight ( ListNode & p, ListNode *& pr, int A ) if (p = NULL & pr= first) 已经在链的最右端coutvv”已经在链的最右端,不能再右移。 vvendl;return;)int i; ListNode *q;if(p= NULL)从链头开始/ = 1 ； pr = NULL; p = first; 重置p到链头也算次右移else i = 0;while (p != NULL &ik)右移 k 个结点q = pTi

35、nk; p-link = pr;链指针 plink 逆转指向 prpr = p； p = q； /+;指针 pr, p 右移cout 右移了 v i vv 个结点。 endl;)(2)指针p左移&个结点template void List :siftToLeft ( ListNode *& p, ListNode *& pry int Z:) if(p= NULL&pr =first) 已经在链的最左端cout v 已经在链的最左端,不能再左移。endl;return;)int / = 0; ListNode *q;while (pr != NULL &ik)左移 k 个结点q = pLlin

36、k; pr-link = p;链指针 pr-欣 逆转指向 pP=pn pr = q； /+;指专左移) cout 左移了 vv i vv 个结点。 endl;if (i v k ) pr = p; p = NULL;指针 p 移出表外,重置 p,pr3-9试写出用单链表表示的字符串类及字符串结点类的定义,并依次实现它的构造函数、以 及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员 函数。要求每个字符串结点中只存放个字符。【解答】用单链表表示的字符串类string !的头文件siringl.h#include const int maxLen = 300;字符串最大长度为300 （理论上可以无限长）class string 1 public:string 1 ();string 1 ( char * obstr );-stringl();构造空字符串从字符数组建立字符串析构函数int Length ( ) const return curLen; 求字符串长度string 1 & operator = ( string 1 & ob );int operator(st