絶滅

どうでもいい

C で双方向リストを作る

最近 Project Euler ばかりでポインタとか,構造化とか,でかいコードとか,そういうの完全に忘却したな~と思ったので色々慣れるために双方向リストをつくった.このへんのやつを再現する感じにしてある.C 縛りプレイ.





/* list.h */

#pragma once

typedef struct node {
    void* data;
    struct node* next;
    struct node* prev;
}*node_t;

typedef struct list {
    node_t head;
    size_t size;
}*list_t;

void* safe_malloc(size_t size);
void* safe_realloc(void* p, size_t size);

node_t mk_node();
list_t mk_list();

void* back(list_t list);
node_t begin(list_t list);
void clear(list_t list);
node_t end(list_t list);
node_t erase(list_t list, node_t node);
void* front(list_t list);
node_t insert(list_t list, node_t node, void* data);
void pop_back(list_t list);
void pop_front(list_t list);
void push_back(list_t list, void* data);
void push_front(list_t list, void* data);
size_t size(list_t list);


これを


/* list.c */

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

void* safe_malloc(size_t size)
{
    void* p = (void *)malloc(size);
    if (p == NULL) {
        printf("error : malloc\n");
        exit(0);
    }
    return p;
}

void* safe_realloc(void* p, size_t size)
{
    void* tmp = (void*)realloc(p, size);
    if (tmp == NULL) {
        printf("error : realloc");
        free(p);
        exit(0);
    }
    p = tmp;
    return p;
}


node_t mk_node()
{
    node_t node = (node_t)safe_malloc(sizeof(struct node));
    return node;
}

list_t mk_list()
{
    list_t list = (list_t)safe_malloc(sizeof(struct list));

    list->head = mk_node();
    list->head->data = NULL;
    list->head->next = list->head->prev = list->head;

    list->size = 0;

    return list;
}


void* back(list_t list)
{
    return list->head->prev->data;
}

node_t begin(list_t list)
{
    return list->head->next;
}

void clear(list_t list)
{
    node_t itr = list->head->next;
    while (itr != end(list)) {
        itr = erase(list, itr);
    }
}

node_t end(list_t list)
{
    return list->head;
}

node_t erase(list_t list, node_t itr)
{
    node_t prev, next;
    prev = itr->prev;
    next = itr->next;
    prev->next = next;
    next->prev = prev;

    free(itr->data);
    free(itr);

    list->size--;

    return next;
}

void* front(list_t list)
{
    return list->head->next->data;
}

node_t insert(list_t list, node_t itr, void* data)
{
    node_t node = mk_node();
    node_t prev = itr->prev;

    node->data = data;
    node->prev = prev;
    node->next = itr;

    itr->prev = node;
    prev->next = node;

    list->size++;

    itr = node;

    return itr;
}

void pop_back(list_t list)
{
    node_t current = list->head->prev;
    node_t prev = current->prev;
    list->head->prev = prev;
    prev->next = list->head;

    list->size--;

    free(current->data);
    free(current);
}

void pop_front(list_t list)
{
    node_t current = list->head->next;
    node_t next = current->next;
    list->head->next = next;
    next->prev = list->head;

    list->size--;

    free(current->data);
    free(current);
}

void push_back(list_t list, void* data)
{
    node_t node = mk_node();
    node_t prev = list->head->prev;

    node->data = data;
    node->prev = prev;
    node->next = list->head;

    prev->next = node;
    list->head->prev = node;

    list->size++;
}

void push_front(list_t list, void* data)
{
    node_t node = mk_node();
    node_t next = list->head->next;

    node->data = data;
    node->prev = list->head;
    node->next = next;

    list->head->next = node;
    next->prev = node;

    list->size++;
}

size_t size(list_t list)
{
    return list->size;
}


こうして


/* main.c */

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

typedef int DATATYPE;

DATATYPE* mk_data(DATATYPE val);
void display(list_t list);


int main()
{
    list_t list = mk_list();
    int n = 10;
    DATATYPE* a[10];
    for (int i = 0; i < n; i++) {
        a[i] = mk_data( rand() );
        push_front(list, a[i]);
    }

    //display
    printf("display :\n");
    display(list);
    printf("\n");

    //front
    printf("front : ");
    printf("%d\n\n", *(DATATYPE*)front(list));

    //back
    printf("back : ");
    printf("%d\n\n", *(DATATYPE*)back(list));

    //size
    printf("size :");
    printf("%d\n\n", size(list));


    DATATYPE *b = mk_data(100), *c = mk_data(1000);

    //push_front
    printf("push_front(100) :\n");
    push_front(list, b);
    display(list);
    printf("\n");
    
    //push_back
    printf("push_back(1000) :\n");
    push_back(list, c);
    display(list);
    printf("\n");

    //pop_front
    printf("pop_front :\n");
    pop_front(list);
    display(list);
    printf("\n");
    
    //pop_back
    printf("pop_back :\n");
    pop_back(list);
    display(list);
    printf("\n");

    //begin, end
    printf("enumerate (begin to end) :\n");
    for (node_t node = begin(list); node != end(list); node = node->next) {
        printf("%d ", *(DATATYPE*)node->data);
    }
    printf("\n\n");


    node_t itr = begin(list);
    for (int i = 0; i < 5; itr = itr->next, i++);
    printf("itr->data = %d\n\n" , *(DATATYPE*)itr->data);

    DATATYPE *in = mk_data(12345);

    //insert
    printf("insert 12345 before %d : \n", *(DATATYPE*)itr->data);
    itr = insert(list, itr, in);
    display(list);
    printf("\n");

    printf("itr->data = %d\n\n", *(DATATYPE*)itr->data);

    //erase
    printf("erase %d : \n", *(DATATYPE*)itr->data);
    itr = erase(list, itr);
    display(list);
    printf("\n");

    printf("itr->data = %d\n\n", *(DATATYPE*)itr->data);

    //clear
    printf("clear : \n");
    clear(list);
    printf("size = %d\n", size(list));

    return 0;
}



DATATYPE* mk_data(DATATYPE val)
{
    DATATYPE* data = (DATATYPE*)safe_malloc(sizeof(DATATYPE));
    *data = val;
    return data;
}

void display(list_t list)
{
    int pos = 0;
    node_t itr = begin(list);
    while (itr != end(list)) {
        //printf("list[%d] = %d\n", pos, *(DATATYPE*)(itr->data));
        printf("%d ", *(DATATYPE*)(itr->data));
        itr = itr->next;
        pos++;
    }
    printf("\n");
}


こう


display :
24464 26962 29358 11478 15724 19169 26500 6334 18467 41

front : 24464

back : 41

size :10

push_front(100) :
100 24464 26962 29358 11478 15724 19169 26500 6334 18467 41

push_back(1000) :
100 24464 26962 29358 11478 15724 19169 26500 6334 18467 41 1000

pop_front :
24464 26962 29358 11478 15724 19169 26500 6334 18467 41 1000

pop_back :
24464 26962 29358 11478 15724 19169 26500 6334 18467 41

enumerate (begin to end) :
24464 26962 29358 11478 15724 19169 26500 6334 18467 41

itr->data = 19169

insert 12345 before 19169 :
24464 26962 29358 11478 15724 12345 19169 26500 6334 18467 41

itr->data = 12345

erase 12345 :
24464 26962 29358 11478 15724 19169 26500 6334 18467 41

itr->data = 19169

clear :
size = 0


はい


三行以上の文章を書くのが back number の次に苦手なので,ぬに、塗、、

なんか

typedef struct hoge{

/* ふにゃふにゃ */

}* hoge_t;

のようにして

hoge_t mk_hoge(/* うにゃうにゃ */){
    hoge_t hoge = (メモリ確保);
    /* うようよ */
    return hoge;
}

のように書くと見通しがよくなるってばあちゃんが言ってた

汎用性をもたせるためにリストの要素を void 型へのポインタとしましたがやはり面倒くさいです

あとで C++ バージョンもつくってみよう

溶けてきたので寝ます