第1章第2节练习题8 奇偶拆分单链表

最后更新于:2022-04-01 19:50:53

## 问题描述 > 将一个带头结点的单链表分解为两个带头结点的单链表A和B,使得A表中含有原表中序号为奇数的元素,而B表中含有元表中序号为偶数的元素,且保持其相对顺序不变。 ## 算法思想 > 因为本题中涉及到到按序号拆分单链表的操作,因此我们对单链表的定义进行一次修改,加入序号元素num,这样只需要对num元素判断奇偶便可。因为题目中需要拆分成两个不同的链表,因此这里创建了两个空的单链表,头节点分别为head1,head2。用指针p对原来的单链表进行一次遍历,如果结点的num域为偶数,则将该结点拆下,为了让其相对顺序不发生变化,采用尾插法将该结点插入到第二个单链表中,这样以来,便成功的将一个链表拆分称为两张链表,head1表中存放的是原表中序号为奇数的元素,而head2表中含有元表中序号为偶数的元素。 ## 算法描述 ~~~ //单链表定义 typedef int ElemType; typedef struct LNode{ ElemType data; int num; struct LNode *next; }LNode, *LinkList; /*------------------------------------------------------*/ //拆分单链表 LinkList SeparateList(LNode *head1) { LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); LNode *r=head2; LNode *pre=head1; LNode *p=pre->next; while(p){ if(p->num%2){ pre=p; p=p->next; }else{ pre->next=p->next; r->next=p; r=p; p=pre->next; } } r->next=NULL; return head2; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; int num; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList SeparateList(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1->next=NULL; head1=CreatList(head1); printf("head :"); Print(head1); LNode *head2; head2=SeparateList(head1); printf("head1:"); Print(head1); printf("head2:"); Print(head2); return 0; } //尾插法建立单链表 LinkList CreatList(LNode* head) { int cnt=1; LNode *r=head; LNode *s; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->num=cnt++; r->next=s; r=s; scanf("%d",&x); } r->next=NULL; return head; } //拆分单链表 LinkList SeparateList(LNode *head1) { LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); LNode *r=head2; LNode *pre=head1; LNode *p=pre->next; while(p){ if(p->num%2){ pre=p; p=p->next; }else{ pre->next=p->next; r->next=p; r=p; p=pre->next; } } r->next=NULL; return head2; } //打印全部结点 void Print(LNode* head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~
';