数据结构答案
【答】：
#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的结点