Дана задача.
Разработайте библиотеку
функций для выполнения операций со структурой
данных в форме кольцевого списка. Необходимо предусмотреть функции
добавления элемента в список и удаления элемента.
необходимо написать алгоритм на языке с/с++. вообще не понимаю алгоритмы этих структур данных. если можно, с объяснением.
Другие языки программирования и технологии
с++.
Шахрух Хасанбаев
143
Понимаешь, это работа программиста такова, что делаешь новую прогу, то приходится изучать термины, определения, понятия которыми оперирует программа или область деятельности куда эту прогу внедряют.
Потому по сути программист и должен знать все и разбираться во всем.
Извини, что не помог, но лучше меня инет поможет и может даже готовое там есть.
Потому по сути программист и должен знать все и разбираться во всем.
Извини, что не помог, но лучше меня инет поможет и может даже готовое там есть.
Антон, что такое "связный список"? Это набор данных, где у каждого элемента есть ссылка на следующий, а у последнего в этой ссылке пусто, например 0. Если есть также ссылка на предыдущий, то это "двусвязный" список. Если у последнего элемента ссылка на 1-й элемент, как на следующий, то это "кольцевой список", а в 2-связном кольцевом списке: у 1-го элемента еще ссылка на последний, как предыдущий.
Допустим, у нас 2-связный список объектов, самый простой случай. У каждого объекта A есть A.Next и A.Prev: ссылки на следующий и предыдущий.
Чтоб удалить объект A, надо просто переписать ссылки:
A.Next.Prev=A.Prev
A.Prev.Next=A.Next
И всио! Потом можно убить объект A.
При добавлении нового объекта A, после B, обратный процесс:
A.Next=B.Next
A.Next.Prev=A
B.Next=A
A.Prev=B
Если список 1-связный, то есть только ссылка на след., а предыдущий надо искать в цикле, от текущего A по ссылкам: искать такой AP, что AP.Next=A. Дальше все аналогично.
Можно также реализовать в виде массива записей, где в каждой записи есть индексы предыдущего и следующего: A[i].Next и A[i].Prev. Или только A[i].Next, для 1-связного. Все делается аналогично, только пишутся индексы, вместо ссылок.
Но для массива, надо в каждом A[i] иметь поле A[i].Deleted, писать в него true при удалении. А при добавлении, надо искать в массиве удаленный элемент, с A[i].Deleted=true, и писать новый элемент туда. А если нет удаленных, то добавлять в конец массива.
На самом деле, там ничего сложного. Просто нарисуйте на бумажке: несколько элементов, и стрелочки от Next и Prev, к другим элементам. И посмотрите: как эти стрелочки переставить, для удаления и добавления/
Допустим, у нас 2-связный список объектов, самый простой случай. У каждого объекта A есть A.Next и A.Prev: ссылки на следующий и предыдущий.
Чтоб удалить объект A, надо просто переписать ссылки:
A.Next.Prev=A.Prev
A.Prev.Next=A.Next
И всио! Потом можно убить объект A.
При добавлении нового объекта A, после B, обратный процесс:
A.Next=B.Next
A.Next.Prev=A
B.Next=A
A.Prev=B
Если список 1-связный, то есть только ссылка на след., а предыдущий надо искать в цикле, от текущего A по ссылкам: искать такой AP, что AP.Next=A. Дальше все аналогично.
Можно также реализовать в виде массива записей, где в каждой записи есть индексы предыдущего и следующего: A[i].Next и A[i].Prev. Или только A[i].Next, для 1-связного. Все делается аналогично, только пишутся индексы, вместо ссылок.
Но для массива, надо в каждом A[i] иметь поле A[i].Deleted, писать в него true при удалении. А при добавлении, надо искать в массиве удаленный элемент, с A[i].Deleted=true, и писать новый элемент туда. А если нет удаленных, то добавлять в конец массива.
На самом деле, там ничего сложного. Просто нарисуйте на бумажке: несколько элементов, и стрелочки от Next и Prev, к другим элементам. И посмотрите: как эти стрелочки переставить, для удаления и добавления/
Евгений Стратонов
48 987