Реализация списка массивом

Список

Двумерный массив

			…	j	…	m
			…	1j	…	1m	l
			…	2j	…	2m
…	…	…	…	…	…	…
i	i1	i2	…	ij	…	im
…	…	…	…	…	…	…
n	n1	n2	…	nj	…	nm

Представление массива в памяти по строкам:

Aij=Am+(i-1)*m*l+(j-1)*l=Am+((i-1)*m+j-1)*l; 1...n

Aij=Am+(i*m+j)*l, 0..n-1

Список – набор пронумерованных однотипных элементов переменной длины. Для списка определены операции:

─ Выборка элемента (чтение). Аргумент: номер элемента, результат6 значение элемента. Ошибка: элемента с заданным номером нет.

─ Добавление элемента. Аргумент: номер элемента и значение, результат: отсутствует. Ошибка: элемента с заданным номером нет.

─ Удаление элемента. Аргумент: номер элемента, результат: отсутствует. Ошибка: элемента с заданным номером нет.

─ Возможна операция «запись в элемент». Аргументы: номер и значение, результат: нет. Ошибка: элемента с заданным номером нет.

Список операций приведен для абстрактного списка, т.е. не имеющего ограничений на длину. В компьютере существуют ограничения на ресурсы и бесконечной длины быть не может. Поэтому при программной реализации списка при операции добавления может возникнуть ошибка «невозможно добавить элемент».

Для реализации списка массивом кроме массива, хранящего значения элементов, необходимо иметь 2 переменных:

S – размер массива, т.е. максимальное количество элементов.

С – текущее количество элементов списка.

При пустом списке С=0.

S					…	n-1
n					…
C

Выборка:

При выборке некоторого i-го элемента (элементы стоят друг за другом), операция заключается в чтении i-го элемента из массива.

Тв=1 уо (условная операция)

Добавление:

Добавить V после i-го элемента.

→ n/2 элементов * 2 уо

Тдоб=(n+1) уо

Туд = n уо

Дата добавления: 2014-01-15