【链表】带头结点的循环链表

还需改进：

creat_node这个函数应有返回类型，来判断新建结点是否成功，不然主函数中不管成不成功都会访问该节点成员。

改了这个函数，在主函数中create_node后要判断是否成功，不成功就提示并退出函数，退出前别忘了还要释放链表！

同时create_link这个函数中也要判断head是否申请成功，不成功的话同样提示并退出函数。

//没写查找函数

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

struct node 
{
    int num;

    struct node * next;
};

typedef struct node Node;
typedef struct node * Link;

void create_node(Link *new_node)
{
    int count = 10;

    do
    {
        *new_node = (Link)malloc(sizeof(Node));
        count--;
    }while(!is_malloc_ok(*new_node) && count);
}

int is_malloc_ok(Link new_node)
{
    if(new_node == NULL)
    {
        printf("malloc error!\n");
        return 0;
    }
    return 1;
}

void create_link(Link *head)
{
    Link new_node;

    create_node(&new_node);
    *head = new_node;
    new_node->next = new_node;
}

void insert_node_head(Link head,Link new_node)
{
    new_node->next = head->next;
    head->next = new_node;
}

void display(Link head)
{
    if(head == NULL)
    {
        printf("(display)该链表已被释放\n");
        return;
    }

    Link p = head->next;

    printf("\n该环形链表为:\n");

    if(p == head)
    {
        printf("Link is empty!\n");
    }
    else
    {
        while(p != head)
        {
            printf("num is %d\n",p->num);
            p = p->next;
        }
    }
}

int length(Link head)
{
    Link p = head->next;
    int count = 0;

    while(p != head)
    {
        count++;
        p = p->next;
    }
    return count;
}

void insert_node_tail(Link head,Link new_node)
{
    Link p = head;

    while(p->next != head)
    {
        p = p->next;
    }

    new_node->next = p->next;
    p->next = new_node;
}

void insert_node_mid_before(Link head,Link new_node,int num)
{
    Link p = head;

    while(p->next != head && p->next->num != num)
    {
        p = p->next;
    }

    if(p->next == head)
    {
        printf("No such node!\n");
        return;
    }
    else
    {
        new_node->next = p->next;
        p->next = new_node;
    }
}

void insert_node_mid_after(Link head,Link new_node,int num)
{
    Link p = head->next;

    while(p != head && p->num != num)
    {
        p = p->next;
    }

    if(p == head)
    {
        printf("No such node!\n");
        return;
    }
    else
    {
        new_node->next = p->next;
        p->next = new_node;
    }
}

void delete_node(Link head,int num)
{
    Link p = head;
    Link q;

    while(p->next != head && p->next->num != num)
    {
        p = p->next;
    }

    if(p->next == head)
    {
        printf("No such node!\n");
    }
    else
    {
        q = p->next;
        p->next = p->next->next;
        free(q);
    }
}

void make_empty(Link head)    //其他函数和带头结点的单链表的函数一样（只是把NULL改成head?)
{                             //但这个清空稍有区别，删时它还是成环的
    Link p = head;
    Link q;

    while(head->next != head)
    {
        q = p->next;
        p->next = p->next->next;
        free(q);
    }
}

void release_link(Link *head)
{
    make_empty(*head);
    free(*head);
    *head = NULL;
}

int main()
{
    Link head;
    Link new_node;
    int i;
    int num;

    create_link(&head);

    for(i = 0; i < 5; i++)
    {
        create_node(&new_node);
        new_node->num = i + 1;

        //insert_node_head(head,new_node);
        insert_node_tail(head,new_node);
    }

    display(head);
    printf("该环形链表长度为%d\n\n",length(head));


    create_node(&new_node);
    printf("请输入你想插入的结点的数值:");
    scanf("%d",&new_node->num);
    printf("请输入你想在数值为哪个的结点之前插入该结点:");
    scanf("%d",&num);

    insert_node_mid_before(head,new_node,num);
    
    display(head);
    printf("该环形链表长度为%d\n\n",length(head));


    create_node(&new_node);
    printf("请输入你想插入的结点的数值:");
    scanf("%d",&new_node->num);
    printf("请输入你想在数值为哪个的结点之后插入该结点:");
    scanf("%d",&num);

    insert_node_mid_after(head,new_node,num);
    
    display(head);
    printf("该环形链表长度为%d\n\n",length(head));


    printf("请输入你想删除的结点的数值:");
    scanf("%d",&num);

    delete_node(head,num);
    display(head);
    printf("该环形链表长度为%d\n\n",length(head));


    make_empty(head);

    display(head);
    printf("该环形链表长度为%d\n\n",length(head));

    release_link(&head);
    if(head == NULL)
    {
        printf("双链表已释放\n");
    }

    return 0;
}