Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

2.Метод транспозиции.
Алгоритм
Переупорядочение путем перестановки в начало  списка

Найденный элемент сразу оказывается в голове списка.

Первоначально указатель q нулевой, указатель p указывает на начало списка; p перемещается на второй элемент, а q на первый. Указатель начала списка (table) перемещается на второй элемент, а указатель второго элемента на третий. Таким образом второй элемент перемещается на первое место.

(ПСЕВДОКОД)
q=nil
p=table
WHILE (p <> nil) do
IF  key=k(p)
then  SEARCH=p
next(q)=next(p)
next(p)=q
table=p
return
end  IF
q=p
p=next(p)
end WHILE
SEARCH=0
return
Метод  транспозиции
В данном методе найденный элемент переставляется  на  один элемент к голове списка. Если к этому элементу обращаются часто, то постепенно перемещаясь к началу списка, он скоро окажется в его голове.
Этот метод удобен тем, что он эффективен не только в  списковых структурах, но и в неупорядоченных массивах, т.к. меняются местами только два рядом стоящих элемента.
Будем использовать три указателя:
p — рабочий указатель, указывает на элемент.
q — вспомогательный указатель, отстает на один шаг от p.

s —  вспомогательный указатель, отстает на два шага от p.

Найденный нами третий элемент передвигается на один шаг к голове списка (т.е. становится вторым). Указатель первого элемента перемещается на третий элемент, указатель второго элемента на четвертый, таким образом третий элемент перемещается на второе место. Если к данному элементу обратиться еще раз, то он окажется в голове списка.

s=nil
q=nil
p=nil
while (p<>nil) do
if key=k(p) then search=p
if q=nil then return
else next(q)=next(p)
next(p)=q
if s=nil then table
else next(s)=p
end if
search=p
end if
end if
return
end while
search=nil return

Задания

Дан массив целых чисел. Составить процедуры метода транспозиции и перестановки в начало. Решить заданную задачу и переставить найденный в задаче элемент обоими методами в начало списка.

ВАРИАНТ 1. Найти максимальный элемент массива.

ВАРИАНТ 2. Найти минимальный элемент массива.

ВАРИАНТ 3. Найти число, нацело делящееся на 11 ( если таких чисел несколько, то найти максимальное; если таких чисел нет — выдать сообщение ).

ВАРИАНТ 4. Найти число, нацело делящееся на 11 ( если таких чисел несколько, то найти максимальное; если таких чисел нет — выдать сообщение ).

ВАРИАНТ 5. Найти элемент, разность соседних элементов которого не меньше 72. Если таких элементов несколько, выбрать максимальный. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 6. Найти элемент, частное соседних элементов которого четное число. Если таких элементов несколько, выбрать максимальный или минимальный элемент. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 7. Найти элемент, разность соседних элементов которого четное число. Если таких элементов несколько, выбрать максимальный или минимальный элемент. Если такого элемента нет, выдать сообщение.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

minsk1.net

Категория: Учебники