Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Создание списка с помощью массивов

Автор: this 28.4.2006, 14:00

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

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

Автор: nostromo 28.4.2006, 14:18

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

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

Автор: Akina 28.4.2006, 14:43

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

Автор: blur 6.5.2006, 17:35

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

Автор: bsa 6.5.2006, 21:57

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

Код


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 );
}