FreeBasic
Главная
Вход
Регистрация
Воскресенье, 18.11.2018, 21:29Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Форум » Freebasic » Исходники » Простой связанный список (Простой связанный список)
Простой связанный список
haavДата: Понедельник, 01.10.2012, 16:23 | Сообщение # 1
Генерал-полковник
Группа: Администраторы
Сообщений: 856
Репутация: 34
Статус: Offline
Простой связанный список


Это простенький связанный список, в котором реализованы методы:

  • добавление в начало, в конец
  • удаление пункта
  • удаление всего листа
  • получение значения


Кто автор, не знаю

Code

Type listnode
     As Any Ptr pData
     As listnode Ptr pNext
     As listnode Ptr pPrev
End Type

Declare Function ListCreate() As listnode Ptr
Declare Function ListAdd(list As listnode Ptr, item As Any Ptr) As Any Ptr
Declare Function ListAddHead(list As listnode Ptr, item As Any Ptr) As Any Ptr
Declare Function ListGetFirst(list As listnode Ptr) As listnode Ptr
Declare Function ListGetLast(list As listnode Ptr) As listnode Ptr
Declare Function ListGetNext(list As listnode Ptr) As listnode Ptr
Declare Function ListGetPrev(list As listnode Ptr) As listnode Ptr
Declare Function ListGetData(list As listnode Ptr) As Any Ptr
Declare Function ListRemove(list as listnode ptr, bDelete as integer = 0) as listnode ptr
Declare Function ListRemoveAll(list as listnode ptr, bDelete as integer = 0) As Integer

Dim As listnode Ptr list, node
Dim As Integer Ptr item
list = ListCreate()
item = ListAdd(list, CAllocate(Len(Integer)))
*item = 4
item = ListAdd(list, CAllocate(Len(Integer)))
*item = 44
item = ListAddHead(list, CAllocate(Len(Integer)))
*item = 56

item = 0 ' just to show it works
node = ListGetFirst(list)

While node <> 0
     Print "found item"
     item = ListGetData(node)
     Print *item
     node = ListRemove(node,1)
Wend

While Inkey$ = "" : Wend

' CREATE
Function ListCreate() As listnode Ptr
     Dim As listnode Ptr pTemp
     pTemp = CAllocate(Len(listnode))
     ' CAllocate automatically zeroes memory.

     Return pTemp
End Function

' ADD, ADDHEAD

Function ListAdd(list As listnode Ptr, item As Any Ptr) As Any Ptr
     Dim As listnode Ptr pTemp

     If (list = 0) Then Return item

     pTemp = ListGetLast(list)

     pTemp->pNext = CAllocate(Len(listnode))
     pTemp->pNext->pPrev = pTemp
     pTemp->pNext->pData = item

     Return item
End Function

Function ListAddHead(list As listnode Ptr, item As Any Ptr) As Any Ptr
     Dim As listnode Ptr pTemp

     If (list = 0) Then Return item
     pTemp = list->pNext ' сохраняем первый
     list->pNext = CAllocate(Len(listnode)) 'выделяем новый адрес для первого
     list->pNext->pPrev = list ' новый адрес для листа
     list->pNext->pData = item ' загоняем наш новый элемент
     list->pNext->pNext = pTemp  
     If (pTemp <> 0) Then
         pTemp->pPrev = list->pNext
     End If

     Return item
End Function

' GETFIRST, GETLAST

Function ListGetFirst(list As listnode Ptr) As listnode Ptr
     If (list = 0) Then Return 0

     Return list->pNext
End Function

Function ListGetLast(list As listnode Ptr) As listnode Ptr
     Dim As listnode Ptr pTemp

     If (list = 0) Then Return 0

     pTemp = list
     While (pTemp->pNext <> 0)
         pTemp = pTemp->pNext
     Wend

     Return pTemp
End Function

' GETNEXT, GETPREV

Function ListGetNext(list As listnode Ptr) As listnode Ptr
     If (list = 0) Then Return 0

     Return list->pNext
End Function

Function ListGetPrev(list As listnode Ptr) As listnode Ptr
     ' can't do anything to a null list
     If (list = 0) Then Return 0
     ' this is needed for below
     If (list->pPrev = 0) Then Return 0
     ' since the list starts with a null node (pPrev and pData = 0),
     ' the first should be the one right after the real first.
     If (list->pPrev->pPrev = 0) Then Return 0

     Return list->pPrev
End Function

' GETDATA

Function ListGetData(list As listnode Ptr) As Any Ptr
     If (list = 0) Then Return 0

     Return list->pData
End Function

' REMOVE, REMOVEALL

Function ListRemove(list as listnode ptr, bDelete as integer = 0) As listnode ptr
     Dim As listnode Ptr pPrev
     Dim As listnode Ptr pNext

     If (list = 0) Then Return 0

     pPrev = list->pPrev
     pNext = list->pNext

     If ((list->pData <> 0) And (bDelete <> 0)) Then Deallocate list->pData

     Deallocate list

     If (pPrev <> 0) Then
         pPrev->pNext = pNext
     End If
     If (pNext <> 0) Then
         pNext->pPrev = pPrev
     End If

     Return pNext
End Function

Function ListRemoveAll(list as listnode ptr, bDelete as integer = 0) As Integer
     Dim As listnode Ptr node

     node = list
     If (list = 0) Then Return 0

     While (node <> 0)
         If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
         node = ListRemove(node)
     Wend

     Return 1
End Function
  


Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
haavДата: Вторник, 18.12.2012, 09:07 | Сообщение # 2
Генерал-полковник
Группа: Администраторы
Сообщений: 856
Репутация: 34
Статус: Offline
Это простейший связанный список, созданный с помощью функций HeapCreate, HeapAlloc, HeapFree, HeapDestroy

Code
#Include "windows.bi"

' ставим кол-во строк в консоли 1000

Width ,1000

' тип связанного списка
Type Tlist
  iValue As Integer
  pPrev As Tlist Ptr = 0
End Type

' глобальные переменные для кучи,текущего и временного объекта  
Dim shared As HANDLE hHeap
Dim shared As Tlist Ptr pCurrent,pGet

'создаем кучу
hHeap = HeapCreate(HEAP_NO_SERIALIZE,1000,0)  

'функция добавления объектов в список
Function addInt(iValue As Integer) As Tlist Ptr
  Dim As Tlist Ptr p = HeapAlloc(hHeap,HEAP_NO_SERIALIZE,SizeOf(Tlist))
  p->iValue = iValue
  p->pPrev = pCurrent
  pCurrent = p
  addInt = p
End Function

'функция удаления объектов из списка
Function deleteInt(pDel As Tlist Ptr) As Integer
  If pDel->pPrev = 0 Then deleteInt = TRUE
  HeapFree(hHeap,HEAP_NO_SERIALIZE,pDel)
End Function

'..........................Проверка работы списка...............

'добавляем в список
For i As Integer = 1 To 500
  addInt(i)
Next

'ставим временный объект равный текущему
pGet = pCurrent
'получаем значение каждого объекта задом наперед
For i As Integer = 1 To 500
  Print pGet->iValue
  pGet = pGet->pPrev
Next

  'удаляем объекты
For i As Integer = 1 To 500
  pGet = pCurrent->pPrev
    deleteInt(pCurrent)
    pCurrent = pGet
Next
Sleep

'удаляем кучу
HeapDestroy(hHeap)


Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
Dr@koNДата: Воскресенье, 06.01.2013, 19:21 | Сообщение # 3
Рядовой
Группа: Пользователи
Сообщений: 4
Репутация: 0
Статус: Offline
Вот моя версия связанного списка:
Код
Type list_element
   next_elem As list_element Ptr = 0
   prev_elem As list_element Ptr = 0
   elem As UShort 'Идентификатор
   'Любые переменные
   Declare Destructor ()
End Type

Type list_class
   first_elem As list_element Ptr = 0
   last_elem As list_element Ptr = 0
   Declare Destructor ()
   Declare Sub add_elem (As UShort, ByRef As list_element Ptr)
   Declare Sub n_elem (ByRef As list_element ptr)
   Declare Sub p_elem (ByRef As list_element Ptr)
   Declare Sub f_elem (ByRef As list_element Ptr)
   Declare Sub find_elem (ByRef As list_element Ptr, As UShort)
End Type

Sub list_class.add_elem (id As UShort, ByRef cur As list_element Ptr)
   Dim temp As list_element Ptr = New list_element
   temp->elem = id
   If first_elem = 0 Then
    first_elem = temp
   Else
    Dim temp2 As list_element Ptr = first_elem
    Do
     If temp2->next_elem <> 0 Then
      If id < temp2->next_elem->elem Then
       temp->next_elem = temp2->next_elem
       temp->prev_elem = temp2
       temp2->next_elem = temp
       temp->next_elem->prev_elem = temp
       Exit Do
      EndIf
     Else
      temp->prev_elem = temp2
      temp2->next_elem = temp
      last_elem = temp
      Exit Do
     EndIf
     temp2 = temp2->next_elem
    Loop
   EndIf
   cur = temp
End Sub

Sub list_class.n_elem (ByRef cur_elem As list_element ptr)
   If cur_elem->next_elem <> 0 Then
    cur_elem = cur_elem->next_elem
   Else
    cur_elem = first_elem
   EndIf
End Sub

Sub list_class.p_elem (ByRef cur_elem As list_element Ptr)
   If cur_elem->prev_elem <> 0 Then
    cur_elem = cur_elem->prev_elem
   Else
    cur_elem = last_elem
   EndIf
End Sub

Sub list_class.f_elem (ByRef cur_elem As list_element Ptr)
   cur_elem = first_elem
End Sub

Sub list_class.l_elem (ByRef cur_elem As list_element Ptr)
   cur_elem = last_elem
End Sub

Sub list_class.find_elem (ByRef cur_elem As list_element Ptr, id As UShort)
   Dim temp As list_element Ptr = first_elem
   Do
    If temp->elem = id Then
     cur_elem = temp
     Exit Do
    ElseIf temp->next_elem = 0 Then
     cur_elem = 0
     Exit Do
    Else
     temp = temp->next_elem
    EndIf
   Loop
End Sub

Destructor list_element
   If prev_elem <> 0 Then
    If next_elem <> 0 Then
     prev_elem->next_elem = next_elem
     next_elem->prev_elem = prev_elem
    Else
     prev_elem->next_elem = 0
    EndIf
   Else
    If next_elem <> 0 Then
     next_elem->prev_elem = 0
    EndIf
   EndIf
End Destructor

Destructor list_class
   Dim As list_element ptr curr
   curr = first_elem
   If curr <> 0 Then
    Do
     If curr->next_elem <> 0 Then
      curr = curr->next_elem
      Delete curr->prev_elem
     Else
      Delete curr
      Exit Do
     EndIf
    Loop
   EndIf
End Destructor

Возможности:
*Добавление элемента в середину списка по идентификатору:
list_name.add_elem(идентификатор, указатель)
*Возвращение в указатель первый, последний, следующий, предыдущий элемент:
list_name.f_elem(указатель)
list_name.l_elem(указатель)
list_name.n_elem(указатель)
list_name.p_elem(указатель)
* Возвращение в указатель элемента с нужным идентификатором:
list_name.find_elem(указатель, идентификатор)
* "Автосвязывание" списка при удалении элемента

Пример использования


Вникаю в ФБ... 4,1%

Сообщение отредактировал Dr@koN - Воскресенье, 06.01.2013, 19:22
 
haavДата: Понедельник, 07.01.2013, 10:10 | Сообщение # 4
Генерал-полковник
Группа: Администраторы
Сообщений: 856
Репутация: 34
Статус: Offline
Цитата (Dr@koN)
Вот моя версия связанного списка:


Нормально. Считаю, что всем кто знакомится с СИ , FreeBasic, Pascal просто необходимо хотя бы раз создать свой связанный список. Как минимум вырастет понимание работы с указателями.


Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
ТесторДата: Вторник, 03.04.2018, 16:14 | Сообщение # 5
Сержант
Группа: Пользователи
Сообщений: 25
Репутация: 0
Статус: Offline
Вопрос по теме.

Это почитал.

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

Упоминается что по скорости они превосходят альтернативу в виде динамического массива, правда на практике нам часто удобно индексированное обращение к элементу + частенько требуется информация размерности структуры. В общем то, нехитрое дело добавить счётчик элементов и методы по индексной работы (вернуть/записать, переместить и т. д.) - но для реализации таких методов, мне ничего не приходит в голову иного как прокрутка структуры в цикле... и тут возникает 2 вопроса:
1. Это даст выигрыш перед динамическим массивом?
2. А собственно динамический массив реализован не так?

Есть ещё одна часто решаемая задача, поиск значени/й из массива путём сопоставления (сравнения), для такой операции как правило производится прокрутка массива в цикле в теле которого совершается сверка. С данной структурой можно осуществить такой поиск формально без цикла, рекурсивным вызовом метода... это даст выигрыш в производительности по сравнению с динамическим массивом?

Не совсем по теме, из опыта использования массивов, правда на другом компиляторе. Я как правило использовал динмассивы для построения и использования структур рабочих данных в памяти приложения, в них грузились данные с носителя, в них данные изменялись в результате целевого использования программы, из них писались на носитель. Эмпирическим путём я пришёл к тому что, даже для операций поиска путем перебора и сравнения, для нескольких десятков тысяч элементов массивы вполне приемлемы (при условии что эти разовые запросы, а не запросы вложенные в другой объёмный цикл), для сотен тысяч элементов задержка становится ощутимой, может компенсироваться мощьным ПК или крепкими нервами, миллионы таких операция могут вызывать несколько секундные задержки. Наиболее критичны динмассивы на выделение/перевыделение памяти, когда на динмассивах построена структура данных в памяти часто приходится вызывать перевыделение памяти ради одного элемента.

При таком использовании связанных списоков заместо динмассивов будет объективный выигрыш в производительности?
 
haavДата: Вторник, 03.04.2018, 17:20 | Сообщение # 6
Генерал-полковник
Группа: Администраторы
Сообщений: 856
Репутация: 34
Статус: Offline
Цитата Тестор ()
Упоминается что по скорости они превосходят альтернативу в виде динамического
массива, правда на практике нам часто удобно индексированное обращение к
элементу + частенько требуется информация размерности структуры. В
общем то, нехитрое дело добавить счётчик элементов и методы по индексной
работы (вернуть/записать, переместить и т. д.) - но для реализации
таких методов, мне ничего не приходит в голову иного как прокрутка
структуры в цикле... и тут возникает 2 вопроса:
1. Это даст выигрыш перед динамическим массивом?

На все вопросы про скорость:

Код
Смотря что измерять. Если обращение к нужному элементу , то массив в 99.99% случаев быстрее. Так же сортировка и поиск в массиве быстрее. А если размер данных заранее неизвестен, очень часто меняется , требуются вставки в произвольное место, удаление произвольных ячеек , то тут в приоритете будет список.
 

Цитата Тестор ()
2. А собственно динамический массив реализован не так?

Динамический или статический массив - обычная область памяти .  Так же выделяется , освобождается и при обращении к индексу , идет обычная математика со смещением от начального адреса. Не знаю что тут обсуждать.


Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
WQДата: Вторник, 03.04.2018, 21:25 | Сообщение # 7
Полковник
Группа: Проверенные
Сообщений: 157
Репутация: 5
Статус: Offline
Цитата Тестор ()
Есть ещё одна часто решаемая задача, поиск значени/й из массива путём сопоставления (сравнения), для такой операции как правило производится прокрутка массива в цикле в теле которого совершается сверка. С данной структурой можно осуществить такой поиск формально без цикла, рекурсивным вызовом метода... это даст выигрыш в производительности по сравнению с динамическим массивом?

Возможно, для этого подойдет хэш-таблица, где получение значения происходит по ключу
На тех примерах, которые я использую, доступ к элементу хэш-таблицы медленнее доступа к элементу массива примерно в 100 раз, но не зависит от положения элемента
Соответственно, если речь идет о поиске в массиве с количеством элементов больше нескольких сотен, хэш-таблица даст ощутимое преимущество

Но, конечно, все зависит от специфики задачи
 
Форум » Freebasic » Исходники » Простой связанный список (Простой связанный список)
  • Страница 1 из 1
  • 1
Поиск: