Примеры написания программ

Списки

Цель работы

1. Научиться:

– объявлять шаблоны динамических структур данных;

– объявлять структурные переменные динамически;

– обращаться к полям структуры через адрес структурной переменной;

– передавать адрес структурных переменных в функцию пользователя;

– научиться вызывать функции пользователя из функции main;

2. Составить, выполнить и протестировать указанную задачу с помощью компьютера.

Порядок написания программы

1. Внимательно прочитать условие задачи и формулировку функций.

2. Провести анализ характеристик функций:

Дать название функции;

Выделить список исходных данных функции, определить их типы;

Определить тип результата функции, передаваемого с помощью оператора return.

Определить тип результатов функции, передаваемых с помощью параметров-ссылок.

3. Написать текст функций пользователя.

4. Написать прототипы функций.

5. Написать функцию main с вызовом функции пользователя.

6. Создать проект из файлов с расширением cpp (для функций пользователя и main), и один заголовочный файл с расширением h. Выполнить проект.

Примечание. Вызов функции Rus перед строками-константами с русским текстом осуществляйте самостоятельно.

Примеры написания программ

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

Для простоты структура Info будет состоять из одного целого поля; хотя адрес последнего элемента в списке может быть вычислен, для удобства будем хранить его в отдельной переменной.

Проанализируем функции:

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

Функция add добавляет структуру в конец списка, для этого ей достаточно знать адрес начала списка, но для краткости действий передадим ей адрес последнего элемента в списке, а результатом функции будет новый адрес последнего элемента в списке.

Функция print выводит список на экран, зная адрес начала списка. Результат не возвращается.

В программе используются переменные: pbegin – для хранения адреса начала списка, pend – для хранения адреса последней структуры в списке.

Программа будет строиться в виде проекта.

Текст заголовочного файлаnode.h будет выглядеть так:

#ifndef NODE_H

#define NODE_H

struct Info

{

int d;

};

struct Node

{

Info info;

Node *next;

};

Node * first(void);

Node * add(Node * pend);

void print(Node * pbegin);

#endif

Текст функций пользователябудет выглядеть так:

#include //подключение системных средств для

using namespace std; //возможности использовать потоки ввода-вывода

#include

#include node.h

//Начальное формирование списка

Node * first(void)

{

//Выделяем память под элемент списка

Node * pv=new Node;

cout

cinpv-info.d;

pv-next=0; //Адрес последней структуры в списке — 0

return pv; //возврат адреса начала списка

}

//Добавление элемента в конец списка

Node * add(Node * pend)

{

//Выделяем память под очередной элемент списка

Node * pv=new Node;

cout

cinpv-info.d;

pv-next=0; //Адрес последней структуры в списке — 0

pend-next=pv; //Сцепляем по адресу созданную структуру со списком

return pv; //возврат нового адреса последней структуры в списке

}

//Вывод списка на экран

void print(Node * pbegin)

{

Node * pv=pbegin;

while (pv) //пока адрес текущей структуры списка не 0

{

cout

pv=pv-next; //переход к следующей структуре в списке

}

return;

}

Текст функции mainбудет выглядеть так:

#include //подключение системных средств для

using namespace std; //возможности использовать потоки ввода-вывода

#include node.h

int main(void)

{

Node *pbegin, *pend;

int i;

pend=pbegin=first(); //создали список

for(i=0; i

pend=add(pend);

print(pbegin); //вывели весь список на экран

return 0;

}

Контрольные вопросы и задания

1. Что такое список?

2. Как объявить шаблон списка?

3. Как элементы списка связаны между собой?

4. В чем сходство и различие между массивом структур и списком?

5. Как обратиться к полям элемента списка?

6. Как осуществить перебор элементов списка?

7. Как добавить элемент в список?

8. Как исключить элемент из списка?

9. Когда удобно использовать список и почему?

Задание

Общая формулировка для всех вариантов

Используя в качестве информативной части структуру из предыдущей темы, объявить однонаправленный список. Используйте также необходимую часть кода.

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

После того, как программа заработает, добавьте еще одну функцию, в соответствии с вашим вариантом.

Вариант 1

Написать функцию добавления элемента списка в конец списка, если исходным данным является адрес начала списка.

Вариант 2

Написать функцию добавления элемента списка в начало списка.

Вариант 3

Написать функцию освобождения памяти, занятой списком.

Вариант 4

Написать функцию, в которой элемент с номером К меняется местом с элементом с номером К+1 (за счет изменения адресов). Считать, что К не первый элемент списка, а К+1 – не последний.

Вариант 5

Написать функцию, в которой первый элемент списка меняется местом со вторым элементом (за счет изменения адресов).

Вариант 6

Написать функцию, в которой последний элемент списка меняется местом с предыдущим (за счет изменения адресов).

Вариант 7

Написать функцию, в которой элемент с номером К меняется местом с элементом с номером М (за счет изменения адресов). Считать, что К и М не первый и не последний элементы списка.

Вариант 8

Написать функцию удаления первого элемента списка.

Вариант 9

Написать функцию удаления последнего элемента списка, если исходным данным является адрес начала списка.

Вариант 10

Написать функцию удаления элемента списка при совпадении ключевого поля.

Вариант 11

Написать функции first, add, print для двунаправленного списка. В функции print для каждого текущего элемента выводить предыдущий и последующий.

Вариант 12

Написать функцию add таким образом, что элемент списка добавляется в порядке убывания ключевого поля.

Вариант 13

Написать функцию add таким образом, что элемент списка добавляется в порядке возрастания ключевого поля.

Вариант 14

Написать функцию поиска адреса элемента списка с заданным ключевым полем. Если элемент не найден – передать в качестве результата NULL.

Вариант 15

Написать функцию вставки элемента списка после элемента с заданным ключом.

Вариант 16

Написать функцию вставки элемента списка до элемента с заданным ключом.

Статьи к прочтению:

Пример простой программы на Java

Похожие статьи: