Типы данных

[Asya7]

Помогите пожалуйста, разобраться! Много литературы уже прочитано, но не могу понять:
1) как в коде программы понять какие используются структуры данных (особенно касается однонаправленного списка, очереди, стека);
2) сортировки различного вида применимы на какие-то конкретные данные или нет(напр. метод Шелла - только на массиве или нет)?;
3) что такое (перемешенные) таблицы?;
4) Динамические структуры (или типы) - они могут создаваться только через указатель? Или есть просто динам.структуры?

Очень мне поможете, если объясните или на хорошую, понятную литературу ссылку укажете.

[Utkin]

1) как в коде программы понять какие используются структуры данных (особенно касается однонаправленного списка, очереди, стека);

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

2) сортировки различного вида применимы на какие-то конкретные данные или нет(напр. метод Шелла - только на массиве или нет)?;

Есть два варианта:
1. Использована стандартная функция/метод (то есть надо знать хотя бы стандартную библиотеку)
2. Написано что-то свое в силу неграмотности либо потому что используется нестандартный алгоритм или не стандартные типы данных.
Большинство алгоритмов сортировки разработано исключительно для чисел. Поэтому в специализированных случаях, когда структура данных не абстрактна, а сильно привязана к предметной области (например код ДНК при биологических исследованиях) могут использоваться специфические алгоритмы (для работы с ДНК есть специальные библиотеки со своими алгоритмами сортировки).

3) что такое (перемешенные) таблицы?;

Требуется привязка к языку программирования чтобы ответить на этот вопрос.

4) Динамические структуры (или типы) - они могут создаваться только через указатель? Или есть просто динам.структуры?

Это также зависит от языка программирования и библиотек. Есть например динамические массивы, в принципе те же указатели, но на более высоком и удобном уровне. Обычно каждый следующий слой абстракции маскирует примитивы (например в динамических массивах используется не указатель на ячейку памяти, а индекс). Вообще конкретика как уже упоминал сильно зависит от того, на чем написано. И вроде все везде одинаково, но детали реализации несколько меняют взгляд на программирование. Например строки в делфи используют технологию "умные указатели", то есть строка будет не нужна автоматически как только на нее перестанет ссылаться хотя бы один из объектов. Это важно так как строки могут быть офигеть как длинные. Да и сами строки также яркий пример динамической структуры данных с замаскированным указателем.

[challengerr]

1. Стек реализован на уровне операционной системы, поэтому все программы в операционной системе используют стек. Стек имеет два методы: push - поместить значение на вершину стека, pop - вытолкнуть значение с вершины стека. Каждая программа в операционной системе использует метод push для помещения аргументов функции на вершину стека и метод pop для выталкивания аргументов с вершины стека. Для хранения стека вызовов функций 32-разрядной операционной системы предусмотрены регистры процессора ESP и ESI. В 16 разрядной операционной системе используются регистры процессора SP и SI.

2. На уровне операционной системы все программы существующие в операционной системе управляются с помощью очереди сообщений, реализованной на уровне операционной системы. Это обеспечивает многозадачность операционной системы. В программах в операционной системе Windows для получения и обработки сообщений предусмотрена функция обратного вызова(callback), которая получает от операционной системы сообщения.

3. Списки применяются для хранения списка процессов в операционной системы, а также для хранения списка потоков. Перечисление окон в оконной операционной системы осуществляется с использованием списка.

Подробное описание архитектуры процессора содержится в книге Кнута "Искусство программирование". Кнут рассматривает архитектуру компьютера MIX. Только книга Кнута будет для вас, наверное, непонятная, так как она не рассчитана на краткосрочное освоение. Чтобы разобраться в какой-то книге Кнута, потребуется очень много времени и очень хорошая математическая подготовка.

Распределение процессорного времени в операционной системе реализовано с использованием очереди процессов на использование центрального процессора (CPU).

Действительно, могут возникнуть трудности с определением типа структуры даже у подготовленного программиста, особенно, если функции имеют нестандартные или очень короткие имена. Опознание типа структуры может производится по именам функций и по типам данным элемента структуры. Задача определения типа структуры может быть неразрешимой, например, в случае макроподстановок. Потребуется писать на языке программирования специальный инструмент для раскручивания макросов, который позволит получить читаемый код.

Элемент однонаправленного списка содержит ссылку на такой же элемент.

Стандартного способа анализа кода НЕТ. Задача обратного проектирования алгоритма и определения типа структур может быть очень сложной.

Для анализа кода используются блок-схемы. Описание блок-схем содержится в государственных стандартах и международных стандартах типа ISO.

Кроме этого, для анализа современных программных систем потребуется строить UML диаграммы, которые содержат имена классов и связи между ними.

Очереди бывают типа LIFO и типа FIFO. От списка отличаются тем, что производится выталкивание элементов списка либо с начала, либо с конца. В случае LIFO выталкивается последний элемент, тогда очередь можно перепутать со стеком, так как в стеке тоже выталкивается последний элемент. В случае FIFO выталкивается первый элемент.

Сортировки могут применяться не только на массивы. Методы сортировки применимы и на списки, и на очереди и на другие структуры данных.

Количество символов сообщения конечное...

[Stilet]

Стек реализован на уровне операционной системы, поэтому все программы в операционной системе используют стек.

Это не правда.

Каждая программа в операционной системе использует метод push для помещения аргументов функции на вершину стека и метод pop для выталкивания аргументов с вершины стека.

Это не относится к операционной системе.

На уровне операционной системы все программы существующие в операционной системе управляются с помощью очереди сообщений

Это ложь. Даже в виндовсе такие программы не все даже в кольце пользователя.

В программах в операционной системе Windows для получения и обработки сообщений предусмотрена функция обратного вызова(callback), которая получает от операционной системы сообщения.

Чего?? О_о. Покажи эту функцию.

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

Чего???

Элемент однонаправленного списка содержит ссылку на такой же элемент.

А это что за выдумки? Кто сказал что элементы списка обязательно однотипные?

для анализа современных программных систем потребуется строить UML диаграммы

Охоспдя... А это тут при чем??

Пфффф... Долго придется переваривать то, что я сейчас прочел...

[GreenWizard]

1) как в коде программы понять какие используются структуры данных (особенно касается однонаправленного списка, очереди, стека);

либо по именам, как сказал Уткин, либо по специфике (например, запись A.pop() - в 90% случаях А является стеком)

2) сортировки различного вида применимы на какие-то конкретные данные или нет(напр. метод Шелла - только на массиве или нет)?;

по сути, 90% изучаемых алгоритмов - универсальны и могут быть перенесены на любые общепринятые структуры данных, НО они могут стать при этом неэффективными или же нарушать логику структуры данных, поэтому и не используются

3) что такое (перемешенные) таблицы?;

скорее всего, не перемешенные, а разряженные (хеш-таблицы)... если кратко, то, например, нам нужно связать ФИО с номером неким... варианты решения:
- массив номер-фио.... если номера идут не подряд, а в разброс, то, имея всего 2 человека, нам может потребоваться массив на 4 миллиарда элементов т. к. у одного номер 0, у второго - 4,000,000,000.... 3,999,999,998 ячеек массива будут пусты, но занимать память... эффективность такого решения близка к 0
кроме того, поиск по ФИО, который нам важен, потребует очень много времени (данные не упорядоченны и бин. поиск не прокатит)
- односвязный список.... тут у нас 2 человека будут всегда требовать списка на 2 элемента и это почти эффективное решение, НО вот у нас стало 1,000,000,000 записей и нам, чтоб получить последний элемент списка, потребуется перебрать их все... если принять время перехода за 0,01мс, то 1,000,000,000 переходов займут 10000 секунд (2.5 часа!), что, опять же, не эффективно даже в этом плане, а уж поиск по ФИО вовсе будет оооочень долгий, а ведь именно он более востребован
- хеш-таблица.... тот же массив, но с функцией, которая, грубо говоря, превращает ФИО в индекс массива, ещё и "уплотняя его" т. е. для 2 человек - оно выдаст, скажем, индексы 5 и 1 (массив от 0 до 5), для 20 - индексы от 0 до 30, для 1,000,000,000 - 1,200,000,000 элементов, что хуже чем у списка, НО у нас ФИО сразу превращается в индекс (ну, пусть за 10 мс, что ооооочень долго), поэтому поиск любого ФИО потребует не нескольких часов, а менее 1 секунды... мы немного перерасходуем память, но получаем возможность быстро находить записи по ФИО (теряя в скорости добавления новых данных, но это можно сделать в фоне, скажем, что уже совсем др. тема..... и то, теряем лишь при нехватке места т. е. при заполнении 99% массива, что очень здорово)
это лишь очень грубый пример с числами "от фонаря", поэтому читаем книги, особенно смотрим на О-нотации каждой операции

Очень мне поможете, если объясните или на хорошую, понятную литературу ссылку укажете.

Бакнелл Джулиан - "Фундаментальные алгоритмы и структуры данных в Delphi"
хоть и Delphi, но именно об алгоритмах и структурах.

[challengerr]

Это не правда.

Стек реализован на уровне операционной системы, поэтому все программы в операционной системе используют стек. Это правда.
У центрального процессора (CPU) есть регистр ESP.
Каждая программа использует stack pointer (SP), так как операционная система вызывает функцию WinMain или main или _tmain или другую обертку для main, то есть точку входа (entry point) в программу.
И помещает адрес вызова в стек.
Так как каждая программа возвращает управление той программе, которой была вызвана, а программу в операционной системе вызывает ядро.
И передачу управления от функции к функции тоже осуществляет операционная система, так как ядро операционной системы контролирует распределение процессорного времени между процессами. Если используется ассемблерный call, то передачу управления осуществляет ntdll.dll.

Передачу управления от функции к функции в программе осуществляет операционная система, конкретно ядро операционной системы ntoskrnl.exe и ntdll.dll. Управление стеком осуществляет операционная система.

Это не относится к операционной системе.

Это относится к операционной системе, так как аппаратным обеспечением компьютера в операционной системе управляет сама операционная система.

Это ложь. Даже в виндовсе такие программы не все даже в кольце пользователя.

Нет, это не ложь. Так как есть IPC ядра (kernel IPC).
IPC - InterProcess Communication
Про IPC в linux
Linux Kernel 2.4 Internals: IPC mechanisms (This chapter describes the semaphore, shared memory, and message queue IPC mechanisms as implemented in the Linux 2.4 kernel). www.tldp.org/LDP/lki/lki-5.html
Ядро linux 2.4. Эта глава описывает семафоры, общую память и очередь сообщений как механизм IPC, реализованный в ядре linux www.tldp.org/LDP/lki/lki-5.html

Windows Driver IPC API (RTKAPI) Overview http://www.intervalzero.com/library/...I_Overview.htm
Windows IPC - CodeProject http://www.codeproject.com/Articles/13724/Windows-IPC

Improving IPC by kernel design - PDOS pdos.csail.mit.edu/6.097/readings/liedtke-ipc.ps

[Stilet]

Передачу управления от функции к функции в программе осуществляет операционная система

Супердовод... А теперь почитай про оператор CALL процессора. А потом скажи где там речь о управлении из-под ОС.
и еще так: По твоим словам без ОС оператор вызова функции работать не будет. Ты в этом уверен?

Это относится к операционной системе, так как аппаратным обеспечением компьютера в операционной системе управляет сама операционная система.

А вот это очень сильно.
Что ж. Кэп, ты победил. Я отстраняюсь, ибо больше ржать не в силах...

[GreenWizard]

Stilet, НО НО! ты это, от святила науки руки убери! он нас, деревенских, тут просвящает, а ты ему ещё дерзишь... не порядок!
Уважаемый, а меня вот всё терзает вопрос: пиксели зажигают, как и свет в холодильнике, пингвины или иные создания? Вы ж святило, вам виднее!

[Stilet]

а ты ему ещё дерзишь... не порядок!

Да ты че? На кого батон крошишь?? Я поражение признал чэстно!!! Пощади-и-и-и-те!!!! А-а-а-а!!!!

[GreenWizard]

Сообщение от Stilet

Да ты че? На кого батон крошишь?? Я поражение признал чэстно!!! Пощади-и-и-и-те!!!! А-а-а-а!!!!

То-то же, таки умом своим он поразил нас вновь, а спорить с ним - удел других святил, мы пока не так начитаны
P. s. кончаем флуд challengerr - красава и пример для меня! это же какая огромная и непоколебимая вера в себя, в свою правоту и знания! как говорится, медицина тут бессильна)