Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

43

Методические указания к лабораторной работе № 8 по курсу

ОСНОВЫ ПРОГРАММИРОВАНИЯ

ГУИМЦ

"Списки - структуры данных в СИ"

( 8 часов)

Москва, МГТУ, СУЦ - 2014 год

_____________________________________________________________________________________________

СОДЕРЖАНИЕ

1. Цель лабораторной работы № 8 по дисциплине ОП (Основы программирования) - СУЦ 5

2. Порядок выполнения лабораторной работы 5

3. Основные понятия 5

3.1. Списки понятие 5

3.2. Особенности структур списков и их назначение 6

3.3. Особенности списков по сравнению с массивами 7

3.4. Простейший список, созданный вручную 7

3.5. Структуры списков и связь элементов списков 7

3.6. Структура элемента списка с вложенными и внешними данными 9

3.7. Однонаправленные и двунаправленные списки 9

3.8. Статические и динамические списки 10

3.9. Операции для работы со списком 11

3.10. Ручная работа с однонаправленным списком 11

3.11. Добавление в голову списка 12

3.12. Добавление в конец списка (в хвост) 13

3.13. Функция распечатки однонаправленного списка 13

3.14. Удаление из головы списка 14

3.15. Удаление из хвоста списка 15

3.16. Очистка статического списка 16

3.17. Простая ручная работа с динамическим списком 16

3.18. Простая ручная работа с двунаправленным списком 18

4. Примеры программы с использованием файлового ввода и вывода 21

4.1. Примеры, описанные в теоретической части ЛР 21

4.2. Структуры данных для примеров с однонаправленными списками 22

4.3. Функции для работы с однонаправленным списком 22

4.4. Функции вставки и удаления по номеру в однонаправленном списке 24

4.5. Замена двух элементов по номеру в однонаправленном списке 25

4.6. Замена двух элементов по адресу в однонаправленном списке 27

4.7. Описание структур и основных функций для двунаправленного списка 27

4.8. Создание, заполнение и распечатка двунаправленного списка 29

4.9. Сумма целочисленных переменных списка 30

4.10. Сумма и печать переменных списка с вложенной структурой 31

4.11. Печать переменных списка с внешними данными (указатель на структуру) 31

4.12. Печать переменных списка с динамическими данными void 32

5. Контрольные задания ЛР №7. 33

5.1. Создать однонаправленный список вручную 33

5.2. Распечатать однонаправленный список 33

5.3. Создать функцию для распечатки списка 33

5.4. Создать функцию для добавления элементов в однонаправленный список (голова) 33

5.5. Создать функцию для добавления элементов в однонаправленный список (хвост) 33

5.6. Выполнить удаление элементов из списка 33

5.7. Создать функцию очистки списка 34

5.8. Написать программу для поиска экстремального элемента списка 34

5.9. Выполнить сложение двух списков 34

6. Варианты заданий для студентов СУЦ. 34

7. Дополнительные требования для студентов СУЦ (д.т.). 35

7.1. Создать функцию для добавления элементов по номеру в двунаправленном списке 35

7.2. Создать функцию для обмена элементов в двунаправленном списке 35

7.3. Отсортировать список по числовому параметру из структуры 35

7.4. Создать функцию для сортировки элементов по номеру 35

7.5. Создать двунаправленный список вручную – вложенные в элемент данные 35

7.6. Записать данные из двунаправленного списка в файл 35

7.7. Прочитать данные из файла в двунаправленный список 35

8. Демонстрация, защита ЛР и отчет по ЛР. 35

9. Контрольные вопросы по ЛР. 35

10. Литература. 36

11. Приложение: фрагменты программ для работы со списками 38

11.1. Структуры данных для примеров 38

11.2. Функция инициализации элемента и списка 38

11.3. Распечатка двунаправленного списка 38

11.4. Добавление в голову двунаправленнного списка список 39

11.5. Добавление в хвост двунаправленнного список 39

11.6. Добавить после заданного номера в двунаправленный список 40

11.7. Удаление из головы двунаправленного списка 40

11.8. Очистка списка двунаправленного списка 41

11.9. Удаление из хвоста двунаправленного списка 41

11.10. Удаление по значению номера в ддвунаправленном списке 41

11.11. Получить из списка элемент по номеру 42

11.12. Обмен в списке 2-х элементов по номеру 42

11.13. Сортировка двунаправленного списка 43

11.14. Сумма элементов двунаправленного списка 43

11.15. Генерация случайных данных и заполнение двунаправленного списка 44

11.16. Распечатка двунаправленного списка с хвоста 44

11.17. Очистка динамического двунаправленного списка 44

11.18. Минимум переменных списка, номер и адрес 44

11.19. Поиск переменных списка по ключу 44

1 Цель лабораторной работы № 8 по дисциплине ОП (Основы программирования) - СУЦ

Целью данной ЛР по дисциплине ОП является получение навыков работы со списками и списковыми структурами при программировании на языке СИ. Студенты используют консольные проекты и отлаживают программы в среде программирования MS VS 2005/2008/2010. Студенты знакомятся с основными операциями при работе со списками, способами их заполнения, распечатки, сортировки, проверяют работу отлаженных примеров и делают контрольные задания. Они выполняют отладку программы по своему варианту и получают исполнимую программу, готовую к выполнению, оформляют отчет по ЛР и защищают его.

2 Порядок выполнения лабораторной работы

1. Познакомиться с методическими указаниями и основными понятиями данной ЛР

2. Проработать порядок выполнения работы.

3. Создать консольные проекты для проверки примеров и выполнения задания ЛР.

4. Проверить в данном проекте примеры из методических указаний, выполнив их в отладчике в пошаговом режиме.

5. Написать программу задания ЛР по варианту, выданному преподавателем и отладить ее.

6. Продемонстрировать работу программы преподавателю в режиме отладчика по шагам и изменяемыми переменными.

7. Подготовить отчет по шаблону.

8. Защитить ЛР с предоставлением отчета и ответами на контрольные вопросы.

9. Для продвинутых студентов выполнить задания для дополнительных (необязательных) требований и также отобразить их в отчете по ЛР.

3 Основные понятия

В теоретической части описания лабораторной работы вводятся основные понятия и рассматриваются принципы для работы со списками на языке программирования СИ.

4 Понятие список

С
писок – это структура данных, в которой данные расположены в определенной последовательности, которая задается с помощью адресации. Для этой цели используются переменные типа указатель. Каждый фрагмент (элемент списка) должен содержать такой указатель и непосредственно информацию списка. На рисунке представлен список, содержащий целые значения. Более подробно структуру списка рассмотрим ниже. Отдельный элемент списка описывается с помощью структурной переменной или объекта (в СИ++). Для примера, простейший элемент списка может на СИ выглядеть так (информация – простая целая переменная ListVal):

// Структура самого простого элемента списка

struct Elem{

Elem * pNext; // адрес следующего элемента списка (Заметьте, указатель имеет тип (Elem *))

int ListVal; // информация, содержащаяся в списке

};

…

// Описание и инициализация элемента LFirst

Elem LFirst = { NULL , 3 }; // NULL – нулевой указатель – нет ссылки на другие элементы

// Значение ListVal = 3

5 Особенности структур списков и их назначение

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

• Простые переменные стандартного типа (int, char , float и т.д.);

• Группы простых переменных (рис. (б));

• Структурные переменные (рис. (в));

• Указатели на структурные переменные (рис. (г));

• Массивы простых и структурных переменных и указатели на них (рис. (г));

• Указатели на другие списки (рис. (д));

Н
а рисунке представлены разные варианты построения элементов списков. Поясним содержание рисунка.

Вариант (а) представляет общий вид отдельного элемента списка. Вариант (б) показывает список с простыми переменными разного типа (Фамилия и дата рождения). Вариант (в) описывает элемент списка с вложенной в него структурой (Student). Вариант (г) иллюстрирует использование указателя на структуру или массивы структур, а вариант (д) может быть использован для построения сложных структур данных со ссылками на списки, например деревьев.

6 Особенности списков по сравнению с массивами

Встает вопрос, у нас уже есть структуры данных типа массив, зачем нам понадобились списки? В чем-то массивы оказываются неэффективными! В первую очередь недостатки массивов заключаются в том, что трудно вставлять новые элементы в массивы и удалять существующие элементы из массива. Кроме этого, несмотря на динамические возможности ( использование динамической памяти) в любой момент времени размер массива должен быть фиксированным. Списки позволяют более эффективно использовать память компьютера. Списки позволяют более полно использовать механизмы динамической памяти: и список и его элементы могут быть динамическими. Эти ограничения снимаются с использованием структур типа список, хотя добавляются и новые недостатки, в частности: трудно получить доступ к элементу списка по номеру. Эти особенности и проблемы мы рассмотрим ниже.

7 Простейший список, созданный вручную

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

// Структура самого простого элемента списка

struct Elem{

Elem * pNext; // адрес следующего элемента списка (Заметьте, указатель имеет тип (Elem *))

int ListVal; // информация, содержащаяся в списке

};

…

// Описание и инициализация элементов списка – трех:

Elem LE3 = { NULL , 3 }; // NULL – нулевой указатель – нет ссылки на другие элементы

Elem LE2 = { &LE3 , 2 }; // &LE3 - задание адреса третьего элемента в pNext

Elem LE1 = { &LE2 , 1 }; // &LE2 - задание адреса второго элемента в pNext

С таким списком уже можно работать, например, его распечатать:

// Печать

printf ("Печать списка в цикле: \n" );

Elem * pETemp = &LE1; // Во временную переменную - указатель задаем адрес первого элемента

while ( pETemp != NULL)

{

printf ("Элемент простого списка Elem: %d \n" , pETemp->ListVal);

pETemp = pETemp->pNext; // НАВИГАЦИЯ: Важнейщий оператор для работы со списком

};

Результат работы фрагмента программы:

Печать списка в цикле:

Элемент простого списка Elem: 1

Элемент простого списка Elem: 2

Элемент простого списка Elem: 3

8 Структуры списков и связь элементов списков

Однако при программировании возникает необходимость нахождения первого элемента списка для начала работы со списком. То есть нужно хранить адрес первого элемента в отдельной переменной. Такая переменная, содержащая адрес первого элемента списка часто называется головой списка. Она может быть задана типом либо указатель на элемент (Elem * - pHead), либо задаваться самим типом элемент списка (Elem Head). Выбор способа задания головы списка часто зависит от характера решаемой задачи и удобства работы со списком. В некоторых задачах со списками, необходимо знать какой из элементов списка является последним (хвост). В частности это важно для добавления в конец списка (в хвост) или организации двунаправленных списков (о них речь пойдет позднее). Для этого предусматривают также специальный указатель (Elem * - pTail) или специальную переменную - элемент списка (Elem Tail). Кроме этого, в некоторых случаях важно знать текущее число элементов списка (списки – динамические структуры данных). Для этого можно ввести специальную переменную целого типа (nCount). Для связи списков используется в отдельных элементах специальное поле – указатель на следующий элемент (Elem * - pNext). На рисунке, представленном ниже показаны рассмотренные выше элементы списков:

Т
аким образом, для описания отдельного списка целесообразно выделить специальную структуру данных типа:

struct EList{ // Простейшая структура список Elem - элементарный список

Elem * pHead; // Голова списка

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов книги