[数据结构与算法]C 实现双向链表(带头节点)

题目

用双向链表实现：将输入的数值按特定规则排序，格式为基数靠左且依次增大，偶数靠右且依次减少
如：依次输入 1 2 3 4 5 6 输出 1 3 5 6 4 2

步骤

双向链表的使用步骤：
1、初始化链表：创建头节点(判断申请空间是否成功，memset初始化，然后让它的前后指针指向空)
2、创建新节点(判断申请空间是否成功，memset初始化，数据的赋值等等操作)
3、尾插法插入新节点
4、完成特定任务
5、遍历链表，打印结果

移动节点

双向链表的节点移动，包含了断开节点和插入节点的操作
断开节点之后如果不用了，可以释放掉，即删除节点

代码示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

struct Node
{
	int data;

	struct Node *prev;
	struct Node *next; 
};

struct Node *init_list(void)
{
	struct Node *head = (struct Node* )malloc(sizeof(struct Node));
	
	if(head != NULL)
	{
		head->prev = head->next = head;
	}
	return head;	
}

struct Node *new_node(int i)
{
	struct Node *new = (struct Node* )malloc(sizeof(struct Node));
	if(new != NULL)
	{
		bzero(new, sizeof(struct Node));
		new->data = i;
		new->prev = new->next = NULL;
		return new;
	}
	return NULL;
}

void add_newNode_tail(struct Node *new, struct Node *head)
{
	new->prev = head->prev;
	new->next = head;

	head->prev->next = new;
	head->prev = new;
}

void showNode(struct Node *head)
{
	struct Node *p = head->next;
	while(p != head)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	putchar('\n');
}

void del_node(struct Node *p)
{
	p->prev->next = p->next;
	p->next->prev = p->prev;

	p->prev = p->next = NULL;
}

void arrange_even(struct Node *head)
{
	struct Node *p = head->prev, *q = NULL;
	bool flag = false;

	while(p != head)
	{
		if(p->data % 2 == 0 && flag != false)
		{
			del_node(p);
			add_newNode_tail(p, head);
			p = q;
		}
		else
		{
			q = p;
		}

		flag = true;

		p = p->prev;
	}
}

void showNode1(struct Node *head)
{
	struct Node *p = head->prev;
	while(p != head)
	{
		printf("%d\t", p->data);
		p = p->prev;
	}
	printf("\n");
}

int main()
{
	int i;
	int n;
	struct Node *head = init_list();
	if(head == NULL)
	{
		printf("fail to creat list head: %s\n", strerror(errno));
		exit(1);
	}
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		struct Node *new = new_node(i);
		if(new == NULL)
		{
			printf("fail to creat new node:%s\n", strerror(errno));
			exit(1);
		}	
		add_newNode_tail(new, head);
	}
	showNode(head);
	arrange_even(head);
	showNode(head);
	showNode1(head);

	return 0;
}