c-不带结构但仅使用数组的链表

Question

#include <stdio.h>
int main()
{
int n, i;
int head = 0;
printf("No of Students:n");
scanf("%d", &n);
int data[n];
int address_of_data[n];
int *next;
printf("Enter Marks:n");
for (i = 0; i < n; i++)
{
scanf("%d", &data[i]);
}
for (i = 0; i < n; i++)
{
if (data[head] != -1)
{
address_of_data[head] = &data[i];
}
else
{
break;
}
head++;
}
next = address_of_data[0];
for (i = 0; i < n; i++)
{
printf("%d ", *(next + i));
}
return 0;
}

在上面的代码中，我使用指针来打印数据值。使用两个数组，一个用于数据，另一个用于地址。但我不知道如何真正实现链表，我真的很困惑，有人能告诉我如何在不使用结构的情况下实现链表吗。

Answer 1

链表的主要优点是，当您插入或附加一个元素时，您可以将该元素存储在内存中的任何位置。列表中的其他元素可以指向它，如果你在列表上迭代，你可以在内存中的任何地方沿着元素形成的链上的指针来回跳跃，直到你到达尾部，尾部有一个空指针，因为它是最后一个元素。

实现"仅使用数组"的链表实际上没有多大意义。即使你可以，你为什么要这样做？数组非常棒，因为你可以在恒定的时间内直接对它们进行索引——你不能对链表进行索引，只能对它们进行迭代。但是数组也有缺点——它们是固定大小的，当它们填满时，就会填满！大多数共享库列表，如Java中的ArrayList或C++中的vector类，都将底层数据存储在一个固定大小的数组中，然后如果您为该数组插入了太多项目，它们会在后台创建一个新的、更大的数组，并为您复制元素。当你的阵列空间不足时，真的没有什么神奇的解决方案。

既然如此，为什么只使用数组来实现链表呢？你去掉了他们唯一的优势——你可以任意追加，而不需要昂贵的重新分配。我甚至不确定这是否是一个定义明确的问题。如果你真的很绝望，你可以创建一个大数组，并将其视为你自己的虚拟内存，在其中分配和释放插槽，然后将一个双元素数组视为一个条目(entry[0]=data，entry[1]=next的"address"，即大数组的索引(。但这有点糟糕的代码，确实没有抓住链表的要点。

Answer 2

这里是一个简单链表的完整示例-为了在纯C中更容易；下一个"；结构中的成员-这是指向列表中后续成员的指针。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct MY_DATA {
int number;
char info[30];
struct MY_DATA *next;
};
#define MAX_ELEMS   5
int main(int argc, char **argv)
{
struct MY_DATA *root = NULL;        /* Root of list */
struct MY_DATA *prev = NULL;        /* Previously created element */
for(int i = 0; i < (MAX_ELEMS); i++)
{
/* Allocate memory ... */
struct MY_DATA *new_data = (struct MY_DATA *)malloc(sizeof(MY_DATA));
/* ...and inialize new data set */
memset(new_data, 0x00, sizeof(MY_DATA));
new_data->number = i * i;
sprintf((char *)&(new_data->info), "This is data record %d", i);

if (root == NULL)
{
root = prev = new_data;      /* Remember the first element */
}
else
{
prev->next = new_data;      /* The previous element has now a successor */
prev = new_data;            /* Remember this for next iteration */
}
}
struct MY_DATA *current = root;     /* Get the 1st element in the list */
struct MY_DATA *temp = NULL;        /* Just for clean up stuff */
for(int i = 0; i < (MAX_ELEMS); i++)
{
/* Display data */
printf("Data set #%d: %sn", current->number, current->info);
temp = current;             /* This becomes deleted */
current = current->next;    /* Set current pointer to successor of current element */
free(temp);
}
return 0;
}

另一个例子-使用索引或指针访问数组：

#include <stdio.h>
#define MAX_ELEMS   5
int my_array[MAX_ELEMS] = { 5, 18, 42, 31, 10 };
int main(int argc, char **argv)
{
int *current = (int *)my_array;     /* Get the 1st element in the list */
for(int i = 0; i < (MAX_ELEMS); i++)
{
/* Using array index */
printf("Data set #%d n" 
"  Indexed access: %dn", i, my_array[i]);
/* Using the pointer*/
printf("  Pointer access: %dn", *current++);
}
return 0;
}