Отправляет email-рассылки с помощью сервиса Sendsay

C и C++ для начинающих

Рассылка закрыта

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Июнь 2001   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор Гость

Статистика

8.368 подписчиков
за неделю
←   Все выпуски   →

C и C++ для начинающих - Выпуск 12. Связные спсики (часть 2)


Служба Рассылок Subscribe.Ru проекта Citycat.Ru
C и C++ для начинающих. Выпуск 12 от 4.06.2001.

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

Разбор полетов

11. 1. Итак, разберемся все же, что за исходник был в 11-м выпуске.

Все наши функции манипулируют связным списком. Он характеризуется указателем на свой первый элемент. А так как он по ходу дела может меняться (скажем, мы добавили элемент в самое начало списка или удалили самый первый элемент), то и указатель на первый элемент по ходу манипуляции со списком также будет меняться. Поэтому в качестве первого параметра для всех функций используется struct TElem **List. Строго говоря, для функции, осуществляющей чтение, это необязательно, но я решил унифицировать параметры функций. Кроме того, я думаю, что мало кто будет работать со связным списком - константой.

В фунции InsertElem первым делом создается требуемый элемент. После этого идет анализ. Если список пуст (т.е. NULL), то после добавления весь список будет состоять из одного только свежедобавленного элемента. Обратите внимание, NULL в поле Next указывает на отсутствие следующего элемента, другими словами - на конец списка. Если же элементы в списке уже есть, то нам следует найти элемент, после которого следует вставить добавляемый. Если мы вставляем элемент в самое начало, то требуемого элемента нет и мы просто связываем элемент со всем списком: теперь поле Next нового элемента указывает на бывший первый элемент (а ныне второй), а указатель на список теперь указывает на добавленный элемент. Если же мы вставляем элемент в другую позицию, то нам следует найти тот элемент, после которого требуется вставить новый (у нас это элемент Cur), и изменить ссылки: Cur->Next теперь указывает на NewElem, а NewElem->Next - на бывший Cur->Next.

Обратите внимание на конструкцию 
    for (Cur = *List; --Place && Cur->Next; Cur = Cur->Next);
Она выполняет две функции: осуществляет поиск необходимого элемента и еще раз демонстрирует вам, что цикл for в C существенно мощнее, чем в остальных языках :-) Итак, остановлюсь на нем еще раз более подробно. Нам нужно найти в списке элемент под индексом (Place - 1). При инициализации цикла мы устанавливаем Cur на начало списка, а затем передвигаемся по нему (Cur = Cur->Next), пока Place не станет равной нулю. При этом мы также уменьшаем Place на единицу (обратите внимание на префиксную форму записи: можно было использовать и постфиксную, но при этом потребовалось бы уменьшить Place на единицу в инициализации цикла). Также предусмотрена проверка: если мы добрались до последнего элемента списка (Cur->Next == NULL), то цикл можно (и нужно!) остановить.

С помощью этого условиея мы и реализуем добавление элемента в самый конец списка, если Place == -1: ведь в таком случае мы, дальше уменьшая его, никогда не приведем его к нулю (тут делается допущение, что количество элементов в списке будет меньше, чем 232). Такое же поведение будет, если Place будет больше, чем количество элементов в списке.

Функция RemoveElem имеет сходное строение. Но так как ее действие - удаление элемента, то она не делает никаких допущений. Если мы задали неверный индекс удаляемого элемента, то список просто останется без изменений. Также имеет смысл ввести некоторое значение статуса: если элемент удален, то возвращается 1, если нет, то 0. (Для InsertElem код возврата не требовался - она всегда добавляла элемент). Это достаточно удобно для применения в таких конструкциях: 
 if (!RemoveElem (&List, 4))
 {
  printf ("Ошибка: невозможно удалить элемент\n");
  return 0;
 }
Итак, разберемся теперь в ней. Если функция InsertElem сперва создает элемент, а потом включает его в список, то RemoveElem сперва исключает элемент из списка, а потом удаляет его. Но если в списке был только один элемент, то после удаления список будет пуст - так что присвоим ему NULL (разумеется, сохранив перед этим указатель на элемент - нам же надо будет его как-то удалять). В противном случае опять-таки проверим, является ли удаляемый элемент первым. Если да, то теперь указатель на список - это просто указатель на его второй элемент. Если нет, то схожей конструкцией найдем элемент под индексом (Place - 1) (он опять будет в Cur) и изменим ссылки: Cur->Next = Cur->Next->Next. Теперь в списке в любом случае нет ссылок на удаляемый элемент и его можно смело удалять.

Да, вообще-то в функцию RemoveElem следовало бы встроить проверку, не пуст ли список, из которого следует ли удалять. Но я просто забыл об этом, когда писал функцию. Что ж, придется за меня это сделать вам - пусть это будет ваше домашнее задание 12.1. (первая часть).

Теперь о функции GetElem. (Извиняюсь, перепутал комментарии к ней. Ошибки в программе можно отследить компилятором, а вот ошибки в пояснениях к ней - нет :-( Надеюсь, все догадалить, что это функция получения элемента, а не удаления). Она еще проще остальных: мы уже ищем элемент с индексом Place, поэтому префиксная форма декремента изменилась на постфиксную. Кроме того, описанная проверка на существование списка уже не нужна: она встроена в цикл for. Если мы нашли элемент, мы копируем его части в соответвтвующие переменные, если не нашли - возвращаем 0.

Теперь еще предолжения по улучшению: нам не всегда необходимо узнавать весь элемент целиком - иногда достаточно одного какого-то его значения. Измените функцию GetElem так, чтобы она допускала передачу параметра NULL в качестве Int1, Int2 или Float, который обозначал бы, что получение данной части элемента не требуется (это вторая часть задания 12.1.)

И наконец последняя функция DeleteList удаляет весь список целиком - ее следует вызвать тогда, когда он вам больше не потребуется, для того, чтобы освободить оперативную память (еще раз напомню для тех, у кого ее 512 Mb: это необходимо и обязательно. А вдруг вашу программу будут гонять 6 часов на машине с 4 Mb памяти? Вот и забьете память до отказа).

Функция main ясна и пояснений не требует.

Программирование

Итак, мы с вами рассмотрели очень важную конструкцию - однонаправленный связный список общего вида. Вместе с тем существуют и другие виды списков:
  • Двунаправленный список - это список, в котором в каждом элементе наряду с указателем на следующий элемент присутствует указатель на предыдущий элемент. У него, конечно, есть недостаток - каждый элемент занимает в памяти на 4 байта больше, чем предыдущий. В связи с этим не стоит создавать список char'ов. Но есть и достоинства - такой список можно читать в обоих направлениях (одинарный список хорошо читается в одном направлении и очень плохо в другом), для работы с ним достаточно одного указателя. Разумеется, с ним несколько сложнее обращаться, но вы как программист должны взять это на себя.

  • Кольцевой список - разновидность однонаправленного списка, в котором последний элемент указывает не на NULL, а на первый элемент. Таким образом образуется кольцо из элементов. Находит применение, скажем, в списках элементов окна. Разумеется, манипуляции с ним проходят несколько по-другому.

  • Очередь - это и есть описанная в 11-м выпуске очередь в чистом виде. Она является сильно упрощенной разновидностью связного списка - для нее разрешено только добавление элемента в самый конец (хвост) очереди и извлечение элемента из начала (головы) очереди. Извлечение элемента влечет за собой его удаление. В некоторых реализациях предусмотрен "просмотр" элемента (т.н. peek) - получение первого элемента очереди без его удаления. Очередь реализует принцип FIFO (First In First Out - первым пришел, первым ушел). Применяется, например, при организации списка событий - пришедшее первым нажатие клавиши должно быть обработано первым.

  • Стек можно представить в виде запаянной с одного конца трубочки, в которую помещаются шарики (элементы стека). Понятно, что поместив такой шарик в стек, мы не сможем получить доступ к оствльным элементам, пока не вытащим его. Формализую: стек - это разновидность однонаправленного списка, для которого разрешено только добавление элемента в начало (голову) стека и удаление элемента из головы же. Для работы со стеком достаточно одного указателя на голову. Стек реализует принцип LIFO (Last In First Out - последним пришел, первым ушел).

  • Дерево является очень специфическим видом списка - каждый элемент ссылается не на один, а на несколько следующих. Наибольшее распространение получили бинарные деревья, в которых каждый элемент (элементы дерева называются узлами) ссылается на два своих подузла. Добавление элементов в дерево разрешается лишь один из его многочисленных концов (листьев). Удаление - даже не знаю, никогда не сталкивался... Деревья хорошо обрабатываются рекурсивными алгоритмами (каждый узел дерева - сам по себе дерево).

Вообще целесообразно иметь один хорошо написанный универсальный двунаправленный список и использовать его при необходимости. Что должно быть элементом такого списка? Разумеется, void*. Таким образом создавать элемент мы должны сами - соответствующие функции Insert и Remove будут лишь связывать его в список. Я предлагаю такой список функций: 
 struct TElem
 {
  void *Item;
  struct TElem *Next, *Prev;
 }

 void  InsertBefore    (struct TElem *Elem, void *NewItem);
 void  InsertAfter     (struct TElem *Elem, void *NewItem);
 void  RemoveElem      (struct TElem *Elem);
 struct TElem *Advance (struct TElem *Elem, int Count);
 void *GetItem         (struct TElem *Elem);
 void  DeleteList      (struct TElem *Elem);
Теперь более подробно о каждой из функций.
  • InsertBefore и InsertAfter - создают элемент со значением Item и помещают соответственно перед или после элемента Elem. Если Elem == NULL, то создается список из одного элемента - Item.

  • RemoveElem - удаляет из списка элемент Elem.

  • Advance - продвигается в списке на |Count| позиций от элемента Elem вперед, если Count > 0, и назад, если Count < 0. Если имеет место выход за границы списка, функция возвращает NULL, в противном случае - указатель на соответствующий элемент списка.

  • GetItem - возвращает поле Item элемента Elem.

  • DeleteList - удаляет весь список по любому его элементу.

Вы можете спросить, зачем нужна функция GetItem, ведь можно и самому прочитать поле Item. Отвечаю: читать поле Item нельзя. В нашем конкретном случае, конечно, этим можно пренебречь, но вообще-то правила написания программ требуют, чтобы все взаимодействия объекта с внешним миром должны осуществляться через функциональный интерфейс. А мы уже сделали полноценный объект - связный список. В противном случае, если кто угодно сможет изменять любые поля объекта, корректная работа может стать невозможной. Поэтому сразу приучайтесь писать хорошо. Когда мы начнем классы, это умение вам сильно понадобится.

Осталась одна маленькая деталь: написать реализацию всего вышеперечисленного. Эту задачу я доверяю вам - напишите сами эти функции, отладьте, оттестируйте и используйте! Этот список вам еще поможет. Это и будет ваше домашнее задание 12.2.

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

За сим на сегодня все. Домашнее задание вы получили. До встречи!

Ведущий рассылки, av

Архив рассылки Подписаться Статистика рассылки Форум
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться Relayed by Corbina
Рейтингуется SpyLog
В избранное