Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Операции со списками при последовательном хранении






При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.

Пусть имеется линейный список с целыми значениями и для его хранения используется массив d (с числом элементов 100), а количество элементов в списке указывается переменной l. Реализация указанных ранее операций над списком представляется следующими фрагментами программ которые используют объявления:

 

float d[100]; int i, j, l; 1) печать значения первого элемента (узла) if (i< 0 || i> l) printf(" \n нет элемента"); else printf(" d[%d]=%f ", i, d[i]); 2) удаление элемента, следующего за i-тым узлом if (i> =l) printf(" \n нет следующего "); l--; for (j=i+1; j< =" 1" if узла i-того соседей обоих печать 3) d[j]=" d[j+1]; " > =l) printf(" \n нет соседа"); else printf(" \n %d %d", d[i-1], d[i+1]); 4) добавление нового элемента new за i-тым узлом if (i==l || i> l) printf(" \n нельзя добавить"); else { for (j=l; j> i+1; j--) d[j+1]=d[j]; d[i+1]=new; l++; } 5) частичное упорядочение списка с элементами К1, К2,..., Кl в список K1', K2',..., Ks, K1, Kt",..., Kt", s+t+1=l так, чтобы K1'= K1. { int t=1; float aux; for (i=2; i< =l; i++) if (d[i]=2; j--) d[j]=d[j-1]; t++; d[i]=aux; } }

Схема движения индексов i, j, t и значения aux=d[i] при выполнении приведенного фрагмента программы приведена на рис.2.


Рис.2. Движение индексов при выполнении операций над списком в последовательном хранении.

Количество действий Q, требуемых для выполнения приведенных операций над списком, определяется соотношениями: для операций 1 и 2 - Q=1; для операций 3, 4 - Q=l; для операции 5 - Q=l*l.

Заметим, что вообще операцию 5 можно выполнить при количестве действий порядка l, а операции 3 и 4 для включения и исключения элементов в конце списка, часто встречающиеся при работе со стеками, - при количестве действий 1.

Более сложная организация операций требуется при размещении в массиве d нескольких списков, или при размещении списка без привязки его начала к первому элементу массива.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.