Главная  Полное построение алгоритма 

[0] [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] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

else [удалить изнутри]

set LINK(PREV) LINK(PTR); and STOP fi else [Выбор следующей ячейки]

set PREVPTR; PTR LINK(FTR) fi. Шаг 4. [He в списке] НАПЕЧАТАТЬ «ЗНАЧЕНИЕ НЕ В СПИСКЕ»; and STOP.

О ,

PREV PTR

ОДИН

ЧЕТЫРЕ

один

ЧЕТЫРЕ

PREV

ОДИН

ЧЕТЫРЕ

PREV

ОДИН

ЧЕТЫРЕ

Рис. 2.3.4. Удаление ячейки из связанного списка.

Следующий алгоритм будет вносить в связанный список новую ячейку. Предположим, что в списке ячейки упорядочены в порядке возрастания содержимого поля ИНФО (INFO). Этот алгоритм аналогичен алгоритму DELETE (УДАЛЕНИЕ) в том отношении, что при выполнении операции внесения используются указатели PREV и PTR.

На рис. 2.3.7 проиллюстрирован процесс внесения, причем мы предполагаем, что

ОДИН < ДВА < ТРИ < ЧЕТЫРЕ

На рис. 2.3.8 и 2.3.9 приведены блок-схема и реализация следующего алгоритма:

Algorithm INSERT (ВНЕСЕНИЕ). Внести новую ячейку ROW (РЯД), где INFO (ROW)=VALUE, в упорядоченной связанный список, первая ячейка которого задается в FIRST (ПЕРВЫЙ). Шаг 1. [Выбор первой ячейки] Set PTR FIRST; PREV 0. Шаг 2. [Ячейка пуста?! While PTR=70 do шаг 3 od.




Шалить спереди

Удалить изнутри

Напечатать что не 6 списке

(Окончание

Рис. 2.3.5. Блок-схема алгоритаа DELETE (УДАЛЕНИЕ).

Шаг 3. [Предшествует ли новая ячейка выбранной?] If

VALUE<INFO(PTR)

then [вносится спереди?]

if PREV=0 then [внести новую ячейку спереди]

set FIRSTS ROW; LINK(ROW) ч- PTR; and STOP else [внесги новую ячейку

внутрь] set LIN К (PREV) ч-ROW; LIN К (ROW)



PTR; and STOP fi else [Выбрать очередную ячейку]

set PREVPTR; PTR LINK(PTR) fi. Шаг 4. [Список пуст?] If PREV=0

then [внести новую ячейку как единственную ячейку в списке] set FIRSTS ROW; LINK(ROW)0; and STOP else [внести новую ячейку в конец списка]

set LINK(PREV)ROW; LINK(ROW)0; and

STOP fi.

Списки смежности

В одном из эффективных способов представления сети G=(V, Е) используются связанные списки смежности. Это представление сильно напоминает векторы смеяшости (см. разд. 2.2), но, как правило, тре-

* SUeROUTINE DELETE CFIRST.INFO.LINK.VALUEJ

INTEGER INFO(500)tLINK{500bFIRST«VAl.OE:iPfiEVfPlR

С • ВЫБОР ПЕРВОЙ ЯЧЕЙКИ С

ITR S FIRST PREV - О

С ПРОВЕРКА НЕ ПУСТА ЛИ ЯЧЕЙКИ.

«г*

5. SF t PTR Ж* в i еоТО £ft

*10 uRiTcce.iooat

4008 FOFriATueti VAt-Ut NOr оМ LISTl RETURIt

С ПРОВЕРКА, НУЖНАЯ т ячейка

20 JF I JHFOtPTRJ «НЕ» VALUE J 50Та 6* С ТОГДА (ЭТО ПЕРВАЯ ЯЧЕЙКА?)

3» (fRctr «не» о } сото т

с ТОГДЛ СШЛИТЬ СПЕРЕДИ)

FIRST SS WNKIPTRI «ЕТиВМ

с ШШ (УДАЛИТЬ ИЗНУТРИ")

SB tlNKtPREVJ s tINK(PTR

RETCKM

<c с

£0 PREV = PTR

PTR = H«K(pTR> COTO 3

ШБОР СЛЕДУЮЩЕЙ ЯЧЕЙКИ

Рис. 2.3.6. Реализация алгоритма DELETE.



[0] [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] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0015