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

Предыдущая тема Следующая тема Перейти вниз

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

Сообщение  Замабувараев в Вс Май 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)
avatar
Замабувараев

Сообщения : 99
Дата регистрации : 2008-08-20
Возраст : 33
Откуда : Красноярск

Посмотреть профиль http://www.freebasic.su

Вернуться к началу Перейти вниз

Предыдущая тема Следующая тема Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения