数据结构
设单循环链表 L1,对其遍历的结果是 。请将该循环链表拆成两个单循环链表 L1 和 L2,使得 L1 中含有原 L1 表中序号为奇数的结点且遍历
结果为 ,L2 中含有原 L1 中序号为偶数的结点且遍历结果为 。
并选择自己擅长的程序设计语言实现本算法写出对应的程序。
程序代码:#include <stdlib.h>
#include <stdio.h>
struct node
{
int a;
struct node *next;
};
void print(node *p)
{
while(p)
{
printf("%d ",p->a);
p=p->next;
}
printf("\n");
}
void main()
{
struct node *l1,*l2,*hl1,*hl2,*p,*head=NULL;
int i;
for(i=0;i<15;i++) //15可换成16,对总链表节点数的奇偶进行验证
{
p=(node*)malloc(sizeof(node));
p->a=i;
p->next=NULL;
if(!head)head=l1=p;
else l1=l1->next=p;
}
print(head); //输出原始链表
hl1=l1=head; //偶数链表头指针
hl2=l2=l1->next; //奇数链表头指针
while(l1->next&&l2->next)
{
l1=l1->next=l1->next->next; //分解形成偶数链表
l2=l2->next=l2->next->next; //分解形成奇数链表
}
if(l1)l1->next=NULL;
if(l2)l2->next=NULL; //分解的链表得到正确的结尾
print(hl1); //输出偶数链表
print(hl2); //输出奇数链表
}
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 Press any key to continue