率先ノードリングの双方向循環チェーン表

29649 ワード

C言語データ構造

//DLinkList.h
#pragma once
#include
#include
#include
#include


typedef char DLinkType;

typedef struct DLinkNode {
    DLinkType data;
    struct DLinkNode* next;
    struct DLinkNode* prev;
}DLinkNode;

void DLinkListInit(DLinkNode** head);//         
DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value);//  
void DLinkListPopBack(DLinkNode* head); //   
void DLinkListPushFront(DLinkNode* head, DLinkType value);//  
void DLinkListPopFront(DLinkNode* head);//  
DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find);//      
void DLinkListInsert(DLinkNode* pos, DLinkType value);//           
void DLinkListInsertAfter(DLinkNode* pos, DLinkType value);//          
void DLinkListErase(DLinkNode* pos);//         
void DLinkListRemove(DLinkNode* head, DLinkType value);//       ,         
void DLinkListRemoveAll(DLinkNode* head, DLinkType value);//       ,             
size_t DLinkListsize(DLinkNode* head);//     
int DLinkListEmpty(DLinkNode* head);//        
void DLinkListPrintChar(DLinkNode *head, const char* msg);//

//DLinkList.c
#include"DLinkList.h"

void DLinkListPrintChar(DLinkNode *head, const char* msg)//    
{
    printf("[%s]: 
", msg);
    printf("[head]");
    DLinkNode* cur = head->next;
    for (; cur != head; cur = cur->next) {
        printf("->[%c:0x%p]", cur->data, cur);
    }
    printf("

");
    DLinkNode* ptr = head->prev;
    for (; ptr != head; ptr = ptr->prev) {
        printf("[%c:Ox%p]->", ptr->data, ptr);
    }
    printf("[head]");
    printf("

");
}


DLinkNode* CreateDNode(DLinkType value)
{
    DLinkNode* cur = (DLinkNode*)malloc(sizeof(DLinkNode));
    cur->data = value;
    cur->next = cur;
    cur->prev = cur;
    return cur;
}

void DestoryDNode(DLinkNode* pos)
{
    free(pos);
}

void DLinkListInit(DLinkNode** head)
{
    if (head == NULL) {
        return;
    }
    *head = NULL;
    *head = (DLinkNode*)malloc(sizeof(DLinkNode));
    (*head)->next = *head;
    (*head)->prev = *head;
}

DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value)
{
    if (head == NULL)
    {
        return NULL;
    }
    DLinkNode* new_node = CreateDNode(value);
    DLinkNode* new_node_next = head;
    DLinkNode* new_node_prev = head->prev;

    new_node_prev->next = new_node;
    new_node->prev = new_node_prev;
    new_node_next->prev = new_node;
    new_node->next = new_node_next;
    return new_node;
}

void DLinkListPopBack(DLinkNode* head)
{
    if (head == NULL) {
        return;
    }
    if (head == head->next) {
        return;
    }
    DLinkNode* to_delete = head->prev;
    DLinkNode* to_delete_prev = to_delete->prev;
    DLinkNode* to_delete_next = head;

    to_delete_next->prev = to_delete_prev;
    to_delete_prev->next = to_delete_next;
    DestoryDNode(to_delete);
}

void DLinkListPushFront(DLinkNode* head, DLinkType value)
{
    if (head == NULL) {
        return;
    }
    DLinkNode* new_node = CreateDNode(value);
    DLinkNode* new_node_prev = head;
    DLinkNode* new_node_next = head->next;

    new_node->next = new_node_next;
    new_node->prev = new_node_prev;
    new_node_next->prev = new_node;
    new_node_prev->next = new_node;
}

void DLinkListPopFront(DLinkNode* head)
{
    if (head == NULL) {
        return;
    }
    if (head == head->next) {
        return;
    }
    DLinkNode* to_delete = head->next;
    DLinkNode* to_delete_next = to_delete->next;
    DLinkNode* to_delete_prev = head;

    to_delete_next->prev = to_delete_prev;
    to_delete_prev->next = to_delete_next;
    DestoryDNode(to_delete);
}

DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find)
{
    if (head == NULL) {
        return NULL;
    }
    DLinkNode* cur = head->next;
    for (; cur != head; cur = cur->next) {
        if (cur->data == to_find) {
            return cur;
        }
    }
    return NULL;
}

void DLinkListInsert(DLinkNode* pos, DLinkType value)
{
    if (pos == NULL) {
        //    
        return;
    }
    DLinkNode* new_node = CreateDNode(value);
    DLinkNode* new_node_next = pos;
    DLinkNode* new_node_prev = pos->prev;

    new_node->next = new_node_next;
    new_node->prev = new_node_prev;
    new_node_next->prev = new_node;
    new_node_prev->next = new_node;
}

void DLinkListInsertAfter(DLinkNode* pos, DLinkType value)
{
    if (pos == NULL) {
        return;
    }
    DLinkNode* new_node = CreateDNode(value);
    DLinkNode* new_node_next = pos->next;
    DLinkNode* new_node_prev = pos;

    new_node->next = new_node_next;
    new_node->prev = new_node_prev;
    new_node_next->prev = new_node;
    new_node_prev->next = new_node;
}

void DLinkListErase(DLinkNode* pos)
{
    if (pos == NULL) {
        return;
    }
        DLinkNode* to_delete = pos;
        DLinkNode* to_delete_next = pos->next;
        DLinkNode* to_delete_prev = pos->prev;  

        to_delete_prev->next = to_delete_next;
        to_delete_next->prev = to_delete_prev;
        DestoryDNode(to_delete);
}

void DLinkListRemove(DLinkNode* head, DLinkType value)
{
    if (head == NULL) {
        return;
    }
    DLinkNode* cur = head->next;
    for (; cur != head; cur = cur->next) {
        if (cur->data == value) {
            DLinkListErase(cur);
            break;
        }
    }
    return;
}

void DLinkListRemoveAll(DLinkNode* head, DLinkType value)
{
    if (head == NULL) {
        return;
    }
    DLinkNode* cur = head;
    while (cur != head->prev) {
        if (cur->next->data == value) {
            DLinkNode* to_delete = cur->next;
            DLinkNode* to_delete_next = to_delete->next;
            DLinkNode* to_delete_prev = to_delete->prev;

            to_delete_next->prev = to_delete_prev;
            to_delete_prev->next = to_delete_next;
            DestoryDNode(to_delete);
        }
        else
            cur = cur->next;
    }
}

size_t DLinkListsize(DLinkNode* head)
{
    if (head == NULL) {
        return (size_t)-1;
    }
    size_t count = 0;
    DLinkNode* cur = head->next;
    while (cur != head) {
        count++;
        cur = cur->next;
    }
    return count;
}

int DLinkListEmpty(DLinkNode* head)
{
    if (head == NULL) {
        return -1;
    }
    return (head == head->next || head == head->prev);
}

//       
//test.c
#include"DLinkList.h"

#define TEST_HEADER printf("
==============%s==============
", __FUNCTION__)

void TestInit()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPrintChar(head, "   ");
}

void TestPushBack()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
}

void TestPopBack()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPopBack(head);
    DLinkListPrintChar(head, "        ");
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListPopBack(head);
    DLinkListPrintChar(head, "        ");
    DLinkListPopBack(head);
    DLinkListPopBack(head);
    DLinkListPrintChar(head, "        ");
}

void TestPushFront()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushFront(head, 'a');
    DLinkListPushFront(head, 'b');
    DLinkListPushFront(head, 'c');
    DLinkListPushFront(head, 'd');
    DLinkListPushFront(head, 'e');
    DLinkListPrintChar(head, "      ");
}

void TestPopFront()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPopFront(head);
    DLinkListPrintChar(head, "        ");
    DLinkListPushFront(head, 'a');
    DLinkListPushFront(head, 'b');
    DLinkListPushFront(head, 'c');
    DLinkListPushFront(head, 'd');
    DLinkListPushFront(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListPopFront(head);
    DLinkListPrintChar(head, "        ");
    DLinkListPopFront(head);
    DLinkListPopFront(head);
    DLinkListPopFront(head);
    DLinkListPrintChar(head, "        ");
}

void TestFind()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushBack(head, 'a');
    DLinkNode* pos_b = DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListFind(head, 'x');
    DLinkListPrintChar(head, "        x");
    DLinkNode* ret = DLinkListFind(head, 'b');
    DLinkListPrintChar(head, "       b");
    printf("0x%p
", ret);
}

void TestInsert()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListInsert(head, 'a');
    DLinkListPrintChar(head, "            ");
    DLinkNode* pos_b = DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListInsert(pos_b, 'x');
    DLinkListPrintChar(head, " b    x");
}

void TestInsertAfter()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListInsertAfter(head, 'a');
    DLinkListPrintChar(head, "            a");
    DLinkNode* pos_b = DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListInsertAfter(pos_b, 'x');
    DLinkListPrintChar(head, " b    x");
}

void TestErase()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushBack(head, 'a');
    DLinkNode* pos_b = DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListErase(pos_b);
    DLinkListPrintChar(head, "    b  ");
}

void TestRemove()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    DLinkListRemove(head, 'a');
    DLinkListPrintChar(head, "      a");

}

void TestRemoveAll()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPushBack(head, 'a');
    DLinkListPrintChar(head, "      ");
    DLinkListRemoveAll(head, 'a');
    DLinkListPrintChar(head, "      a");
}

void TestSize()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPushBack(head, 'e');
    DLinkListPrintChar(head, "      ");
    size_t ret = DLinkListsize(head);
    printf("ret expect 8, actual %lu
", ret);
}

void TestEmpty()
{
    TEST_HEADER;
    DLinkNode* head;
    DLinkListInit(&head);
    int ret = DLinkListEmpty(head);
    printf("ret expect 1, actual %d
", ret);
    DLinkListPushBack(head, 'a');
    DLinkListPushBack(head, 'b');
    DLinkListPushBack(head, 'c');
    DLinkListPushBack(head, 'd');
    DLinkListPrintChar(head, "      ");
    ret = DLinkListEmpty(head);
    printf("ret expect 0, actual %d
", ret);
}

int main()
{
    TestInit();
    TestPushBack();
    TestPopBack();
    TestPushFront();
    TestPopFront();
    TestFind();
    TestInsert();
    TestInsertAfter();
    TestErase();
    TestRemove();
    TestRemoveAll();
    TestSize();
    TestEmpty();
    system("pause");
    return 0;
}

javaデータ構造——Binary SearchTree(二叉検索ツリー)