リードしないノードの双方向循環チェーンの基本操作
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;
}