Организация кода. Проектирование кода

si1n3rd

Доброго времени суток!Появилось желание реализовать в учебных целях библиотеку для связанных списков, очередей, стеков. Возник ряд вопросов. 1. Как реализовать эти библиотеки универсальными, чтобы они принимали в качестве своих элементов данные любого формата. Например, чтобы можно было бы организовывать очереди не только из целых чисел, но и различных структур данных. 2. Как подойти к процессу проектирования интерфейса библиотеки? Возможно, есть какая-та литература по вопросам проектирования ПО? В практике пока не очень силен.
9 ответов

si1n3rd

1. Как реализовать эти библиотеки универсальными, чтобы они принимали в качестве своих элементов данные любого формата. Например, чтобы можно было бы организовывать очереди не только из целых чисел, но и различных структур данных.
si1n3rd, можно посмотреть как в ядре линуха реализованы списки, загуглить linux list_head.


si1n3rd

можно посмотреть как в ядре линуха
Взять библиотеку Glib и посмотреть.
Как реализовать эти библиотеки универсальными, чтобы они принимали в качестве своих элементов данные любого формата. Например, чтобы можно было бы организовывать очереди не только из целых чисел, но и различных структур данных.
Думаю, нужно использовать указатели на void.


si1n3rd

<**************, разрешите задать еще такой вопрос. Реально ли написать универсальную единую библиотеку для реализации различных видов списков. Например, я запускаю функцию list_init("single"), и мне функция возвращает указатель на односвязный список. Или лучше не морочить голову, а сделать для каждого вида списка свой интерфейс?


si1n3rd

Реально ли написать универсальную единую библиотеку для реализации различных видов списков. Например, я запускаю функцию list_init("single"), и мне функция возвращает указатель на односвязный список. Или лучше не морочить голову, а сделать для каждого вида списка свой интерфейс?
Думаю, что реально сделать что-то подобное. Я тоже хочу реализовать нечто похожее и универсальное. Однако, думаю, что на си это будет несколько неуклюже выглядеть. Ведь универсализм против специфики конкретной задачи, а значит несколько неоптимален. Да и кстати в glib это уже реализовано, например, для односвязных списков:https://developer.gnome.org/glib/2.52/glib-Singly-Linked-Lists.html
Например, я запускаю функцию list_init("single"), и мне функция возвращает указатель на односвязный список.
Я недавно нечто подобное делал:
#include <stdio.h>
#include <stdlib.h>
 
typedef struct list
{
    int data;
    struct list *next;
} List;
 
List * InitList( void )
{
    List *u1 = (List*)malloc(sizeof(List));
    if(u1==NULL)return NULL;
    u1->next=NULL;
    return u1;
}
List * InsertInList(List *u, int a)
{
    List *uk;
    uk=u;
    uk->data=a;
    uk->next=(List*)malloc(sizeof(List));
    uk=uk->next;
    uk->next=NULL;
    return uk;
}
 
void ListClear(List* u)
{
    List* uk;
    while(u!=NULL)
    {
        uk=u;
        u=u->next;
        free(uk);
    }
}
 
void PrintList(List * u)
{
    List* uk=u;
    while(uk->next!=NULL)
    {
        printf("%d\n", uk->data);
        uk=uk->next;
    }
}
 
List* FindInList(List * u, int a)
{
    List *uk=u;
    while(uk->next!=NULL)
    {
        if(uk->data==a)
            return uk;
        uk=uk->next;
    }
    return NULL;
}
 
int main(void)
{
    List *x,*myList = NULL;
    myList=InitList();
    x=myList;
        x=InsertInList(x, 1);
        x=InsertInList(x, 2);
        x=InsertInList(x, 3);
        x=InsertInList(x, 4);
        x=InsertInList(x, 5);
PrintList(myList);
 
printf("\n%d\n", FindInList(myList, 3)->data);
    
ListClear(myList);
 
    return 0;
}
Правда это нужно переделать, так как это просто набросок, хотя и работающий. Однако идея налицо: нужно абстрагироваться от конкретного списка и иметь возможность работать теми же функциям с множеством различных списков. Ну, а что касается типов, то тут нужно подумать.si1n3rd, Вот "сырцы" гномовской библиотеки: https://opensource.apple.com/source/...5/glib-1.2.10/ Реализация односвязных списков: https://opensource.apple.com/source/...st.c.auto.html Общий заголовочный файл: https://opensource.apple.com/source/...ib.h.auto.html


si1n3rd

<**************, спасибо. Я парочку библиотек уже пересмотрел с реализацией списков и очередей. Везде виды списков реализовываются разными интерфейсами. То есть, я не нашел пока библиотеки, где хотя бы три базовых вида списков реализовывались в одном наборе интерфейсов. Да, и если так подумать, то по всей видимости это не практично. А вот сделать так, чтобы принимался любой вид данных реально, я уже это реализовал. Правда, работы еще завались


si1n3rd

<**************, есть такой вопрос. Есть два варианта реализовать принятие любого вида данных. Первый, принимать указатель на объект и цеплять его к void *data. Второй, принимать указатель на объект, выделять malloc'ом место в ноде под data и копировать туда данные из объекта, но тогда нужно где-то хранить размер передаваемых данных. Попробую кодом передать. Первый случай:
typedef struct list_node {
  void *data;
  struct list_node *next;
} list_node;
 
typedef struct list {
  list_node *head;
  list_node *tail;
  size_t data_size;
} list;
 
list_append(&item, &list);
list_append(void *data, list *list)
{
  list_node *node;
  
  node = malloc(sizeof(node));
  node -> data = malloc(list -> data_size); // data_size даем при инициализации списка и храним дополнительно в структуре списка
  memcpy(node -> data, data, list -> data_size);
  node -> next = NULL;
 
  // Далее подцепляем к списку новую ноду
}
Вторый случай:
typedef struct list_node {
  void *data;
  struct list_node *next;
} list_node;
 
typedef struct list {
  list_node *head;
  list_node *tail;
} list;
 
list_append(&item, &list);
list_append(void *data, list *list)
{
  list_node *node;
  
  node = malloc(sizeof(node));
  node -> data = (void *) data;
  node -> next = NULL;
 
  // Далее подцепляем к списку новую ноду
}
В первом случае вся работа с памятью ложится на плечи пользователя, насколько я понимаю. Во втором, на мои плечи. Или я что-то не доганяю


si1n3rd

Первый, принимать указатель на объект и цеплять его к void *data. Второй, принимать указатель на объект, выделять malloc'ом место в ноде под data и копировать туда данные из объекта, но тогда нужно где-то хранить размер передаваемых данных.
Второй вариант это конечно бред. По первому варианту лучше: так как размер данных при определениии функции задан, как void*, то при вызове этой функции мы просто в параметрах сразу приводим указатель на даные к нужному типу, и все дела. Хотя, компилятор это может сделать и за нас. Поэтому не:
node -> data = (void *) data;
а:
node -> data = data;
Единственный указатель в параметрах функции естественно может указывать на структуру любой сложности.


si1n3rd

<**************, обращусь к вам, как к человеку более опытному. Может вы сможете посоветовать какую-то литературу про проектированию ПО? А то не особо понимаю, куда знания то применять.


si1n3rd

обращусь к вам, как к человеку более опытному.
Тут есть намного более опытные товарищи.
Может вы сможете посоветовать какую-то литературу про проектированию ПО? А то не особо понимаю, куда знания то применять.
Литературы по программированию пруд пруди. Но по проектированию ПО мало. В основном это литература по ООП проектированию. Видимо это потому, что способы проектирования являются своеобразным "ноу-хау" разработки. Оно приходит с опытом, а этим опытом мало кто делится. Могу посоветовать только в каком направлении рыть. Мэйн-стрим это ООП разработка - там деньги, понты и прочее. Но будущее на мой взгляд за автоматным програмированием, хотя оно только начинает прокладывать себе дорогу. На мой взгляд это и есть истинный путь, но многие могут со мной поспорить. Когда-нибудь оно будет мэйн-стримом, и если сейчас начать изучать этот подход, то в будущем будешь первым. Вот здесь сайт по автоматам:, там много материалов по этому вопросу:http://is.ifmo.ru и здесь(хотя этот сайт немного поломался):http://www.softcraft.ru/auto/