数据结构(第二版)习题答案第3章(3)

数据结构答案

【答】：
#include "linklist.h"
void verge(linklist head)
{/*本函数的功能是就地倒置带头结点的单链表
*/



linklist p,q;
p=head->next;
head->next=NULL;
while (p) /*每次从原表取一个结点插入到新表的最前面
*/
{q=p;


p=p->next;
q->next=head->next;
head->next=q;


}
}
int main() /*测试函数*/
{linklist head;

head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
*/
verge(head); /*就地倒置单链表
*/
print(head); /*输出倒置后的单链表
*/


}

3.7设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的
结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。
【答】：
#include "linklist.h"
linklist sprit(linklist head)
{ /*将带头结点的单链表
head中的奇数值结点删除生成新的单链表并返回
*/


linklist L,pre,p,r;
L=r=(linklist)malloc(sizeof(linknode));
r->next=NULL;
pre=head;
p=head->next;
while (p)
{ if (p->data%2==1) /*删除奇数值结点
*/


{
pre->next=p->next;
r->next=p;
r=p;
p=pre->next;


}
else /*保留偶数值结点
*/
{ pre=p;


p=p->next;
}



}
r->next=NULL; /*置链表结束标记
*/
return L;

}
int main() /*测试函数*/
{linklist head,L;


head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
*/
L=sprit(head); /*分裂单链表
head*/
printf("\n原单链表为
:\n");
print(head); /*输出倒置后的单链表
*/
printf("\n分裂所得奇数单链表为
:\n");
print(L);


}

本程序的一组测试情况如下图所示。



3.8设计一个算法，对一个有序的单链表，删除所有值大于
x而不大于
y的结点。
【答】：
#include "linklist.h"
void deletedata(linklist head,datatype x,datatype y)
{ /*删除带头结点单链表中所有结点值大于
x而不大于
y的结点*/


linklist pre=head,p,q;
p=head->next; /*初始化*/
while (p && p->data<=x) /*找第
1处大于
x的结点位置
*/


{ pre=p;
p=p->next;
}
while (p && p->data<=y) /*找第
1处小于
y的位置*/


p=p->next;
q=pre->next; /*删除大于
x而小于
y的结点*/
pre->next=p;
pre=q->next;



while (pre!=p) /*释放被删除结点所占用的空间
*/

{free(q);
q=pre;
pre=pre->next;


}
}
void main() /*测试函数*/
{ linklist head,L;

datatype x,y;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
*/
printf("\n请输入要删除的数据区间
:\n");
scanf("%d%d",&x
,&y);
deletedata(head,x,y);
print(head); /*输出删除后的单链表
*/


}

3.9设计一个算法，在双链表中值为
y的结点前面插入一个值为
x的新结点。即使值为
x的新
结点成为值为
y的结点

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构(第二版)习题答案第3章(3)在线全文阅读。