Динамические структуры данных: списки

Замабувараев Вс Май 25, 2014 8:17 pm

Предлагаю свою реализацию списков.
Lists.bi

Код:: NameSpace Lists ' Узел Type Node ' Данные Dim p As Object Ptr ' Указатель на левый и правый элементы Dim NextNode As Node Ptr Dim PreviousNode As Node Ptr End Type ' Базовый класс итератора Type IteratorBase Extends Object Protected: ' Указатель текущий узел Dim m_CurrentNode As Node Ptr Public: ' Увеличение индекса Declare Abstract Sub Increment() ' Уменьшение индекса Declare Abstract Sub Decrement() ' Текущий элемент Declare Abstract Property Item()As Object Ptr Declare Abstract Property Item(ByVal Value As Object Ptr) End Type ' Итератор стэка ' Поддерживает только инкрементацию Type StackIterator Extends IteratorBase Public: Declare Constructor(ByVal Value As Node Ptr) ' Увеличение индекса Declare Sub Increment() ' Уменьшение индекса Declare Sub Decrement() ' Текущий элемент Declare Property Item()As Object Ptr Declare Property Item(ByVal Value As Object Ptr) End Type ' Итератор очереди ' Поддерживает только инкрементацию Type QueueIterator Extends IteratorBase Public: Declare Constructor(ByVal Value As Node Ptr) ' Увеличение индекса Declare Sub Increment() ' Уменьшение индекса Declare Sub Decrement() ' Текущий элемент Declare Property Item()As Object Ptr Declare Property Item(ByVal Value As Object Ptr) End Type ' Итератор списка ' Двунаправленный итератор Type ListIterator Extends IteratorBase Public: Declare Constructor(ByVal Value As Node Ptr) ' Увеличение индекса Declare Sub Increment() ' Уменьшение индекса Declare Sub Decrement() ' Текущий элемент Declare Property Item()As Object Ptr Declare Property Item(ByVal Value As Object Ptr) ' Текущий узел Declare Property CurrentNode()As Node Ptr End Type ' Класс стэка Type Stack Extends Object Private: ' Вершина Dim m_TopNode As Node Ptr Public: Declare Destructor() ' Добавление в стэк Declare Sub Push(ByVal p As Object Ptr) ' Извлечение из стэка с удалением Declare Function Pop()As Object Ptr ' Получение начального и конечного элементов стэка Declare Function pBegin()As Node Ptr Declare Function pEnd()As Node Ptr End Type ' Класс очереди Type Queue Extends Object Private: ' Вершина Dim m_TopNode As Node Ptr ' Хвост Dim m_TailNode As Node Ptr Public: Declare Destructor() ' Добавление в конец очереди Declare Sub Add(ByVal p As Object Ptr) ' Извлечение из очереди первого элемента с удалением Declare Function Pop()As Object Ptr ' Итераторы очереди Declare Function pBegin()As Node Ptr Declare Function pEnd()As Node Ptr End Type ' Класс списка Type List Extends Object Private: ' Количество элементов Dim m_Count As Integer ' Вершина Dim m_TopNode As Node Ptr ' Хвост Dim m_TailNode As Node Ptr Public: Declare Destructor() ' Добавление элемента в начало Declare Sub AddBegin(ByVal p As Object Ptr) ' Добавление элемента в конец Declare Sub AddEnd(ByVal p As Object Ptr) ' Удаление элемента Declare Sub Remove(ByVal Value As ListIterator Ptr) ' Количество элементов в списке Declare Property Count()As Integer ' Элемент Declare Property Item(ByVal Index As Integer)As Object Ptr Declare Property Item(ByVal Index As Integer, ByVal Value As Object Ptr) ' Итераторы списка Declare Function pBeginForward()As Node Ptr Declare Function pEndForward()As Node Ptr Declare Function pBeginBack()As Node Ptr Declare Function pEndBack()As Node Ptr End Type End Namespace

Lists.bas

Код:: #include "Lists.bi" NameSpace Lists /' Стэк '/ Public Destructor Stack() ' Уничтожение стэка Dim objNode As Node Ptr Do While m_TopNode ' Удаление данных Delete(m_TopNode->p) ' Сохранение следующего указателя objNode = m_TopNode->NextNode ' Удаление вершины Delete(m_TopNode) ' Перемещение указателя m_TopNode = objNode Loop End Destructor ' Добавление элемента в стэк Public Sub Stack.Push(ByVal p As Object Ptr) ' Новый узел Dim objNode As Node Ptr = New Node objNode->p = p ' Если вершина пуста, то создаём If m_TopNode Then ' Левый узел — новый узел objNode->NextNode = m_TopNode m_TopNode = objNode Else ' Создаём вершину и добавяем данные m_TopNode = objNode End If End Sub ' Извлечение данных из стэка и возвращение ссылки на него ' Удалять элемент данных будет сама программа Public Function Stack.Pop()As Object Ptr If m_TopNode Then Pop = m_TopNode->p ' Перемещение указателя Dim objNode As Node Ptr = m_TopNode->NextNode Delete(m_TopNode) m_TopNode = objNode Else Return 0 End If End Function ' Получение конечного итератора Public Function Stack.pEnd()As Node Ptr Return 0 End Function ' Получение начального итератора Public Function Stack.pBegin()As Node Ptr ' Создать итератор Return m_TopNode End Function /' Итератор стэка '/ ' Конструктор итератора стэка Public Constructor StackIterator(ByVal Value As Node Ptr) ' Сохранить указатель на стэк m_CurrentNode = Value End Constructor ' Увеличение итератора стэка Sub StackIterator.Increment() If m_CurrentNode Then ' Перемещение указателя m_CurrentNode = m_CurrentNode->NextNode End If End Sub ' Уменьшение итератора стэка Public Sub StackIterator.Decrement() ' Операция не поддерживается End Sub ' Получение текущего элемента стэка Public Property StackIterator.Item()As Object Ptr If m_CurrentNode Then Return m_CurrentNode->p Else Return 0 End If End Property ' Изменение текущего элемента стэка Public Property StackIterator.Item(ByVal Value As Object Ptr) If m_CurrentNode Then m_CurrentNode->p = Value End If End Property /' Очередь '/ Public Destructor Queue() ' Уничтожение очереди Dim objNode As Node Ptr Do While m_TopNode ' Удаление данных Delete(m_TopNode->p) ' Сохранение следующего указателя objNode = m_TopNode->NextNode ' Удаление вершины Delete(m_TopNode) ' Перемещение указателя m_TopNode = objNode Loop End Destructor ' Добавление в конец очереди Public Sub Queue.Add(ByVal p As Object Ptr) ' Новый узел Dim objNode As Node Ptr = New Node objNode->p = p ' Вершина If m_TopNode Then m_TailNode->NextNode = objNode m_TailNode = objNode Else ' Очередь пуста, создаём вершину и хвост m_TopNode = objNode m_TailNode = objNode End If End Sub ' Извлечение из очереди (из начала) Public Function Queue.Pop()As Object Ptr If m_TopNode Then Pop = m_TopNode->p ' Перемещение указателя Dim objNode As Node Ptr = m_TopNode->NextNode Delete(m_TopNode) m_TopNode = objNode Else Return 0 End If End Function ' Получение конечного итератора Public Function Queue.pEnd()As Node Ptr Return 0 End Function ' Получение начального итератора Public Function Queue.pBegin()As Node Ptr ' Создать итератор Return m_TopNode End Function /' Итератор очереди '/ ' Конструктор итератора очереди Public Constructor QueueIterator(ByVal Value As Node Ptr) ' Сохранить указатель на очередь m_CurrentNode = Value End Constructor ' Увеличение итератора очереди Sub QueueIterator.Increment() If m_CurrentNode Then ' Перемещение указателя m_CurrentNode = m_CurrentNode->NextNode End If End Sub ' Уменьшение итератора очереди Public Sub QueueIterator.Decrement() ' Операция не поддерживается End Sub ' Получение текущего элемента очереди Public Property QueueIterator.Item()As Object Ptr If m_CurrentNode Then Return m_CurrentNode->p Else Return 0 End If End Property ' Изменение текущего элемента очереди Public Property QueueIterator.Item(ByVal Value As Object Ptr) If m_CurrentNode Then m_CurrentNode->p = Value End If End Property /' Список '/ Public Destructor List() ' Уничтожение очереди Dim objNode As Node Ptr Do While m_TopNode ' Удаление данных Delete(m_TopNode->p) ' Сохранение следующего указателя objNode = m_TopNode->NextNode ' Удаление вершины Delete(m_TopNode) ' Перемещение указателя m_TopNode = objNode Loop End Destructor ' Добавление элемента в начало Public Sub List.AddBegin(ByVal p As Object Ptr) ' Новый узел Dim objNode As Node Ptr = New Node objNode->p = p ' Вершина If m_TopNode Then objNode->NextNode = m_TopNode m_TopNode->PreviousNode = objNode m_TopNode = objNode Else ' Список пуст, создаём вершину и хвост m_TopNode = objNode m_TailNode = objNode End If m_Count += 1 End Sub ' Добавление элемента в конец Public Sub List.AddEnd(ByVal p As Object Ptr) ' Новый узел Dim objNode As Node Ptr = New Node objNode->p = p ' Вершина If m_TopNode Then objNode->PreviousNode = m_TailNode m_TailNode->NextNode = objNode m_TailNode = objNode Else ' Список пуст, создаём вершину и хвост m_TopNode = objNode m_TailNode = objNode End If m_Count += 1 End Sub ' Удаление текущего элемента Public Sub List.Remove(ByVal Value As ListIterator Ptr) Dim objNode As Node Ptr = Value->CurrentNode If objNode Then If objNode->NextNode Then objNode->NextNode->PreviousNode = objNode->PreviousNode End If If objNode->PreviousNode Then objNode->PreviousNode->NextNode = objNode->NextNode End If Delete(objNode->p) Delete(objNode) m_Count -= 1 End If End Sub ' Количество элементов в списке Public Property List.Count()As Integer Return m_Count End Property ' Возвращаем элемент в списке Public Property List.Item(ByVal Index As Integer)As Object Ptr If m_TopNode Then If Index < m_Count Then Dim objNode As Node Ptr = m_TopNode For i As Integer = 0 To Index - 1 objNode = objNode->NextNode Next i Return objNode->p Else Return 0 End If Else Return 0 End If End Property ' Устанавливаем элемент в списке Public Property List.Item(ByVal Index As Integer, ByVal Value As Object Ptr) If m_TopNode Then If Index < m_Count Then Dim objNode As Node Ptr = m_TopNode For i As Integer = 0 To Index - 1 objNode = objNode->NextNode Next i objNode->p = Value End If End If End Property Public Function List.pBeginForward()As Node Ptr Return m_TopNode End Function Public Function List.pEndForward()As Node Ptr Return 0 End Function Public Function List.pBeginBack()As Node Ptr Return 0 End Function Public Function List.pEndBack()As Node Ptr Return m_TailNode End Function /' Итератор списка '/ Public Constructor ListIterator(ByVal Value As Node Ptr) m_CurrentNode = Value End Constructor ' Увеличение индекса Public Sub ListIterator.Increment() If m_CurrentNode Then ' Перемещение указателя m_CurrentNode = m_CurrentNode->NextNode End If End Sub ' Уменьшение индекса Public Sub ListIterator.Decrement() If m_CurrentNode Then ' Перемещение указателя m_CurrentNode = m_CurrentNode->PreviousNode End If End Sub ' Текущий элемент Public Property ListIterator.Item()As Object Ptr If m_CurrentNode Then Return m_CurrentNode->p Else Return 0 End If End Property Public Property ListIterator.Item(ByVal Value As Object Ptr) If m_CurrentNode Then m_CurrentNode->p = Value End If End Property ' Текущий узел Public Property ListIterator.CurrentNode()As Node Ptr Return m_CurrentNode End Property End Namespace

Компиляция в библиотеку

Код:: fbc Lists.bas -lib

Использование

Код:: ' Подключить заголовочный файл #include once "Lists.bi"

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

Код:: Type DataNode Extends Object Dim X As Integer End Type

Теперь объявим список и заполним его значениями:

Код:: Dim objList As Lists.List For i As Integer = 0 To 100 ' Наш указатель на объект данных, создаём его Dim objData As DataNode Ptr = New DataNode() ' заполнаем данными objData->X = i ' Добавляем объект в конец списка ' в список может быть добавлен любой тип данных, унаследованных от типа Object objList.AddEnd(objData) Next i

Список с данными готов. Теперь нам нужно пройтись по списку и распечатать его. Будем использовать итератор. Итератор — это объект, абстрагирующий за единым интерфейсом доступ к элементам списка.

Код:: Dim it As Lists.ListIterator Ptr = New Lists.ListIterator(objList.pBeginForward) ' Объект, хранящийся в списке Dim objNode As DataNode Ptr ' Будем проходить список с помощью итератора, до тех пор, пока не получим пустой объект Do While it->Item ' Приводим объект к нашему типу данных objNode = CPtr(DataNode Ptr, it->Item) ' Распечатываем данные объекта Print objNode->X, ' Продвигаем итератор вперёд it->Increment Loop

В конце работы итератор нужно удалить

Код:: Delete(it)