Технологии Программирования. 8 лекция

Например, Удалим из списка элемент С.

После проделанных операций указатель списка

свободных мест Us=3, а 1-ый элемент списка Un=D.

5. Операция добавления элемента в список после заданного

элемента

Алгоритм Чтобы добавить элемент после заданного элемента Х, последний

надо найти в списке. Используем функцию Find

Если элемент Х найден, то вставляем после него новый элемент

Е, изменяя указатель записи элемента Х таким образом, чтобы он указывал на элемент Е.

// Функция добавления

Void Insert_after(int Pos, int Us, int Е)

{ List[0][Us]= Е ;

List[1][Us]= List[1][Pos]; // Pos – индекс элемента Х

List[1][Pos]=Us;

}

После добавления элемента Y в предыдущую таблицу

получим список

6. Сортировка списков – перестановка элементов списка в определенном порядке.

Используем алгоритмы сортировки массивов.

Исходный список

Отсортированный по элементам

В некоторых задачах требуется отсортировать так, чтобы по указателя

можно было восстановить исходный список.

Исходный

Отсортированный по-новому

В данном случае при сортировке местами менялись не только элементы списка, но и указатели.

// Код программы

Void Swap (int x,int y)

{ int temp; temp=List[0][x];

List[0][x]= List[0][y]; List[0][y]=temp;

temp=List[1][x]; List[1][x]= List[1][y];

List[1][y]=temp;

}

Пример Вокруг ведущего стоят N человек, которые пронумерованы по часовой стрелке от 1 до N. Ведущий, начиная с первого, отсчитывает М человек, и тот, на ком

остановился счет, выходит из круга. Список сокращается,

алгоритм повторяется, пока не останется в списке 1 человек. Это классический пример списка.

…

int List[100]; // список – только указатели int before_start,I,N,M,Start;

void Find()

{for(i=0; i<M-1;i++) {before_start=Start;

//запоминаем номер человека на данном шаге

Start=List[Start];

// Номер человека, на котором счет остановился

}

}

main()

{cin >>N>>M; for(i=o;i<N-1;i++) List[i]=i+1;

//каждый элемент массива равен индексу следующего за ним элемента

//последний элемент ссылается на нулевой

List[N-1]=0;

While(Start!=List[Start])

{ Find(); // запускаем поиск М-го человека

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

List[before_start]=List[Start]; Start=List[Start];

}

cout<<(Start+1); // выводим результат

…

}

Пример (Лабиринт)

Дано поле размером N х М клеток, в которые помещены 0 и 1. Назовем его лабиринтом. 1 – стенки лабиринта, 0 – дорога. Рассмотрим программу, которая определит и выведет на экран кратчайший путь фишки из точки (x1,y1) лабиринта в точку (x2,y2). Фишка может ходить только по нулевым ячейкам поля.

Перебираются все возможные пути из одной ячейки в другую

При реализации используется структура очередь, кратчайший путь

находится автоматически.

…

int const N=5;

int const M=5; main()

{int x,y,x1,y1,x2,y2,p,i,j, Start, Last; int FIFO[3][N*M], result[2][N*M]; int labirint[N][M]={{0 , 0, 0, 1, 0},

{0 , 1, 0, 1, 0}, {0 , 0, 0, 0, 1}, {1 , 1, 0, 0, 0}, {0 , 0, 0, 1, 0}

};

cout<<” input start coordinates x1,y1”<<endl;

cin>>x1>>y1;

cout<<” input finish coordinates x2,y2”<<endl; cin>>x2>>y2;

====================

Алгоритм начинает работу со стартовой клетки с координатами (x1,y1).

В очередь помещаем координаты клеток, которые фишка прошла.

Если фишка побывала в некоторой клетке поля, то в

лабиринте в пройденной ячейке ставим «след» -1.

На первом этапе помечаем, что фишка стартует из клетки (x1,y1) и заносим ее координаты в очередь.

=====================