|
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программированияNext K Next J Next I End Sub Sub Fast() Dim I As Integer Dim J As Integer Dim K As Integer For I = 1 To N For J = 1 To N Slow ' Вызов процедуры Slow. Next J Next I End Sub Sub MainProgram() Fast End Sub С другой стороны, если процедуры независимо вызываются из основной программы, их вычислительная сложность суммируется. В этом случае полная сложность будет равна O(N3)+O(N2)=O(N3). Такую сложность, например, будет иметь следующий фрагмент кода: Sub Slow() Dim I As Integer Dim J As Integer Dim K As Integer For I = 1 To N For J = 1 To N For K = 1 To N ' Выполнить какие-либо действия. Next K Next J Next I End Sub Sub Fast() Dim I As Integer Dim J As Integer For I = 1 To N For J = 1 To N ' Выполнить какие-либо действия. Next J Next I End Sub Sub MainProgram() Slow Fast End Sub ==============5 Сложность рекурсивных алгоритмов Рекурсивными процедурами (recursive procedure) называются процедуры, вызывающие сами себя. Во многих рекурсивных алгоритмах именно степень вложенности рекурсии определяет сложность алгоритма, при этом не всегда легко оценить порядок сложности. Рекурсивная процедура может выглядеть простой, но при этом вносить большой вклад в сложность программы, многократно вызывая саму себя. Следующий фрагмент кода содержит подпрограмму всего из двух операторов. Тем не менее, для заданного N подпрограмма выполняется N раз, таким образом, вычислительная сложность фрагмента порядка O(N). Sub CountDown(N As Integer) If N ArraySize Then ArraySize = ArraySize + 10 ReDim Preserve List(1 To ArraySize) End If List(NumInList) = value End Sub ‘ Удалить последний элемент из списка. Если осталось больше ‘ 20 пустых ячеек, уменьшить список, освобождая память. Sub RemoveFromList() NumInList = NumInList – 1 If ArraySize – NumInList > 20 Then ArraySize = ArraySize –10 ReDim Preserve List(1 To ArraySize) End If End Sub =============20 Для очень больших массивов это решение может также оказаться не самым лучшим. Если вам нужен список, содержащий 1000 элементов, к которому обычно добавляется по 100 элементов, то все еще слишком много времени будет тратиться на изменение размера массива. Очевидной стратегией в этом случае было бы увеличение приращения размера массива с 10 до 100 или более ячеек. Тогда можно было бы добавлять по 100 элементов одновременно без частого изменения размера списка. Более гибким решением будет изменение приращения в зависимости от размера массива. Для небольших списков это приращение было бы также небольшим. Хотя изменения размера массива происходили бы чаще, они потребовали бы относительно немного времени для небольших массивов. Для больших списков, приращение размера будет больше, поэтому их размер будет изменяться реже. Следующая программа пытается поддерживать примерно 10 процентов списка свободным. Когда массив заполняется, его размер увеличивается на 10 процентов. Если свободное пространство составляет более 20 процентов от размера массива, программа уменьшает его. При увеличении размера массива, добавляется не меньше 10 элементов, даже если 10 процентов от размера массива составляют меньшую величину. Это уменьшает число необходимых изменений размера массива, если список очень мал. Const WANT_FREE_PERCENT = .1 ‘ 10% свободного места. Const MIN_FREE = 10 ‘ Минимальное число пустых ячеек. Global List() As String ‘ Массив элементов списка. Global ArraySize As Integer ‘ Размер массива. Global NumItems As Integer ‘ Число элементов в списке. Global ShrinkWhen As Integer ‘ Уменьшить размер, если NumItems < ShrinkWhen. ‘ Если массив заполнен, увеличить его размер. ‘ Затем добавить новый элемент в конец списка. Sub Add(value As String) NumItems = NumItems + 1 If NumItems > ArraySize Then ResizeList List(NumItems) = value End Sub ‘ Удалить последний элемент из списка. ‘ Если в массиве много пустых ячеек, уменьшить его размер. Sub RemoveLast() NumItems = NumItems – 1 If NumItems < ShrinkWhen Then ResizeList End Sub ‘ Увеличить размер массива, чтобы 10% ячеек были свободны. Sub ResizeList() Dim want_free As Integer want_free = WANT_FREE_PERCENT * NumItems If want_free < MIN_FREE Then want_free = MIN_FREE ArraySize = NumItems + want_free ReDim Preserve List(1 To ArraySize) ‘ Уменьшить размер массива, если NumItems < ShrinkWhen. ShrinkWhen = NumItems – want_free End Sub ===============21 Класс SimpleList Чтобы использовать этот простой подход, программе необходимо знать все параметры списка, при этом нужно следить за размером массива, числом используемых элементов, и т.д. Если необходимо создать больше одного списка, потребуется множество копий переменных и код, управляющий разными списками, будет дублироваться. Классы Visual Basic могут сильно облегчить выполнение этой задачи. Класс SimpleList инкапсулирует эту структуру списка, упрощая управление списками. В этом классе присутствуют методы Add и Remove для использования в основной программе. В нем также есть процедуры извлечения свойств NumItems и ArraySize, с помощью которых программа может определить число элементов в списке и объем занимаемой им памяти. Процедура ResizeList объявлена как частная внутри класса SimpleList. Это скрывает изменение размера списка от основной программы, поскольку этот код должен использоваться только внутри класса. Используя класс SimpleList, легко создать в приложении несколько списков. Для того чтобы создать новый объект для каждого списка, просто используется оператор New. Каждый из объектов имеет свои переменные, поэтому каждый из них может управлять отдельным списком: Dim List1 As New SimpleList Dim List2 As New SimpleList Когда объект SimpleList увеличивает массив, он выводит окно сообщения, показывающее размер массива, количество неиспользуемых элементов в нем, и значение переменной ShrinkWhen. Когда число использованных ячеек в массиве становится меньше, чем значение ShrinkWhen, программа уменьшает размер массива. Заметим, что когда массив практически пуст, переменная ShrinkWhen иногда становится равной нулю или отрицательной. В этом случае размер массива не будет уменьшаться, даже если вы удалите все элементы из списка. =============22 Программа SimList добавляет к массиву еще 50 процентов пустых ячеек, если необходимо увеличить его размер, и всегда оставляет при этом не менее 1 пустой ячейки. Эти значения был выбраны для удобства работы с программой. В реальном приложении, процент свободной памяти должен быть меньше, а число свободных ячеек больше. Более разумным в таком случае было бы выбрать значения порядка 10 процентов от текущего размера списка и минимум 10 свободных ячеек. Неупорядоченные списки В некоторых приложениях может понадобиться удалять элементы из середины списка, добавляя при этом элементы в конец списка. В этом случае порядок расположения элементов может быть не важен, но при этом может быть необходимо удалять определенные элементы из списка. Списки такого типа называются неупорядоченными списками (unordered lists). Они также иногда называются «множеством элементов». Неупорядоченный список должен поддерживать следующие операции: 1. добавление элемента к списку; 2. удаление элемента из списка; 3. определение наличия элемента в списке; 4. выполнение каких-либо операций (например, вывода на дисплей или принтер) для всех элементов списка. Простую структуру, представленную в предыдущем параграфе, можно легко изменить для того, чтобы обрабатывать такие списки. Когда удаляется элемент из середины списка, остальные элементы сдвигаются на одну позицию, заполняя образовавшийся промежуток. Это показано на рис. 2.1, на котором второй элемент удаляется из списка, и третий, четвертый, и пятый элементы сдвигаются влево, заполняя свободный участок. Удаление из массива элемента при таком подходе может занять достаточно много времени, особенно если удаляется элемент в начале списка. Чтобы удалить первый элемент из массива с 1000 элементов, потребуется сдвинуть влево на одну позицию 999 элементов. Гораздо быстрее удалять элементы можно при помощи простой схемы чистки памяти (garbage collection). Вместо удаления элементов из списка, пометьте их как неиспользуемые. Если элементы списка — данные простых типов, например целые, можно помечать элементы, используя определенное, так называемое «мусорное» значение (garbage value). @Рисунок 2.1 Удаление элемента из середины массива ===========23 Для целых чисел можно использовать для этого значение -32.767. Для переменной типа Variant можно использовать значение NULL. Это значение присваивается каждому неиспользуемому элементу. Следующий фрагмент кода демонстрирует удаление элемента из подобного целочисленного списка: Const GARBAGE_VALUE = -32767 ‘ Пометить элемент как неиспользуемый. Sub RemoveFromList(position As Long) List(position) = GARBAGE_VALUE End Sub Если элементы списка — это структуры, определенные оператором Type, вы можете добавить к такой структуре новое поле IsGarbage. Когда элемент удаляется из списка, значение поля IsGarbage устанавливается в True. Type MyData Name As Sring ‘ Данные. IsGarbage As Integer ‘ Этот элемент не используется? End Type ‘ Пометить элемент, как не использующийся. Sub RemoveFromList (position As Long) List(position).IsGarbage = True End Sub Для простоты далее в этом разделе предполагается, что элементы данных являются данными универсального типа и их можно помечать значением NULL. Теперь можно изменить другие процедуры, которые используют список, чтобы они пропускали помеченные элементы. Например, так можно модифицировать процедуру, которая печатает список: ‘ Печать элементов списка. Sub PrintItems() Dim I As Long For I = 1 To ArraySize If Not IsNull(List(I)) Then ‘ Если элемент не помечен Print Str$(List(I)) ‘ напечатать его. End If Next I End Sub После использования в течение некоторого времени схемы пометки «мусора», список может оказаться полностью им заполнен. В конце концов, подпрограммы вроде этой процедуры больше времени будут тратить на пропуск ненужных элементов, чем на обработку настоящих данных. =============24 Для того, чтобы избежать этого, можно периодически запускать процедуру очистки памяти (garbage collection routine). Эта процедура перемещает все непомеченные записи в начало массива. После этого можно добавить их к свободным элементам в конце массива. Когда потребуется добавить к массиву дополнительные элементы, их также можно будет использовать без изменения размера массива. После добавления помеченных элементов к другим свободным ячейкам массива, полный объем свободного пространства может стать достаточно большим, и в этом случае можно уменьшить размер массива, освобождая память: Private Sub CollectGarbage() Dim i As Long Dim good As Long good = 1 ‘ Первый используемый элемент. For i = 1 To m_NumItems ‘ Если он не помечен, переместить его на новое место. If Not IsNull(m_List(i)) Then m_List(good) = m_list(i) good = good + 1 End If Next i ‘ Последний используемый элемент. m_NumItems(good) = good - 1 ‘ Необходимо ли уменьшать размер списка? If m_NumItems < m_ShrinkWhen Then ResizeList End Sub При выполнении чистки памяти, используемые элементы перемещаются ближе к началу списка, заполняя пространство, которое занимали помеченные элементы. Значит, положение элементов в списке может измениться во время этой операции. Если другие часть программы обращаются к элементам списка по их положению в нем, необходимо модифицировать процедуру чистки памяти, с тем, чтобы она также обновляла ссылки на положение элементов в списке. В общем случае это может оказаться достаточно сложным, приводя к проблемам при сопровождении программ. Можно выбирать разные моменты для запуска процедуры чистки памяти. Один из них — когда массив достигает определенного размера, например, когда список содержит 30000 элементов. Этому методу присущи определенные недостатки. Во-первых, он использует большой объем памяти. Если вы часто добавляете или удаляете элементы, «мусор» будет занимать довольно большую часть массива. При таком неэкономном расходовании памяти, программа может тратить время на свопинг, хотя список мог бы целиком помещаться в памяти при более частом переупорядочивании. ===========25 Во-вторых, если список начинает заполняться ненужными данными, процедуры, которые его используют, могут стать чрезвычайно неэффективными. Если в массиве из 30.000 элементов 25.000 не используются, подпрограмма типа описанной выше PrintItems, может выполняться ужасно медленно. И, наконец, чистка памяти для очень большого массива может потребовать значительного времени, в особенности, если при обходе элементов массива программе приходится обращаться к страницам, выгруженным на диск. Это может приводить к «подвисанию» вашей программы на несколько секунд во время чистки памяти. Чтобы решить эту проблему, можно создать новую переменную GarbageCount, в которой будет находиться число ненужных элементов в списке. Когда значительная часть памяти, занимаемой списком, содержит ненужные элементы, вы может начать процедуру «сборки мусора». Dim GarbageCount As Long ‘ Число ненужных элементов. Dim MaxGarbage As Long ‘ Это значение определяется в ResizeList. ‘ Пометить элемент как ненужный. ‘ Если «мусора» слишком много, начать чистку памяти. Public Sub Remove(position As Long) m_List(position) = Null m_GarbageCount = m_GarbageCount + 1 ‘ Если «мусора» слишком много, начать чистку памяти. If m_GarbageCount > m_MaxGarbage Then CollectGarbage End Sub Программа Garbage демонстрирует этот метод чистки памяти. Она пишет рядом с неиспользуемыми элементами списка слово «unused», а рядом с помеченными как ненужные — слово «garbage». Программа использует класс GarbageList примерно так же, как программа SimList использовала класс SimpleList, но при этом она еще осуществляет «сборку мусора». Чтобы добавить элемент к списку, введите его значение и нажмите на кнопку Add (Добавить). Для удаления элемента выделите его, а затем нажмите на кнопку Remove (Удалить). Если список содержит слишком много «мусора», программа начнет выполнять чистку памяти. При каждом изменении размера списка объекта GarbageList, программа выводит окно сообщения, в котором приводится число используемых и свободных элементов в списке, а также значения переменных MaxGarbage и ShrinkWhen. Если удалить достаточное количество элементов, так что больше, чем MaxGarbage элементов будут помечены как ненужные, программа начнет выполнять чистку памяти. После ее окончания, программа уменьшает размер массива, если он содержит меньше, чем ShrinkWhen занятых элементов. Если размер массива должен быть увеличен, программа Garbage добавляет к массиву еще 50 процентов пустых ячеек, и всегда оставляет хотя бы одну пустую ячейку при любом изменении размера массива. Эти значения были выбраны для упрощения работы пользователя со списком. В реальной программе процент свободной памяти должен быть меньше, а число свободных ячеек — больше. Оптимальными выглядят значения порядка 10 процентов и 10 свободных ячеек. ==========26 Связные списки Другая стратегия используется при управлении связанными списками. Связанный список хранит элементы в структурах данных или объектах, которые называются ячейками (cells). Каждая ячейка содержит указатель на следующую ячейку в списке. Так как единственный тип указателей, которые поддерживает Visual Basic — это ссылки на объекты, то ячейки в связном списке должны быть объектами. В классе, задающем ячейку, должна быть определена переменная NextCell, которая указывает на следующую ячейку в списке. В нем также должны быть определены переменные, содержащие данные, с которыми будет работать программа. Эти переменные могут быть объявлены как открытые (public) внутри класса, или класс может содержать процедуры для чтения и записи значений этих переменных. Например, в связном списке с записями о сотрудниках, в этих полях могут находиться имя сотрудника, номер социального страхования, название должности, и т.д. Определения для класса EmpCell могут выглядеть примерно так: Public EmpName As String Public SSN As String Public JobTitle As String Public NextCell As EmpCell Программа создает новые ячейки при помощи оператора New, задает их значения и соединяет их, используя переменную NextCell. Программа всегда должна сохранять ссылку на вершину списка. Для того, чтобы определить, где заканчивается список, программа должна установить значение NextCell для последнего элемента списка равным Nothing (ничего). Например, следующий фрагмент кода создает список, представляющий трех сотрудников: Dim top_cell As EmpCell Dim cell1 As EmpCell Dim cell2 As EmpCell Dim cell3 As EmpCell ‘ Создание ячеек. Set cell1 = New EmpCell cell1.EmpName = "Стивенс” cell1.SSN = "123-45-6789" cell1.JobTitle = "Автор" Set cell2 = New EmpCell cell2.EmpName = "Кэтс” cell2.SSN = "123-45-6789" cell2.JobTitle = "Юрист" Set cell3 = New EmpCell cell3.EmpName = "Туле” cell3.SSN = "123-45-6789" cell3.JobTitle = "Менеджер" ‘ Соединить ячейки, образуя связный список. Set cell1.NextCell = cell2 Set cell2.NextCell = cell3 Set cell3.NextCell = Nothing ‘ Сохранить ссылку на вершину списка. Set top_cell = cell1 ===============27 На рис. 2.2 показано схематическое представление этого связного списка. Прямоугольники представляют ячейки, а стрелки — ссылки на объекты. Маленький перечеркнутый прямоугольник представляет значение Nothing, которое обозначает конец списка. Имейте в виду, что top_cell, cell1 и cell2 – это не настоящие объекты, а только ссылки, которые указывают на них. Следующий код использует связный список, построенный при помощи предыдущего примера для печати имен сотрудников из списка. Переменная ptr используется в качестве указателя на элементы списка. Она первоначально указывает на вершину списка. В коде используется цикл Do для перемещения ptr по списку до тех пор, пока указатель не дойдет до конца списка. Во время каждого цикла, процедура печатает поле EmpName ячейки, на которую указывает ptr. Затем она увеличивает ptr, указывая на следующую ячейку в списке. В конце концов, ptr достигает конца списка и получает значение Nothing, и цикл Do останавливается. Dim ptr As EmpCell Set ptr = top_cell ‘ Начать с вершины списка. Do While Not (ptr Is Nothing) ‘ Вывести поле EmpName этой ячейки. Debug.Print ptr.Empname ‘ Перейти к следующей ячейке в списке. Set ptr = ptr.NextCell Loop После выполнения кода вы получите следующий результат: Стивенс Кэтс Туле @Рис. 2.2. Связный список =======28 Использование указателя на другой объект называется косвенной адресацией (indirection), поскольку вы используете указатель для косвенного манипулирования данными. Косвенная адресация может быть очень запутанной. Даже для простого расположения элементов, такого, как связный список, иногда трудно запомнить, на какой объект указывает каждая ссылка. В более сложных структурах данных, указатель может ссылаться на объект, содержащий другой указатель. Если есть несколько указателей и несколько уровней косвенной адресации, вы легко можете запутаться в них Для того, чтобы облегчить понимание, в изложении используются иллюстрации, такие как рис. 2.2,(для сетевой версии исключены, т.к. они многократно увеличивают размер загружаемого файла) чтобы помочь вам наглядно представить ситуацию там, где это возможно. Многие из алгоритмов, которые используют указатели, можно легко проиллюстрировать подобными рисунками. Добавление элементов к связному списку Простой связный список, показанный на рис. 2.2, обладает несколькими важными свойствами. Во-первых, можно очень легко добавить новую ячейку в начало списка. Установим указатель новой ячейки NextCell на текущую вершину списка. Затем установим указатель top_cell на новую ячейку. Рис. 2.3 соответствует этой операции. Код на языке Visual Basic для этой операции очень прост: Set new_cell.NextCell = top_cell Set top_cell = new_cell @Рис. 2.3. Добавление элемента в начало связного списка Сравните размер этого кода и кода, который пришлось бы написать для добавления нового элемента в начало списка, основанного на массиве, в котором потребовалось бы переместить все элементы массива на одну позицию, чтобы освободить место для нового элемента. Эта операция со сложностью порядка O(N) может потребовать много времени, если список достаточно длинный. Используя связный список, моно добавить новый элемент в начало списка всего за пару шагов. ======29 Так же легко добавить новый элемент и в середину связного списка. Предположим, вы хотите вставить новый элемент после ячейки, на которую указывает переменная after_me. Установим значение NextCell новой ячейки равным after_me.NextCell. Теперь установим указатель after_me.NextCell на новую ячейку. Эта операция показана на рис. 2.4. Код на Visual Basic снова очень прост: Set new_cell.NextCell = after_me.NextCell Set after_me.NextCell = new_cell Удаление элементов из связного списка Удалить элемент из вершины связного списка так же просто, как и добавить его. Просто установите указатель top_cell на следующую ячейку в списке. Рис. 2.5 соответствует этой операции. Исходный код для этой операции еще проще, чем код для добавления элемента. Set top_cell = top_cell.NextCell Когда указатель top_cell перемещается на второй элемент в списке, в программе больше не останется переменных, указывающих на первый объект. В этом случае, счетчик ссылок на этот объект станет равен нулю, и система автоматически уничтожит его. Так же просто удалить элемент из середины списка. Предположим, вы хотите удалить элемент, стоящий после ячейки after_me. Просто установите указатель NextCell этой ячейки на следующую ячейку. Эта операция показана на рис. 2.6. Код на Visual Basic прост и понятен: after_me.NextCell = after_me.NextCell.NextCell @Рис. 2.4. Добавление элемента в середину связного списка =======30 @Рис. 2.5. Удаление элемента из начала связного списка Снова сравним этот код с кодом, который понадобился бы для выполнения той же операции, при использовании списка на основе массива. Можно быстро пометить удаленный элемент как неиспользуемый, но это оставляет в списке ненужные значения. Процедуры, обрабатывающие список, должны это учитывать, и соответственно быть более сложными. Присутствие чрезмерного количества «мусора» также замедляет работу процедуры, и, в конце концов, придется проводить чистку памяти. При удалении элемента из связного списка, в нем не остается пустых промежутков. Процедуры, которые обрабатывают список, все так же обходят список с начала до конца, и не нуждаются в модификации. Уничтожение связного списка Можно предположить, что для уничтожения связного списка необходимо обойти весь список, устанавливая значение NextCell для всех ячеек равным Nothing. На самом деле процесс гораздо проще: только top_cell принимает значение Nothing. Когда программа устанавливает значение top_cell равным Nothing, счетчик ссылок для первой ячейки становится равным нулю, и Visual Basic уничтожает эту ячейку. Во время уничтожения ячейки, система определяет, что в поле NextCell этой ячейки содержится ссылка на другую ячейку. Поскольку первый объект уничтожается, то число ссылок на второй объект уменьшается. При этом счетчик ссылок на второй объект списка становится равным нулю, поэтому система уничтожает и его. Во время уничтожения второго объекта, система уменьшает число ссылок на третий объект, и так далее до тех пор, пока все объекты в списке не будут уничтожены. Когда в программе уже не будет ссылок на объекты списка, можно уничтожить и весь список при помощи единственного оператора Set top_cell = Nothing. @Рис. 2.6. Удаление элемента из середины связного списка ========31 Сигнальные метки Для добавления или удаления элементов из начала или середины списка используются различные процедуры. Можно свести оба этих случая к одному и избавиться от избыточного кода, если ввести специальную сигнальную метку (sentinel) в самом начале списка. Сигнальную метку нельзя удалить. Она не содержит данных и используется только для обозначения начала списка. Теперь вместо того, чтобы обрабатывать особый случай добавления элемента в начало списка, можно помещать элемент после метки. Таким же образом, вместо особого случая удаления первого элемента из списка, просто удаляется элемент, следующий за меткой. Использование сигнальных меток пока не вносит особых различий. Сигнальные метки играют важную роль в гораздо более сложных алгоритмах. Они позволяют обрабатывать особые случаи, такие как начало списка, как обычные. При этом требуется написать и отладить меньше кода, и алгоритмы становятся более согласованными и более простыми для понимания. В табл. 2.1 сравнивается сложность выполнения некоторых типичных операций с использованием списков на основе массивов со «сборкой мусора» или связных списков. Списки на основе массивов имеют одно преимущество: они используют меньше памяти. Для связных списков необходимо добавить поле NextCell к каждому элементу данных. Каждая ссылка на объект занимает четыре дополнительных байта памяти. Для очень больших массивов это может потребовать больших затрат памяти. Программа LnkList1 демонстрирует простой связный список с сигнальной меткой. Введите значение в текстовое поле ввода, и нажмите на элемент в списке или на метку. Затем нажмите на кнопку Add After (Добавить после), и программа добавит новый элемент после указанного. Для удаления элемента из списка, нажмите на элемент и затем на кнопку Remove After (Удалить после). @Таблица 2.1. Сравнение списков на основе массивов и связных списков =========32 Инкапсуляция связных списков Программа LnkList1 управляет списком явно. Например, следующий код показывает, как программа удаляет элемент из списка. Когда подпрограмма начинает работу, глобальная переменная SelectedIndex дает положение элемента, предшествующего удаляемому элементу в списке. Переменная Sentinel содержит ссылку на сигнальную метку списка. Private Sub CmdRemoveAfter_Click() Dim ptr As ListCell Dim position As Integer If SelectedIndex < 0 Then Exit Sub ‘ Найти элемент. Set ptr = Sentinel position = SelectedIndex Do While position > 0 position = position - 1 Set ptr = ptr.nextCell Loop ‘ Удалить следуюший элемент. Set ptr.NextCell = ptr.NextCell.NextCell NumItems = NumItems - 1 SelectItem SelectedIndex ‘ Снова выбрать элемент. DisplayList NewItem.SetFocus End Sub Чтобы упростить использование связного списка, можно инкапсулировать его функции в классе. Это реализовано в программе LnkList2 . Она аналогична программе LnkList1, но использует для управления списком класс LinkedList. Класс LinekedList управляет внутренней организацией связного списка. В нем находятся процедуры для добавления и удаления элементов, возвращения значения элемента по его индексу, числа элементов в списке, и очистки списка. Этот класс позволяет обращаться со связным списком почти как с массивом. Это намного упрощает основную программу. Например, следующий код показывает, как программа LnkList2 удаляет элемент из списка. Только одна строка в программе в действительности отвечает за удаление элемента. Остальные отображают новый список. Сравните этот код с предыдущей процедурой: Private sub CmdRemoveAfter_Click() Llist.RemoveAfter SelectedIndex SelectedItem SelectedList ‘ Снова выбрать элемент. DisplayList NewItem.SetFocus CmdClearList.Enabled End Sub =====33 Доступ к ячейкам Класс LinkedList, используемый программой LnkLst2, позволяет основной программе использовать список почти как массив. Например, подпрограмма Item, приведенная в следующем коде, возвращает значение элемента по его положению: Function Item(ByVal position As Long) As Variant Dim ptr As ListCell If position < 1 Or position > m_NumItems Then ‘ Выход за границы. Вернуть NULL. Item = Null Exit Function End If ‘ Найти элемент. Set ptr = m_Sentinel Do While position > 0 position = position - 1 Set ptr = ptr.NextCell Loop Item = ptr.Value End Function Эта процедура достаточно проста, но она не использует преимущества связной структуры списка. Например, предположим, что программе требуется последовательно перебрать все объекты в списке. Она могла бы использовать подпрограмму Item для поочередного доступа к ним, как показано в следующем коде: Dim i As Integer For i = 1 To LList.NumItems ‘ Выполнить какие-либо действия с LList.Item(i). : Next i При каждом вызове процедуры Item, она просматривает список в поиске следующего элемента. Чтобы найти элемент I, программа должна пропустить I-1 элементов. Чтобы проверить все элементы в списке из N элементов, процедура пропустит 0+1+2+3+…+N-1 =N*(N-1)/2 элемента. При больших N программа потеряет много времени на пропуск элементов. Класс LinkedList может ускорить эту операцию, используя другой метод доступа. Можно использовать частную переменную m_CurrentCell для отслеживания текущей позиции в списке. Для возвращения значения текущего положения используется подпрограмма CurrentItem. Процедуры MoveFirst, MoveNext и EndOfList позволяют основной программе управлять текущей позицией в списке. =======34 Например, следующий код содержит подпрограмму MoveNext: Public Sub MoveNext() ‘ Если текущая ячейка не выбрана, ничего не делать. If Not (m_CurrentCell Is Nothing) Then _ Set m_CurrentCell = m_CurrentCell.NextCell End Sub При помощи этих процедур, основная программа может обратиться ко всем элементам списка, используя следующий код. Эта версия несколько сложнее, чем предыдущая, но она намного эффективнее. Вместо того чтобы пропускать N*(N-1)/2 элементов и опрашивать по очереди все N элементов списка, она не пропускает ни одного. Если список состоит из 1000 элементов, это экономит почти полмиллиона шагов. LList.MoveFirst Do While Not LList.EndOfList ‘ Выполнить какие-либо действия над элементом LList.Item(i). : LList.MoveNext Loop Программа LnkList3 использует эти новые методы для управления связным списком. Она аналогична программе LnkList2, но более эффективно обращается к элементам. Для небольших списков, используемых в программе, эта разница незаметна. Для программы, которая обращается ко всем элементам большого списка, эта версия класса LinkedList более эффективна. Разновидности связных списков Связные списки играют важную роль во многих алгоритмах, и вы будете встречаться с ними на протяжении всего материала. В следующих разделах обсуждаются несколько специальных разновидностей связных списков. Циклические связные списки Вместо того, чтобы устанавливать указатель NextCell равным Nothing, можно установить его на первый элемент списка, образуя циклический список (circular list), как показано на рис. 2.7. Циклические списки полезны, если нужно обходить ряд элементов в бесконечном цикле. При каждом шаге цикла, программа просто перемещает указатель на следующую ячейку в списке. Допустим, имеется циклический список элементов, содержащий названия дней недели. Тогда программа могла бы перечислять дни месяца, используя следующий код: ===========35 @Рис. 2.7. Циклический связный список ‘ Здесь находится код для создания и настройки списка и т.д. : ‘ Напечатать календарь на месяц. ‘ ‘ first_day — это индекс структуры, содержащей день недели для ‘ первого дня месяца. Например, месяц может начинаться ‘ в понедельник. ‘ ‘ num_days — число дней в месяце. Private Sub ListMonth(first_day As Integer, num_days As Integer) Dim ptr As ListCell Dim i As Integer Set ptr = top_cell For i = 1 to num_days Print Format$(i) & ": " & ptr.Value Set ptr = ptr.NextCell Next I End Sub Циклические списки также позволяют достичь любой точки в списке, начав с любого положения в нем. Это вносит в список привлекательную симметрию. Программа может обращаться со всеми элементами списка почти одинаковым образом: Private Sub PrintList(start_cell As Integer) Dim ptr As Integer Set ptr = start_cell Do Print ptr.Value Set ptr = ptr.NextCell Loop While Not (ptr Is start_cell) End Sub ========36 Проблема циклических ссылок Уничтожение циклического списка требует немного больше внимания, чем удаление обычного списка. Если вы просто установите значение переменной top_cell равным Nothing, то программа не сможет больше обратиться к списку. Тем не менее, поскольку счетчик ссылок первой ячейки не равен нулю, она не будет уничтожена. На каждый элемент списка указывает какой-либо другой элемент, поэтому ни один из них не будет уничтожен. Это проблема циклических ссылок (circular referencing problem). Так как ячейки указывают на другие ячейки, ни одна из них не будет уничтожена. Программа не может получить доступ ни к одной из них, поэтому занимаемая ими память будет расходоваться напрасно до завершения работы программы. Проблема циклических ссылок может встретиться не только в этом случае. Многие сети содержат циклические ссылки — даже одиночная ячейка, поле NextCell которой указывает на саму эту ячейку, может вызвать эту проблему. Решение ее состоит в том, чтобы разбить цепь ссылок. Например, вы можете использовать в своей программе следующий код для уничтожения циклического связного списка: Set top_cell.NextCell = Nothing Set top_cell = Nothing Первая строка разбивает цикл ссылок. В этот момент на вторую ячейку списка не указывает ни одна переменная, поэтому система уменьшает счетчик ссылок ячейки до нуля и уничтожает ее. Это уменьшает счетчик ссылок на третий элемент до нуля, и соответственно, он также уничтожается. Этот процесс продолжается до тех пор, пока не будут уничтожены все элементы списка, кроме первого. Установка значения top_cell элемента в Nothing уменьшает его счетчик ссылок до нуля, и последняя ячейка также уничтожается. Двусвязные списки Во время обсуждения связных списков вы могли заметить, что большинство |
|
