我的教授给了我一个名为CursorList.cpp的文件,实现了“游标链表”。问题是 - 我甚至不知道那是什么!
有人能简要解释一下吗?
谢谢!
我的教授给了我一个名为CursorList.cpp的文件,实现了“游标链表”。问题是 - 我甚至不知道那是什么!
有人能简要解释一下吗?
谢谢!
5, 3, 2, 11, 9
,我们将得到5 -> 3 -> 2 -> 11 -> 9 -> NULL
。插入操作并不是问题,我们只需更改最后一个指针指向插入的节点,并使插入的节点指向NULL
。删除也是一样的,我们只需要重新调整指针。然而,总是需要动态分配(使用malloc或new)内存来创建新节点可能会有问题。listNode cursorList[10]
,其中我们声明一个listNode对象如下:class listNode {
public:
listNode() {
data = -1;
next = NULL;
}
listNode(int inputData, &listNode inputNext) {
data = inputData;
next = inputNext;
}
private:
int data;
listNode* next;
};
在用listNode对象填充数组后,我们将得到以下类似的结果:
现在,如果我们想要移除5,我们只需要更新next
索引。这样我们就会得到下面这个结果:
一个问题出现了,我们怎么知道要设置5的next
索引为什么值呢?这就是Freelist(@Justin Ethier回答中提到的)发挥作用的地方。Freelist包含数组中仍然空闲的索引。在创建CursorList时,Freelist包含0-9。当listNode对象被分配给数组元素时,Freelist会删除这些索引。当一个数字被移除(例如上面的5),该索引将被添加回Freelist中。如果我们想要向CursorList中添加一个数字,我们只需要更新相应元素的next
索引即可。
我猜测它是一个链表,除此之外还保留了一个指向“当前”元素的指针,例如用于遍历列表。
如果你想确切地知道你的教授的意思,看一下.cpp文件,并找出那里实现了什么。