Курс лекций мдк 01. 02 «Прикладное программирование» пм 01 «Разработка программных модулей программного обеспечения для компьютерных систем»

Рис. 1 Первый элемент в связанном списке.

Предположим, что пользователь вводит еще информацию о фильме. Программа выделяет память для второй структуры film, сохраняя адрес новой структуры в элементе next первой структуры (замещая значение NULL , хранившееся здесь ранее), чтобы указатель next одной структуры указывал на следующую структуру в связанном списке. Этот список показан на рисунке.

2240

2240

Modern Times

10

2360

head

название

рейтинг

next

2360

Titanic

12

NULL

название

рейтинг

next

Рис. 2 Связанный список с двумя элементами.

Каждый новый фильм

будет отображаться таким же образом. Его

адрес будет сохраняться в предшествующей структуре, новая информация будет записываться в новую структуру, а элемент структуры next будет устанавливаться в NULL.

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

Все что требуется для проекта описания фильмов - это список элементов. Каждый элемент содержит название фильма и рейтинг. Необходимо иметь возможность добавлять новые элементы к концу списка и отображать его содержимое. Назовем абстрактный тип, который будет выполнять эти задачи, list. Какими свойствами должен обладать список? Ясно, что он должен быть способным содержать последовательность элементов. Иначе говоря, список может содержать несколько элементов, и эти элементы должны каким-то образом быть упорядочены, чтобы можно было говорить о первом элементе в списке, о втором или о последнем. Далее, тип списка должен поддерживать такие операции, как добавление элемента в список.

Ниже приведены некоторые операции:

11

• 
  Инициализация пустого списка.
  
• 
  Добавление элемента в конец списка.
  
• 
  Определение того, является ли список пустым.
  
• 
  Определение того, является ли список заполненным.
  
• 
  Определение количества элементов в списке.
  

• 
  Обращение к каждому элементу списка для выполнения какого-либо действия.
  
• 
  Вставка элемента в любое место списка.
  
• 
  Удаление элемента из списка.
  
• 
  Замена одного элемента списка другим.
  

• 
  Поиск элемента в списке
  

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

Вот как выглядит краткое описание типа: