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

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;

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