数据结构习题答案(全部算法)严蔚敏版
第一章绪论
1.16
void print_descending(int x,int y,int z)//按从大到小顺序输出三个数
{
scanf("%d,%d,%d",&x,&y,&z);
if(xy; //<->为表示交换的双目运算符,以下同
if(yz;
if(xy; //冒泡排序
printf("%d %d %d",x,y,z);
}//print_descending
1.17
Status fib(int k,int m,int &f)//求 k 阶斐波那契序列的第 m 项的值 f
{
int tempd;
if(k<2||m<0) return ERROR;
if(melse if (m==k-1 || m==k) f=1;
else
{
for(i=0;i<=k-2;i++) temp[i]=0;
temp[k-1]=1;temp[k]=1; //初始化
sum=1;
j=0;
for(i=k+1;i<=m;i++,j++) //求出序列第 k 至第 m 个元素的值
temp[i]=2*sum-temp[j];
f=temp[m];
}
return OK;
}//fib
分析: k 阶斐波那契序列的第 m 项的值 f[m]=f[m-1]+f[m-2]+......+f[m-k]
=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]
=2*f[m-1]-f[m-k-1]
所以上述算法的时间复杂度仅为 O(m). 如果采用递归设计,将达到 O(k^m). 即使采用暂存中
间结果的方法,也将达到 O(m^2).
1.18
typedef struct{
char *sport;
enum{male,female} gender;
char schoolname; //校名为'A','B','C','D'或'E'
char *result;
int score;
} resulttype;
typedef struct{
int malescore;
int femalescore;
int totalscore;
} scoretype;
void summary(resulttype result[ ])// 求 各 校 的 男 女 总 分 和 团 体 总 分, 假 设 结 果 已 经 储 存 在
result[ ]数组中
{
scoretype score[MAXSIZE];
i=0;
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
case 'A':
score[ 0 ].totalscore+=result[i].score;
if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;
else score[ 0 ].femalescore+=result[i].score;
break;
case 'B':
score[ 0 ].totalscore+=result[i].score;
if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;
else score[ 0 ].femalescore+=result[i].score;
break;
………………
}
i++;
}
for(i=0;i<5;i++)
{
printf("School %d:\n",i);
printf("Total score of male:%d\n",score[i].malescore);
printf("Total score of female:%d\n",score[i].femalescore);
printf("Total score of all:%d\n\n",score[i].totalscore);
}
}//summary
1.19
Status algo119(int a[ARRSIZE])//求 i!*2^i 序列的值且不超过 maxint
{
last=1;
for(i=1;i<=ARRSIZE;i++)
{
a[i-1]=last*2*i;
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
last=a[i-1];
return OK;
}
}//algo119
分析:当某一项的结果超过了 maxint 时,它除以前面一项的商会发生异常.
1.20
void polyvalue()
{
float temp;
float *p=a;
printf("Input number of terms:");
scanf("%d",&n);
printf("Input value of x:");
scanf("%f",&x);
printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);
p=a;xp=1;sum=0; //xp 用于存放 x 的 i 次方
for(i=0;i<=n;i++)
{
scanf("%f",&temp);
sum+=xp*(temp);
xp*=x;
}
printf("Value is:%f",sum);
}//polyvalue
第二章 线性表
2.10
Status DeleteK(SqList &a,int i,int k)//删除线性表 a 中第 i 个元素起的 k 个元素
{
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
a.elem[i+count-1]=a.elem[i+count+k-1];
a.length-=k;
return OK;
}//DeleteK
2.11
Status Insert_SqList(SqList &va,int x)//把 x 插入递增有序表 va 中
{
if(va.length+1>va.listsize) return ERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return OK;
}//Insert_SqList
2.12
int ListComp(SqList A,SqList B)//比较字符表 A 和 B,并用返回值表示结果,值为 1,表示 A>B;
值为-1,表示 A{
for(i=1;i<=A.length&&i<=B.length;i++)
if(A.elem[i]!=B.elem[i])
return A.elem[i]>B.elem[i]?1:-1;
if(A.length==B.length) return 0;
return A.length>B.length?1:-1; //当两个字符表可以互相比较的部分完全相同时,哪个较长,哪
个就较大
}//ListComp
2.13
LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针
{
for(p=l->next;p&&p->data!=x;p=p->next);
return p;
}//Locate
2.14
int Length(LinkList L)//求链表的长度
{
for(k=0,p=L;p->next;p=p->next,k++);
return k;
}//Length
2.15
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表 hb 接在 ha 后面形成链表 hc
{
hc=ha;p=ha;
while(p->next) p=p->next;
p->next=hb;
}//ListConcat
2.16
见书后答案.
2.17
Status Insert(LinkList &L,int i,int b)//在无头结点链表 L 的第 i 个元素之前插入元素 b
{
p=L;q=(LinkList*)malloc(sizeof(LNode));
q.data=b;
if(i==1)
{
q.next=p;L=q; //插入在链表头部
}
else
{
while(--i>1) p=p->next;
q->next=p->next;p->next=q; //插入在第 i 个元素的位置
}
}//Insert
2.18
Status Delete(LinkList &L,int i)//在无头结点链表 L 中删除第 i 个元素
{
if(i==1) L=L->next; //删除第一个元素
else
{
p=L;
while(--i>1) p=p->next;
p->next=p->next->next; //删除第 i 个元素
}
}//Delete
2.19
Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表 L 中值大于
mink 且小于 maxk 的所有元素
{
p=L;
while(p->next->data<=mink) p=p->next; //p 是最后一个不大于 mink 的元素
if(p->next) //如果还有比 mink 更大的元素
{
q=p->next;
while(q->datanext; //q 是第一个不小于 maxk 的元素
p->next=q;
}
}//Delete_Between
2.20
Status Delete_Equal(Linklist &L)//删除元素递增排列的链表 L 中所有值相同的元素
{
p=L->next;q=p->next; //p,q 指向相邻两元素
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p->next; //当相邻两元素不相等时,p,q 都向后推一步
}
else
{
while(q->data==p->data)
{
free(q);
q=q->next;
}
p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
2.21
void reverse(SqList &A)//顺序表的就地逆置
{
for(i=1,j=A.length;iA.elem[i]<->A.elem[j];
}//reverse
2.22
void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于 2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把 L 的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
分析:本算法的思想是,逐个地把 L 的当前元素 q 插入新的链表头部,p 为新表表头.
2.23
void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表 A 和 B 合并为 C,A 和 B 的元素间
隔排列,且使用原存储空间
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; //将 B 的元素插入
if(s)
{
t=q->next;q->next=s; //如 A 非空,将 A 的元素插入
}
p=s;q=t;
}//while
}//merge1
2.24
void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表 A 和 B 合
并为 C,且 C 中元素递减排列,使用原空间
{
pa=A->next;pb=B->next;pre=NULL; //pa 和 pb 分别指向 A,B 的当前元素
while(pa||pb)
{
if(pa->data data||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //将 A 的元素插入新表
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //将 B 的元素插入新表
}
pre=pc;
}
C=A;A->next=pc; //构造新表头
}//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把 A 和 B 的元素插入新表的头部 pc 处,最后处
理 A 或 B 的剩余元素.
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表 A 和 B 的元素
的交集并存入 C 中
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]if(A.elem[i]>B.elem[j]) j++;
if(A.elem[i]==B.elem[j])
{
C.elem[++k]=A.elem[i]; //当发现了一个在 A,B 中都存在的元素,
i++;j++; //就添加到 C 中
}
}//while
}//SqList_Intersect
2.26
void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题
{
p=A->next;q=B->next;
pc=(LNode*)malloc(sizeof(LNode));
C=pc;
while(p&&q)
{
if(p->datadata) p=p->next;
else if(p->data>q->data) q=q->next;
else
{
s=(LNode*)malloc(sizeof(LNode));
s->data=p->data;
pc->next=s;pc=s;
p=p->next;q=q->next;
}
}//while
}//LinkList_Intersect
2.27
void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表 A 和 B 的元素的交
集并存回 A 中
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]else if(A.elem[i]>B.elem[j]) j++;
else if(A.elem[i]!=A.elem[k])
{
A.elem[++k]=A.elem[i]; //当发现了一个在 A,B 中都存在的元素
i++;j++; //且 C 中没有,就添加到 C 中
}
else {i++;j++;}
}//while
while(A.elem[k]) A.elem[k++]=0;
}//SqList_Intersect_True
2.28
void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题
{
p=A->next;q=B->next;pc=A;
while(p&&q)
{
if(p->datadata) p=p->next;
else if(p->data>q->data) q=q->next;
else if(p->data!=pc->data)
{
pc=pc->next;
pc->data=p->data;
p=p->next;q=q->next;
}