《数据结构实用教程第二版答案-徐孝凯(共67页).doc》由会员分享，可在线阅读，更多相关《数据结构实用教程第二版答案-徐孝凯(共67页).doc（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 第一章绪习 题 一1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。 A=(K,R)其中K=a1,a2,a3.,anR= B=(K,R)其中K=a,b,c,d,e,f,g,hR=rr=, C=(K,R)其中K=a,b,c,d,f,g,hR=rr=, D=(K,R)其中K=1,2,3,4,5,6R=rr=(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,43R=r1,
2、r2,r3r1=,r2=,r3=,解：是集合结构；是线性结构；是树型结构；散列结构。只作为参考。2.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。 初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成员的默认值为0。Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0);解：Quadratic InitQuadratic(float aa,float bb,float cc)Quadra
3、tic q;q.a=aa;q.b=bb;q.c=cc;return q; 做两个多项式加法,即使对应的系数相加,并返回相加的结果。Quadratic Add(Quadratic q1,Quadratic q2);解：Quadratic Add(Quadratic q1,Quadratic q2);Quadratic q;q.a=q1.a+q2.a;q.b=q1.b+q2.b;q.c=q1.c+q2.c;return q; 根据给定x的值计算多项式的值。float Eval(Quadratic q,float x);解：float Eval(Quadratic q,float x)return(
4、q.a*x*x+q.b*x+q.c); 计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程(即a=0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。int Root(Quadratic q,float& r1,float& r2);解：int Root(Quadratic q,float& r1,float& r2)if(q.a=0)return -1;float x=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);retur
5、n 1;elsereturn 0; 按照ax*2+bx+c的格式(x2用x*2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。void Print(Quadratic q)解：void Print(Quadratic q)if(q.a) coutq.a0)cout+q.bx;elsecoutq.b0)cout+q.c;elsecoutq.c;coutx2,x1=x2和x1=和x2) return;else if(x1=x2) return =;else return;其时间复杂度为O(1) 将一个字符串中的所有字符按相反方的次序重新放置。解：vo
6、id Reverse(char*p)int n=strlen(p);for(int i=0;in/2;i+)char ch;ch=pipi=pn-i-1;pn-i-1=ch;其时间复杂度为O(n) 求一维double型数组an中的所有元素之乘积。解：double product(double a,int n)double p=1;for(int i=0;in;i+)p*=ai;return p;其时间复杂度为O(n) 计算ni=0xi/i+1的值。解：double Accumulate(double x,int n)double p=1,s=1;for(int i=1;i=n;i+)p*=x;
7、s+=p/(i+1);return s;其时间复杂度为O(n) 假定一维数组an中的每个元素值均在0，200区间内，分别统计出落在0，20),20,50),50,80),80,130),130,200等各区间的元素个数。解：int Count(int a,int n,int c5)/用数组c5保存统计结果int d5=20,50,80,130,201;/用来保存各统计区间的上限int i,j;for(i=0;i5;i+)ci=0;/给数组c5中的每个元素赋初值0for(i=0;in;i+)if(ai200)return 0;/返回数值0表示数组中数据有错，统计失败for(j=0;j5;j+)/
8、查找ai所在区间if(ai=n和N=n的条件，Lin和Col为引用/形参，它是对应实参的别名，其值由实参带回Lin=0;Col=0;for(int i=0;im;i+)for(int j=0;jaLinCol)Lin=i;Col=j;其时间复杂度为O(m*n)4.指出下列各算法的功能并求出其时间复杂度。 int prime(int n)int i=2;int x=(int)sqrt(n);while(ix)return 1;elsereturn 0;解：判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为O(n1/2)。 int sum1(int n)int p=1,s=0
9、;for(int i=1;i=n;i+)p*=i;s+=p;return s;解：计算i!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。 int sum2(int n)int s=0;for(int i=1;i=n;i+)int p=1;for(int j=1;j=i;j+)p*=j;s+=p;return s;解：计算i!的值，时间复杂度为O(n2) int fun(int n)int i=1,s=1;while(sn)s+=+i;return i;解：求出满足不等式1+2+3.+in的最小i值， 其时间复杂度为O(n1/2)。 void UseFile(ifstream& in
10、p,int c10)/假定inp所对应的文件中保存有n个整数for(int i=0;ix)i=x%10;ci+;解：利用数组c10中的每个元素ci对应统计出inp所联系的整数文件中个位值同为i的整数个数，时间复杂度为O(n) void mtable(int n)for(int i=1;i=n;i+)for(int j=i;j=n;j+)couti*j=setw(2)i*j;coutend1;解：打印出一个具有n行的乘法表，第i行(1in)中有n-i+1个乘法项，每个乘法项为i与j(ijn)的乘积，时间复杂度为O(n2)。 void cmatrix(int aMN,int d)/M和N为全局整型
11、常量for(int i=0;iM;i+)for(int j=0;jN;j+)aij*=d;解：使数组aMN中的每一个元素均详细以d的值，时间复杂度为O(M*N) void matrimult(int aMN,int bNL,int cML)/int i,j,k;for(i=0;iM;i+)for(j=0;jL;j+)cij=0;for(i=0;iM;i+)for(j=0;jL;j+)for(k=0;kN;k+)cij+=aik*bkj;解：矩阵相乘，即aMNbNLcML，时间复杂度为O(MNL)。5.题目略解：void InitSet(Set& s)for(int i=1;i=SETSIZE;
12、i+)s.mi=0;解：void InitSet(Set& s,int a,int n)fot(int i=0;in;i+)s.mai=1;解：Set operator + (Set s1,Set s2)Set s;InitSet(s);for(int i=1;i=SETSIZE;i+)if(s1.mi=1)|s2.mi=1)s.mi=1;return s;解：Set operator*(Set s1,Set s2)Set s;InitSet(s);for(int i=1;i=SETSIZE;i+)if(s1.mi=1)&(s2.mi=1)s.mi=1;return s;解：Boolean o
13、perator(int elt,Set s)if(s.melt=1)return True;elsereturn False;解：void Inisert(Set& s,int n)s.mn=1;解：void Delete(Set& s,int n)s.mn=0;解：ostream& operator(ostream& ostr,Set& s)ostrfor(int i=1;i=SETSIZE;i+)if(s.mi=1)ostri,;ostrend1;return ostr;第二章 线性表 习题 二1.解：(79,62,34,57,26,48)解：(26,34,48,57,62,79)解：(4
14、8,56,57,62,79,34)解：(56,57,79,34)解：(26,34,39,48,57,62)2.解：为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)(8(56,4),(57,7),(79,5),(34
15、,0)3.对于List类型的线性表,编写出下列每个算法。 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。解： ElemType DMValue(List&L)/从线性表中删除具有最小值的元素并由函数返回,空出的位置/由最后一个元素填补,若线性表为空则显示出错信息并退出运行if(ListEmpty(L)cerrList is Empty!end1;exit(1);ElemType x;x=L.list0;int k=0;for(int i=1;iL.size;i+)ElemType y=L.listi;if(yx)x=y;k=i;
16、L.listk=L.listL.size-1;L.size-;return x; 从线性表中删除第i个元素并由函数返回。解：int Deletel(List& L,int i)/从线性表中删除第i个元素并由函数返回if(iL.size)cerrIndex is out range!end1;exit(1);ElemType x;x=L.listi-1;for(int j=i-1;jL.size-1;j+)L.listj=L.listj+1;L.size-;return x; 向线性表中第i个元素位置插入一个元素。解：void Inser1(List& L,int i,ElemType x)/向
17、线性表中第i个元素位置插入一个元素if(iL.size+1)cerrIndex is out range!end1;exit(1);if(L.size=MaxSize)cerrList overflow!i-1;j-)L.listj+1=L.listj;L.listi-1=x;L.size+; 从线性表中删除具有给定值x的所有元素。解：void Delete2(List& L,ElemType x)/从线性表中删除具有给定值x的所有元素int i=0;while(iL.size)if(L.listi=x)for(int j=i+1;jL.sizr;j+)L.listj-1=L.listj;L.
18、size-;elsei+; 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete3(List& L,ElemType s,ElemType t)/从线性表中删除其值在给定值s和t之间的所有元素int i=0;while(i=s)&(L.listi=t)for(int j=i+1;jL.size;j+)L.listj-i=L.listj;L.size-;elsei+; 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete4(List& L,ElemType s,ElemType t)/从有序表中删除其值在给定值s和t之间
19、的所有元素int i=0;while(iL.size)/从有序表L中查找出大于等于s的第一个元素if(L.listis)i+;else break;if(iL.size)While(i+jL.size)&(L.listi+j=t)j+;/求出s和t之间元素的个数for(int k=i+j;kMaxSize)cerrList overflow!end1;exit(1);int i=0,j=0,k=0;while(iL1.size)&(jL2.size)if(L1.listi=L2.listj) /将L1中的元素赋给LL.listk=L1.listi;i+;else /将L2中的元素赋给LL.li
20、stk=L2.listj;j+;k+;while(iL1.size) /将L1中剩余的元素赋给LL.listk=L1.listi;i+;k+;while(jL2.size) /将L2中剩余的元素赋给LL.listk=L2.listj;j+;k+;L.size=k; 从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9,2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。解：void Delete5(List& L)/从线性表中删除所有其值重复的元素,使其所有元素的值均不同int i=0;while(iL.size)int j=i+1;whi
21、le(jL.size) /删除重复值为L.listi的所有元素if(L.listj=L.listi)for(int k=j+1;knext; /p指向下一个待逆序的结点/将q结点插入到已陈序单链表的表头q-next=HL;HL=q; 删除单链表中的第i个结点。解：void Delete1(LNode*&HL,int i)/删除单链表中的第i个结点if(i1|HL=NULL)cerrIndex is out range!next;j+;if(cp=NULL)cerrIndex is out range!next;elseap-next=cp-next;delete cp; 从单链表中查找出所有元
22、素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。解：ElemType MaxValue(LNode*HL)/从单链表中查找出所有元素的最大值，该值由函数返回if(HL=NULL)cerrLinked list is empty!data;LNode*p=HL-next;while(p!=NULL)if(maxdata) max=p-data;p=p-next;return max; 统计出单链表中结点的值等于给定值x的结点数。解：int Count(LNode*HL,ElemType x)/统计出单链表中结点的值等于给定值x的结点数int n=0;while(HL!=NUL
23、L)if(HL-data=x) n+;HL=HL-next;return n; 根据一维数组an建立一个单链表，使单链表中元素的次序与an中元素的次序相同，并使该算法的时间复杂度为O(n)。解：void Create(LNode*&HL,ElemType a,int n)/根据一维数组an建立一个单链表InitList(HL);for(int i=n-1;i=0;i-)InsertFront(HL,ai; 将一个单链表重新链接成有序单链表。解：void OrderList(LNode*&HL)/将一个单链表重新链接成有序单链表LNode* p=HL;/p指向待处理的第一个结点，初始指向原表头结
24、点HL=NULL; /HL仍为待建立的有序表的表头指针，禄始值为空while(p!=NULL) /把原单链表中的结点依次进行有序链接LNode* q=p; /q指向待处理的结点p=p-next; /p指向下一个待处理的结点LNode* ap=NULL,*cp=HL;/cp指向有序表中待比较的结点，ap指向其前驱结点while(cp!=NULL) /为插入q结点寻找插入位置if(q-datadata)break;elseap=cp;cp=cp-next; /将q结点插入到ap和cpxf hko pp ujq-next=cp;if(ap=NULL)HL=q;elseap-next=q; 将两个有序
25、单链表合并成一个有序单链表，合并后使原有单链表为空。解：LNode*Mergel(LNode*&p1,LNode*&p2)/将两个有序单链表合并成一个有序单链表LNode a; /a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理/结束后返回a结点的镄针域的值LNode*p=&a; /p指向结果的有序单链表的表尾结点p-next=NULL;/初始指向表头附加结点while(p1!=NULL)&(p2!=NULL)/处理两个表非空的情况if(p1-datadata)p-next=p1;p1=p1-next;elsep-next=p2;p2=p2-;p=p-next;if(p1!=NUL
26、L)p-next=p1;if(p2!=NULL)p-next=p2;p1=p2=NULL;return a.next; 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15,16,20)。解：LNode*Merge2(LNode*p1,LNode*p2)/根据两个有序单链表生成一个新的有序单链表LNode a; /用a作为新的有序单链表的表头附加结点LNode*p=&a; /p指向结果有序单链表的表尾结点p-next=NULL; /初始指向表头附
27、加结点while(p1!=NULL&(p2!=NULL) /处理两个表非空时的情况LNode*newptr=new LNode;if(p1-datadata) /由p1-data建立新结点，然后p1指针后移newptr-data=p1-data;p1=p1-next;else /由p2-data建立新结点，然后p2指针后移newptr-data=p2-data;p2=p2-next;/将newptr结点插入到结果的有序表的表尾p-next=newptr;p=newptr;while(p1!=NULL) /继续处理p1单链表中剩余的结点LNode*newptr=new LNode;newptr-
28、data=p1-data;p1=p1-next;p-next=newptr;p=newptr;while(p2!=NULL) /继续处理p2单链表中剩余的结点LNode*newptr=new LNode;newptr-data=p2-data;p2=p2-next;p-next=newptr;p=newptr;p-next=NULL;return a.next; 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表保持不变。解：void Separate(LNode*HL,LNo
29、de*&p1,LNode*&p2)/根据一个单链表HL按条件拆分生成两个单链表p1和p2LNode a,b; /a和b结点分别作为p1和p2单链表的表头附加结点LNode*t1=&a,*t2=&b; /t1和t2分别作为指向p1和p2单链表的/表尾结点，初始指向表头附加结点Lnode*p=HL;while(p!=NULL) /每循环一次产生一个新结点，并把它加入到p1或p2单链表/的未尾LNode*newptr=new LNode;if(p-data%2=1)newptr-data=p-data;t1-next=newptr;t1=newptr;elsenewptr-data=p-data;t
30、2-next=newptr;t2=newptr;p=p-next;t1-next=t2-next=NULL;p1=a.next;p2=b.next; /把指向两个单链表的表头结点的指针分别赋给/p1和p2返回6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位，不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下去直到所有人都出列为止，试求出它们的出列次序。假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2.,n)开始报数，则得
31、到的出列次序为:4,8,5,2,1,3,7,6。此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。解：void Josephus(int n,int m,int s)/使用带表头附加结点的循环单链表解决约瑟夫问题/生成表头附加结点，此时循环单链表为空LNode*HL=new LNode;HL-next=HL;int i;/生成含有n个结点、结点依次为1,2,.n的带表头结点的循环单链表for(i=n;i=1;i-)/生成新的结点LNode*newptr=new LNode;newptr-data=i;/把新的结点插入到表头newptr-next=HL-next;HL-next=n
32、ewptr;/从表头开始顺序查找出第s个结点，对应第一个开始报数的人LNode*ap=HL,*cp=HL-next;for(i=1;inext;/若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点if(cp=HL)ap=HL;cp=HL-next;/依次使n-1个人出列for(i=1;in;i+)/顺序查找出待出列的人，即为循环结束后cp所指向的结点for(int j=1;jnext;if(cp=HL)ap=HL;cp=HL-next;/输出cp结点的值，即出列的人coutdatanext=cp-next;delete cp;/使cp指向被删除结点的后继结点cp=ap-nex
33、t;/若cp指向了表头附加结点，则后移ap和cp指针if(cp=HL)ap=HL;cp=HL-next;/使最后一个人出列coutnext-datanext;delete HL;7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点的循环单链表上实现的对应算法。初始化单链表解：void InitList(LNode*HL)HL-next=HL;/将单链表置空删除单链表中的所有结点，使之成为一个空表void ClearList(LNode*HL)LNode*cp,*np;cp=HL-next;/将指向第一个结点的指针赋给cpwhile(cp!=HL)/遍历单链表，
34、向系统交回每一个结点。np=cp-next;/保存下一个结点的指针。delete cp;/删除当前结点。cp=np;/使下一个结点成为当前结点。HL-next=HL;/置单链表为空得到单链表的长度int ListSize(LNode*HL)LNode*p=HL-next;int i=0;while(p!=HL)i+;p=p-next;return i;检查单链表是否为空int ListEmpty(LNode*hl)return(HL-next=HL);得到单链表中第pos个结点中的元素ElemType GetElem(LNode*HL,int pos)if(pos1)cerrpos is ou
35、t range!next;int i=0;while(p!=HL)i+;if(i=pos)break;p=p-next;if(p!=HL)return p-data;elsecerrpos is out range!next;while(p!=HL)coutdatanext;coutnext;while(p!=HL)if(p-data=item)item=p-data;return 1;elsep=p-next;return 0;更新单链表中具有给定值的第一个元素int Updata(LNode* HL,const ElemType& item)LNode* p=HL-next;while(p