Файл: Отчет по лабораторной работе. Отчет по работе включает следующие пункты.pdf
Добавлен: 12.12.2023
Просмотров: 49
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
2. Контрольные вопросы
1. Понятие типа указатель.
Задание переменных типа указатель. Операции над указателями.
Понятие статического и динамического объекта.
Создание и уничтожение динамического объекта. Операции над динамическим объектом.
Понятие списка.
Понятие линейного односвязного списка. Задание односвязного списка.
Операции над односвязным списком.
3. Варианты задания
1. Задан текст, состоящий из строк, разделенных пробелом и оканчивающийся точкой. Написать подпрограмму поиска заданного элемента в списке. Используя эту подпрограмму : а) подсчитать количество вхождений заданного символа в каждую строку текста. Вхождение задавать номером строки и номером позиции в строке б) найти все вхождения ( см. пункта) заданного символа в текст в) найти первое вхождение ( см. пункта) каждой десятичной цифры в текст г) найти первое вхождение ( см. пункта) гласных латинских букв в текст д) подсчитать количество вхождений четных ( нечетных ) десятичных цифр в каждую строку текста е) заменить заданный символ, если он имеется в тексте, на новое значение символ, считая, что символ входит в каждую строку не более одного раза ж) удалить все вхождения заданного символа из текста з) после последнего вхождения каждой гласной латинской буквы в строку текста вставить цифру, изображающую число вхождений этой гласной в данную строку ( в строке содержится не более девяти одинаковых гласных ); и) если в строке текста содержится заданный символ, то переместить его на место первого символа в этой строке к) если в строке текста содержится заданный символ, то переместить его на место последнего символа в этой строке.
2. Даны действительные числа x
1
, x
2
, . . . , x n
( n >= 2 и заранее неизвестно. Получить последовательность ( x
1
– x n
) , ( x
2
– x n
) , . . . , ( x n-1
– x n
).
3. Дана последовательность действительных чисел a
1
, a
2
, . . . , a n
( n >= 2 и заранее неизвестно. Если последовательность упорядочена по неубыванию, то оставить ее без изменения, иначе получить последовательность a n
, a n-1
, . . . , a
1 4. Для заданных полиномов P
n
( x ) и Q
n
( x ) найти полином R - сумму полиномов P и Q. Каждый полином представить в виде списка
P
• • •
Причем в список а) включать, б) не включать и коэффициенты равные нулю. Считать, что входные данные не содержат равных нулю коэффициентов.
5. Дана последовательность символов s
1
, s
2
, . . . , s n
( n >= 2 и заранее неизвестно. Получить те символы, принадлежащие последовательности, которые входят в нее по одному разу.
6. Дана последовательность символов s
1
, s
2
, . . . , s n
( n >= 2 и заранее неизвестно. Получить последовательность символов, содержащую только последние вхождения каждого символа в строку с сохранением их исходного взаимного порядка.
7. Дана последовательность символов s
1
, s
2
, . . . . Известно, что s
1
отличен от точки и , что среди s
2
, s
3
, . . . имеется хотя бы одна точка. Пусть s
1
, s
2
, . . . , s n
- символы, предшествующие первой точке. Получить последовательность s
1
, s
3
,
. . . , s n
, если n нечетно и последовательность s
2
, s
4
, . . . , s n
, если n четно. n a n
0 a
0 nil
1 a
1
Nn–1 a n-1
Понятие двусвязного списка. Возможные структуры двусвязного списка.
Задание двусвязного списка.
Основные операции над двусвязным списком.
3. Варианты задания Дана последовательность символов, оканчивающаяся точкой а) найти всех соседей заданного символа ( первый и последний символы считать соседями ); б) подсчитать количество символов, у которых левый сосед больше правого соседа ( первый и последний элемент считать соседями ); в) удалить все символы, у которых равные соседи ( первый и последний символы считать соседями ); г) переставить в обратном порядке все символы между первыми последним вхождениями заданного символа д) вконец последовательности добавить все ее символы, располагая их в обратном порядке ( например, из последовательности 1, 2, 3 получить 1, 2, 3, 2, 1
).
Дана последовательность латинских букв, оканчивающаяся точкой. Среди букв есть специальный символ, появление которого означает отмену предыдущей буквы k знаков подряд отменяют k предыдущих букв, если такие есть. Учитывая вхождение этого символа преобразовать последовательность.
Даны две разреженные квадратные матрицы A и B порядка n ( разреженная матрица это матрица высокого порядка с большим количеством нулевых элементов ). Получить матрицу C = A+B. Для представления разреженной матрицы использовать двусвязный циклический список. Каждое звено списка состоит из пяти полей :
- поле с номером строки ненулевого элемента,
- поле с номером столбца ненулевого элемента,
- поле со значением элемента,
- поле со ссылкой на предыдущий ненулевой элемент в этой же строке,
- поле со ссылкой на предыдущий ненулевой элемент в этом же столбце. Каждая строка ( и столбец ) имеют заглавное звено, соответствующее ссылочное поле которого содержит ссылку на последний ненулевой элемент в строке ( в столбце ) .
4. Дан многочлен P( x ) произвольной степени с целыми коэффициентами, причем его одночлены могут быть не упорядочены по степеням x , а одночлены с одинаковой степенью могут повторяться (например, -75x + 8x
4
- x
2
+ 6x
4
– 5 - x). Привести подобные члены в этом многочлене и расположить одночлены по убыванию степеней x .
5. Даны действительные числа x
1
, x
2
, . . . , x n
( n >= 2 и заранее неизвестно. Вычислить а) x
1
x n
+ x
2
x n-1
+ . . . + x n
x
1
; б) ( x
1
+ x n
) ( x
2
+ x n-1
) . . . ( x n
+ x
1
) ; в) ( x
1
+ x
2
+ 2x n
) ( x
2
+ x
3
+ 2x n-1
) . . . ( x n-1
+ x n
+ 2x
2
) .
6. Даны действительные числа y
1
, y
2
, . . . , y n
( n >= 2 и заранее неизвестно. Получить последовательность а) y
1
, y
2
, . . . , y n
, y
1
, . . . , y n
; б) y
1
, y
2
, . . . , y n
, y n
, . . . , y
1
; в) y n
, y n-1
, . . . , y
1
, y
1
, . . . , y n
7. Даны действительные числа a
1
, a
2
, . . . , a
2n
(n >= 2 и заранее неизвестно. Вычислить а) a
1
a
2n
+ a
2
a
2n-1
+ . . . + a n
a n+1
; б) min ( a
1
+ a n+1
, a
2
+ a n+2
, . . . , a n
+ a
2n
) ; в) max ( min ( a
1
, a
2n
) , min ( a
3
, a
2n-2
) , . . . , min ( a
2n-1
, a
2
) ) .
ЛАБОРАТОРНАЯ РАБОТА СТРУКТУРЫ ДАННЫХ СТЕКИ и ОЧЕРЕДИ
Цель работы сформировать практические навыки организации таких распространенных структур как стеки и очереди и их использования при решении задач.
1. Методические указания
Стек – это список, у которого доступен один элемент (одна позиция. Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека.
Очередь – это список, у которого доступны два элемента (две позиции) начало и конец очереди. Поместить элемент можно только вконец очереди, а взять элемент только из ее начала.
Стеки и очереди могут быть организованы различными способами. При этом они могут быть размещены как в статической памяти, таки в динамической.
Статический стек можно задать следующим образом struct stack
{ int top; type data [ n ] ;}
Здесь type – тип элементов, хранимых в стеке. Поле top определяет вершину стека. Ограничение на количество элементов в массиве (константа n) задает размер стека. Статический стек может быть полон. top 0 K n-1 вершина
Вершина стека это либо позиция стека (массива, куда был помещен последний элемент либо позиция, куда будет помещен очередной элемент.
Динамический стек можно задать линейным односвязным списком struct list
{ type pole1; list *pole2 ; } typedef list stack ; z z z вершина стека
В стеке, представленном линейным односвязным списком, вершина стека – первый элемент списка. К • •
• • •
NULL
Ввести в употребление переменную типа стек можно следующим образом stack *S;
Чтобы инициализировать статический стек (задать начальное значение стека, достаточно определить такое начальное значение поля top, которое показывало бы, что в стеке еще нет элементов, те. стек пуст. Если S.top = -1 (или 0 в случае, когда top показывает на позицию, куда будет помещен очередной элемент, то стек пуст. В таком случае при помещении в стек элемента значение S.top увеличивается на единицу, при взятии элемента уменьшается на единицу. Если top равно n-1 (или n), то стек полон. Если указатель равен 0 (или 1), тов стеке один элемент. При взятии из стека единственного элемента, он становиться пустым, поле top должно получить значение -1 (или Обращение к элементу в вершине статического стека
S.data [ S.top ].
Чтобы инициализировать динамический стек, те. создать пустой динамический стек достаточно указателю на вершину стека задать значение NULL: S = NULL. Обращение к значению элемента в вершине динамического стека S -> pole1.
Основные операции над стеком ( S - переменная типа stack ): Таблица 1 Название Операции Статистический способ определения стека Динамический способ определения стека Очистить стек создать стек) Поместить элемент в стек Взять элемент из стека Проверка пуст ли стек В поле S.top
← ∅ Если S.top < n-1 , то S.top = S.top + 1;
S.data[S.top] = элемент , иначе ошибка - переполнение стека Если стек не пуст, то элемент = S.data[ S.top];
S.top = S.top – 1; , иначе ошибка - операция не определена пуст (S)=true, если S.top =
∅ пуст false, eсли S.top
≠∅
S:= NULL Добавить элемент в начало линейного списка (см. лабораторная работа № 1)
Элемент = S ->pole1; Удалить первый элемент из линейного списка, сделав первым следующий элемент списка S = S -> pole2; Операция определена, если стек не пуст. Пуст, если S =
NULL
Пуст(S)=false,если S!=
NULL
Статическую очередь можно представить
1. Понятие типа указатель.
Задание переменных типа указатель. Операции над указателями.
Понятие статического и динамического объекта.
Создание и уничтожение динамического объекта. Операции над динамическим объектом.
Понятие списка.
Понятие линейного односвязного списка. Задание односвязного списка.
Операции над односвязным списком.
3. Варианты задания
1. Задан текст, состоящий из строк, разделенных пробелом и оканчивающийся точкой. Написать подпрограмму поиска заданного элемента в списке. Используя эту подпрограмму : а) подсчитать количество вхождений заданного символа в каждую строку текста. Вхождение задавать номером строки и номером позиции в строке б) найти все вхождения ( см. пункта) заданного символа в текст в) найти первое вхождение ( см. пункта) каждой десятичной цифры в текст г) найти первое вхождение ( см. пункта) гласных латинских букв в текст д) подсчитать количество вхождений четных ( нечетных ) десятичных цифр в каждую строку текста е) заменить заданный символ, если он имеется в тексте, на новое значение символ, считая, что символ входит в каждую строку не более одного раза ж) удалить все вхождения заданного символа из текста з) после последнего вхождения каждой гласной латинской буквы в строку текста вставить цифру, изображающую число вхождений этой гласной в данную строку ( в строке содержится не более девяти одинаковых гласных ); и) если в строке текста содержится заданный символ, то переместить его на место первого символа в этой строке к) если в строке текста содержится заданный символ, то переместить его на место последнего символа в этой строке.
2. Даны действительные числа x
1
, x
2
, . . . , x n
( n >= 2 и заранее неизвестно. Получить последовательность ( x
1
– x n
) , ( x
2
– x n
) , . . . , ( x n-1
– x n
).
3. Дана последовательность действительных чисел a
1
, a
2
, . . . , a n
( n >= 2 и заранее неизвестно. Если последовательность упорядочена по неубыванию, то оставить ее без изменения, иначе получить последовательность a n
, a n-1
, . . . , a
1 4. Для заданных полиномов P
n
( x ) и Q
n
( x ) найти полином R - сумму полиномов P и Q. Каждый полином представить в виде списка
P
• • •
Причем в список а) включать, б) не включать и коэффициенты равные нулю. Считать, что входные данные не содержат равных нулю коэффициентов.
5. Дана последовательность символов s
1
, s
2
, . . . , s n
( n >= 2 и заранее неизвестно. Получить те символы, принадлежащие последовательности, которые входят в нее по одному разу.
6. Дана последовательность символов s
1
, s
2
, . . . , s n
( n >= 2 и заранее неизвестно. Получить последовательность символов, содержащую только последние вхождения каждого символа в строку с сохранением их исходного взаимного порядка.
7. Дана последовательность символов s
1
, s
2
, . . . . Известно, что s
1
отличен от точки и , что среди s
2
, s
3
, . . . имеется хотя бы одна точка. Пусть s
1
, s
2
, . . . , s n
- символы, предшествующие первой точке. Получить последовательность s
1
, s
3
,
. . . , s n
, если n нечетно и последовательность s
2
, s
4
, . . . , s n
, если n четно. n a n
0 a
0 nil
1 a
1
Nn–1 a n-1
ЛАБОРАТОРНАЯ РАБОТА ЛИНЕЙНЫЕ ДВУНАПРАВЛЕННЫЕ СПИСКИ
Цель работы получить практические навыки организации двунаправленных двусвязных) списков и их использования при решении задач.
1. Методические указания
Динамический список, в котором каждый элемент (кроме возможно первого и последнего) связан с предыдущими следующим за ним элементами называется двусвязным. Каждый элемент такого списка имеет два поля с указателями одно поле содержит ссылку наследующий элемент, другое поле – ссылку на предыдущий элемент и третье поле - информационное. Наличие ссылок наследующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении от звена к концу списка или от звена к началу списка, поэтому такой список называют еще и двунаправленным.
Пример 1 ( строка символов BETA представлена двусвязным списком
Рис. Первое звено не имеет ссылки на предыдущее, последнее звено не имеет ссылки наследующее звено ( рис.
Рис. Такой список ( рис) называют кольцевым ( циклическим ). Здесь первое звено имеет ссылку на последнее, а последнее звено на первое. Поэтому начинать обработку такого списка можно как с первого звена, таки с последнего. Двусвязный список может иметь заглавное звено (рис.
Рис.
B
A
T
E
B
A
T
E
B
NULL
A
NULL
T
E
Цель работы получить практические навыки организации двунаправленных двусвязных) списков и их использования при решении задач.
1. Методические указания
Динамический список, в котором каждый элемент (кроме возможно первого и последнего) связан с предыдущими следующим за ним элементами называется двусвязным. Каждый элемент такого списка имеет два поля с указателями одно поле содержит ссылку наследующий элемент, другое поле – ссылку на предыдущий элемент и третье поле - информационное. Наличие ссылок наследующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении от звена к концу списка или от звена к началу списка, поэтому такой список называют еще и двунаправленным.
Пример 1 ( строка символов BETA представлена двусвязным списком
Рис. Первое звено не имеет ссылки на предыдущее, последнее звено не имеет ссылки наследующее звено ( рис.
Рис. Такой список ( рис) называют кольцевым ( циклическим ). Здесь первое звено имеет ссылку на последнее, а последнее звено на первое. Поэтому начинать обработку такого списка можно как с первого звена, таки с последнего. Двусвязный список может иметь заглавное звено (рис.
Рис.
B
A
T
E
B
A
T
E
B
NULL
A
NULL
T
E
Заглавное звено позволяет обрабатывать первое и последнее звенья также как другие. Возможны и другие структуры двусвязных списков.
Задание двусвязного списка struct list2
{ type elem ; list2 * next, * pred ;
} list2 * headlist2 ;
Здесь type – тип информационного поля элемента списка.
Переменная-указатель headlist2 задает список как единый программный объект, ее значение - указатель на первый (или заглавный) элемент списка (см. рис.
Пример 2. Формирование двунаправленного кольцевого списка void main ( ) struct list2
{ char elem ; list2 * next, * pred ; } list2 *l, *r, *x; char sym;
{ l = new list2; // Создание пустого l -> next = l; // кольцевого списка l -> pred = l; // с заглавным звеном r = l; while ( (sym = getchar ( )) != ‘\n’ )
{ x = new list2; x -> elem = sym; // Создание очередного звена x -> next = r -> next; // Поле next - указатель наследующее звено
получило значение указателя на первое звено списка x -> pred = r; Поле pred - указатель на предыдущее звено получило
// значение указателя на текущее последнее звено списка r -> next = x; // Поле next текущего последнего элемента - указатель наследующий элемент получило значение указателя на новый
элемент, таким образом, новое звено добавлено вконец списка r -> next -> pred = x; // Поле pred заглавного элемента - указатель
// на последнее звено списка получило значение указателя
// на добавленный вконец списка элемент, таким образом,
// сформирован кольцевой список r = r -> next; // Текущий указатель получил значение ссылки на
// новый последний элемент списка
} }
Основные операции, выполняемые над двусвязным списком, те же, что и для односвязного списка. Так как двусвязный список более гибкий, чем односвязный, то при включении элемента в список, можно использовать указатель как на элемент, за которым происходит включение, таки указатель на элемент перед которым происходит включение. При исключении элемента из списка можно
Задание двусвязного списка struct list2
{ type elem ; list2 * next, * pred ;
} list2 * headlist2 ;
Здесь type – тип информационного поля элемента списка.
Переменная-указатель headlist2 задает список как единый программный объект, ее значение - указатель на первый (или заглавный) элемент списка (см. рис.
Пример 2. Формирование двунаправленного кольцевого списка void main ( ) struct list2
{ char elem ; list2 * next, * pred ; } list2 *l, *r, *x; char sym;
{ l = new list2; // Создание пустого l -> next = l; // кольцевого списка l -> pred = l; // с заглавным звеном r = l; while ( (sym = getchar ( )) != ‘\n’ )
{ x = new list2; x -> elem = sym; // Создание очередного звена x -> next = r -> next; // Поле next - указатель наследующее звено
получило значение указателя на первое звено списка x -> pred = r; Поле pred - указатель на предыдущее звено получило
// значение указателя на текущее последнее звено списка r -> next = x; // Поле next текущего последнего элемента - указатель наследующий элемент получило значение указателя на новый
элемент, таким образом, новое звено добавлено вконец списка r -> next -> pred = x; // Поле pred заглавного элемента - указатель
// на последнее звено списка получило значение указателя
// на добавленный вконец списка элемент, таким образом,
// сформирован кольцевой список r = r -> next; // Текущий указатель получил значение ссылки на
// новый последний элемент списка
} }
Основные операции, выполняемые над двусвязным списком, те же, что и для односвязного списка. Так как двусвязный список более гибкий, чем односвязный, то при включении элемента в список, можно использовать указатель как на элемент, за которым происходит включение, таки указатель на элемент перед которым происходит включение. При исключении элемента из списка можно
использовать как указатель на сам исключаемый элемент, таки указатель на элемент предшествующий или следующий за исключаемым. Но так как элемент двусвязного списка имеет два указателя, то при выполнении операций включения/исключения элемента надо изменять больше связей, чем в односвязном списке. Поиск элемента в двусвязном списке можно вести а) просматривая элементы от начала к концу списка, б) просматривая элементы от конца списка к началу, в) просматривая список в обоих направлениях одновременно от начала к середине списка и от конца к середине (учитывая, что элементов в списке может быть четное или нечетное количество.
Пример 3. Фрагменты программ, выполняющих различные действия с двусвязным списком void exam1( list2 *p) // Просмотр циклического (возможно пустого)
// списка без заглавного звена
{ list2 *ph; // в направлении от начала к концу списка if ( p = = NULL ) return; ph = p; do { . . . p = p -> next; } while ( p != ph ); Просмотр продолжается пока текущий указатель
// p неравен указателю на начало списка - ph
} void exam2( list2 *p) // Просмотр кольцевого (возможно пустого)
// списка с заглавным звеном
{ list2 *pr; // в направлении от конца списка к началу if ( p –> next = = p ) return; pr = p -> pred; // Текущий указатель pr получил значение ссылки
// на последний элемент списка while (pr != p) Просмотр продолжается пока текущий указатель pr
// неравен указателю на заглавное звено списка - p
{ . . . pr = pr -> pred; } x = new list2; // Включение нового элемента (в список с x -> pred = p -> pred; // заглавным звеном) перед элементом, на x -> next = p; // который ссылается p p -> pred -> next = x; p -> pred = x; p -> pred -> next = p -> next; // Исключение из списка с заглавным p -> next -> pred = p -> pred; // звеном элемента, на который delete p; // ссылается указатель p
2. Контрольные вопросы
Пример 3. Фрагменты программ, выполняющих различные действия с двусвязным списком void exam1( list2 *p) // Просмотр циклического (возможно пустого)
// списка без заглавного звена
{ list2 *ph; // в направлении от начала к концу списка if ( p = = NULL ) return; ph = p; do { . . . p = p -> next; } while ( p != ph ); Просмотр продолжается пока текущий указатель
// p неравен указателю на начало списка - ph
} void exam2( list2 *p) // Просмотр кольцевого (возможно пустого)
// списка с заглавным звеном
{ list2 *pr; // в направлении от конца списка к началу if ( p –> next = = p ) return; pr = p -> pred; // Текущий указатель pr получил значение ссылки
// на последний элемент списка while (pr != p) Просмотр продолжается пока текущий указатель pr
// неравен указателю на заглавное звено списка - p
{ . . . pr = pr -> pred; } x = new list2; // Включение нового элемента (в список с x -> pred = p -> pred; // заглавным звеном) перед элементом, на x -> next = p; // который ссылается p p -> pred -> next = x; p -> pred = x; p -> pred -> next = p -> next; // Исключение из списка с заглавным p -> next -> pred = p -> pred; // звеном элемента, на который delete p; // ссылается указатель p
2. Контрольные вопросы
Понятие двусвязного списка. Возможные структуры двусвязного списка.
Задание двусвязного списка.
Основные операции над двусвязным списком.
3. Варианты задания Дана последовательность символов, оканчивающаяся точкой а) найти всех соседей заданного символа ( первый и последний символы считать соседями ); б) подсчитать количество символов, у которых левый сосед больше правого соседа ( первый и последний элемент считать соседями ); в) удалить все символы, у которых равные соседи ( первый и последний символы считать соседями ); г) переставить в обратном порядке все символы между первыми последним вхождениями заданного символа д) вконец последовательности добавить все ее символы, располагая их в обратном порядке ( например, из последовательности 1, 2, 3 получить 1, 2, 3, 2, 1
).
Дана последовательность латинских букв, оканчивающаяся точкой. Среди букв есть специальный символ, появление которого означает отмену предыдущей буквы k знаков подряд отменяют k предыдущих букв, если такие есть. Учитывая вхождение этого символа преобразовать последовательность.
Даны две разреженные квадратные матрицы A и B порядка n ( разреженная матрица это матрица высокого порядка с большим количеством нулевых элементов ). Получить матрицу C = A+B. Для представления разреженной матрицы использовать двусвязный циклический список. Каждое звено списка состоит из пяти полей :
- поле с номером строки ненулевого элемента,
- поле с номером столбца ненулевого элемента,
- поле со значением элемента,
- поле со ссылкой на предыдущий ненулевой элемент в этой же строке,
- поле со ссылкой на предыдущий ненулевой элемент в этом же столбце. Каждая строка ( и столбец ) имеют заглавное звено, соответствующее ссылочное поле которого содержит ссылку на последний ненулевой элемент в строке ( в столбце ) .
4. Дан многочлен P( x ) произвольной степени с целыми коэффициентами, причем его одночлены могут быть не упорядочены по степеням x , а одночлены с одинаковой степенью могут повторяться (например, -75x + 8x
4
- x
2
+ 6x
4
– 5 - x). Привести подобные члены в этом многочлене и расположить одночлены по убыванию степеней x .
5. Даны действительные числа x
1
, x
2
, . . . , x n
( n >= 2 и заранее неизвестно. Вычислить а) x
1
x n
+ x
2
x n-1
+ . . . + x n
x
1
; б) ( x
1
+ x n
) ( x
2
+ x n-1
) . . . ( x n
+ x
1
) ; в) ( x
1
+ x
2
+ 2x n
) ( x
2
+ x
3
+ 2x n-1
) . . . ( x n-1
+ x n
+ 2x
2
) .
6. Даны действительные числа y
1
, y
2
, . . . , y n
( n >= 2 и заранее неизвестно. Получить последовательность а) y
1
, y
2
, . . . , y n
, y
1
, . . . , y n
; б) y
1
, y
2
, . . . , y n
, y n
, . . . , y
1
; в) y n
, y n-1
, . . . , y
1
, y
1
, . . . , y n
7. Даны действительные числа a
1
, a
2
, . . . , a
2n
(n >= 2 и заранее неизвестно. Вычислить а) a
1
a
2n
+ a
2
a
2n-1
+ . . . + a n
a n+1
; б) min ( a
1
+ a n+1
, a
2
+ a n+2
, . . . , a n
+ a
2n
) ; в) max ( min ( a
1
, a
2n
) , min ( a
3
, a
2n-2
) , . . . , min ( a
2n-1
, a
2
) ) .
ЛАБОРАТОРНАЯ РАБОТА СТРУКТУРЫ ДАННЫХ СТЕКИ и ОЧЕРЕДИ
Цель работы сформировать практические навыки организации таких распространенных структур как стеки и очереди и их использования при решении задач.
1. Методические указания
Стек – это список, у которого доступен один элемент (одна позиция. Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека.
Очередь – это список, у которого доступны два элемента (две позиции) начало и конец очереди. Поместить элемент можно только вконец очереди, а взять элемент только из ее начала.
Стеки и очереди могут быть организованы различными способами. При этом они могут быть размещены как в статической памяти, таки в динамической.
Статический стек можно задать следующим образом struct stack
{ int top; type data [ n ] ;}
Здесь type – тип элементов, хранимых в стеке. Поле top определяет вершину стека. Ограничение на количество элементов в массиве (константа n) задает размер стека. Статический стек может быть полон. top 0 K n-1 вершина
Вершина стека это либо позиция стека (массива, куда был помещен последний элемент либо позиция, куда будет помещен очередной элемент.
Динамический стек можно задать линейным односвязным списком struct list
{ type pole1; list *pole2 ; } typedef list stack ; z z z вершина стека
В стеке, представленном линейным односвязным списком, вершина стека – первый элемент списка. К • •
• • •
NULL
Ввести в употребление переменную типа стек можно следующим образом stack *S;
Чтобы инициализировать статический стек (задать начальное значение стека, достаточно определить такое начальное значение поля top, которое показывало бы, что в стеке еще нет элементов, те. стек пуст. Если S.top = -1 (или 0 в случае, когда top показывает на позицию, куда будет помещен очередной элемент, то стек пуст. В таком случае при помещении в стек элемента значение S.top увеличивается на единицу, при взятии элемента уменьшается на единицу. Если top равно n-1 (или n), то стек полон. Если указатель равен 0 (или 1), тов стеке один элемент. При взятии из стека единственного элемента, он становиться пустым, поле top должно получить значение -1 (или Обращение к элементу в вершине статического стека
S.data [ S.top ].
Чтобы инициализировать динамический стек, те. создать пустой динамический стек достаточно указателю на вершину стека задать значение NULL: S = NULL. Обращение к значению элемента в вершине динамического стека S -> pole1.
Основные операции над стеком ( S - переменная типа stack ): Таблица 1 Название Операции Статистический способ определения стека Динамический способ определения стека Очистить стек создать стек) Поместить элемент в стек Взять элемент из стека Проверка пуст ли стек В поле S.top
← ∅ Если S.top < n-1 , то S.top = S.top + 1;
S.data[S.top] = элемент , иначе ошибка - переполнение стека Если стек не пуст, то элемент = S.data[ S.top];
S.top = S.top – 1; , иначе ошибка - операция не определена пуст (S)=true, если S.top =
∅ пуст false, eсли S.top
≠∅
S:= NULL Добавить элемент в начало линейного списка (см. лабораторная работа № 1)
Элемент = S ->pole1; Удалить первый элемент из линейного списка, сделав первым следующий элемент списка S = S -> pole2; Операция определена, если стек не пуст. Пуст, если S =
NULL
Пуст(S)=false,если S!=
NULL
Статическую очередь можно представить
а) линейным массивом с двумя указателями на начало и наконец очереди. Указатель на начало определяет позицию очереди (массива, откуда можно взять элемент, указатель наконец позицию, куда кладем элемент struct ch1
{ int begin, end ;
type data [ N ] ; }
0 K L N-1 begin end data начало конец
Задать очередь – это определить переменную типа ch1: ch1 Q;
Чтобы инициализировать очередь достаточно определить начальное значение указателя на начало и/или конец очереди. Для этого полю begin дадим значение, не принадлежащее диапазону от 0 до N-1 (а полю end можно задать значение, указывающее на первый элемент очереди – это упростит работу с указателями при включении элемента в очередь. При включении элемента в непустую очередь увеличивается на единицу значение указателя end, при взятии элемента из очереди значение указателя на начало. При включении элемента впустую очередь увеличиваются оба указателя.
В этом варианте не используются освободившиеся после взятия элементов из очереди позиции, поэтому возможно мнимое переполнение очереди. Если end равно N-1 и begin равно 0 – очередь полна, а если begin больше 0, то очередь псевдополна (те. из очереди были взяты элементы ив начале массива есть свободные позиции.
Обращение к элементу при взятии из очереди Q.data [ Q.begin ], при занесении в очередь Q.data [ Q.end ]. Если в очереди один элемент, то оба указателя показывают на него, те. их значения равны, если из очереди взять единственный элемент, она должна стать пустой б) линейным массивом с одним указателем на начало или наконец очереди, вторая позиция очереди фиксируется (например, начало очереди это первый элемент массива. В таком случае очередь сдвигается после каждого взятия из нее элемента struct ch2
{ int end ; type data [ N ] ;
0 K N-1 end data начало конец в) линейным массивом с двумя указателями (аналогично варианту а. При достижении конца массива (последнего элемента) очередь сдвигается на начало z z z z z z z z К z z z z z z
{ int begin, end ;
type data [ N ] ; }
0 K L N-1 begin end data начало конец
Задать очередь – это определить переменную типа ch1: ch1 Q;
Чтобы инициализировать очередь достаточно определить начальное значение указателя на начало и/или конец очереди. Для этого полю begin дадим значение, не принадлежащее диапазону от 0 до N-1 (а полю end можно задать значение, указывающее на первый элемент очереди – это упростит работу с указателями при включении элемента в очередь. При включении элемента в непустую очередь увеличивается на единицу значение указателя end, при взятии элемента из очереди значение указателя на начало. При включении элемента впустую очередь увеличиваются оба указателя.
В этом варианте не используются освободившиеся после взятия элементов из очереди позиции, поэтому возможно мнимое переполнение очереди. Если end равно N-1 и begin равно 0 – очередь полна, а если begin больше 0, то очередь псевдополна (те. из очереди были взяты элементы ив начале массива есть свободные позиции.
Обращение к элементу при взятии из очереди Q.data [ Q.begin ], при занесении в очередь Q.data [ Q.end ]. Если в очереди один элемент, то оба указателя показывают на него, те. их значения равны, если из очереди взять единственный элемент, она должна стать пустой б) линейным массивом с одним указателем на начало или наконец очереди, вторая позиция очереди фиксируется (например, начало очереди это первый элемент массива. В таком случае очередь сдвигается после каждого взятия из нее элемента struct ch2
{ int end ; type data [ N ] ;
0 K N-1 end data начало конец в) линейным массивом с двумя указателями (аналогично варианту а. При достижении конца массива (последнего элемента) очередь сдвигается на начало z z z z z z z z К z z z z z z
массива (к первому элементу, если есть свободные позиции вначале массива. Таким образом, освобождаемся от псевдопереполнения очереди г) циклическая очередь – линейный массив с двумя указателями (аналогично варианту а, в котором при достижении каким-либо указателем конца массива последнего элемента) значение этого указателя очереди округляется по модулю
N, где N – размер массива. Таким образом, в циклической очереди при достижении конца массива (end = N-1) и наличии свободных позиций вначале, новый элемент помещается в массивна место с индексом 0, при этом указателю end присваивается значение 0. конец начало
0 1 N-1 data begin end Очередь будет полна, если поле end = N-1, а поле begin = 0 или поле end = K, а begin = K+1. Здесь 0 < K < N-1.
В динамической памяти очередь можно представить а) линейным односвязным списком с двумя указателями struct list1
{ type pole1; list1 *pole2; } struct ch3
{ list1 *beg, *end ; } начало конец beg end
Задать динамическую очередь - это определить переменную типа ch3: ch3 Q1;
Чтобы инициировать очередь достаточно указателю на начало Q1.beg и/или наконец присвоить значение NULL. При взятии единственного элемента из очереди она должна стать пустой б) линейным двусвязным циклическим списком с одним указателем struct list2
{ type pole1; list2 *pole1, *pole2; } э
3
э
4
• • •
э
1
э
2
N
-2 1
NULL
N, где N – размер массива. Таким образом, в циклической очереди при достижении конца массива (end = N-1) и наличии свободных позиций вначале, новый элемент помещается в массивна место с индексом 0, при этом указателю end присваивается значение 0. конец начало
0 1 N-1 data begin end Очередь будет полна, если поле end = N-1, а поле begin = 0 или поле end = K, а begin = K+1. Здесь 0 < K < N-1.
В динамической памяти очередь можно представить а) линейным односвязным списком с двумя указателями struct list1
{ type pole1; list1 *pole2; } struct ch3
{ list1 *beg, *end ; } начало конец beg end
Задать динамическую очередь - это определить переменную типа ch3: ch3 Q1;
Чтобы инициировать очередь достаточно указателю на начало Q1.beg и/или наконец присвоить значение NULL. При взятии единственного элемента из очереди она должна стать пустой б) линейным двусвязным циклическим списком с одним указателем struct list2
{ type pole1; list2 *pole1, *pole2; } э
3
э
4
• • •
э
1
э
2
N
-2 1
NULL
1 2 3 4