数据结构实用教程第二版答案徐孝凯

第一章绪习题一1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。⑴A=(K,R)其中K={a1,a2,a3...,an}R={}⑵B=(K,R)其中K={a,b,c,d,e,f,g,h}R={r}r={a,b,b,c,c,d,d,e,e,f,f,g,g,h}⑶C=(K,R)其中K={a,b,c,d,f,g,h}R={r}r={d,b,d,g,b,a,b,c,g,e,g,h,e,f}⑷D=(K,R)其中K={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}⑸E=(K,R)其中K={48,25,64,57,82,36,75,43}R={r1,r2,r3}r1={48,25,25,64,64,57,57,82,82,36,36,75,75,43}r2={48,25,48,64,64,57,64,82,25,36,82,75,36,43}r3={25,36,36,43,43,48,48,57,57,64,64,75,75,82}解：⑴是集合结构；⑵是线性结构；⑶⑷是树型结构；⑸散列结构。只作为参考。2.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。⑴初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成员的默认值为0。QuadraticInitQuadratic(floataa=0,floatbb=0,floatcc=0);解：QuadraticInitQuadratic(floataa,floatbb,floatcc){Quadraticq;q.a=aa;q.b=bb;q.c=cc;returnq;}⑵做两个多项式加法,即使对应的系数相加,并返回相加的结果。QuadraticAdd(Quadraticq1,Quadraticq2);解：QuadraticAdd(Quadraticq1,Quadraticq2);{Quadraticq;q.a=q1.a+q2.a;q.b=q1.b+q2.b;q.c=q1.c+q2.c;returnq;}⑶根据给定x的值计算多项式的值。floatEval(Quadraticq,floatx);解：floatEval(Quadraticq,floatx){return(q.a*x*x+q.b*x+q.c);}⑷计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程(即a==0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。intRoot(Quadraticq,float&r1,float&r2);解：intRoot(Quadraticq,float&r1,float&r2){if(q.a==0)return-1;floatx=q.b*q.b-4*q.a*q.c;if(x=0){r1=(float)(-q.b+sqrt(x))/(2*q.a);r2=(float)(-q.b-sqrt(x))/(2*q.a);return1;}elsereturn0;}⑸按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。voidPrint(Quadraticq)解：voidPrint(Quadraticq){if(q.a)coutq.ax**2;if(q.b)if(q.b0)cout+q.bx;elsecoutq.bx;if(q.c)if(q.c0)cout+q.c;elsecoutq.c;coutend1;}3.用c++函数描述下列每一个算法，并分别求出它们的时间复杂度。⑴比较同一简单类型的两个数据x1和x2的大小，对于x1x2,x1=x2和x1x2这三种不同情况分别返回'''='和''字符。假定简单类型用SimpleType表示，它可通过typedef语句定义为任一简单类型。解：charcompare(SimpleTypex1,SimpleTypex2){if(x1x2)return'';elseif(x1==x2)return'=';elsereturn'';}其时间复杂度为O(1)⑵将一个字符串中的所有字符按相反方的次序重新放置。解：voidReverse(char*p){intn=strlen(p);for(inti=0;in/2;i++){charch;ch=p[i]p[i]=p[n-i-1];p[n-i-1]=ch;}}其时间复杂度为O(n)⑶求一维double型数组a[n]中的所有元素之乘积。解：doubleproduct(doublea[],intn){doublep=1;for(inti=0;in;i++)p*=a[i];returnp;}其时间复杂度为O(n)⑷计算Σni=0xi/i+1的值。解：doubleAccumulate(doublex,intn){doublep=1,s=1;for(inti=1;i=n;i++){p*=x;s+=p/(i+1);}returns;}其时间复杂度为O(n)⑸假定一维数组a[n]中的每个元素值均在[0，200]区间内，分别统计出落在[0，20),[20,50),[50,80),[80,130),[130,200]等各区间的元素个数。解：intCount(inta[],intn,intc[5])//用数组c[5]保存统计结果{intd[5]={20,50,80,130,201};//用来保存各统计区间的上限inti,j;for(i=0;i5;i++)c[i]=0;//给数组c[5]中的每个元素赋初值0for(i=0;in;i++){if(a[i]0||a[i]200)return0;//返回数值0表示数组中数据有错，统计失败for(j=0;j5;j++)//查找a[i]所在区间if(a[i]d[j])break;c[j]++;//使统计相应区间的元素增1}return1;//返回数值1表示统计成功}其时间复杂度为O(n)⑹从二维整型数组a[m][n]中查找出最大元素所在的行、列下标。解：voidfind(inta[M][N],intm,intn,int&Lin,int&Col)//M和N为全局常量，应满足M=n和N=n的条件，Lin和Col为引用//形参，它是对应实参的别名，其值由实参带回{Lin=0;Col=0;for(inti=0;im;i++)for(intj=0;jn;j++)if(a[i][j]a[Lin][Col]){Lin=i;Col=j;}}其时间复杂度为O(m*n)4.指出下列各算法的功能并求出其时间复杂度。⑴intprime(intn){inti=2;intx=(int)sqrt(n);while(i=x){if(n%i==0)break;i++;}if(ix)return1;elsereturn0;}解：判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为O(n1/2)。⑵intsum1(intn){intp=1,s=0;for(inti=1;i=n;i++){p*=i;s+=p;}returns;}解：计算Σi!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。⑶intsum2(intn){ints=0;for(inti=1;i=n;i++){intp=1;for(intj=1;j=i;j++)p*=j;s+=p;}returns;}解：计算Σi!的值，时间复杂度为O(n2)⑷intfun(intn){inti=1,s=1;while(sn)s+=++i;returni;}解：求出满足不等式1+2+3...+i≥n的最小i值，其时间复杂度为O(n1/2)。⑸voidUseFile(ifstream&inp,intc[10])//假定inp所对应的文件中保存有n个整数{for(inti=0;i10;i++)c[i]=0;intx;while(inpx){i=x%10;c[i]++;}}解：利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个数，时间复杂度为O(n)⑹voidmtable(intn){for(inti=1;i=n;i++){for(intj=i;j=n;j++)couti*j=setw(2)i*j;coutend1;}}解：打印出一个具有n行的乘法表，第i行(1≤i≤n)中有n-i+1个乘法项，每个乘法项为i与j(i≤j≤n)的乘积，时间复杂度为O(n2)。⑺voidcmatrix(inta[M][N],intd)//M和N为全局整型常量{for(inti=0;iM;i++)for(intj=0;jN;j++)a[i][j]*=d;}解：使数组a[M][N]中的每一个元素均详细以d的值，时间复杂度为O(M*N)⑻voidmatrimult(inta[M][N],intb[N][L],intc[M][L])//{inti,j,k;for(i=0;iM;i++)for(j=0;jL;j++)c[i][j]=0;for(i=0;iM;i++)for(j=0;jL;j++)for(k=0;kN;k++)c[i][j]+=a[i][k]*b[k][j];}解：矩阵相乘，即a[M][N]×b[N][L]→c[M][L]，时间复杂度为O(M×N×L)。5.题目略⑴解：voidInitSet(Set&s){for(inti=1;i=SETSIZE;i++)s.m[i]=0;}⑵解：voidInitSet(Set&s,inta[],intn){fot(inti=0;in;i++)s.m[a[i]]=1;}⑶解：Setoperator+(Sets1,Sets2){Sets;InitSet(s);for(inti=1;i=SETSIZE;i++)if((s1.m[i]==1)||s2.m[i]===1))s.m[i]=1;returns;}⑷解：Setoperator*(Sets1,Sets2){Sets;InitSet(s);for(inti=1;i=SETSIZE;i++)if((s1.m[i]==1)&&(s2.m[i]==1))s.m[i]=1;returns;⑸解：Booleanoperator＾(intelt,Sets){if(s.m[elt]==1)returnTrue;elsereturnFalse;}⑹解：voidInisert(Set&s,intn){s.m[n]=1;}⑺解：voidDelete(Set&s,intn){s.m[n]=0;}⑻解：ostream&operator(ostream&ostr,Set&s){ostr'{'for(inti=1;i=SETSIZE;i++)if(s.m[i]==1)ostri',';ostr'}'end1;returnostr;}第二章线性表习题二1.⑴解：(79,62,34,57,26,48)⑵解：(26,34,48,57,62,79)⑶解：(48,56,57,62,79,34)⑷解：(56,57,79,34)⑸解：(26,34,39,48,57,62)2.解：为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表