Главная Полное построение алгоритма [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.
(Окончание Рис. 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 |