Связанные списки
Связанный список является структурой, которая легко расширяется с помощью одной функции, и бывает полезна, когда вам небходим массив, но вы изначально понятия не имеете, какого размера. Концепция связанного списка такова, что каждый узел структуры имеет указатель на следующий и предыдущий узел структуры. Это называется двойным связанным списком , так как узел связан с двумя различными узлами. Используя указатель на структуру, можно указать нулевой указатель, если нет следующего или предыдущего узла. И так как указатель хранит адрес памяти, количество узлов, которые можно хранить, ограничивается только объемом памяти.
Единственным недостатком связанного списка является то, что для того, чтобы хранить скажем Integer, вы должны выделить место не только для этого Integer, но и структуру, содержащую указатель на Integer , а так же указатель на окружающие узлы. Это не делает особой разницы на современных компьютерах, если вы не храните миллионы узлов.
Базовой структурой связанного списка является узел. Декларация заключается в следующем:
Type listnode
As Any Ptr pData
As listnode Ptr pNext
As listnode Ptr pPrev
End Type
As Any Ptr pData
As listnode Ptr pNext
As listnode Ptr pPrev
End Type
Эта структура содержит три указателя. Первый является указателем на что-нибудь (Any Ptr), это означает, что вы можете хранить строки, целые числа, символы, даже пользовательские типы и union. Но это также означает, что вы должны передать указатель. Вы можете выделить память для указателя с помощью функций Allocate (или CAllocate).
Следующие два указатели, указатели на listnodes, то есть, технически это можно сделать:
Print node->pNext->pNext->pNext->pNext->pNext...
поскольку каждый узел содержит указатель на другой узел. Проблема с предыдущим вариантом синтаксиса в том, что вы ограничиваете себя кол-вом узлов и кроме того код становится трудно понять. Вы можете использовать функцию ListGetNext и цикл While в ней для этой цели.
Прежде чем идти дальше, давайте посмотрим, все декларации функций для использования связанных списков. Обратите внимание, что каждая функция имеет префикс "List".
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 Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
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 Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Вы можете видеть, что есть функции для создания связанного списка, добавления элемента, получения различных узлов, получения данных, и для удаления узлов. В настоящее время мы сосредоточимся на функции ListCreate. Она не принимает никаких параметров и возвращает указатель listnode. Структура, которую она создает, не имеет данных для заполнения. Вся структура является действительной, но это по-прежнему структура. Если добавить узел, член pNext изменится и будет указывать на новый пункт, поэтому он не будет оставаться как узел со значением null, так как не было бы никакого смысла в этом. То есть по сути значение, возвращенное с помощью ListCreate является нулевым узлом без данных о предыдущем узле pPrev и без данных для pData, но в этом узле будет ссылка на первый узел в pNext.
Функция ListCreate выглядит так:
' СОЗДАНИЕ
Function ListCreate() As listnode Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate автоматически забивает нулями память.
Return pTemp
End Function
Function ListCreate() As listnode Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate автоматически забивает нулями память.
Return pTemp
End Function
Я предпочитаю использовать Return для возврата значения из функции, но FUNCTION = pTemp и ListCreate = pTemp также допускаются, хотя они не дают сразу выход из функции.
Суть этой функции легко увидеть, для узла выделяется память и происходит возврат из функции. Комментарий говорит, что функция CAllocate автоматически забивает нулями память. Если вы будете использовать функцию Allocate, то память не будет автоматически обнуляться и вам придется это делать самим.
Следующие функции, ListAdd и ListAddHead, добавление узла к списку. ListAdd добавляет узел в конец списка (в хвост), а ListAddHead вставляет узел на самом верху (в голову).
' ДОБАВЛЕНИЕ В КОНЕЦ СПИСКА, ДОБАВЛЕНИЕ В НАЧАЛО СПИСКА
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
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
Вы можете увидеть, что ListAdd делает ссылку на функцию ListGetLast. Пока все, что вам нужно знать, это то, что она возвращает указатель на последний узел в списке. Позже она будет рассмотрена.
ListAdd извлекает последний узел и задает его в указатель pNext новой структуры listnode. Это не вызовет потерю памяти, поскольку последний узел имеет значение null. После того, как наш узел добавился, мы можем получить доступ к нему с помощью оператора ->. Линия
pTemp->pNext->pPrev = pTemp
является всей основой связанных списков, за счет связующих звеньев. Это говорит о том, что у нас есть ссылка на узел. Это узел знает, где ссылка на следующий узел, и теперь мы определяем для узла где будет предыдущий узел. Это может выглядеть немного излишним сначала, но компилятор не знает, где узлы, пока вы не установите их. После того как вы сделали это, вы можете пройти по связанному списку.
Функция ListAddHead немного сложнее, так как мы на самом деле вставляем узел между текущим первым узлом и нулевым узлом от ListCreate. Что она делает? В основном выделяет место для хранения текущего первого узла, создает там новый узел, и связывает их все вместе. Если вы немного изучите пример, то это станет казаться намного яснее. Заявление IF в конце просто гарантирует, что мы не пытаемся получить доступ к памяти, которая не существует (NULL-> pPrev). Если pTemp, фактически не равен нулю, то его член pPrev будет назначен. В противном случае, нет никаких оснований беспокоиться об этом.
Следующие функции ListGetFirst и ListGetLast. Я реализовал их рядом, потому что ListGetLast была ссылкой в вышеупомянутой функции.
' ПОЛУЧИТЬ ПЕРВЫЙ УЗЕЛ, ПОЛУЧИТЬ ПОСЛЕДНИЙ УЗЕЛ
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
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
Первая функция, вероятно самая простая для понимания. Ее работа опирается на тот факт, что вы имеете указатель на узел, возвращенный ListCreate и с помощью этого указателя вы получаете указатель на первый узел или узел, который приходит сразу после нулевого узла.
Вторая функция ListGetLast, перебирает список до тех пор, пока не будет найден узел со значением null. Причина, по которой я проверяю if pTemp->pNext = 0 вместо pTemp = 0 это то, что я не хочу возвращать нуль. Я хочу вернуть последний узел , который имеет в pNext значение, равное нулю. После того, как узел найден, ListGetLast возвращает его.
Следующие 3 функции - просто вспомогательные функции и могли быть легко достигнуты одной линией кода, но все таки удобнее данную функциональность завернуть в функции.
' ПОЛУЧЕНИЕ СЛЕДУЮЩЕГО УЗЛА, ПОЛУЧЕНИЕ ПРЕДЫДУЩЕГО УЗЛА
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
' не делать ничего, если список равен нулю
If (list = 0) Then Return 0
' Это необходимо для нижней записи
If (list->pPrev = 0) Then Return 0
' Поскольку список начинается с нулевого узла(pPrev = 0 и pData = 0),
' мы проверяем: а не окажется ли предыдущий узел нулевым.
If (list->pPrev->pPrev = 0) Then Return 0
Return list->pPrev
End Function
' ПОЛУЧЕНИЕ ДАННЫХ УЗЛА
Function ListGetData(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pData
End Function
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
' не делать ничего, если список равен нулю
If (list = 0) Then Return 0
' Это необходимо для нижней записи
If (list->pPrev = 0) Then Return 0
' Поскольку список начинается с нулевого узла(pPrev = 0 и pData = 0),
' мы проверяем: а не окажется ли предыдущий узел нулевым.
If (list->pPrev->pPrev = 0) Then Return 0
Return list->pPrev
End Function
' ПОЛУЧЕНИЕ ДАННЫХ УЗЛА
Function ListGetData(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pData
End Function
Первая функция, ListGetNext, точно такая же, как ListGetFirst, но разница в том как вы будете ее использовать. И хотя вы можете использовать ListGetFirst в этой реализации, это не очень умная идея, потому что в некоторых других реализациях могут быть циклы к началу списка, чтобы найти первый узел, и в этом случае вы бы застряли в бесконечном цикле.
Функция ListGetPrev немного сложнее, так как я не хочу, возвращать нулевой узел. Первая и третья строка кода (не учитывая комментарии) действительно необходимы, но вторая гарантирует, что мы не обращается к нулевой памяти. Третья строка говорит, что если два узла до нулевого узла, мы должны вернуть ноль. Это делается для того, чтобы мы не могли возвратить ссылку на нулевой узел, в котором по сути нет никаких данных, кроме ссылки на реально используемый первый узел. Последняя строка обрабатывает условие по умолчанию, где на самом деле является предыдущий узел, и он должен быть возвращен.
Функция ListGetData так же проста, как и функции ListGetFirst и ListGetNext. Она просто возвращает указатель на данные узла.
Окончательные две функции для удаления узлов из списка.
' УДАЛЕНИЕ УЗЛА, УДАЛЕНИЕ ВСЕХ УЗЛОВ
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
Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
End Sub
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
Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
End Sub
Функция ListRemove выполняет две работы: удаляет указанный узел и связывает два окружающих его узла вместе. Вы можете видеть, что он хранит предыдущий и следующий указатель, чтобы осуществить это. Необязательный параметр, bDelete нужен для указания удалять или нет элемент данных. Если вы просто храните целые числа, или даже структуры без инициализированных указателей в них, можно указать 1 для этого параметра и узел будет удален. Но если у вас сложные структуры, для которых вы сами выделяли память, то во избежание утечек памяти, лучше проделать удаление данных отдельным кодом. Указатель listnode освобождается независимо от параметра bDelete.
ListRemoveAll опирается на функцию ListRemove для удаления узлов. Она просто перебирает список, используя цикл WHILE и удаляет все узлы. Оригинальный код, использует цикл FOR, но FB кажется, не нравится такое
For node = list To 0 Step ListRemove(node)
таким образом, это было изменено.
Вот и все, ниже готовый пример всего вышесказанного. Это мой первый учебник, так что не стесняйтесь оставлять комментарии о тех вещах, которые можно улучшить. Кроме того, если вы найдете ошибку в коде (я нашел пару ошибок во время написания учебника), пожалуйста, дайте мне знать. Не стесняйтесь редактировать ошибки, но я хотел бы знать о них.
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 Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
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 = 0 ' просто чтобы показать, что это работает
node = ListGetFirst(list)
While node <> 0
Print "found item"
item = ListGetData(node)
Print *item
node = ListRemove(node,1)
Wend
While Inkey$ = "" : Wend
' СОЗДАНИЕ
Function ListCreate() As listnode Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate автоматически забивает нулями память.
Return pTemp
End Function
' ДОБАВЛЕНИЕ В КОНЕЦ СПИСКА, ДОБАВЛЕНИЕ В НАЧАЛО СПИСКА
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
' ПОЛУЧИТЬ ПЕРВЫЙ УЗЕЛ, ПОЛУЧИТЬ ПОСЛЕДНИЙ УЗЕЛ
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
' ПОЛУЧЕНИЕ СЛЕДУЮЩЕГО УЗЛА, ПОЛУЧЕНИЕ ПРЕДЫДУЩЕГО УЗЛА
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
' не делать ничего, если список равен нулю
If (list = 0) Then Return 0
' Это необходимо для нижней записи
If (list->pPrev = 0) Then Return 0
' Поскольку список начинается с нулевого узла(pPrev = 0 и pData = 0),
' мы проверяем: а не окажется ли предыдущий узел нулевым.
If (list->pPrev->pPrev = 0) Then Return 0
Return list->pPrev
End Function
' ПОЛУЧЕНИЕ ДАННЫХ УЗЛА
Function ListGetData(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pData
End Function
' УДАЛЕНИЕ УЗЛА, УДАЛЕНИЕ ВСЕХ УЗЛОВ
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
Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
End Sub
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 Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
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 = 0 ' просто чтобы показать, что это работает
node = ListGetFirst(list)
While node <> 0
Print "found item"
item = ListGetData(node)
Print *item
node = ListRemove(node,1)
Wend
While Inkey$ = "" : Wend
' СОЗДАНИЕ
Function ListCreate() As listnode Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate автоматически забивает нулями память.
Return pTemp
End Function
' ДОБАВЛЕНИЕ В КОНЕЦ СПИСКА, ДОБАВЛЕНИЕ В НАЧАЛО СПИСКА
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
' ПОЛУЧИТЬ ПЕРВЫЙ УЗЕЛ, ПОЛУЧИТЬ ПОСЛЕДНИЙ УЗЕЛ
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
' ПОЛУЧЕНИЕ СЛЕДУЮЩЕГО УЗЛА, ПОЛУЧЕНИЕ ПРЕДЫДУЩЕГО УЗЛА
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
' не делать ничего, если список равен нулю
If (list = 0) Then Return 0
' Это необходимо для нижней записи
If (list->pPrev = 0) Then Return 0
' Поскольку список начинается с нулевого узла(pPrev = 0 и pData = 0),
' мы проверяем: а не окажется ли предыдущий узел нулевым.
If (list->pPrev->pPrev = 0) Then Return 0
Return list->pPrev
End Function
' ПОЛУЧЕНИЕ ДАННЫХ УЗЛА
Function ListGetData(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pData
End Function
' УДАЛЕНИЕ УЗЛА, УДАЛЕНИЕ ВСЕХ УЗЛОВ
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
Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
End Sub
Если вы еще не заметили , ListAdd и ListAddHead возвращает указатель на данные, которые вы вводили. Пример кода (см. выше) показывает, как использовать эту функцию. ListRemove возвращает указатель на следующий узел. ListRemoveAll удаляет узлы. ListRemoveAll является единственной функцией, которая ничего не возвращает. Там нет необходимости, так как весь список будет пуст после того как вы ее назвали.