Односвязные списки в Си

Это известный препод с ВМК ННГУ. Спорить с ним бесполезно и вредно - пересдавать будешь до посинения.

О, да ты еще и регистрант сцуко %)

А ну и да, я настолько беспомощен, что удалил свой коммент быстрее, чем я на него смог ответить.

Да лень мне тебя пинать. Ну начнешь ты высерать стены текста - так лень читать же.

О, да ты еще и регистрант сцуко %)

Нет, просто скилл.

Да лень мне тебя пинать. Ну начнешь ты высерать стены текста - так лень читать же.

Ну и как ты можешь меня пинать? В чём - приведи пример. Мне очень интересно.

Давай дружить и пинай сколько хочешь, только честно и поделу, хорошо?

Уровень кода препода ниже плинтуса.

Даже если отвлечься от полной бессмысленности и беспощадности односвязного списка интов.

Вот прямо в самом верху заголовочника виден уровень автора

#ifndef __LIBLIST_H
#define __LIBLIST_H

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

Дальше

struct LIST

Далее не менее дурное название с соответствующим называнию дурным содержанием

struct DESCRIPTOR_LIST
{
LIST         *first,	     // Указатели на: первый,
             *cur,	     //               текущий,
             *end;	     //               последний 
unsigned int  CoObjList;     // Кол-во объектов в списке
int           Error;	     //  0 - нормальное завершение 
};

Зачем пихать в список состояние в виде cur и Error - загадка. Товарищ вообще не в курсе, что количество переменных состояния надо изо всех сил минимизировать. Соответственно в интерфейсе куча дерьма для работы с этими переменными состояния.

Вот это талантливо

#define DL DESCRIPTOR_LIST

За это просто убивать:

//Согласование кодировок для вывода символов кириллицы
char *Rus(char *str);

Что касается остального интерфейса к списку, 2/3 надо или удалить, или переделать. Даже лень комментировать.

В общем, учебный пример можно было сделать намного проще и красивей.

Твой код смотрел совсем мельком, на первый взгляд лучше.

Какой-то мудрец выше:

slist_index(), slist_append(), slist_prepend(), slist_delhead(), >slist_deltail() - что это за даунство?

а почему их не должно быть? если я хочу удалять с хедера и с хвоста)? и инсертить соответственно? И кстати, почему структура

struct _slist {
    snode* head;
    snode* tail;
    void (*free_data) (void*);
    void (*foreach)   (snode*);
    uint32_t size;
};

лишняя?

https://en.wikipedia.org/wiki/XOR_linked_list
When you traverse the list from left to right: supposing you are at C, you can take the address of the previous item, B, and XOR it with the value in the link field (B⊕D). You will then have the address for D and you can continue traversing the list.

а адрес В откуда возьмётся?

если malloc вернул NULL, то ошибочное значение передастся из ф-ции slist_new(), в то время как, очевидно, данная функция должна возвращать строго ненулевое значение. лучше уж вообще не делать проверку на if(l != NULL) тогда.

если я хочу удалять с хедера и с хвоста)? и инсертить соответственно

Стек и очередь не проходили еще? У тебя слишком широкий интерфейс для одногосвязного списка. Ну да щас царь объяснит популярно.

Для функций типа slist_new() возврат NULL в случае нехватки памяти — это вполне нормальное поведение.

проходили. заигрался просто. хотелось создать широкий функционал

Нормально что для каждого создаваемого списка есть функция разрушения поля data, которую можно задать самостоятельно? или это лишнее?

И есть функция slist_foreach прохода по всему списку и выполнить функцию с данными текущей ноды как параметром. или это тоже лишнее?

а почему их не должно быть? если я хочу удалять с хедера и с хвоста)?

Ты понимаешь зачем нужен список? Он нужен только для того, чтобы его обходить с постоянно вставкой в текущие место.

Никому, если он конечно не больной, не нужно туда вставлять в конец/начало. Это не имеет смысла.

и инсертить соответственно?

В пустоту - как в том инсерте?

И кстати, почему структура

Зачем она нужна? Зачем для списка нужна длинна? Зачем для списка нужно вообще что-то? Если мне нужна голова - я сам её сохраню.

void (*free_data) (void*);

Ты не смог придумать как удалить ноду, если ты не создаёшь data и поэтому впихнул эту куллфункцию.

void (*foreach) (snode*);

Который возвращает текущую ноду и вставить за/удалить её нельзя. Типичная куллфункция.

typedef struct node {
  struct node * next;
  void * data[];
} node_t;

typedef node_t * node_ptr_t;

inline node_ptr_t __create_node(node_ptr_t next, void * data, uint64_t len) {
  return memcpy(memcpy(malloc(sizeof(node_t) + len), &(node_t){next}, sizeof(node_t)) + sizeof(node_t), data, len) - sizeof(node_t);
}
#define create_node_static(el) __create_node(NULL, &el, sizeof(el))

inline node_ptr_t __insert(node_ptr_t cur, void * data, uint64_t len) {
  return (cur->next = __create_node(cur->next, data, len));
}
#define insert_static(cur, el) __insert(cur, &el, sizeof(el))

inline void read_all(node_ptr_t root) {
  do {
    fprintf(stderr, "%s\n", root->data);
  } while((root = root->next));
}

int main(void) {
  node_ptr_t tail;
  node_ptr_t head = insert_static(insert_static(insert_static(insert_static(tail = create_node_static("one"), "two"), "three"), "four"), "five");
  read_all(tail);
}

Забахал пару однострочников - вот тебе все списки. Там больше ничего не надо, да и списки не нужны. Зачем все эти заморочки. А если уж задали либу - напиши просто тонну дерьма и выкини после зачётки.

На работоспособность не проверял.

Для ответа нужно знать, зачем вообще всё это. Учебная задача? Ну, тогда достаточно сделать предельно простой и при этом элегантный вариант, выбросив не очень нужные фичи.

Реальное применение? На Си пишут для того, чтобы было быстро и жрало минимум памяти. Предельно быстро и совсем минимум памяти. Односвязные списки этому ортогональны.

Первое, что ты должен понимать - на современных процессорах списки сливают даже динамическим массивам с «умным» ростом размера а-ля std::vector в С++ практически всегда. Сливают, когда, казалось бы, не должны (типа вставки в середину при очень большом количестве элементов). Потому что постоянные кэш-промахи из-за прыжков по указателям и, как правило, динамическое выделение памяти на каждый элемент.

slist_foreach просто безумно тормозная функция по сравнению с проходом по линейному массиву. Если это типовой сценарий использования - так жить нельзя. Если не типовой - функция не очень-то и нужна. Вообще, достаточно сложно придумать сценарий, когда односвязный список действительно оптимален и это подтверждается бенчмарками.

Если сможешь придумать такой сценарий, интерфейс списка нужно затачивать под него.

Хороший тон - не добавлять в интерфейс функции с плохой для данного контейнера асимптотикой. Например, slist_index. Вместо этого предоставить средства для их реализации при необходимости (что-то вроде итераторов, например).

LibList.cpp

Pascal/Microsoft головного мозга. 5 опенсорсных проектов внутривенно!

а «научиться учиться». т.е. уважать начальство/авторитетов, в данном случае преподов и делать как велено, не больше не меньше, а не умничать. И не выделяться из коллектива.

Лул, это ктож тебе такое в голову вбил?

Это ж ННГУ. Там действительно wintel головного мозга. В терминальной стадии и уже не лечится.

для такого однопольного двунаправленного списка необходимо 2 указателя на 2 последовательных элемента списка тогда навигация в любую сторону - ну и для лучшести обычно таковой список менеджать как кольцевой.

slist_delete()

- if(l->size > 0) {
+ if(l->free_data && l->size > 0) {

slist_append()

+ if (! l) {
+     l = slist_new();
+     if (! l) return NULL; 
+ }
  snode* n = slist_node_new();

+ if (! l && !(l = slist_new())) return NULL;
  snode* n = slist_node_new();

Вот так. Потому, что:

1. не всегда требуется деструктор (например, данные могут быть внешними по отношению к контейнеру)
2. список — это абстракция, главное — данные, что в нём хранятся. Поэтому добавление существующего элемента в несуществующий список можно считать созданием списка (аналогичное применимо и к удалению последнего элемента, но только если не нужно отличать ситуацию когда список пуст от ситуации, когда он не существует

И не заводи привычку именовать переменные/аргументы одной буквой!

Прочитал это -> https://isis.poly.edu/kulesh/stuff/src/klist/ Правда тут уже двусвязный список.

Получается, что бы реализовать похожую вещь нужно создать структурку типа

struct list {
    struct list* next;
    struct list* prev;
};

Которая может вставляться в любые другие структуры которые нужно объединить в список? нужно только дать возможность юзеру создавать свои собственные функции для работы со списком?)

Кстати, бонусная задача: попробуй заюзать фичу из C99 именующуюся «Flexible Array Member»: https://en.m.wikipedia.org/wiki/Flexible_array_member

Заодно получишь базовые знания о работе наследования (внутренней реализации) в С++.

Односвязные списки в Си

new DL

Я что-то пропустил?

char _str[256];

ЛОЛ!

Но вообще тебе правильно намекают, что не надо катить бочку на товарища преподавателя. Делай как все и не выёживайся, пока не получишь диплом.

Дело в том, что ты не знаешь, зачем и почему тебе суют именно такую либу. А может это в дидактических целях, и потом тебе покажут как из этого куска «а ла паскаль» сделать класс в крестах? Что касается «каждый раз исправлять библиотеку чтобы работать в другими типами данных» - нет, не придется, т.к. в учебном плане их нет. Не надо ломать человеку учебный процесс, ему и так копейки платят, ещё ты тут умничать будешь не к месту. Всё равно что в мединституте предъявлять претензии, что тебе на 1 курсе не дают лечить настоящих людей, а заставляют рассматривать муляжи.

+ if (! l && !(l = slist_new())) return NULL;
snode* n = slist_node_new();

А зачем создавать список если он не существует, ибо у меня предполагается крах функции если l == NULL ?

Я ответил на твой вопрос в пункте 2.

Другими словами, это подход к реализации. Что тебе важнее: структура или данные?

Конечно, для обучения необходимо показать владение структурой. Однако в более реалистичной обстановке структура данных — вторична (а точнее её внутренняя организация), и единственное, что интересует клиента твоей структуры (в данном случае списка) это доступ к данным внутри (итерация, поиск, манипулирование).

По этому, функцию создания списка можно упразднить во благу удобства использования: пускай добавление первого элемента сразу же и создаёт (до сих пор вторичную) структуру данных (список).

понял)

Ну и дерьмище

что именно?

Код по ссылке. Возьми queue.h, распечатай 72 кеглем, сверни в тугой рулон, и избей им автора этого убожества.

Так там ссылок то много. какая именно)?

Но это лишь один из вариантов подхода к решению задачи. Т.е. это *не* единственный и правильный.

Да обе, на самом деле. Как минимум потому, что ты можешь засунуть в список любой тип. Это убого.

#include <sys/queue.h>

struct foo {
        char             *foo_a;
        int               foo_b;
        struct bar        foo_c;
        SLIST_ENTRY(foo)  entry;
};
SLIST_HEAD(foo_slist, foo);

Вот что-то такое и работать быстрее будет, и проверит тебе тип.

Возьми queue.h, распечатай

Как референсная имплемементация — сойдёт. Но там куча левого хлама, который при обучении только шум создаёт.

И там все на макросах. Новичок явно попадется на чем-нибудь типо двойной евалуации.

Понимаешь, в чем дело. Списки, содержащие в себе любое левое говно - плохо. Преподы, которые советуют использовать такие библиотеки - мудаки.

Списки, содержащие в себе любое левое говно - плохо.

Зависит от поставленной задачи. А в общем случае — да, стоит избавляется от лишних сущностей.

Вот как раз для обучения лучше что-то удобочитаемое и простое, как палка (== без опциональных наворотов и фичей и главное — «ловушек»). Чтоб можно было понять концепцию. А потом можно уже переходить и к более изощрённым заданиям/вариациям.

Ну сразу видно линукс, а а не эта моча мочи queue.h.

Которая может вставляться в любые другие структуры которые нужно объединить в список? нужно только дать возможность юзеру создавать свои собственные функции для работы со списком?)

Да, но этот интерфайс помойка.

Уж проще так делать:

typedef struct {
  uint64_t to, from;
} coolstruct_t;

inline void read_all(node_ptr_t root) {
  do {
    coolstruct_t * s = (void *)root->data;
    fprintf(stderr, "(coolstruct_t){%lu, %lu}\n", s->to, s->from);
  } while((root = root->next));
}

int main(void) {

  node_ptr_t tail;
  node_ptr_t head = insert_static(insert_static(insert_static(insert_static(tail = create_node_static(((coolstruct_t){1, 2})), ((coolstruct_t){3, 4})), ((coolstruct_t){5, 6})), ((coolstruct_t){7, 8})), ((coolstruct_t){9, 10}));
  read_all(tail);
}

Чем маяться такой херёй: list_add(&(tmp->list), &(mylist.list));

Если ты хочешь в обобщенные интерфейсы - тебе в кресты. На сишке это сделать нормально нереально.

queue.h неюзабельная моча дерьма.

Списки

Списки юзают только кря-кря.

содержащие в себе любое левое говно - плохо

queue.h содержит в себе 100% бесполезного дерьма.

Преподы, которые советуют использовать такие библиотеки - мудаки.

Балаболы, которые советуют queue.h - ну ты понял.

Чтобы он объяснял, что только он умеет писать на C? :-)

А разве это не так?

Может и так, но почему-то в таком случае кода неумеющих в C я вижу больше :-)

Может и так, но почему-то в таком случае кода неумеющих в C я вижу больше :-)

Это для искоренения этой убогости. Вот когда ты сможешь настолько в волю, чтобы не признавать дерьмо за что-то, тогда все твои проблемы исчезнут сами собою. И таких вопросов не возникнет.

Говно - это говно, а не код. Говно не может быть кодом. Да хотя что далеко ходить - и говна-то ни у кого нету.

Да и зачем тебе мой код - это всё равно другая реальность, а если бы ты хотел это проверить - всегда пожалуйста. Ради любого из вася я напишу всё, что угодно в пределах разумного, если это задача уровня реального мира. Если уж тебе так интересно как пишу я.

4 звезды, а такой глупый.

Ну и самое важное - я никого не говорил, что только я умею в си. Я просто показывал, что те, кто кукарекают, что умеют - на самом деле не умеют. Всё. Про себя я никогда и ничего не говорил - это проблемы твоего восприятия.

Да, я отчасти считаю, что в сишку я могу лучше, чем любой лор-адепт, которого я встречал, но всё ровно я не умаляю его достоинства - он реально может быть в чем-то мочь больше меня, да и скорее всего может. Да и на обычных пацанов я не агрюсь.

Я агрюсь только на тех, кто кукарекает «я знаю» - знаешь - отвечай. И будь готов быть обосанным, если это не так. Такие дела.

При том есть много людей которые воспринимают критику в аддресс своего кода как личное оскорбление. А такое в отношении препода чревато проблемами.

что будет, если память внезапно НЕ выделится?

std::bad_alloc будет, а при непоймвнлм экзепшне -это крэш.

О да. У нас один чудик сделал #define Ok 1

Как минимум потому, что ты можешь засунуть в список любой тип. Это убого.

Это называется полиморфизм. В C-стиле.

Прочитал это -> https://isis.poly.edu/kulesh/stuff/src/klist/
isis.poly.edu
isis

Поменьше такого читай.

может вставляться в любые другие структуры

Если это твои структуры. Если внешние — не может.

Нафига в ВУЗ пошёл, купил бы диплом и умничал бы дальше.

Тебе бы зачёт поставили без разговоров, за две реализации. Одну, как в задании + одну свою. Это правильный подход. Ты выдвинул гипотезу, подтвердил экспериментом, сравнил с существующим решением, показал (или нет) лучший результат. Вот этому учат в ВУЗах.

Зашёл в тред только за утренней порцией Царя. Всем привет.

научиться учиться
т.е. уважать начальство/авторитетов

Дураки и дороги, две проблемы у которых нет решения.