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 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;
}
/*保留偶数值结点*/
16
}
r->next=NULL; return L;
/*置链表结束标记*/
}
int main() /*测试函数*/ {linklist head,L;
head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ L=sprit(head); /*分裂单链表 head*/ printf(\原单链表为:\\n\
print(head); /*输出倒置后的单链表*/ printf(\分裂所得奇数单链表为:\\n\ print(L); }
本程序的一组测试情况如下图所示。
3.8 设计一个算法，对一个有序的单链表，删除所有值大于 x 而不大于 y 的结点。 【答】：
#include \
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;
17
while (pre!=p) {free(q); q=pre;
pre=pre->next; }
/*释放被删除结点所占用的空间*/
}
void main() /*测试函数*/ { linklist head,L;
datatypex,y;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表*/ printf(\请输入要删除的数据区间:\\n\
scanf(\ deletedata(head,x,y);
print(head); /*输出删除后的单链表*/ }
3.9 设计一个算法，在双链表中值为 y 的结点前面插入一个值为 x 的新结点。即使值为 x 的新 结点成为值为 y 的结点的前驱结点。 【答】：
首先定义双链表的数据结构，相关文件 dlink.h，内容如下：
typedef int datatype; /*预定义的数据类型*/ typedef struct dlink_node{ /*双链表结点定义*/ datatype data; struct dlink_node *llink,*rlink; }dnode;
typedef dnode* dlinklist; /*双链表结点指针类型定义*/
/*尾插法创建带头结点的双链表*/
dlinklist creatdlinklist(void) { dlinklist head,r,s; datatype x;
head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点*/ head->llink=head->rlink=NULL;
printf(\请输入双链表的内容：（整数序列，以 0 结束）\\n\ scanf(\
while (x) /*输入结点值信息，以 0 结束*/ { s=(dlinklist ) malloc(sizeof(dnode)); s->data=x;