c - 仅使用数组的链表实现

Question

我必须只使用数组(没有 malloc-only 静态内存)来实现一种链表类型的数据结构。 我要做的是这样的: (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)而且这个指向过程必须按递增顺序，我的意思是你可以在下面看到我的意思是如果我们在索引 0,1 处添加 Freq 我们将得到 3 那么这个 3 是设置为 at last index on array 我们可以看到在索引 2 处 next 指向索引 4(不是 3 - 就像上面那样 - 这样做只是为了保持递增顺序，我们只需要处理索引的移动(每个元素都是静态的(不要改变它的位置，只是索引会以递增的顺序指向 Freq。))。

(这部分很容易实现，我已经做到了。) 当我必须添加我在第 (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++;
}.

有什么想法可以实现“下一个”部分吗？

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
}