Файл: Операции производимые с данными.pdf

Решение

/* подключение заголовочных файлов */

struct spisok{ char fam[20];

int d,m,y;

spisok *p; };

void main () {

int n,j;

cout<<"Введите количество записей: \n"; cin>>n;

spisok *t;

spisok *first=new spisok;

cout<<"Введите фамилию \n"; gets(first->fam);

cout<<"Введите дату рождения в виде: 7 11 2006 \ (7-е ноября 2006 года)";

cin>>first->d>>first->m>>first->y;

first->p=0;

t=first;

for (j=2; j<=n; j++){

spisok *z=new spisok;

if(t!=0) t->p=z;

cout<<"Введите фамилию \n"; gets(z->fam);

cout<<"Введите дату рождения в виде: 7 11 2006";

cin>>z->d>>z->m>>z->y;

t=z; t->p=0;

}

cout <<"Введенный список\n";

t=first;

j=1;

while(t!=0){

coutp!=0){

q=g;w=g->p;

if (strcmp(q->fam,w->fam)>0) {

if(q==t){t=w;r=w;q->p=w->p;w->p=q;}

else {q->p=w->p;w->p=q;r->p=w;r=w;}

flag=0; }

else {g=g->p;r=q;}

}

}while (flag==0);

cout <<"\n Отсортированный по алфавиту список\n";

j=1;

while(t!=0){

cout

Глава 2. Списковые структуры данных

2.1. Линейные списки (однонаправленные цепочки).

Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Каждый элемент связанного списка, во-первых, хранит какую-либо информацию, во-вторых, указывает на следующий за ним элемент. Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой.

Лишь на самый первый элемент списка (голову) имеется отдельный указатель. Последний элемент списка никуда не указывает.

Рисунок 5 – Однонаправленный список

Пример описание списка

Type ukazat= ^ S;

S= record

Inf: integer;

Next: ukazat;

End;

В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан. Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип.

Чтобы список существовал, надо определить указатель на его начало.

---

Type ukazat= ^S;

S= record

Inf: integer;

Next: ukazat;

End;

Рисунок 6 – Элемент списка

Создадим первый элемент списка:

New (u); {выделяем место в памяти}

u^. Next:= nil; {указатель пуст}

u^. Inf:=3;

Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.

А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:

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

New(x);

Readln(x^.Inf);

x^. Next:= u;

u:= x;

Б) Добавление элемента в конец списка. Для этого введем вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv.

x:= hv;

New( x^. next); {выделяем память для следующего элемента}

Рисунок 7 – Добавление элемента в конец списка.

x:= x^.next;

x^.next:= nil;

x^. inf:= 5;

hv:=x;

Просмотр списка

While u<> nil do

Begin

Writeln (u^.inf);

u:= u^.next;>

end;

Удаление элемента из списка

А) Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.

Рисунок 7 – Удаление первого элемента

x:= u;

u:= u^.next;

dispose(x);

Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.

Рисунок 8 – Удаление элемента из середины списка

x:= u;

while ( x<> nil) and ( x^. inf<> digit) do

begin

dx:= x;

x:= x^.next;

end;

dx:= x^.next:

dispose(x);

В) Удаление из конца списка. Для этого нужно найти предпоследний элемент.

x:= u; dx:= u;

while x^.next<> nil do

begin

dx:= x; x:= x^.next;

end;

dx^.next:= nil;

dispose(x);

Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.

summa:= 0;

x:= u;

while x<> nil do

begin

summa:= summa+ x^.inf;

x:= x^.next;

end;

---

2.2. Динамические объекты сложной структуры

Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от головы списка к последнему звену. Между тем нередко возникает необходимость произвести какую-либо операцию с элементом, предшествующим элементу с заданным свойством. Однако после нахождения элемента с данным свойством в однонаправленном списке у нас нет возможности получить удобный и быстрый способ доступа к предыдущему элементу.

Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено.

Type ukazat= ^S;

S= record

Inf: integer;

Next: ukazat;

Pred: ukazat;

End;

Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:

Рисунок 9 – Двунаправленный список

Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).

В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:

Рисунок 10 – Кольцевой список

Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.

Существуют различные методы использования динамических списков:

• Стек – особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».
• Очередь – это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».
• Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.

---

2.3. Примеры списковых структур на Паскале

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

Поменять местами 1-й с 5-м элементом в стеке, не изменяя расположение в динамической памяти информационной части всех элементов стека.

Решение

Представим исходное состояние стека в следующем виде :

Рисунок 11 – Исходное состояние стека

Затем, согласно варианту 5, порядок следования изменится следующим образом:

5

4

3

2

1

Рисунок 12 Изменение состояние стека

Пояснение

1. Заполняем стек элементами от 1 до 5.
2. Переменной UU присваиваем значение указателя на последний элемент в стеке – число 5.
3. Переменной А2 присваиваем значение указателя на последний элемент в стеке – число 5.
4. Двигаясь от последнего элемента стека до первого, запоминаем Динамические структуры данных. Линейные списки элементов: первого и пятого в переменных А1 и А5.
5. Меняем значения указателей :

указатель 5-го элемента на А1;

указатель 1-го элемента на А5;

переменной UU присваиваем значение указателя 2-го элемента;

указатель 2-го элемента на А2.

1. Далее, передвигаясь от последнего элемента стека числа 1 до первого – числа 5 выводим их значения.

Текст и результат работы программы представлены в приложении Б.

Пример 2. ЗАДАЧА 1

На рис. 13 изображено дерево с пятнадцатью вершинами. Корнем дерева служит точка 1. Кроме того, для каждой вершины указана целочисленная пометка, согласно следующей ниже таблицы.

Используя рекурсивные процедуры для перебора всех вершин дерева, пройти вершины дерева с помощью рекурсивной процедуры, дойти до вершины с пометкой 25 и вывести хотя бы один номер такой вершины.

3

1

---

2

4

5

7

61

8

9

10

11

12

13

14

15

Рисунок 13 – Дерево

Номер вершины	1	2	3	4	5	6	7	8	9	10	11	12	13	14	45
Число-пометка	10	22	16	11	45	25	25	4	10	7	8	25	10	1	9

Решение

Задаем узел дерева записью, которая содержит метки: правая, левая, имя: номер узла и вес: число-пометка. Создаем три процедуры: поиск узла по содержимому-имени, вывод списка узлов и поиск узла с заданным весом.

Задаем начальные значения для корня дерева - текущего узла – его номер и вес. Значения правой и левой меток обнуляем.

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

Выводим имя текущего узла и его вес-пометку.

В зависимости от введенного значения переменной n: 1, 2,3 ,4 или 0 выполняются следующие задачи:

1: присваивается имя левому потомку и правому потомку;

2: вводится имя текущего узла;

3: выводит список всех созданных узлов дерева;

4: ищет номер узла с весом 25;

0: выход из цикла.

Текст и результат работы программы представлены в приложении А

Пример 3. В типизированном файле хранится некоторый текст, как последовательность слов, число слов , длина слова .

1. сформировать линейный однонаправленный список из слов, хранимых в файле, используя структуру массива;
2. модифицировать список, удалив все чётные по номеру слова, корректируя только связи, не удаляя элементы физически из массива;
3. подсчитать в списке количество двухбуквенных слов;
4. удалить из списка заданное слово, которое вводится с клавиатуры:

а) слово находится в начале списка;

б) слово находится в середине списка;

в) слово находится в конце списка;

г) слово находится в произвольном месте;

д) слово отсутствует в списке.

Текст и результат работы программы представлены в приложении В

Заключение

Хотя динамика и не является значительной особенностью языка Паскаль, все-таки существует возможность создавать динамические объекты и оперировать ими. Динамический объект представляет собой область памяти без идентификатора. Для обращения к этой области создается специальная переменная-ссылка, которая описывается в программе. Элементами множества значений типа ссылка на значение адреса оперативной памяти.

---