реализация связанного списка с использованием только массива

Question

Мне нужно реализовать один тип связанного типа данных с использованием только массивов (без статической памяти только для malloc). То, что мне нужно сделать, это вот так: (1) У меня есть массив из множества элементов, скажем, массив [216] = {1 2 3 4} (я возьму очень большой размер, вот почему здесь 216) ,

(2) Я должен сделать добавление с индексом 0,1 и 2,3 и 4,5 и т. Д. (У индекса 0,1 есть «1», «2», их добавление равно 3). этот 3 затем будет помещен в конце массива (я имею в виду после «6», поэтому теперь массив: = {1 2 3 4 3}). Это я уже реализовал.

* Что я должен сделать, это:

(3) Я должен сделать программу так, что каждый элемент должен иметь это значение (Предположим, что я называю значение как «Freq» в моем коде) и индекс следующего элемента, на который он указывает, и последний элемент, который не должен указывать, должен содержать «-1» в следующем. Точно так же, как показано ниже: ** Я еще не сделал добавления, Это в принципе, После того, как добавлено, он будет расти (см., Наконец, для этого, пожалуйста). Перед выполнением добавление структуры данных, как это:

index:0 Freq: 1 Next :1 
index:1 Freq: 2 Next :2 
index:2 Freq: 3 Next :3 
index:3 Freq: 4 Next :-1 

(4) И это porocess указывать должно быть в порядке возрастания, я имею в виду вы можете увидеть ниже, что я имею в виду, если мы добавим Freq по индексу 0,1, мы получим 3, тогда это 3 будет последним индексом на массиве, и мы увидим, что при индексе 2 следующий указывает на индекс 4 (не 3- как делается только выше). Это делается только для поддержания возрастающего порядка , Нам просто нужно иметь дело с движением индекса (каждый элемент статичен (не меняйте его положение, только индекс укажет на Freq в порядке возрастания.))

(Эта часть проста в использовании mplement, я это сделал.) У меня проблема, когда я должен добавить в индексы, упомянутые в пункте (2). Структура данных должна выглядеть следующим образом: (после того) После выполнения добавления:

index:0 Freq: 1 Next :1 
index:1 Freq: 2 Next :2 
index:2 Freq: 3 Next :4 //It don't point to index 3.In order to mantain increasing order 
index:3 Freq: 4 Next :5 
index:4 Freq: 3 Next :3 //this is obtained by addition of Freq at index 0 and 1 
index:5 Freq: 7 Next :-1 //this is obtained by addition of Freq at index 2 and 3 

Любая идея, как реализовать вторую часть? (после добавления). Мой код (до добавления Партийно-не индексирует часть):

struct node 
{ 
int freq; 
int next; 
}; 
main() 
{ 
int i,count=0,j,f,s,data_size; 
struct node data[1000]; 


//I am skipping sime understood part 

data[data_size].freq=data[f].freq+data[s].freq;//where data_size=**elementsSize+1** .In out case there are 4 elements so data_size=5.The added element is to be placed at last.That's why i too it **"elementSize+1"**. 
data_size++; 
}. 

Любые идеи, как tmplement «следующий» часть?

Answer 1

Вы спрашиваете, как вставить элемент и сохранить список в порядке возрастания?

int insert(struct node *data, int new_freq, int data_size) { 
    // Impossible if new_freq is less than first element, 
    // because you don't have a head pointer(index) 
    assert(data[0].freq <= new_freq); 

    int i; 
    for (i = 0; data[i].next != -1; i = data[i].next) 
     if (data[data[i].next].freq > new_freq) // insert after i 
      break; 
    // insert at end of array if loop doesn't break 

    data[data_size].freq = new_freq; 
    data[data_size].next = data[i].next; 
    data[i].next = data_size; 
    return data_size + 1; // return new size 
}