![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
||||||||||||
1 | ||||||||||||
Динамические структуры данных (списки, очереди, стеки, деревья)21.12.2009, 04:41. Показов 222085. Ответов 8
Метки двунаправленный список, Дек, деревья, динамика, динамические структуры, кольцевой список, кольцевые списки, однонаправленны список, односвязный список, Очередь, списки, стек (Все метки)
Решил я начать писать мини FAQ по моим любимым Динамическим структурам данных.
Все программы я пишу на Turbo Pascal 7.0 версии, не проверяю их работоспособности на разновидностях компиляторов под Pascal, прошу принять это во внимание. И начну я своё повествование со стеков. И так, что же такое стек? По своей сути это структура, где мы не можем обратиться к элементу стоящему "ниже" вершины, если мы не "сняли" вершину. Но я решил писать программу так, как будто у нас "видно" весь стек и мы можем просматривать любой элемент в любое время (если будет не понятен этот момент, пишите в теме, я расскажу подробнее что поменяется тогда). Я тут набросал программу, демонстрирующую работу со стеком, опишу процедуры и функции для ясности: 1) procedure AddElem(var stek1:List;znach1:TInf) - процедура добавление элемента в стек. 2) procedure Print(stek1:List) - вывод стека. 3) Procedure FreeStek(stek1:List) - освобождение памяти использованного под стек. 4) Function SearchElemZnach(stek1:List;znach1:TInf):List - поиск в стеке по значению, функция возвращает адрес найденного элемента. 5) Procedure DelElem(var stek1:List;tmp:List) - процедура удаления из стека элемента с адресом tmp. 6) procedure DelElemZnach(var Stek1:List;znach1:TInf) - удаление из стека элемента со значением znach1. 7) Procedure DelElemPos(var stek1:List;posi:integer) - удаление из стека элемента с порядковым номером posi. 8) procedure SortBublInf(nach:list) - сортировка стека "пузырьком" (самый простой вариант), с обменом данными между элементами. 9) procedure SortBublLink(nach:List)- сортировка стека "пузырьком" (самый простой вариант), с изменением лишь указателей на элементы. Ну а вот и сам код проекта:
Готов выслушать критику относительно кода, материла и конечно же Ваши пожелания. (Я готов в самой этой теме дать пояснения что такое стек, списки, деревья, с картинками и моими разъяснениями, готов дописывать код, под какие-нибудь интересные задачи по работе с динамическими структурами).Все Ваши просьбы высылайте мне средствами ЛС (Личных Сообщений). З.Ы. Работа с динамическими массивами рассматриваться не будет, т.к. она идентична работе со статическими массивами, разница лишь в выделении памяти во время работы программы. З.Ы.Ы. Могу поискать информацию о том, где используются динамические структуры, хотя опять же всё есть в инете, не хочется повторяться. С нетерпением жду ответов.
50
|
21.12.2009, 04:41 | |
21.12.2009, 04:41 | |
Ответы с готовыми решениями:
8
Динамические структуры данных (списки, очереди, стеки, деревья)
Динамические списки, стеки, очереди |
![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
||||||||||||
22.12.2009, 03:21 [ТС] | 2 | |||||||||||
В дальнейшем прошу не спрашивать в этой теме вопросы, не относящиеся к теме "Динамически структуры данных". На вопрос отвечу просто, т.к. для данной задачи (построить меню и организовать с ним работу) считаю что структура case подходить лучше всего.
И так, а теперь по делу. Рассмотрим работу со связным списком... Для начала разберёмся что же это такое: Википедия ссылка 1 Википедия ссылка 2 Это очень удобная структура, при помощи неё можно работать с Хеш таблицами, разряженными матрицами, да в общем то применений можно найти много, я очень уважаю списки, т.к. если правильно организовать с ними работу, то это просто приятно. Опять же не буду много говорить, если что-то Вам не понятно, то спрашивайте, перейду сразу к программе реализованной мной, для работы со списками, пройдёмся по процедурам: 1) procedure AddElem(var spis1:List;znach1:TInf); 2) procedure Print(spis1:List); 3) Procedure FreeStek(spis1:List); 4) Function SearchElemZnach(spis1:List;znach1:TInf):List; 5) Procedure DelElem(var spis1:List;tmp:List); 6) procedure DelElemZnach(var Spis1:List;znach1:TInf); 7) Procedure DelElemPos(var spis1:List;posi:integer); 8) procedure SortBublInf(nach:list); 9) procedure SortBublLink(nach:List); Все действия у этих процедур и функций аналогичны тем, которые я описывал для работы со стеком, ведь по сути разница между этими структурами, лишь в методе доступа к ним и добавлении элементов. (в стеке добавляется на вершину, т.е. перед "первым" элементом, а в списке после последнего элемента). Вот и сам код:
28
|
![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|||||||||||||||||
24.12.2009, 01:54 [ТС] | 3 | ||||||||||||||||
В принципе ничего сложного, для начала я расскажу про двунаправленные списки, и если сегодня успею, то напишу процедуру для построения списка "вставками".Это будет отдельная процедура, которая может вызываться вместо той, которая будет описана мною ниже.
Приступим... Что такое списки мы разобрали выше, материал для изучения не изменился, хотелось бы только оговорить, что следует никогда не забывать "занулять" указатели у элементов - т.к. это очень критично (многие циклы строятся на основе
1) procedure AddElem(var nach,ends:List;znach1:TInf); 2) procedure Print(spis1:List); 3) Procedure FreeStek(spis1:List); 4) Function SearchElemZnach(spis1:List;znach1:TInf):List; 5) Procedure DelElem(var spis1,spis2:List;tmp:List); 6) procedure DelElemZnach(var Spis1,spis2:List;znach1:TInf); 7) Procedure DelElemPos(var spis1,spis2:List;posi:integer); 8) procedure SortBublInf(nach:list); 9) procedure SortBublLink(var nach,ends:List); 10) Procedure Swap(var nach,ends:List;a,b,c:integer); - Берёт часть списка и вставляет в нужную позиицию 11) procedure AddElemVst(var nach,ends:List;znach1:TInf); - Процедура добавления нового элемента в двунаправленный список методом "вставок" Все процедуры и функции выполняют те же роли что и в предыдущих сообщениях, их описание есть в первом сообщении темы. Ну и непосредственно сам код:
17
|
![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
29.12.2009, 01:28 [ТС] | 4 |
![]() Пока отойдём от каких-либо структур. Для начала вспомним массивы. Все мы представляем массивы для себя по-разному, чаще всего, если массив одномерный, в виде строки элементов, если двумерный, в виде матрицы, если трёхмерный - в виде куба. Я уже начинал говорить про этот вопрос: И понимаю что следует раскрыть ответ. Самое важное для чего Вы используете очередь, если это какая-то банковская программа и очередь у Вас реализована через класс, то конечно же ни в коем случае не следует писать метод (так называются функции и процедуры у классов) который выводил бы нам всю очередь. Так как я пишу программы для ознакомления со структурами, то я отхожу от некоторых принципов и реализую процедуры сортировки (с изменением данных, адресов), вывода данных (Print) - которые немного "искривляют" принципы доступа в той или иной структуре. Но я всегда придерживаюсь концепции структуры, т.е. если я пишу про стек, то элементы добавляются именно так, как это следует делать в стеке, если очередь, то так, как следует это делать для очереди, если бинарные деревья, то так, как это следует делать для них... Вопрос как бы с подвохом. Когда я раньше ещё сдавал программы по "Динамическим структурам данных" преподавателям, то спрашивал у них, а для чего в задании про стеки написано: "Написать процедуру вывода стека?Ведь это означает, что мне придётся: "Брать элемент начиная с вершины, выводить его значение и удалять" - и так сделать пока не будет виден весь стек!" - на что получал вполне ясный ответ:"Мы изучаем структуры, выполняйте задание.". Т. к. я хочу иметь чистую совесть, то я представляю себе стек, как прозрачную колбу, в которую закидываются элементы и,если мы начнём смотреть через колбу с верхнего элемента, двигаясь вниз, то мы просмотрим все элементы, не вытягивая их из колбы. Очередь я представляю как живую очередь в магазине, ведь "наблюдатель" (указатель) всегда сможет пройтись с самого конца очереди в самое начало заглянув в каждого человека (элемент). Из всего вышесказанного мной, следует: - Т.к. программы пишутся исключительно для ознакомления со структурами, то способ доступа к структуре расширяется, т.е. мы оставляем основу (LIFO, FIFO...), но разрешаем и просмотр элементов, обращение к любого элементу с целью его "перестановки" с другим элементом.
16
|
![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
||||||||||||
07.01.2010, 19:52 [ТС] | 5 | |||||||||||
Приступим к работе с кольцевыми списками.
И так, прочитав информацию на Википедии из предыдущих сообщений Вы уже имеете представление о том что такое список, почитайте ещё вот эту статейку ссылка на Википедию. Хотелось бы сказать про небольшую особенность, т.к. у нас последний элемент указывает на первый - это означает, что все бывшие циклы, которые работают до nil, теперь приходится делать пока не встретится первый элемент. А теперь пройдёмся по процедурам/функциям реализованными мной: 1) procedure AddElem(var nach,ends:List;znach1:TInf); 2) procedure Print(spis1:List); 3) Procedure FreeStek(spis1:List); 4) Function SearchElemZnach(spis1:List;znach1:TInf):List; 5) Procedure DelElem(var spis1,spis2:List;tmp:List); 6) procedure DelElemZnach(var Spis1,spis2:List;znach1:TInf); 7) Procedure DelElemPos(var spis1,spis2:List;posi:integer); 8) procedure SortBublInf(nach:list); Описания действия выполняемыми процедурами/функциями описаны выше, в предыдущих постах. Вот и сам код:
16
|
![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
||||||||||||
16.01.2010, 12:23 [ТС] | 6 | |||||||||||
Приступим к работе с очередью.
Работа с очередями похожа на работу со стеком, только лишь изменится способ удаления элементов. И так, прочитав информацию на Википедии из предыдущих сообщений Вы уже имеете представление о том что такое стек, почитайте ещё вот эту статейку ссылка на Википедию. Очередь строится также как и стек. Каждый элемент "видит" предшествующий ему элемент. А теперь пройдёмся по процедурам и функция реализованными мной: 1) procedure AddElem(var nach,ends:List;znach1:TInf); 2) procedure Print(spis1:List); 3) Procedure FreeStek(spis1:List); 4) Function SearchElemZnach(spis1:List;znach1:TInf):List; 5) Procedure DelElem(var spis1,spis2:List;tmp:List); 6) procedure DelElemZnach(var Spis1,spis2:List;znach1:TInf); 7) Procedure DelElemPos(var spis1,spis2:List;posi:integer); 8) procedure SortBublInf(nach:list); 9) procedure SortBublLink(var nach,ends:List); Описания действия выполняемыми процедурами/функциями описаны выше, в предыдущих постах. Вот и сам код:
18
|
![]() 3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
||||||
02.06.2010, 00:43 [ТС] | 7 | |||||
И вот пришло время добавить работу с деревьями.
Код любезно предоставлен пользователем lera8 (ссылка на страницу пользователя lera8) Начнём с того, что же такое дерево. И как ни странно все Вы имеете представление о том, что такое дерево: давайте представим себе генеалогическое дерево (все знаю, что это такое), так вот деревья в программировании имеет по своей сути очень и очень схожее строение: есть какой-то корень (обычно он располагается в самом верху, т.е. дерево "растёт" вниз) и у него есть потомки, а у тех потомков свои потомки и т.д. В нашем случае рассматривается так называемое "Двоичное дерево поиска", ссылка на Википедию. Вы спросите почему? А потому, что оно очень часто используется для решения очень широкого круга задач, чаще всего для поиска и сортировки (при больших объёмах сортируемой информации, очень даже неплохие результаты показывает). И так, опишем функции, которые реализованы: 1)procedure AddToTree (var Tree:PNode;x:integer); - добавление элемента в дерево 2)function Search(Tree:PNode;x:integer):PNode; - функция поиска в дереве 3)procedure Lkp(Tree:PNode); - обход дерева по принципу "Левле поддерево, корень, правое поддерево" 4)procedure DeleteTree(var Tree1:PNode ) - процедура удаления дерева А вот и сам код:
19
|
![]() 300 / 76 / 6
Регистрация: 23.11.2009
Сообщений: 25
|
||||||
19.08.2010, 16:52 | 8 | |||||
Задание :
На основе процедуры обхода дерева снизу вверх реализовать операцию поиска узла с заданным значением в дереве, не являющемся деревом поиска. Из двух последовательностей символов построить два бинарных дерева минимальной высоты. В первом дереве найти элемент с заданным значением и подключить второе дерево в качестве его левого поддерева, если оно пусто, или левого поддерева первого из его крайних левых потомков, имеющих пустое левое поддерево. Добавлено через 1 минуту Программа на pascal:
Выложила программу, написала сама, может кому-нибудь понадобится. Там много хороших процедур, за ними часто обращаются в разделе.
13
|
58 / 51 / 0
Регистрация: 25.08.2010
Сообщений: 43
|
||||||||||||||||||||||||||
27.10.2010, 22:31 | 9 | |||||||||||||||||||||||||
Постановка задачи
Реализовать хранилище стеков, с операциями добавления, поиска, удаления стеков, а так же со всеми стандартными операциями внутри отдельного стека. Среда программирования Turbo Pascal 7.1. Ход решения 1.Реализовать стек в ООП со всеми стандартными операциями: добавление элемента, взятие вершины, проверки на пустоту и заполнение, вывод содержимого стека на экран. 2.Реализовать список, в каждом узле которого содержится стек. 3.В основной программе реализовать меню, для удобства работы. Стек Структура данных – это множество элементов данных и связей между ними. Они разделяются на статические и динамические. Статические формируются в памяти одномоментно до начала работы со структурами и во время своего существования не меняют свои размеры и место положения в памяти. Примерами являются массивы и записи. Динамические структуры данных могут менять свои размеры и расположение, их состав может постоянно меняться в ходе работы с программой. Они в свою очередь делятся на линейные (списки, стеки, очереди) и нелинейные (деревья, графы). В линейных структурах элементы идут один за другим, в нелинейных – возможно ветвление. Рассмотрим подробнее линейные структуры данных, а именно списки. Списки бывают односвязными, двусвязными, циклическими. В каждом элементе односвязного списка содержится указатель на следующий элемент, двусвязного – на следующий и предыдущий, в циклическом последний элемент содержит указатель на первый. В списке в любой момент времени можно обратиться к любому его элементу. Для ряда задач произвольность доступа является недопустимой, для этого введено понятие дисциплины обработки данных (стек, очередь, дек). Дисциплина определяет к какому элементу и каким образом пользователь может обратиться в данный момент времени. Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю. Стек – это дисциплина обработки данных, имеющая линейную структуру, доступ в которой разрешается только к последнему добавленному элементу( вершине стека). Стек работает по принципу LIFO (Last In, First Out. Последний вошёл, первый вышел ). Простым примером использования стека может послужить ситуация, когда мы просматриваем множество данных и составляем список особых данных, которые должны обрабатываться позднее. Когда первоначальное множество обработано, мы возвращаемся к этому списку и выполняем обработку, удаляя элементы, пока наш список не станет пустым. Например, рекурсивные функции, пока не обработан последний вызов, все предыдущие вызовы находятся в своеобразном стеке. Стек активно используется в архитектуре компьютера, в ней преобладает стековая адресация. Рассмотрим основные функции обработки стека: Push – добавление в вершину стека, в процедуру передаётся добавляемое значение. Pop – взятие элемента из вершины стека, возвращает содержимое вершины IsEmpty – проверка на пустоту, возвращает True или False. IsFull – проверка на заполнение, максимальное число элементов в стеке определяет константа MaxStack, возвращает True или False. Top – указатель на вершину стека Рассмотрим структуру узла стека:
Value – значение узла стека ( data = Integer; указывает, что стек числовой) Prev – указатель на предыдущий элемент. Для реализации хранилища стеков использован односвязный список с указателем на начало и конец. Рассмотрим узел списка:
Stack – непосредственно стек, описанный как объект в модуле UStack. Next – указатель на следующий элемент списка. Рассмотрим функции обработки данного списка: AddNode – добавление узла, в процедуру передаётся имя нового стека. DelNode – удаление узла, в процедуру передаётся указатель на удаляемый узел Find – поиск стека, возвращает указатель на узел ChangeStack – процедура обработки отдельного стека, в процедуру передаётся указатель на узел с обрабатываемым стеком. Процедура ChangeStack вызывает соответствующие процедуры обработки стека из модуля со стеком, посредством активного меню. Процедура Find выводит все стеки, поиск осуществляется посредством активного меню, которое организованно следующим образом: считается количество стеков, далее с нажатием клавиш вверх и вниз, на экране передвигается стрелка, изменяется значение переменной m, которая указывает на порядковый номер стека в списке. Затем снова отсчитывается стек с порядковым номером m и возвращается указатель на него. После добавлений и удалений стеков, которые происходит в основной программе, список изменяется. Остальные функции обработки стеков и списка реализованы по стандартным алгоритмам. Как работать с программой (этот пунк мы опустим) !!!!! Программа написана в Turbo Pascal 7.1, чтобы подключить модули, нужно скопировать файлы UList.TPU и UStack.TPU в директорию компилятора BIN\. Код программы. Модуль «Стек»
Модуль «Список стеков»
В ходе работы были закреплены навыки работы с модулями, с динамическими структурами данных в объектно ориентированном программировании. Была написана программа для работы со стеками с интуитивно понятным для пользователя интерфейсом. Не по теме: зы Это оригинальный текст написанный группой программистов для сдачи зачета( xDDD ),и впервые публикуется тут cyberforum.ru (28.10.10)
41
|
27.10.2010, 22:31 | |
27.10.2010, 22:31 | |
Помогаю со студенческими работами здесь
9
Динамические структуры данных: списки
Стеки, списки, деревья, графы. Динамические структуры данных. Линейные списки Динамические структуры данных. Простые списки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
![]() |
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Почему могут не шифроваться русские символы в Java
Wired 17.02.2025
При разработке на Java нередко возникают сложности с шифрованием русских символов. Эта проблема особенно актуальна для разработчиков, создающих программное обеспечение для русскоязычной аудитории. . . .
|
Отличия ОС для x86_64 и ARM
Wired 17.02.2025
На данный момент сосуществуют две основные архитектуры процессоров - x86_64 и ARM. Эти архитектуры имеют принципиально разные подходы к организации вычислений и обработке данных, что накладывает. . .
|
Многопоточность в Python: как использовать Thread
bytestream 17.02.2025
Поток выполнения (thread) - это наименьшая последовательность инструкций, которая может управляться планировщиком операционной системы. Представьте себе, что ваша программа - это книга, а потоки -. . .
|
Как воспроизвести Race Condition в Python
bytestream 17.02.2025
В многопоточном программировании существует множество подводных камней, и одним из самых коварных является состояние гонки (Race Condition). Этот термин описывает ситуацию, когда результат выполнения. . .
|
Ошибка "node: --openssl-legacy-provider is not allowed in NODE_OPTIONS"
bytestream 17.02.2025
Каждый разработчик рано или поздно сталкивается с ситуацией, когда при запуске проекта Node. js неожиданно выскакивает ошибка "node: --openssl-legacy-provider is not allowed in NODE_OPTIONS". Это. . .
|
Ошибка pip Python "AttributeError: module 'lib' has no attribute 'OpenSSL_add_all_algorithms'"
bytestream 17.02.2025
При разработке на Python частенько сталкиваешься с разными сюрпризами, но ошибка AttributeError: module 'lib' has no attribute 'OpenSSL_add_all_algorithms' - это что-то особенное. Знаете, это как. . .
|
Сообщение Play Store "You must complete the advertising ID declaration before you can release an app that targets"
bytestream 17.02.2025
Рекламный идентификатор - это уникальный, но восстанавливаемый строковый идентификатор для каждого устройства Android. Думаю, вы удивитесь, но даже если ваше приложение не показывает рекламу. . .
|
Отличия App Router от Pages Router в Next.js
bytestream 17.02.2025
Next. js прошел длинный путь развития, и одним из самых значительных изменений стало появление App Router - революционного подхода к организации маршрутизации в приложении. Этот новый способ пришел на. . .
|
Топ10 лучших фреймворков JavaScript для изучения в 2025
bytestream 16.02.2025
В современной веб-разработке JavaScript занимает особое место, являясь одним из наиболее востребованных языков программирования. По мере развития веб-технологий появляется все больше фреймворков,. . .
|
Temporal в JavaScript - новый формат даты и времени
bytestream 16.02.2025
В мире JavaScript скоро произойдет значимое событие - появление нового встроенного объекта Temporal, который призван полностью заменить устаревший объект Date. Это революционное изменение в работе с. . .
|