数据结构习题答案(全部算法)严蔚敏版
第一章绪论
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(knext,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->datanext; //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...