VPF::Создание списка с помощью массивов

this

Дата 28.4.2006, 14:00 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 98
Регистрация: 12.9.2005

Репутация: нет
Всего: 1

Всем привет,
Подскажите как можно реализовать список без использования указателей, с помощью двух массивов (вроде как в одном массиве храняться данные, а в другом их адреса). Не откажусь и откода с примером smile

. Это задание - лаба по алгоритмам и структурам данных.

nostromo

Дата 28.4.2006, 14:18 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

Первый массив (data) -- сами данные.
Второй (nextIndexes) содержит индексы следующих элементов (односвязный список).

Алгоритм вставки нового элемента после заданного (k-го):
1. Добавляем в массив data новый элемент (пусть его индекс равен i0).
2. iTmp := nextIndexes[k]; nextIndexes[k] := i0; nextIndexes[i0] := iTmp.

--------------------

На пыльных тропинках далеких планет останутся наши следы.

Akina

Дата 28.4.2006, 14:43 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

или массив структур. структура состоит из полей Data и NextIndex

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

blur

Дата 6.5.2006, 17:35 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 126
Регистрация: 9.11.2004

Репутация: нет
Всего: 1

А не поясните на примере кода? Например, как создается такой список.

bsa

Дата 6.5.2006, 21:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: нет
Всего: 196

Что-то в этом духе (это двусвязный список).

Код


struct data {
         ....
         int prev, next;
};

struct data ArrayData[100];

int input_data(void) {
   int i = 0;
   while( i < 100) {
       fill_data(ArrayData + i); 
       if ( i > 0 )
         ArrayData[i - 1].next = i;
       ArrayData[i].prev = i - 1;       //prev = -1 означает что это первый элемент списка
       ArrayData[i].next = -1;       //next = -1 означает что это последний элемент списка
       ++i;
   }
   return i; // число считанных блоков
}

struct data * get_data( int i, int first ) { // i - номер желаемой записи, first - индекс первой записи.
     while( (i--) && ( first >= 0 ) )
          first = ArrayData[first].next;
     return ( first < 0 ) ? NULL : ( ArrayData + first );
}

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »