链表中奇偶结点的移动

骑猪看日落 2022-12-12 01:55 100阅读 0赞

**本题要求实现一个函数，实现对单循环链表中奇数和偶数结点的移动，要求奇数在前面，偶数在后面，且结点之间的相对顺序不变。**  
1.建立结构体并宏定义变量。代码如下

LinkList CreateList_Tail_loop()
    { 
    	LinkList head = (LinkList)malloc(sizeof(struct Node));
    	PNode cur = NULL;
    	PNode tail = head;
    	DataType data;
    	scanf("%d", &data);
    	while (data != -1)
    	{ 
    		cur = (struct Node*)malloc(sizeof(struct Node));
    		cur->data = data;
    		tail->next = cur;
    		tail = cur;
    		scanf("%d", &data);
    	}
    	tail->next = head;
    	return tail;
    }

2.奇偶点移动函数，此函数是本题的重点，采用的方法大致为：  
①建立两个新链表，head1链表负责装偶数，head2链表负责装奇数。  
②遍历链表每一个节点，若为奇数，则利用尾插法插入head2链表；若为偶数，则利用尾插法插入head1链表；  
③将head1和head2的链表头尾连接，形成一个新的单向循环链表，并将次链表的尾指针作为返回值。  
代码如下

PNode  Move_Odd_Even(LinkList tail)
    { 
       PNode head=tail->next,pre=head->next,q=pre->next;
    
       free(head);//释放原链表的头指针，因为头指针无数据
       LinkList head1=(LinkList)malloc(sizeof(struct Node));
        PNode pre1=head1;//pre1指针随着新插入的节点移动，便于进行尾插法
       LinkList head2=(LinkList)malloc(sizeof(struct Node));
        PNode pre2=head2;//pre2指针随着新插入的节点移动，便于进行尾插法
       while(q!=head->next)//原链表是循环链表，当q遍历到原来pre的位置时,遍历结束
       { 
           if(pre->data%2==0)//判断元素是否为偶数
           { 
               pre->next=pre1->next;
               pre1->next=pre;
               pre1=pre1->next;
           }
           else//若不是偶数，则为奇数
           { 
               pre->next=pre2->next;
               pre2->next=pre;
               pre2=pre2->next;
           }
           pre=q;
           q=q->next;//pre始终保持在q的前面
       }
       head1=head1->next;//********
       pre2->next=head1;//*******
       pre1->next=head2;//**星号部分的语句均为将0head1链表和head2链表进行形成一个新的但循坏链表
       return pre1;//返回新循坏链表的尾指针
    
    }

3.打印链表函数。注意，该函数的形参为单循环链表的尾指针，代码如下

void print(LinkList tail)
    { 
    	PNode  head = tail->next;
    	PNode p = head->next;
    	while (p != head)
    	{ 
    		printf("%d ", p->data);
    		p = p->next;
    	}
    }

4.释放链表，防止占用内存，注意，此函数的形参也是尾指针  
代码如下

void DestoryList_Link(LinkList tail)
    { 
    	PNode pre = tail->next;
    	PNode p = pre->next;
    	while (p != tail)
    	{ 
    		free(pre);
    		pre = p;
    		p = pre->next;
    	}
    	free(pre);
    	free(tail);
    }

5.主函数如下

int main()
    { 
    	LinkList tail = NULL;
    	LinkList p = NULL;
    	tail = CreateList_Tail_loop();
    	p = Move_Odd_Even(tail);
    	print(p);
    	DestoryList_Link(tail);
    	return 0;
    }

输入和输出样例如下，此编译环境为Code::Block17.12  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/99f8983fa96049cba430fd9b8700f95b.png