Cписки и деревья

Связанные списки или массив без размера

Программы обычно оперируют с табличной информацией. В большинстве случаев это не просто куча чисел. В таблицах присутствуют важные структурные отношения . Эти отношения видны из вопросов. Кто первый? Кто последний? Кто впереди? Кто сзади?

Для начала введем несколько терминов. Списки состоят из элементов. Каждый элемент состоит из полей.

Расмотрим пример списка карт. У нас будут поля TAG - признак перевернута или нет. SUIT - масть. RANG - ранг. NEXT - следующая карта.

Код:


TYPE CField
  DECLARE CONSTRUCTOR ()
  DIM tag AS INTEGER
  DIM suit AS INTEGER
  DIM rang AS INTEGER
  DIM next_ AS CField PTR
END TYPE

CONSTRUCTOR CField ()
  next_ = NULL
END CONSTRUCTOR


NULL используется для пустой связи. Ведь когда мы создаем карту , следующей связи нет. Введение связей очень важная идея. Это ключ к представлению сложных структур. В нашем вариате это будет выглядь так:

_____CField_____CField_____CField
top ->........_+->_......._+->_.......
______...... _!___........_!___.......
______......._!___........_!___.......
______NEXT-+___NEXT-+___NEXT -> NULL

Попробуем создать программу для демонстрации связей.

Код:


DIM AS CField PTR top, step1, step2
REM ----- Создание колоды ---------
top = NEW CField ()                          ' создать первую карту
top->tag = 1                                  ' установить её свойство
top->next_ = NEW CField ()                ' создать вторую карту
step1 = top->next_                          ' взять вторую карту 
step1->next_ = NEW CField ()            ' создать третью карту
step1->tag = 0                                ' установить её свойство
step2 = step1->next_                      '  взять третью карту
step2->tag = 1                                ' установить её свойство

REM ---- Начало подсчёта карт -----
DIM temp AS CField PTR                  ' указатель на временный объект
DIM count AS INTEGER = 0              ' счётчик карт
temp = top                                    '  временный объект вначале равен первому
WHILE temp                                  ' пока есть карты
  count = count + 1                      ' подсчитать карту
  PRINT temp->tag                        ' вывести статус на экран 
  temp = temp->next_                    ' взять следующую
WEND
PRINT count                                  ' вывести количество карт
REM ---- Конец подсчёта карт -----
SLEEP


Идея понятна. В классе есть указатель на другой класс и по указателю мы по ним ходим.
Что здесь хорошего? Первое - массив не имеет размера, т.е. размер ограничен памятью компьютера.
данный пример, конечно, далек от совершества - поэтому идём дальше...

Оболочка для класса

В предыдущем примере мы каждый раз описывали и переменную и вручную связывали. Вообше нужно, что бы это делалось автоматически, скажем, по команде AddField. Для этого заведем класс для записей(контейнер):

Код:


TYPE CAllField
    DECLARE CONSTRUCTOR ()   
    DECLARE SUB AddField ()          ' добавить запись   
    DECLARE FUNCTION GetCount () ' определить количество записей 
    DIM top AS CField PTR              ' указатель на первый элемент
END TYPE

CONSTRUCTOR CAllField ()
  top = NULL
END CONSTRUCTOR

SUB CAllField.AddField ()
  DIM temp AS CField PTR
  IF top                                    ' если хотя бы одна запись уже есть
      temp = top                       
      WHILE temp->next_              ' проходим по записям до последней
          temp = temp->next_
      WEND
      temp->next_ = NEW CField ()  ' и создаём в конце новую
  ELSE                                      ' иначе
      top = NEW CField ()              ' создаём первую
  END IF
END SUB

FUNCTION CAllField.GetCount ()
  DIM temp  AS CField PTR = top ' создаём временный объект и делаем его первым в списке
  DIM count AS INTEGER    = 0  ' создаём счётчик записей
  WHILE temp                          ' пока записи не закончились
      count = count + 1              ' учитываем текущую
      temp = temp->next_          ' переходим на следующую
  WEND
  RETURN count
END FUNCTION


Теперь проиллюстрируем что у нас получилось:

Код:


DIM alls AS CAllField
alls.AddField ()
alls.AddField ()
alls.AddField ()
PRINT alls.GetCount ()
SLEEP


Мы создали 3 записи. После этого их подсчитали и выведи на экран их количество - 3.
Ключевой момент: для аолучения очередного элемента списка (записи) необходимо идти по связям:

Код:


DIM temp CField PTR = top
temp = temp->next_


Пожалуйста напишите самый простой рабочий код работы со списками. Все примеры высвечивают ошибки. Трудно понять, если изначально примеры выдают ошибки...
Задача у меня такая стоит:
Открывать файл и читая заносить в список. В любой момент, удалять из списка ненужное или редактировать по надобности.

Я вот тут набросал двусвязный список. Там реализовано только три метода. Так сказать минимум для понимания. Возможны различные варианты, в зависимости от потребностей.
Например у меня есть метод AddLast, который добавляет узел в конец списка. Но можно добавить ещё два метода: AddFirst, для добавление узла в начало списка и Insert для вставки узла в произвольное место.
Так же можно добавить всякие плюшки, например методы для поиска узла или удаления. Ну и ещё многое другое.
Да и вообще, можно написать всё совсем по другому. Я сделал так. И оно работает. Надеюсь, будет понятно.

Код:


declare function main() as integer

' точка входа
end main()



' класс узла списка
type ListNode

' конструктор
declare constructor()


' индекс узла
id as uinteger

' значение которое хранится в узле списка
value as string

' указатель на предыдущий узел
prev_node as ListNode ptr

' указатель на следующий узел
next_node as ListNode ptr

end type


' класс списка
type List

' конструктор
declare constructor()

' деструктор
declare destructor()

'  метод очистки всего списка
declare sub Clear()

' метод добавление нового узла в конец списка
declare function AddLast( as string ) as uinteger

' удаляет узел по индексу
declare sub Remove( as uinteger )

' ищет узел по индексу
declare function FindByID( as uinteger ) as ListNode ptr

' метод отображение всего списка
declare sub ShowAll()


' указатель на первый узел
first_node as ListNode ptr

' указатель на последний узел
last_node as ListNode ptr

end type


' конструктор узла
constructor ListNode()
' просто обнуляет указатели
this.id = 0
this.prev_node = 0
this.next_node = 0
end constructor


' конструктор списка
constructor List()
' просто обнуляет указатели
this.first_node = 0
this.last_node = 0
end constructor


' деструктор списка
destructor List()
' вызывает метод очистки списка
this.Clear()
end destructor


' метод очищающий весь список
sub List.Clear()

' указатель на разрушаемый узел
dim del_node as ListNode ptr

' указатель на следующий узел
dim next_node as ListNode ptr

' начинает с первого узла
del_node = this.first_node

' проходит по всему списку, пока есть узел для разрушения
do while del_node

' запоминает указатель на следующий узел
next_node = del_node->next_node

' разрушает узел
delete del_node

' переходит к следующему узлу
del_node = next_node

loop

' обнуляет указатели
this.first_node = 0
this.last_node = 0
end sub



' метод добавление узла в конец списка
function List.AddLast( value  as string ) as uinteger

' указатель на новый узел
dim new_node as ListNode ptr

' создаёт объект узла
new_node = new ListNode()

' задаёт значение
new_node->value = value

if this.first_node = 0 then
' если в списке нет первого узла, то делает новый узел первым
new_node->id = 1
this.first_node = new_node
else
' если в списке есть первый узел, то подключает новый к последнему
new_node->id = this.last_node->id + 1
this.last_node->next_node = new_node
new_node->prev_node = this.last_node
end if
 
' делает новый узел последним
this.last_node = new_node

' возвращает идентификатор нового узла
return new_node->id
end function


' метод который проходит по всему списку и показывает его содержимое
sub List.ShowAll()

' указатель на показываемый узел
dim seek_node as ListNode ptr

' начинает с первого узла
seek_node = this.first_node

' проходит по всему списку, пока есть указатель на узел
do while seek_node

' показывает содержимое узла
print str(seek_node->id) & " '" & seek_node->value & "'"

' переходит к следующему узлу
seek_node = seek_node->next_node
loop
end sub


' удаляет узел по индексу
sub List.Remove( id as uinteger )

' указатель на удаляемый узел
dim del_node as ListNode ptr

' ищет удаляемый узел
del_node = this.FindByID( id )

' выходит, если узел не найден
if del_node = 0 then
exit sub
end if


' если удаляется первый узел
if this.first_node = del_node then
this.first_node = del_node->next_node
else
del_node->prev_node->next_node = del_node->next_node
end if

' если удаляется последний узел
if this.last_node = del_node then
this.last_node = del_node->prev_node
else
del_node->next_node->prev_node = del_node->prev_node
end if

' разрушает объект узла
delete del_node
end sub


' ищет узел по индексу
function List.FindByID( id as uinteger ) as ListNode ptr

' указатель на показываемый узел
dim seek_node as ListNode ptr

' начинает с первого узла
seek_node = this.first_node

' проходит по всему списку, пока есть указатель на узел
do while seek_node

' возвращает указатель на узел
if seek_node->id = id then
return seek_node
end if

' переходит к следующему узлу
seek_node = seek_node->next_node
loop

' возвращает 0, если узел не найден
return 0
end function


' главная функция
function main() as integer
print "тест списка"

' указатель на список
dim l1 as List ptr

' создаёт список
l1 = new List()

' добавляет узлы в список
l1->AddLast( "первый" )
l1->AddLast( "второй" )
l1->AddLast( "третий" )

' удаляет второй узел
l1->Remove( 2 )

' показывает содержимое всего списка
l1->ShowAll()


' разрушает список
delete l1

sleep
return 0
end function


Eric спасибо, ваш пример отлично работает, буду разбираться. Вообще ООП для меня как черная бездна... Надо будет больше разбирать туторы на этом сайте.
Кстати прошу прощения у justar первый код работает, это я не правильно компилил... (в GUI). А вот код ниже так и не получилось запустить, ошибок 10 выдает компилятор. Возможно, я опять чего не так делаю...

Во втором примере от justar подправил, теперь запускается, по крайней мере у меня.

Код:

TYPE CAllField
    DECLARE CONSTRUCTOR ()   
    DECLARE SUB AddField ()          ' добавить запись   
    DECLARE FUNCTION GetCount () As Integer ' определить количество записей 
    DIM top AS CALLField PTR              ' указатель на первый элемент
    DIM next_ AS CallField Ptr
END TYPE

CONSTRUCTOR CAllField ()
  top = 0
END CONSTRUCTOR

SUB CAllField.AddField ()
  DIM temp AS CallField PTR
  IF top    Then                                ' если хотя бы одна запись уже есть
      temp = top                       
      WHILE temp->next_              ' проходим по записям до последней
          temp = temp->next_
      WEND
      temp->next_ = NEW CallField ()  ' и создаём в конце новую
  ELSE                                      ' иначе
      top = NEW CallField ()              ' создаём первую
  END IF
END SUB

FUNCTION CAllField.GetCount () As integer
  DIM temp  AS CallField PTR = top ' создаём временный объект и делаем его первым в списке
  DIM count AS INTEGER    = 0  ' создаём счётчик записей
  WHILE temp                          ' пока записи не закончились
      count = count + 1              ' учитываем текущую
      temp = temp->next_          ' переходим на следующую
  WEND
  RETURN count
END Function

DIM alls AS CAllField
alls.AddField ()
alls.AddField ()
alls.AddField ()
PRINT alls.GetCount ()
SLEEP