앞장 서지 않 는 노드 의 양 방향 순환 링크 기본 작업

NHN 의 시험 문 제 를 필기시험 해 봤 는데, 그 중 하 나 는 결점 을 앞 세우 지 않 는 양 방향 순환 링크 기본 조작 으로 생 성, 삽입, 삭제, 소각.예전 에는 모두 앞장 서 는 노드 를 사 용 했 는데 사용 하기에 편리 했다. 그 결과 필기시험 이 끝 난 후에 야 앞장 서 는 노드 가 없 는 상황 에서 전면적 인 고려 를 하지 않 은 경우 가 많다 는 것 을 알 게 되 었 다.다시 썼 습 니 다.

#include 
#include 
#include 

typedef struct Node
{
	int data;
	struct Node *prev;
	struct Node *next;
}Node;


Node *creat()
{
	Node *head, *p, *q;
	int data;
	
	scanf("%d", &data);
	if(data != -1)
	{
		head = (Node *)malloc(sizeof(Node));
		if(!head)
		{
			printf("malloc head error
");
			return NULL;
		}

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

	p = head;
	scanf("%d", &data);
	while(data != -1)
	{
		q = (Node *)malloc(sizeof(Node));
		if(!q)
		{
			printf("malloc q %d error
", data);
			return head;
		}

		q->data = data;
		q->prev = p->prev;
		q->next = p;
		p->prev->next = q;
		p->prev = q;

		scanf("%d", &data);
	}

	return head;
}

Node* destroy(Node *h)
{
	assert(NULL != h);
	Node *p = h->next;
	Node *q;

	while(p != h)
	{
		q = p;
		p->prev->next = p->next;
		p->next->prev = p->prev;
		p = q->next;

		free(q);
	}
	free(h);
	h = NULL;
	return h;
}

Node *CreatNode(int data)
{
	if(data == -1)
	{
		printf("para error
");
		return NULL;
	}
	Node *p = (Node *)malloc(sizeof(Node));
	if(!p)
	{
		printf("malloc p error
");
		return NULL;
	}

	p->data = data;
	return p;
}

void insertNode(Node *h, Node *ne)
{
	assert(h != NULL && ne != NULL);

	ne->prev = h->prev;
	ne->next = h;
	h->prev->next = ne;
	h->prev = ne;
}

// ne     data     
int insert(Node *h, Node *ne, int data)
{
	Node *p = (Node *)malloc(sizeof(Node));
	if(!p)
	{
		printf("malloc p error
");
		return -1;
	}
	p->data = data;

	if(ne == NULL || ne == h->prev)
	{
		p->prev = h->prev;
		p->next = h;
		h->prev->next = p;
		h->prev = p;
	}
	else
	{
		Node *q = h;
		while(q->next != h)
		{
			if(q == ne)
			{
				p->next = q->next;
				p->prev = q;
				q->next = p;
				p->next->prev = p;
				break;
			}
			q = q->next;
		}
	}
	return 0;
}

//      
Node* deleteNode(Node *h, Node *dNode)
{
	assert(NULL != h && NULL != dNode);

	Node *p = h;

	//          
	if(dNode == h)
	{
		if(h->next == h)
		{
			free(h);
			h = NULL;
		}
		else
		{
			h = h->next;
			h->prev = p->prev;
			p->prev->next = p->next;
		}
	}
	else
	{
		p = p->next;
		while(p != h)
		{
			if(p == dNode)
			{
				p->prev->next = p->next;
				p->next->prev = p->prev;
				free(p);
				break;
			}
			p = p->next;
		}
	}
	return h;
}

void print_list(Node *h)
{
	assert(NULL != h);
	Node *p = h;
	while(p->next != h)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("%d ", p->data);
	printf("
");
}

void print_reverse(Node *h)
{
	assert(NULL != h);
	Node *p = h->prev;
	while(p != h)
	{
		printf("%d ", p->data);
		p = p->prev;
	}
	printf("%d ", p->data);
	printf("
");
}

int main(void)
{
	Node *h = NULL;
	h = creat();
	print_list(h);

	Node *p = CreatNode(555);
	insertNode(h, p);
	print_list(h);

	Node *p1 = CreatNode(666);
	insertNode(h, p1);
	print_list(h);

	insert(h, p, 333);
	print_list(h);

	h = deleteNode(h, h);
	print_list(h);

	print_reverse(h);
	h = destroy(h);
	return 0;
}