リードしないノードの双方向循環チェーンの基本操作

3534 ワード

N HNの試験問題を筆記しました.この中には率先して結点しない双方向循環チェーンの基本操作が問題になり、作成、挿入、削除、廃棄されました.以前は率先ノードを使っていましたが、使いやすいです.筆記試験が終わってから、率先ノードがないことに気づきました.書き直しました.
#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; }