1 
class Nodetype
{
  int info;
  Nodetype next;

  Nodetype(int i)
  {
     info=i;
     next=null;
  }
}

我的教科书有这个代码来动态创建链接列表。问题是，当程序逐行执行时，它将变量“info”定义为“int”类型，然后将变量“next”定义为 Nodetype。

这里实际发生了什么？

这是否意味着变量“下一个”将包含 -

  1. 构造函数“节点类型”
  2. 信息
  3. 节点类型“next”，其中“next”将再次具有所有 1、2、3，然后 3 将再次具有 1、2、3 ......等等......直到无穷大？

我真的很生气，因为我无法理解它是如何工作的，有人可以轻松解释一下吗？

4

9 回答 9

3

您的代码很好地遵循了列表的定义：列表是null或元素后跟列表。
在您的情况下，“元素”是由一个int值定义的，而“跟随”部分是next变量；在 Java 变量中（当它们不是字面量时，int值是）实际上是指针，所以虽然它们没有被初始化，但它们不存储任何有效值并且它们不指向任何内存区域（即它们的值是null），所以虽然next变量保持原样，但您的元素后面没有任何其他元素。要动态地将元素添加到您的列表中，您需要一个指向您添加的最后一个元素的指针，否则您将无法再次找到它们：

int i = 0;
Nodetype head = new Nodetype(i++);
Nodetype last = new Nodetype(i++);
head.next = last;
while (i<5) {
    Nodetype temp = new Nodetype(i++);
    last.next = temp;
    last = temp;
}
while(head) {
    System.out.println(head.info);
    head = head.next;
}

请注意，在最后几行中，您丢失了head指针，并且无法返回列表的起点。使用列表时请记住这一点；）

于 2011-12-10T11:43:10.203 回答
1

首先变量next不指向任何对象（它指向null）。有时您会使用next = new NodeType(number). 这个想法是你使用组合 - 你有一个类的实例，它引用了另一个实例。它就像nodeA指向nodeB，nodeB指向nodeC。这里有三个实例，第一个实例引用第二个实例，第二个实例引用第三个实例。第三个实例是最后一个实例，它的下一个实例指向null。

于 2011-12-10T11:27:43.990 回答
1

该字段next是对类型对象的引用Nodetype。起初它不会指向任何东西——因为它被实例化为null. 当您为其分配一个值时，它将仅指向该值，除​​非您在列表中创建一个循环，否则任何事情都不会无限继续。

于 2011-12-10T11:28:14.003 回答
1

您创建了类NodeType并在类内部定义了该类的对象。因此该对象（在您的示例中next）将具有int info变量NodeType next对象和构造函数。

于 2011-12-10T11:28:18.157 回答
1

next是对另一个Nodetype实例的引用。如果next == null这意味着当前元素是列表中的最后一个。

让我们看一个例子：

Nodetype node = new Nodetype(0);        // i = 0, next = null
Nodetype anotherNode = new Nodetype(1); // i = 1, next = null
node.next = anotherNode;                // now the first node has a ref to the second
于 2011-12-10T11:28:25.720 回答
1

它将包含 Null，因为变量未初始化为任何值。

于 2011-12-10T11:28:26.643 回答
1

Nodetype是您的类，它定义节点实例将包含的数据以及对链表中下一个节点的引用。对下一个节点的引用将是 type 的对象Nodetype。这里没什么难的，这是链表的经典实现。

您可能想查看斯坦福的这个很棒的链表资源。

于 2011-12-10T11:28:42.337 回答
1

其工作方式是列表由单个元素组成，每个元素只有一个指向其后元素的指针：

Nodetype next;

列表中每个元素实际包含的信息如下：

int info;

你可以把一个列表想象成一个“链”：它不是一个真正的单个对象，而是多个链接的复合对象。从每个链接中，您只能看到下一个链接（或者，如果链表在两个方向都有引用：下一个和上一个链接），因此为了使所有元素可用，您必须保留引用到“链”中的第一个元素。

注意：List对象是引用“链”的第一个链接的单个对象。

于 2011-12-10T12:17:24.197 回答
0 
#include<stdio.h>
#include<stdlib.h>

void print_list(int *arr,int *size,int *capacity)
{
     printf("capacity = %d; size = %d; elements = ",*capacity,*size);
     for(int i=0;i<(*size);i++){
        printf("%d ",arr[i]);
    }
     printf("\n");
}

int * push_back(int *arr,int data,int *size,int *capacity)
{
    int *b;
    if(*size == *capacity){

        *capacity = 2*(*capacity);
        b = (int *)malloc(sizeof(int)*(*capacity));

        for(int i=0;i<(*size);i++){
        b[i]= arr[i];
        }
        b[*size]=data;
        *size=*size+1;
        print_list(b,size,capacity);
        return b;
    }

     arr[*size]=data;
     *size=*size+1;
     print_list(arr,size,capacity);

     return arr;
}
int main()
{
     int size=0;
     int n;
     int x;
     int *arr;
     arr = (int *) malloc(sizeof(int));
     int capacity=1;

     scanf("%d",&n);

     for(int i=0;i<n;i++){
        scanf("%d",&x);
        arr=push_back(arr,x,&size,&capacity);
     }
}

它的工作。

于 2019-08-31T06:28:11.577 回答