Добавлен: 21.10.2018
Просмотров: 1308
Скачиваний: 21
1
Контрольная работа по дисциплине «Алгоритмы и структуры данных»
1. Выбрать тип списка по варианту.
2. Выбрать тип хранимых данных.
3. Сформировать тип звена списка для заданного типа списка.
4. Выбрать из имеющегося набора процедуру добавления звена для заданного типа списка.
5. Выбрать из имеющегося набора процедуру удаления звена для заданного типа списка.
6. Выбрать из имеющегося набора процедуру поиска звена для заданного типа списка.
7. Разработать процедуру просмотра списка.
8. Создать ведущее звено для заданного типа списка.
9. Выбрать из имеющегося набора процедуру сортировки массива по варианту.
Вариант выбирается по двум последним цифрам номера студенческого билета AB.
Хранящиеся в списке данные выбираются по сумме цифр A и B (см. таблицу), если A+B = 0, то
выбирается вариант 10:
1 Целые числа (int)
10 Знаковые целые числа (signed int)
2 Знаковые символы (signed char)
11 Беззнаковые целые числа (unsigned int)
3 Длинные целые числа (long)
12 Длинные беззнаковые целые числа
4 Действительные числа (float)
13 Действительные числа (long float)
5 Действительные числа (long double)
14 Знаковые символы (signed char)
6 Короткие целые числа (short)
15 Беззнаковые целые числа (unsigned int)
7 Действительные числа (double)
16 Действительные числа (float)
8 Символы (char)
17 Короткие целые числа (short)
9 Беззнаковые символы (unsigned char)
18 Действительные числа (double)
Тип списка определяется по младшей цифре 4-ричного кода, соответствующего сумме цифр
A и B.
(A+B)
4
Тип списка
0
1
2
3
Односвязный кольцевой
Односвязный линейный
Двусвязный кольцевой
Двусвязный линейный
2
Соответствие между 10-тичным и 4-ричным кодами приведено в таблице
(A+B)
10
0 1
2
3
4
5
6
7
8
9
10
11 12 13 14 15 16 17 18
(A+B)
4
0
1
2
3
10 11 12 13 20 21
22
23 30 31 32 33 40 41 42
Метод сортировки определяется по B (последняя цифра номера), если B больше 4, то по B – 5:
B Метод сортировки
0 Отбор
1 Вставка
2 Пузырьковая
3 Быстрая сортировка
4 Метод Шелла
Показанные процедуры работы со списками и сортировки приведены только в качестве образца
и могут не совпадать по именам типов, переменных и типам полей записей с выбранными
студентом.
Процедуры добавления звена
void i1(Link* Pred, int data)
{
Link* Loc = new Link;
Loc->Value = data;
Loc->next = Pred->next;
Pred->next = Loc;
}
void i2(Link* Pred, int data)
{
Link* Loc = new Link;
Loc->Value = data;
Loc->next = Pred->next;
Loc->prev = Pred;
Pred->next = Loc;
if (Loc->next)
Loc->next->prev = Loc;
}
3
void i3(Link* Pred, int data)
{
Link* Loc = new Link2;
Loc->Value = data;
Loc->next = Pred->next;
Loc->prev = Pred;
Pred->next = Loc;
Loc->next->prev = Loc;
}
Процедуры удаления звена
void d1(Link* Pred)
{
Link* Loc;
if (Pred->next)
{
Loc = Pred->next;
Pred->next = Loc->next;
delete Loc;
}
}
void d2(Link* Pred)
{
Link* Loc;
Loc = Pred->next;
Pred->next = Loc->next;
delete Loc;
}
4
void d3(Link* Del)
{
Del->prev->next = Del->next;
if (Del->next)
Del->next->prev = Del->prev;
delete Del;
}
void d4(Link* Del)
{
Del->prev->next = Del->next;
Del->next->prev = Del->prev;
delete Del;
}
Процедуры поиска звена
int p1(Link* Start, Link*& Find, Link*& Pred, int Key)
{
Link* Cur = Start->next;
Pred = Start;
int Success = 0;
while (Cur && !Success)
{
if (Cur->Value == Key)
{
Find = Cur;
Success = 1;
break;
}
Pred = Cur;
Cur = Cur->next;
}
return Success;
}
5
int p2(Link* Start, Link*& Find, Link*& Pred, int Key)
{
Link* Cur = Start->next;
Pred = Start;
int Success = 0;
while (Cur != Start && !Success)
{
if (Cur->Value == Key)
{
Find = Cur;
Success = 1;
break;
}
Pred = Cur;
Cur = Cur->next;
}
return Success;
}
int p3(Link* Start, Link*& Find, int Key)
{
Link* Cur = Start->next;
int Success = 0;
while (Cur && !Success)
{
if (Cur->Value == Key)
{
Find = Cur;
Success = 1;
break;
}
Cur = Cur->next;
}