数据结构实用教程第二版答案-徐孝凯(共67页).doc

精选优质文档-倾情为你奉上 第一章绪习 题 一1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。 A=(K,R)其中K=a1,a2,a3.,anR= B=(K,R)其中K=a,b,c,d,e,f,g,hR=rr=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h> C=(K,R)其中K=a,b,c,d,f,g,hR=rr=<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f> 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,r2,r3r1=<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。Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0);解：Quadratic InitQuadratic(float aa,float bb,float cc)Quadratic 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(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);return 1;elsereturn 0; 按照ax*2+bx+c的格式(x2用x*2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。void Print(Quadratic q)解：void Print(Quadratic q)if(q.a) cout<<q.a<<"x*2"if(q.b)if(q.b>0)cout<<"+"<<q.b<<"x"elsecout<<q.b<<"x"if(q.c)if(q.c>0)cout<<"+"<<q.c;elsecout<<q.c;cout<<end1;3.用c+函数描述下列每一个算法，并分别求出它们的时间复杂度。 比较同一简单类型的两个数据x1和x2的大小，对于x1>x2,x1=x2和x1<x2这三种不同情况分别返回'>''='和'<'字符。假定简单类型用SimpleType表示，它可通过typedef语句定义为任一简单类型。解：char compare(SimpleType x1,SimpleType x2)if(x1>x2) return'>'else if(x1=x2) return '='else return'<'其时间复杂度为O(1) 将一个字符串中的所有字符按相反方的次序重新放置。解：void Reverse(char*p)int n=strlen(p);for(int i=0;i<n/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;i<n;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;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;i<5;i+)ci=0;/给数组c5中的每个元素赋初值0for(i=0;i<n;i+)if(ai<0|ai>200)return 0;/返回数值0表示数组中数据有错，统计失败for(j=0;j<5;j+)/查找ai所在区间if(ai<dj) break;cj+;/使统计相应区间的元素增1return 1;/返回数值1表示统计成功其时间复杂度为O(n) 从二维整型数组amn中查找出最大元素所在的行、列下标。解：void find(int aMN,int m,int n,int&Lin,int&Col)/M和N为全局常量，应满足M>=n和N>=n的条件，Lin和Col为引用/形参，它是对应实参的别名，其值由实参带回Lin=0;Col=0;for(int i=0;i<m;i+)for(int j=0;j<n;j+)if(aij>aLinCol)Lin=i;Col=j;其时间复杂度为O(m*n)4.指出下列各算法的功能并求出其时间复杂度。 int prime(int n)int i=2;int x=(int)sqrt(n);while(i<=x)if(n%i=0)break;i+;if(i>x)return 1;elsereturn 0;解：判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为O(n1/2)。 int sum1(int n)int p=1,s=0;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(s<n)s+=+i;return i;解：求出满足不等式1+2+3.+in的最小i值， 其时间复杂度为O(n1/2)。 void UseFile(ifstream& inp,int c10)/假定inp所对应的文件中保存有n个整数for(int i=0;i<10;i+)ci=0;int x;while(inp>>x)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+)cout<<i<<"*"<<j<<"="<<setw(2)<<i*j<<""cout<<end1;解：打印出一个具有n行的乘法表，第i行(1in)中有n-i+1个乘法项，每个乘法项为i与j(ijn)的乘积，时间复杂度为O(n2)。 void cmatrix(int aMN,int d)/M和N为全局整型常量for(int i=0;i<M;i+)for(int j=0;j<N;j+)aij*=d;解：使数组aMN中的每一个元素均详细以d的值，时间复杂度为O(M*N) void matrimult(int aMN,int bNL,int cML)/int i,j,k;for(i=0;i<M;i+)for(j=0;j<L;j+)cij=0;for(i=0;i<M;i+)for(j=0;j<L;j+)for(k=0;k<N;k+)cij+=aik*bkj;解：矩阵相乘，即aMN×bNLcML，时间复杂度为O(M×N×L)。5.题目略解：void InitSet(Set& s)for(int i=1;i<=SETSIZE;i+)s.mi=0;解：void InitSet(Set& s,int a,int n)fot(int i=0;i<n;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 operator(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)ostr<<''for(int i=1;i<=SETSIZE;i+)if(s.mi=1)ostr<<i<<','ostr<<''<<end1;return ostr;第二章 线性表 习题 二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.解：为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。(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,0)3.对于List类型的线性表,编写出下列每个算法。 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。解： ElemType DMValue(List&L)/从线性表中删除具有最小值的元素并由函数返回,空出的位置/由最后一个元素填补,若线性表为空则显示出错信息并退出运行if(ListEmpty(L)cerr<<"List is Empty!"<<end1;exit(1);ElemType x;x=L.list0;int k=0;for(int i=1;i<L.size;i+)ElemType y=L.listi;if(y<x)x=y;k=i;L.listk=L.listL.size-1;L.size-;return x; 从线性表中删除第i个元素并由函数返回。解：int Deletel(List& L,int i)/从线性表中删除第i个元素并由函数返回if(i<1|i>L.size)cerr<<"Index is out range!"<<end1;exit(1);ElemType x;x=L.listi-1;for(int j=i-1;j<L.size-1;j+)L.listj=L.listj+1;L.size-;return x; 向线性表中第i个元素位置插入一个元素。解：void Inser1(List& L,int i,ElemType x)/向线性表中第i个元素位置插入一个元素if(i<1|i>L.size+1)cerr<<"Index is out range!"<<end1;exit(1);if(L.size=MaxSize)cerr<<"List overflow!"<<end1;exit(1);for(int j=L.size-1;j>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(i<L.size)if(L.listi=x)for(int j=i+1;j<L.sizr;j+)L.listj-1=L.listj;L.size-;elsei+; 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete3(List& L,ElemType s,ElemType t)/从线性表中删除其值在给定值s和t之间的所有元素int i=0;while(i<L.size)if(L.listi>=s)&&(L.listi<=t)for(int j=i+1;j<L.size;j+)L.listj-i=L.listj;L.size-;elsei+; 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete4(List& L,ElemType s,ElemType t)/从有序表中删除其值在给定值s和t之间的所有元素int i=0;while(i<L.size)/从有序表L中查找出大于等于s的第一个元素if(L.listi<s)i+;else break;if(i<L.size)While(i+j<L.size)&&(L.listi+j<=t)j+;/求出s和t之间元素的个数for(int k=i+j;k<L.size;k+)L.listk-j=L.listk;L.size-=j; 将两个有序表合并成一个新的有序表并由变量返回。解：void Merge(List& L1,List& L2,List& L3)/将两个有序表合并成一个新的有序表并由变量返回if(L1.size+L2.size>MaxSize)cerr<<"List overflow!"<<end1;exit(1);int i=0,j=0,k=0;while(i<L1.size)&&(j<L2.size)if(L1.listi<=L2.listj) /将L1中的元素赋给LL.listk=L1.listi;i+;else /将L2中的元素赋给LL.listk=L2.listj;j+;k+;while(i<L1.size) /将L1中剩余的元素赋给LL.listk=L1.listi;i+;k+;while(j<L2.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(i<L.size)int j=i+1;while(j<L.size) /删除重复值为L.listi的所有元素if(L.listj=L.listi)for(int k=j+1;k<L.size;k+)L.listk-1=L.listk;L.size-;elsej+;i+;4.对于结点类型为LNode的单链接表,编写出下列每个算法。 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,.,an,则逆序链接后变为an,an-1,.a1。解：void Contrary(LNode*&HL)/将一个单多办实事有按逆序链接LNode*p=HL;/p指向待逆序的第一个结点，初始指向原表头结点HL=NULL;/HL仍为逆序后的表头指针，禄始值为空while(p!=NULL) /把原单链表中的结点依次进行逆序链接LNode*q=p; /q指向待处理的结点p=p->next; /p指向下一个待逆序的结点/将q结点插入到已陈序单链表的表头q->next=HL;HL=q; 删除单链表中的第i个结点。解：void Delete1(LNode*&HL,int i)/删除单链表中的第i个结点if(i<1|HL=NULL)cerr<<"Index is out range!"<<end1;exit(1);LNode*ap,*cp;ap=NULL;cp=HL; /cp指向当前结点，ap指向其前驱结点int j=1;while(cp!=NULL)if(j=i)break; /cp结点即为第i个结点else /继续向后寻找ap=cp;cp=cp->next;j+;if(cp=NULL)cerr<<"Index is out range!"<<end1;exit(1);if(ap=NULL)HL=HL->next;elseap->next=cp->next;delete cp; 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。解：ElemType MaxValue(LNode*HL)/从单链表中查找出所有元素的最大值，该值由函数返回if(HL=NULL)cerr<<"Linked list is empty!"<<end1;exit(1);ElemType max=HL->data;LNode*p=HL->next;while(p!=NULL)if(max<p->data) max=p->data;p=p->next;return max; 统计出单链表中结点的值等于给定值x的结点数。解：int Count(LNode*HL,ElemType x)/统计出单链表中结点的值等于给定值x的结点数int n=0;while(HL!=NULL)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指向待处理的第一个结点，初始指向原表头结点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->data<cp->data)break;elseap=cp;cp=cp->next; /将q结点插入到ap和cpxf hko pp ujq->next=cp;if(ap=NULL)HL=q;elseap->next=q; 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。解：LNode*Mergel(LNode*&p1,LNode*&p2)/将两个有序单链表合并成一个有序单链表LNode a; /a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理/结束后返回a结点的镄针域的值LNode*p=&a; /p指向结果的有序单链表的表尾结点p->next=NULL;/初始指向表头附加结点while(p1!=NULL)&&(p2!=NULL)/处理两个表非空的情况if(p1->data<p2->data)p->next=p1;p1=p1->next;elsep->next=p2;p2=p2->p=p->next;if(p1!=NULL)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; /初始指向表头附加结点while(p1!=NULL&&(p2!=NULL) /处理两个表非空时的情况LNode*newptr=new LNode;if(p1->data<p2->data) /由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->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,LNode*&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;t2->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)开始报数，则得到的出列次序为: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=newptr;/从表头开始顺序查找出第s个结点，对应第一个开始报数的人LNode*ap=HL,*cp=HL->next;for(i=1;i<s;i+)/ap和cp指针后移一个位置ap=cp;cp=cp->next;/若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点if(cp=HL)ap=HL;cp=HL->next;/依次使n-1个人出列for(i=1;i<n;i+)/顺序查找出待出列的人，即为循环结束后cp所指向的结点for(int j=1;j<m;j+)ap=cp;cp=cp->next;if(cp=HL)ap=HL;cp=HL->next;/输出cp结点的值，即出列的人cout<<cp->data<<""/从单链表中删除cp结点ap->next=cp->next;delete cp;/使cp指向被删除结点的后继结点cp=ap->next;/若cp指向了表头附加结点，则后移ap和cp指针if(cp=HL)ap=HL;cp=HL->next;/使最后一个人出列cout<<HL->next->data<<end1;/删除表头结点和表头附加结点delete HL->next;delete HL;7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点的循环单链表上实现的对应算法。初始化单链表解：void InitList(LNode*HL)HL->next=HL;/将单链表置空删除单链表中的所有结点，使之成为一个空表void ClearList(LNode*HL)LNode*cp,*np;cp=HL->next;/将指向第一个结点的指针赋给cpwhile(cp!=HL)/遍历单链表，向系统交回每一个结点。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(pos<1)cerr<<"pos is out range!"<<end1;exit(1);LNode* p=HL->next;int i=0;while(p!=HL)i+;if(i=pos)break;p=p->next;if(p!=HL)return p->data;elsecerr<<"pos is out range!"<<end1;exit(1);遍历单链表void TraverseList(LNode*HL)LNode* p=HL->next;while(p!=HL)cout<<p->data<<""p=p->next;cout<<end1;从单链表查找具有给定值的第一个元素int Find(LNode* HL,ElemType& item)LNode* p=HL->next;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