Реализация основных алгоритмов. Практическое занятие 1

Август 1, 2022

Главная
Информатика
Реализация основных алгоритмов. Практическое занятие 1

Содержание

2. Основные термины 1. Информация в таблице представлена множеством узлов (записей, объектов, элементов). Узел обозначается так: 2.
3. Определение линейного списка Линейный список – это множество, состоящее из n≥0 узлов: x[0], …, x[n-1], структурные
4. Организация хранения данных Для хранения данных целесообразно использовать следующую конструкцию: struct list { int inf; //информационная
5. Генерация псевдослучайных чисел Используется команда rand() Заголовочный файл Для того, чтобы генератор каждый раз начинал генерацию
6. Создание линейного списка n=7; list *first=new list; list *p=first; cin>>p->inf ; for (int i=0; i p->next=new
7. Печать линейного списка p = first; while (р) { cout inf р = p->next; } cout
8. Создание пользовательского интерфейса int num = 1; while (num) { cin >> num; switch (num) {
9. Вставка элемента в начало списка list * q = new list; cin >> q->inf; q->next =
10. Включение элемента в середину (после i-го элемента) p = first; int k = 2; for (i=0;
11. Удаление элемента из середины (i-го элемента) k = 2; p = first; for (i=0; i p
12. Создание копии списка p = first; list *newlist =new list; newlist->inf = p->inf; p = p->next;
14. Скачать презентацию

Слайд 2

Основные термины
1. Информация в таблице представлена множеством узлов (записей, объектов, элементов).
Узел

обозначается так:
2. Каждый узел состоит из одного или нескольких последовательных слов в памяти машины, разделенных на именуемые части, называемые полями.
3. Адресом узла является адрес первого слова в узле (связь, указатель, ссылка, стрелка на узел).
Для обозначения пустой связи используется:

Слайд 3

Определение линейного списка
Линейный список – это множество, состоящее из n≥0 узлов:

x[0], …, x[n-1], структурные свойства которого ограничиваются условиями:
если n≥0, то x[0] является первым
если 0

Слайд 4

Организация хранения данных
Для хранения данных целесообразно использовать следующую конструкцию:
struct list {
int

inf; //информационная часть
list * next; //ссылка на следующий элемент
};
list * first;

Слайд 5

Генерация псевдослучайных чисел
Используется команда rand()
Заголовочный файл
Для того, чтобы генератор каждый

раз начинал генерацию с нового числа, необходимо подключить заголовочный файл
Для получения различных чисел: srand((unsigned)time(0));
Для генерации целого числа от a до b int irand(int a, int b) { return rand() % (b-a+1)+a; }
Пример: получить псевдослучайное число от -7 до 4 irand(-7, 4)

Слайд 6

Создание линейного списка
n=7;
list first=new list;
list p=first;
cin>>p->inf ;
for

(int i=0; i p->next=new list ;
p=p->next ;
cin>>p->inf;
}
p->next=0;

Здесь описано построение линейного списка из n (n=7) элементов.
Элементы списка вводятся с клавиатуры.
cin - заставляет программу ожидать ввода числа от пользователя.
Cin – объект, определенный в С++ для работы со стандартным потоком ввода.
>> - операция извлечения.
Приведенный код удобно использовать, когда число элементов в списке известно заранее.
Подумайте, как нужно модифицировать программу, чтобы она работала для произвольного числа элементов.

Слайд 7

Печать линейного списка
p = first;
while (р)
{
cout <<

p->inf << “ “ ;
р = p->next;
}
cout << endl;

Данный код работает для произвольного числа элементов в списке.
Идентификатор cout является объектом С++, предназначенным для работы со стандартным потоком вывода.
Оператор << называется операцией вставки.
Манипулятор endl – вставка в символьный поток символа окончания строки.
Манипулятор - это особая инструкция, обращенная к потоку и предназначенная для изменения вывода.

Слайд 8

Создание пользовательского интерфейса
int num = 1;
while (num) {
cin

>> num;
switch (num) {
case 0: break;
case 1: {
//ввод списка
break; }
case 2: {
//вывод списка
break; }
default: cout << “Error!” << end l;
}
}

Слайд 9

Вставка элемента в начало списка
list * q = new list;
cin

>> q->inf;
q->next = first;
first = q;

Рассмотрен случай, когда список не пуст.

first

элемент для вставки

Слайд 10

Включение элемента в середину (после i-го элемента)
p = first;
int k =

2;
for (i=0; i p = p->next;
list *w=new list;
cin >> w->inf ;
w->next = p->next;
p->next = w;

Рассмотрен случай, когда список не пуст.

first

Слайд 11

Удаление элемента из середины (i-го элемента)
k = 2;
p = first;

for (i=0; i p = p->next;
w = p->next;
p->next = w->next;
delete w;

Используется отдельная переменная для сохранения удаляемого элемента.
Это необходимо для того, чтобы память не оставалась помеченной как занята программой.

first

удаляемый элемент

Слайд 12

Создание копии списка
p = first;
list *newlist =new list;
newlist->inf =

p->inf;
p = p->next;
list *newfirst = newlist;
while (p) {
newlist->next = newlist;
newlist = newlist->next;
newlist->inf = p->inf;
p = p->next ;
}
newlist->nex t = 0;

Создание копии списка происходит фактически (а не только созданием нового начала и присоединения к нему остатка списка).
Код работает, только если список содержит хотя бы 1 элемент.

Реализация основных алгоритмов. Практическое занятие 1

Содержание

Основные термины1. Информация в таблице представлена множеством узлов (записей, объектов, элементов).Узел

Определение линейного спискаЛинейный список – это множество, состоящее из n≥0 узлов:

Организация хранения данныхДля хранения данных целесообразно использовать следующую конструкцию:struct list { int

Генерация псевдослучайных чиселИспользуется команда rand()Заголовочный файл Для того, чтобы генератор каждый

Создание линейного спискаn=7; list *first=new list; list *p=first; cin>>p->inf ; for

Печать линейного спискаp = first; while (р) { cout <<

Создание пользовательского интерфейсаint num = 1; while (num) { cin

Вставка элемента в начало спискаlist * q = new list; cin

Включение элемента в середину (после i-го элемента)p = first;int k =

Удаление элемента из середины (i-го элемента)k = 2; p = first;

Создание копии спискаp = first; list *newlist =new list; newlist->inf =

Похожие презентации

Основные термины
1. Информация в таблице представлена множеством узлов (записей, объектов, элементов).
Узел

Определение линейного списка
Линейный список – это множество, состоящее из n≥0 узлов:

Организация хранения данных
Для хранения данных целесообразно использовать следующую конструкцию:
struct list {
int

Генерация псевдослучайных чисел
Используется команда rand()
Заголовочный файл
Для того, чтобы генератор каждый

Создание линейного списка
n=7;
list first=new list;
list p=first;
cin>>p->inf ;
for

Печать линейного списка
p = first;
while (р)
{
cout <<

Создание пользовательского интерфейса
int num = 1;
while (num) {
cin

Вставка элемента в начало списка
list * q = new list;
cin

Включение элемента в середину (после i-го элемента)
p = first;
int k =

Удаление элемента из середины (i-го элемента)
k = 2;
p = first;

Создание копии списка
p = first;
list *newlist =new list;
newlist->inf =