LINUX.ORG.RU

8
Всего сообщений: 46

Подскажите классификацию структур данных

Затруднительно сформулировать вопрос, поэтому посмотрим на примере, а пример - связный список.

Можно представлять список таким образом:

struct integer_list_node
{
    int data;
    struct integer_list_node *next;
    struct integer_list_node *prev;
};

К примеру, так реализованы списки (и другие структуры данных) в C++.

А можно так:

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

struct integer_list_node
{
    int data;
    struct list node;
};

При этом обычно используют макрос типа container_of, чтобы по указателю на list получить указатель на контейнер. Так, например, списки используются в ядре Linux.

Так вот, существуют термины для обозначения этих двух способов представления. Может, кто-нибудь знает?

 ,

eve ()

Структуры условного выбора типа

У меня возникла идея структуры условного выбора типа.

struct{
int selector_of_type;
void * data_of_selected_type;
}

То есть, это структура последовательности из «выбирающего» и «выбираемого» типа. От значения выбирающего типа зависит тип выбираемого. Было б очень удобно для хранения данных, передачи через сеть итп.

В сишном стандарте этого нет, есть ли в библиотеках типа glib? Хочу знать не изобретаю ли я уже изобретенное?

 , ,

metaprog ()

Дерево, список и соседи

По мотивам: Прикрутить список к элементам уже содержащим ссылки на соседей?

У меня предполагается структура данных, которую можно визуально представить так:

root
|
-> a
   |
   -> b -> c -> d
   |       |
   |       -> h -> i -> j -> k
   |
   -> e -> f -> g

Каким образом я могу обеспечить удобный доступ из любого узла в любой другой узел?

Мыслю так, на примере «a»:

Добавить в список только потомков «b» и «e», а так же указать этим «b» и «e» что их родитель это «a».

Затем, «скрепить» соседей «b» и «c» и соседей «c» и «d», указав для «c» и «d», что их родитель тоже «a».

Повторить процедуру скрепления соседей для «e» как для «b».

Повторить процедуру для «c» как для «a».

Таким образом, смотря на любой узел, если левый сосед NULL, значит этот узел в списке родителя, если правый сосед NULL, значит узел в конце «отростка», если список потомков не пуст, то можно провалиться глубже, ну и у каждого узла есть указатель на родителя для подъёма вверх.

Всё ли я предусмотрел? Насколько сложно будет этим разруливать при добавлении, удалении, перемещении узлов? Есть ли более подходящие варианты взаимосвязей для такой структуры данных?

 , ,

deep-purple ()

Типы нестандартного размера в Kaitai Struct

Пытаюсь написать парсер для ar при помощи Kaitai Struct (cast GreyCat). Заголовок должен выглядеть следующим образом:

Offset 	Length 	Name 	 	 	 	Format
0 	16 	File identifier 	 	ASCII
16 	12 	File modification timestamp 	Decimal
28 	6 	Owner ID 	 	 	Decimal
34 	6 	Group ID 	 	 	Decimal
40 	8 	File mode 	 	 	Octal
48 	10 	File size in bytes 	 	Decimal
58 	2 	Ending characters 	 	0x60 0x0A
Там есть переменные типа decimal размером 6, 10 и 12 байт. Как их правильно обозначить в kaitai struct?
Пока мой ksy выглядит так:
meta:
  id: ar
  file-extension: a
seq:
  - id: sections
    type: section
types:
  section:
    seq:
      - id: artype
        type: str
        encoding: ascii
        terminator: 0x0a
      - id: arhead
        type: header
      - id: file
        size: arhead.filesize
  header:
    seq:
      - id: fileid
        type: str
        encoding: ascii
        size: 16
      - id: timestamp
        size: 12
      - id: owner
        size: 6
      - id: group
        size: 6
      - id: mode
        size: 8
      - id: filesize
        size: 10
      - id: ending
        contents: [0x60, 0x0a]

 , , ,

CYB3R ()

Структура данных для набора одинаковых std::vector

Есть контейнер типа std::vector<std::vector<T>>. Обычно в нем хранится 3-5 векторов гарантированно одинакого размера (по 2-6 элементов). Хочу, чтоб контейнер находился в одном куске памяти, как какое проще всего сделать? (может уже есть такая структура?)

 , ,

KennyMinigun ()

Алгоритмы и структуры данных

Уважаемые специалисты! Посоветуйте, пожалуйста, книгу/курс по алгоритмам и структурам данных!

Требования:

  • достаточно фундаментальное изложение материала;
  • актуальность;
  • если на английском - не проблема, может, даже лучше.

Во много хотелось бы повысить собственную квалификацию и систематизировать знания для интервью. Грубо говоря, если бы вы нанимали сотрудника и в требованиях писали «знание основных алгоритмов и структур данных» - в рамках какой литературы/курса вы бы это требование предъявляли?

 , ,

omegatype ()

Что означает точка перед элементом структуры в C++?

Здравствуйте! Я прочитал про структуры, но поиск «c++ structures dot before member name» ничего не показал.

Подскажите, что определяет элемент структуры .common?

Также, зачем нужно равно HAL_MODULE_INFO_SYM =

И почему все элементы начинаются с точки: .tag, .id, .name?

struct audio_module HAL_MODULE_INFO_SYM = {
    .common = {
        .tag = HARDWARE_MODULE_TAG,
        .module_api_version = AUDIO_MODULE_API_VERSION_0_1,
        .hal_api_version = HARDWARE_HAL_API_VERSION,
        .id = AUDIO_HARDWARE_MODULE_ID,
        .name = "NVIDIA Tegra Audio HAL",
        .author = "The Android Open Source Project",
        .methods = &hal_module_methods,
    },
};

https://source.android.com/devices/architecture/hal

 , ,

comoestasyan ()

А есть нормальная и адекватная литература по структурам данных и алгоритмам

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

 , ,

peregrine ()

Фрагментации памяти тред.

Ночи доброй, ЛОР. Давно на жабе уже пишу, а задумался об этом только сейчас, но, скорее всего, это и к другим языкам относится. Вот есть у нас List<T>, у него есть 2 реализации, LinkedList и ArrayList. Насколько я помню ещё из С, мы можем производить т.н. арифметику указателей в случае с массивом (ArrayList), т.е. память под него выделяется одним куском, в то время как LinkedList, насколько я понимаю, может быть раскидан по всему адресному пространству, просто каждая нода содержит указатель на next, если таковой имеется. Главный вопрос: Правильно ли я понимаю, что в ситуации, когда у нас доступно, допустим, 8 кб памяти и мы пытаемся создать List с данными на 6 - мы можем вывалиться в ООМ в случае с ArrayList из-за фрагментации этой самой памяти? И верно ли утверждение, что в случае с LinkedList такого не произойдет, потому что ему на фрагментацию положить? Заранее спасибо.
/cast stevejobs

 ,

Jefail ()

Подскажите алгоритм/структуру данных

Имеется огромный проект на С++ (около 9681 файлов исходников). И есть утилитарный скрипт, в котором основная задача сказать, встречаются ли два отдельно взятых файла в какой-либо единице трансляции (название единицы трансляции не важно). Иными словами, если имееются foo.h и bar.h и нужно сказать включены ли одновременно оба эти файла в какою-либо единицу трансляции, например baz.cpp.

Подскажите пожалуйста алгоритм/структуру данных чтоб можно было быстро дать ответ на вопрос из предыдущего абзаца. Причем ответ надо давать довольно часто (порядка 500 раз за прогон скрипта) и для разных пар файлов.

Disjoint Set (aka Union Find) не подходит, т.к. один заголовочный файл может включатся в разные единицы трансляции. Причем сами единицы трансляции имеют разный набор включенных файлов. Например, если имеется:

bar.h  foo.h  baz.h
  |   /     \ |
  bar.cpp    baz.cpp
то, bar.h и baz.cpp не имеют соединения. И, что важно, bar.h и baz.h не встречаются вместе ни в одной единице трансляции.

 , , ,

KennyMinigun ()

Как пользоваться указателями и структурами в си

Здравствуйте. Пытаясь накодить задание для зачётки столкнулся с проблемкой. А именно не знанием как передавать в функции структуры, использовать их внутри функции, правильно определять.А также чем отличается, когда передаёшь в качестве параметра указатель и когда просто передаёшь саму переменную(ну или структуру). Если несложно то я был бы благодарен и за примеры синтаксиса и объяснение где, когда и что использовать. Учителя я могу спросить, а вот понять не особо, так как учусь в Словакии, а в инете находил только поверхностные упоминания. P.s. Только сейчас заметил, что забыл упомянуть, что всё происходит в языке си.

 , , ,

Nullum ()

Индексирование частично упорядоченного множества

В частично упорядоченном множестве хочу быстро узнавать, верно ли, что А<Б. Видимо, для этого надо построить какой-то индекс и пользоваться им. Какой? Как его быстро построить?

Пока нашёл вот это: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.6760&rep=rep1... но даже не смотрел. Мне кажется, это должно быть в каком-то учебнике, который я не читал.

 

den73 ()

(Есть ли) система мониторинга, обсчитывающая граф объектов мониторинга?

Знаю, что есть такое в Spectrum и там это довольно удобно реализовано, но в открытых/бесплатных системах мониторинга не встречал.

В самом общем виде нужно следующее:

1) Инструменты, позволяющие тем или иным способом выстраивать объекты мониторинга в связные графы, показывая таким образом зависимости между объектами в различных разрезах ресурсно-сервисной модели

2) Движок системы мониторинга должен быть привязан к графам рессурсно-сервисной модели и способен делать «свёртки» триггеров на основании РСМ. Классический пример: если «упал» маршрутизатор, недоступность сетевого железа за ним не должна порождать миллиард триггеров и лавину всевозможного флуда

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

В очень условно opensource'ном Zabbix'е, например, ресурсно-сервисная модель живёт вообще отдельно от так называемых «карт»/maps - при этом РСМ - это абстрактное дерево, где только листья привязаны хоть к чему-то, вся остальная структура висит в полном вакууме.

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

 , ,

DRVTiny ()

выбор структуры данных

Вопрос такой возник. Надо из списка объектов с числовым полем «x» выбирать тот объект, у которого этот самый «x» максимален. Делать так надо многократно. Кроме того есть метод, который на каждой итерации эти «иксы» выборочно пересчитывает (как раз перед выбором очередного максимального).

Вопрос, собственно, в том, как это реализовать наиболее оптимально в смысле скорости выполнения.

Решение в лоб - словарь с ключом типа целое число; элемент словаря - хэшсет объектов. Пересчитали «икс» - ищем в соответствующем старому значению «икса» множестве объект и удаляем его оттуда; добавляем пересчитанный объект в множество по новому ключу и т.д. И хранить дополнительно значение максимального ключа.

Но этот какой-то слишком рабоче-крестьянский вариант. Подскажите, пожалуйста, более элегантое решение.

 ,

jcdr ()

Оптимальная структура данных

Имеется таблица из трех колонок. Первая — просто номер строки. Во второй и третьей — целые числа. Пример:

1 3 2

2 4 3

3 4 2

4 5 3

5 6 3

и т.д. Пары чисел, образованные второй и третьей колонками, не повторяются. Но по отдельности могут повторяться, как в примере. Нужно по номеру строки получать числа из колонок и наоборот: по заданной паре найти номер строки. Какая структура данных лучше всего для этого подходит? Наивным вариантом был бы массив пар, тогда a[i].up, a[i].low давали бы числа во второй и третьей колонках из строки i. Но в этом случае неудобно искать в обратную сторону, то есть по паре получать индекс.

 

hotpil ()

Множество непересекающихся прямоугольников.

Всем привет.

А подскажет кто структуру, которая позволила бы хранить множество непересекающихся прямоугольников? А самое главное в такой структуре - быстро найти все пересечения произвольного прямоугольника. Ну и поиск прямоугольника в который входит какая-либо координата.

Куда копать?

 ,

seryoga ()

Занимательный PAS2C

Привет!

Вчера вечером от нефиг делать игрался с сабжем.

Кто скажет почему этот код работает не так как ожидается?

/* Output from p2c 2.00.Oct.15, the Pascal-to-C translator */
/* From input file "Numbers.pas" */


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

typedef struct item {
  int data;
  struct item *next;
} item;


int main()

{
  struct item *first = NULL;
  struct item *tmp;
  

  

  while (scanf("%d", &tmp->data)!= EOF) {
    
    tmp = (item *)malloc(sizeof(item));

    tmp->next = first;
    first = tmp;			
  }
  tmp = first;
  

  while (tmp != NULL) {
    printf("%d", tmp->data);
    tmp = tmp->next;
  }

  return 0;
}



/* End. */

program Numbers1;
type
itemptr = ^item;
item = record
data: integer;
next: itemptr;
end;
var
first,tmp: itemptr;
n: integer;
begin
first := nil;

while not SeekEof do

begin
read(n);
new(tmp);

tmp^.data := n;

tmp^.next := first;
first := tmp;

end;
tmp := first;

while tmp <> nil do

begin
writeln(tmp^.data);
tmp := tmp^.next 
end
end.

А именно, как вы можете видеть, теряется последний элемент связного списка, а головной элемент записывается дважды.

Такой вот машинный перевод)

Программа взята из книги Столярова, for fun.

 , , ,

Twissel ()

Хранение, поиск и изменение больших наборов вида строка:значение

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

 , , ,

kinkstarter ()

Python: нет ли хорошей искоробочной реализации деревьев?

Нужна мне структура данных типа «дерево». Не бинарное, а такое, у которого каждый узел может иметь сколько угодно потомков (причём расположенных в заданном порядке). Ну и нужна возможность перемещаться вверх-вниз по дереву, конечно.

Имею спросить: а нет ли под Python такого в уже готовом виде? Очень неохота велосипедизмом заниматься...

 , ,

Yak ()

Помогите найти

Однажды в теме про обучение программированию кто-то запостил ссылку на лекции какого-то питерского(вроде как) вуза по дисциплине

Алгоритмы и структуры данных

Помогите найти или предложите альтернативу

А так же скидывайте все сюда ссылки на достойные материалы по разработке и тестированию.

Кто в курсе про тестировщиков. Что надо знать? Что почитать?

 , ,

wackobird ()