数据结构实用教程第二版答案徐孝凯Word格式.docx
- 文档编号:7495235
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:115
- 大小:46.84KB
数据结构实用教程第二版答案徐孝凯Word格式.docx
《数据结构实用教程第二版答案徐孝凯Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构实用教程第二版答案徐孝凯Word格式.docx(115页珍藏版)》请在冰点文库上搜索。
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);
q.a=q1.a+q2.a;
q.b=q1.b+q2.b;
q.c=q1.c+q2.c;
⑶根据给定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);
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;
else
return0;
⑸按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式,在输出时要注意
去掉系数为0的项,并且当b和c的值为负时,其前不能出现加号。
voidPrint(Quadraticq)
if(q.a)cout<
<
q.a<
"
x**2"
;
if(q.b)
if(q.b>
0)
cout<
+"
q.b<
x"
if(q.c)
if(q.c>
q.c;
end1;
3.用c++函数描述下列每一个算法,并分别求出它们的时间复杂度。
⑴比较同一简单类型的两个数据x1和x2的大小,对于x1>
x2,x1=x2和x1<
x2这三种不同
情况分别返回'
>
'
='
和'
字符。
假定简单类型用SimpleType表示,它可通过typedef
语句定义为任一简单类型。
charcompare(SimpleTypex1,SimpleTypex2)
if(x1>
x2)return'
elseif(x1==x2)return'
elsereturn'
其时间复杂度为O
(1)
⑵将一个字符串中的所有字符按相反方的次序重新放置。
voidReverse(char*p)
intn=strlen(p);
for(inti=0;
i<
n/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;
n;
i++)
p*=a[i];
returnp;
⑷计算Σni=0xi/i+1的值。
doubleAccumulate(doublex,intn)
doublep=1,s=1;
for(inti=1;
=n;
p*=x;
s+=p/(i+1);
returns;
⑸假定一维数组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;
5;
i++)c[i]=0;
//给数组c[5]中的每个元素赋初值0
if(a[i]<
0||a[i]>
200)
//返回数值0表示数组中数据有错,统计失败
for(j=0;
j<
j++)//查找a[i]所在区间
d[j])break;
c[j]++;
//使统计相应区间的元素增1
//返回数值1表示统计成功
⑹从二维整型数组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;
m;
for(intj=0;
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(i>
x)
判断n是否是一个素数,若是则返回数值1,否则返回0。
该算法的时间复杂度为
O(n1/2)。
⑵intsum1(intn)
intp=1,s=0;
p*=i;
s+=p;
计算Σi!
(上标为n,下标为i=1)的值,其时间的复杂度为O(n)。
⑶intsum2(intn)
ints=0;
intp=1;
for(intj=1;
=i;
p*=j;
的值,时间复杂度为O(n2)
⑷intfun(intn)
inti=1,s=1;
while(s<
n)
s+=++i;
returni;
求出满足不等式1+2+3...+i≥n的最小i值,其时间复杂度为O(n1/2)。
⑸voidUseFile(ifstream&
inp,intc[10])
//假定inp所对应的文件中保存有n个整数
10;
c[i]=0;
intx;
while(inp>
x){
i=x%10;
c[i]++;
利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个
数,时间复杂度为O(n)
⑹voidmtable(intn)
for(intj=i;
*"
="
setw
(2)<
i*j<
打印出一个具有n行的乘法表,第i行(1≤i≤n)中有n-i+1个乘法项,每个乘法项为i与j(
i≤j≤n)的乘积,时间复杂度为O(n2)。
⑺voidcmatrix(inta[M][N],intd)
//M和N为全局整型常量
M;
N;
a[i][j]*=d;
使数组a[M][N]中的每一个元素均详细以d的值,时间复杂度为O(M*N)
⑻voidmatrimult(inta[M][N],intb[N][L],intc[M][L])
//
inti,j,k;
L;
c[i][j]=0;
for(k=0;
k<
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)
=SETSIZE;
s.m[i]=0;
⑵解:
s,inta[],intn)
fot(inti=0;
s.m[a[i]]=1;
⑶解:
Setoperator+(Sets1,Sets2)
Sets;
InitSet(s);
if((s1.m[i]==1)||s2.m[i]===1))
s.m[i]=1;
⑷解:
Setoperator*(Sets1,Sets2)
if((s1.m[i]==1)&
&
(s2.m[i]==1))
⑸解:
Booleanoperator^(intelt,Sets)
if(s.m[elt]==1)
returnTrue;
returnFalse;
⑹解:
voidInisert(Set&
s,intn)
s.m[n]=1;
⑺解:
voidDelete(Set&
s.m[n]=0;
⑻解:
ostream&
operator<
(ostream&
ostr,Set&
ostr<
{'
if(s.m[i]==1)
'
}'
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.
为了排版方便,假定采用以下输出格式表示单链接表的示意图;
每个括号内的数据表示一个元
素结点,其中第一个数据为元素值,第二个数据为后继结点的指针,第一个元素结点前的数值为
表头指针。
⒈(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类型的线性表,编写出下列每个算法。
⑴从线性表中删除具有最小值的元素并由函数返回,空出的位置由最后一个元素填补,若
线性表为空则显示出错信息并退出运行。
ElemTypeDMValue(List&
L)
//从线性表中删除具有最小值的元素并由函数返回,空出的位置
//由最后一个元素填补,若线性表为空则显示出错信息并退出运行
if(ListEmpty(L)){
cerr<
ListisEmpty!
exit
(1);
ElemTypex;
x=L.list[0];
intk=0;
L.size;
ElemTypey=L.list[i];
if(y<
x){x=y;
k=i;
L.list[k]=L.list[L.size-1];
L.size--;
returnx;
⑵从线性表中删除第i个元素并由函数返回。
intDeletel(List&
L,inti)
//从线性表中删除第i个元素并由函数返回
if(i<
1||i>
L.size){
Indexisoutrange!
x=L.list[i-1];
for(intj=i-1;
L.size-1;
L.list[j]=L.list[j+1];
⑶向线性表中第i个元素位置插入一个元素。
voidInser1(List&
L,inti,ElemTypex)
//向线性表中第i个元素位置插入一个元素
L.size+1){
if(L.size==MaxSize)
Listoverflow!
for(intj=L.size-1;
j>
i-1;
j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
⑷从线性表中删除具有给定值x的所有元素。
voidDelete2(List&
L,ElemTypex)
//从线性表中删除具有给定值x的所有元素
inti=0;
L.size)
if(L.list[i]==x){
for(intj=i+1;
L.sizr;
L.list[j-1]=L.list[j];
⑸从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。
voidDelete3(List&
L,ElemTypes,ElemTypet)
//从线性表中删除其值在给定值s和t之间的所有元素
if((L.list[i]>
=s)&
(L.list[i]<
=t)){
L.list[j-i]=L.list[j];
⑹从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。
voidDelete4(List&
//从有序表中删除其值在给定值s和t之间的所有元素
L.size)//从有序表L中查找出大于等于s的第一个元素
if(L.list[i]<
s)i++;
elsebreak;
While((i+j<
L.size)&
(L.list[i+j]<
=t))
j++;
//求出s和t之间元素的个数
for(intk=i+j;
L.list[k-j]=L.list[k];
L.size-=j;
⑺将两个有序表合并成一个新的有序表并由变量返回。
voidMerge(List&
L1,List&
L2,List&
L3)
//将两个有序表合并成一个新的有序表并由变量返回
if(L1.size+L2.size>
MaxSize){
inti=0,j=0,k=0;
while((i<
L1.size)&
(j<
L2.size)){
if(L1.list[i]<
=L2.list[j])
{//将L1中的元素赋给L
L.list[k]=L1.list[i];
else{//将L2中的元素赋给L
L.list[k]=L2.list[j];
k++;
L1.size){//将L1中剩余的元素赋给L
while(j<
L2.size){//将L2中剩余的元素赋给L
L.size=k;
⑻从线性表中删除所有其值重复的元素,使其所有元素的值均不同,如对于线性表(2,8,9,
2,5,5,6,8,7,2),则执行此算法后变为(2,8,9,5,6,7)。
voidDelete5(List&
L)
//从线性表中删除所有其值重复的元素,使其所有元素的值均不同
intj=i+1;
{//删除重复值为L.list[i]的所有元素
if(L.list[j]==L.list[i]){
for(intk=j+1;
L.list[k-1]=L.list[k];
4.对于结点类型为LNode的单链接表,编写出下列每个算法。
⑴将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则
逆序链接后变为an,an-1,...a1。
voidContrary(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个结点。
voidDelete1(LNode*&
HL,inti)
//删除单链表中的第i个结点
1||HL==NULL){
LNode*ap,*cp;
ap=NULL;
cp=HL;
//cp指向当前结点,ap指向其前驱结点
intj=1;
while(cp!
if(j==i)
break;
//cp结点即为第i个结点
else{//继续向后寻找
ap=cp;
cp=cp->
if(cp==NULL){
if(ap==NULL)
HL=HL->
ap->
next=cp->
deletecp;
⑶从单链表中查找出所有元素的最大值,该值由函数返回,若单链表为空,则显示出错信息
并停止运行。
ElemTypeMaxValue(LNode*HL)
//从单链表中查找出所有元素的最大值,该值由函数返回
if(HL==NULL){
Linkedlistisempty!
ElemTypemax=HL->
data;
LNode*p=HL->
=NULL){
if(max<
p->
data)max=p->
returnmax;
⑷统计出单链表中结点的值等于给定值x的结点数。
intCount(LNode*HL,ElemTypex)
//统计出单链表中结点的值等于给定值x的结点数
intn=0;
while(HL!
if(HL->
data==x)n++;
returnn;
⑸根据一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实用教程 第二 答案 徐孝凯