Связанный список без struct

Question

Может ли кто-нибудь помочь мне с единственным списком? Я знаю, как это сделать со структурой, но теперь я хочу знать, как это сделать, только с массивами и указателями без структуры или узлов. Алгоритмы, пожалуйста, благодарю вас.

#include <iostream> 
using namespace std; 

const int size=5; 
int data[size]; 
int *mem; 
int add[size]; 
int top = -1; 

void AddLast(int value) 
{ 
if(top==-1) 
{ 
    top=data[value];    
} 
else 
{ 
top++; 
top=data[value];  
} 
} 


void print() 
{ cout << "Queue: "; 
for(int i = 0; i != top; i = (i + 1) % size) 
{ 
    cout << data[i] << "->"; 
} 
cout << endl; 

} 


int main() 
{ 

AddLast(2); 
print(); 
AddLast(3); 
print(); 
AddLast(4); 
print(); 
cin.get(); 
    return 0; 
    } 

Я хочу добавить, добавить и добавить отсортированные ... это так?

Answer 1

Вы не можете сделать это только с одним массивом, вам нужно как минимум два: один для данных и один для ссылок. Если вы вообще не хотите использовать структуры (хотя на самом деле я не вижу причины для этого), у вас может быть несколько массивов данных.

В массиве данных содержатся фактические данные, в этом нет ничего особенного. Массив ссылок содержит индексы в массиве данных, где каждый индекс является «следующим» указателем.

Например, предположим, что вы хотите иметь связанный список целых чисел, и у вас есть три целых числа в списке (их значения не имеет значения), позволяет назвать этот массив d данных, то у вас есть d[0], d[1] и d[2]. Первый узел в списке: d[1], затем d[0] и последний d[2]. Затем вам нужна переменная головы, которая сообщает, какой индекс является главой списка, эта переменная головы инициализируется на 1 (и «указывает» на d[1]). Затем мы имеем массив ссылок, назовем его l, так как голова «указывает» на 1, мы получаем l[1], чтобы получить следующий узел, содержимое l[1] - это 0, которое сообщает нам, что следующий узел - d[0]. Чтобы получить следующий узел, мы проверяем l[0], который дает нам 2 для d[2]. Следующая ссылка, l[2] может быть -1, чтобы отметить конец списка.

Конечно, массивы данных и массив ссылок должны быть одного размера.

Answer 2

Массив s из структур с членами A, B, C, можно эмулировать тремя массивами a, b и c, где например a[i] представляет s[i].A и так далее. Так что это ваше требование о каких-либо структурах. Затем выполнение связанного списка с массивами, то есть с индексами вместо указателей, является простой записью; концепции абсолютно одинаковы. Но вы можете найти технику использования бесплатного списка, списка доступных логических узлов; это позволяет вам освобождать узлы, а также выделять их простым способом.

Answer 3

Существует (уродливый) способ сделать связанный список с массивами.

Вот пример того, как вы можете что-то делать с массивами, но я бы никогда не рекомендовал даже думать об этом.

template<class T> 
typedef char[sizeof(T) + sizeof(uintptr_t)] listNode; 

template<class T> 
listNode<T>* getNext(const listNode<T>& x){ 
    return (listNode<T>*)(((char*)x)[sizeof(T)]); //notice how you have to increment the pointer address 
} 

template<class T> 
T& getValue(listNode<T>& x){ 
     return (T) x; 
} 

Это слишком много отливок. Это менее уродливо, если вы создаете массив из двух указателей и просто бросаете первое значение в указатель на то, что вас волнует, но это все еще не то, что я бы рекомендовал.