【チェーンテーブル】先頭ノードの双方向ループチェーンテーブル

8795 ワード
C チェーン？メーター
さらに改善する必要があります.
creat_Nodeという関数は、新しいノードが成功したかどうかを判断するために戻ります.そうしないと、メイン関数では成功しないにかかわらず、ノードメンバーにアクセスします.
この関数を変更し、メイン関数でcreate_Node後に成功するかどうかを判断するには、成功しないと関数を提示して終了し、終了する前にチェーンテーブルを解放することを忘れないでください.
同時にcreate_linkという関数でもheadが申請に成功したかどうかを判断し、成功しなければ同様に関数を提示して終了します.
#include 
#include 

struct dnode
{
    int num;

    struct dnode * prior;
    struct dnode * next;
};

typedef struct dnode Dnode;
typedef struct dnode * Dlink;

void create_dnode(Dlink *DblNode)
{
    int count = 10;

    do
    {
        *DblNode = (Dlink)malloc(sizeof(Dnode));
        count--;
    }while(!is_malloc_ok(*DblNode) && count);
}

int is_malloc_ok(Dlink DblNode)
{
    if(DblNode == NULL)
    {
        printf("malloc error!
");
        return 0;
    }
    return 1;
}

void create_dlink(Dlink *DblHead)
{
    Dlink DblNode;
    create_dnode(&DblNode);

    *DblHead = DblNode;
    DblNode->next = DblNode;
    DblNode->prior= DblNode;
}

void insert_dnode_head(Dlink DblHead,Dlink DblNode)
{
    DblHead->next->prior = DblNode;
    DblNode->next = DblHead->next;
    DblHead->next = DblNode;
    DblNode->prior = DblHead;
}

void display(Dlink DblHead)
{
    if(DblHead == NULL)
    {
        printf("       
");
        return;
    }

    Dlink p = DblHead;
    
    printf("      :
");
    if(p->next == DblHead)
    {
        printf("Link is empty!
");
    }
    else
    {
        p = p->next;
        while(p != DblHead)
        {
            printf("num is %d
",p->num);
            p = p->next;
        }
    }
}

int length(Dlink DblHead)
{
    Dlink p = DblHead->next;
    int count = 0;

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

    return count;
}

void insert_dnode_tail(Dlink DblHead,Dlink DblNode)
{
    DblNode->prior = DblHead->prior;
    DblHead->prior->next = DblNode;
    DblNode->next = DblHead;
    DblHead->prior = DblNode;
}

void insert_dnode_mid_before(Dlink DblHead,Dlink DblNode,int num)
{
    Dlink p = DblHead->next;

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

    if(p == DblHead)
    {
        printf("No such node!
");
    }
    else
    {
        DblNode->prior = p->prior;
        p->prior->next = DblNode;
        DblNode->next = p;
        p->prior = DblNode;
    }
}

void insert_dnode_mid_after(Dlink DblHead,Dlink DblNode,int num)
{
    Dlink p = DblHead->next;

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

    if(p == DblHead)
    {
        printf("No such node!
");
    }
    else
    {
        p->next->prior = DblNode;
        DblNode->next = p->next;
        p->next = DblNode;
        DblNode->prior = p;
    }
}

void delete_dnode(Dlink DblHead,int num)
{
    Dlink p = DblHead->next;

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

    if(p == DblHead)
    {
        printf("No such node!
");
    }
    else
    {
        p->next->prior = p->prior;
        p->prior->next = p->next;
        free(p);
    }
}

Dlink find(Dlink DblHead,int num)
{
    Dlink p = DblHead->next;

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

    if(p == DblHead)
    {
        p = NULL;
        return p;
    }
    else
    {
        return p;
    }
}

void make_empty(Dlink DblHead)
{
    Dlink p = DblHead->next;
    Dlink q;

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

void release_dlink(Dlink *DblHead)
{
    make_empty(*DblHead);
    free(*DblHead);
    *DblHead = NULL;
}

int main()
{
    Dlink DblHead;
    Dlink DblNode;
    int i;
    int num;

    create_dlink(&DblHead);

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

        //insert_dnode_head(DblHead,DblNode);
        insert_dnode_tail(DblHead,DblNode);
    }

    display(DblHead);
    printf("      %d

",length(DblHead));


    create_dnode(&DblNode);
    printf("             :");
    scanf("%d",&DblNode->num);
    printf("                   :");
    scanf("%d",&num);

    insert_dnode_mid_before(DblHead,DblNode,num);

    display(DblHead);
    printf("      %d

",length(DblHead));


    create_dnode(&DblNode);
    printf("             :");
    scanf("%d",&DblNode->num);
    printf("                   :");
    scanf("%d",&num);

    insert_dnode_mid_after(DblHead,DblNode,num);

    display(DblHead);
    printf("      %d

",length(DblHead));

    
    printf("             :");
    scanf("%d",&num);

    delete_dnode(DblHead,num);
    
    display(DblHead);
    printf("      %d

",length(DblHead));

    
    printf("             :");
    scanf("%d",&num);

    DblNode = find(DblHead,num);
    if(DblNode == NULL)
    {
        printf("      
");
    }
    else
    {
        printf("        %d

",DblNode->num);
    }

    make_empty(DblHead);

    display(DblHead);
    printf("      %d

",length(DblHead));

    release_dlink(&DblHead);
    display(DblHead);
    
    

    return 0;
}

小練:
注意すべき点:
  • 前ポインタと後ポインタの名前
  • MakeEmpty関数私が空になったとき、削除するたびにリングを維持していなかったので、最後のステップはheadのpriorにheadを指させなければなりません.そうしないと、nodeを加えると
    • に間違いがあります.
  • Display関数は、ヘッダノードが空かどうかを判断します!空はもう解放された!これも忘れないように気をつけて
  • Delete関数でもポインタを削除するときは、前後の2つのノードに2本の線がつながっていて、1つだけつながっていないように注意してください.
    • #include 
#include 

struct node
{
	int num;
	struct node *prior;
	struct node *next;
};

typedef struct node Node;
typedef struct node *Link;

int CreateNode(Link *new_node)
{
	*new_node = (Link)malloc(sizeof(Node));

	if(*new_node == NULL)
		return 0;
	return 1;
}

int CreateLink(Link *head)
{
	if(!CreateNode(head))
		return 0;

	(*head)->next = (*head);
	(*head)->prior = (*head);
	return 1;
}

void InsertHead(Link head, Link node)
{
	head->next->prior = node;
	node->next = head->next;
	head->next= node;
	node->prior = head;
}

void InsertTail(Link head, Link node)
{
	head->prior->next = node;
	node->prior = head->prior;
	head->prior = node;
	node->next = head;
}

void InsertBefore(Link head, Link node, int num)
{
	Link p = head->next;

	while(p != head)
	{
		if(p->num == num)
		{
			p->prior->next = node;
			node->prior = p->prior;
			node->next = p;
			p->prior = node;
			return;
		}
		p = p->next;
	}

	printf("Cannot find the node!
    ");
}

void InsertAfter(Link head, Link node, int num)
{
	Link p = head->next;

	while(p != head)
	{
		if(p->num == num)
		{
			p->next->prior = node;
			node->next = p->next;
			p->next = node;
			node->prior = p;
			return;
		}
		p = p->next;
	}

	printf("Cannot find the node!
    ");
}

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

	while(p != head)
	{
		if(p->num == num)
		{
			p->prior->next = p->next;
			p->next->prior = p->prior;
			free(p);
			return;
		}
		p = p->next;
	}

	printf("Cannot find the node!
    ");
}

void Display(Link head)
{
	Link p = head->next;

	if(p == head)
	{
		printf("Link is empty!
    ");
		return;
	}

	while(p != head)
	{
		printf("num = %d
    ", p->num);
		p = p->next;
	}
}

void MakeEmpty(Link head)
{
	Link p = head->next;

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

	head->prior = head;
}

void ReleaseLink(Link *head)
{
	MakeEmpty(*head);
	free(*head);
	*head = NULL;
}

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

	CreateLink(&head);

	for(i = 0; i < 7; i++)
	{
		if(CreateNode(&new_node))
		{
			new_node->num = i + 1;
			InsertTail(head,new_node);
		}
	}

	Display(head);
	printf("
    ");

	if(CreateNode(&new_node))
	{
		new_node->num = 23;
		InsertBefore(head,new_node,3);
	}

	Delete(head, 6);

	Display(head);
	printf("
    ");

	MakeEmpty(head);

	for(i = 0; i < 7; i++)
	{
		if(CreateNode(&new_node))
		{
			new_node->num = i + 1;
			InsertTail(head,new_node);
		}
	}

	Display(head);
	printf("
    ");

	ReleaseLink(&head);


	return 0;
}

    [Daily] 20200813
    KVMにDebian Wheezyをコンソールでインストールする