什麼是光標鏈接列表？ [C++]

我的教授向我提供了一個名爲CursorList.cpp的文件，它實現了「光標鏈接列表」。問題是 - 我不知道甚至是什麼！什麼是光標鏈接列表？ [C++]

有人能給我它的要點嗎？

謝謝！

2010-04-07 Yuval Karmi

尤瓦，你應該通過看到的接口開始文件已經暴露。也就是說，閱讀它，查看哪些公共方法，如何使用它們等等。從名稱看，它似乎非常確定它實現了鏈接列表數據結構，即可以插入，刪除，遍歷的鏈接列表數據結構，之類的東西。測試一下。 – 2010-04-07 03:27:51

據this，這裏是一個指針鏈表的一些背景：

某些語言不支持指針對象
使用數組來代替
開始有空閒列表
從分配空間空閒列表需要時
刪除：更改指針，添加到空閒列表

所以基本上是一個不使用指針實現的鏈表。也許這個實現應該是「容易」理解的？

來源

2010-04-07 01:57:59

仍然不是很清楚它們是什麼。那麼我能否擴展我的問題並詢問在這種情況下使用的是什麼清單？謝謝！ – 2010-04-07 01:59:09

http://en.wikipedia.org/wiki/Linked_list – stefanB 2010-04-07 02:06:52

我的猜測是它是一個linked list另外保留一個指向「current」元素的指針，例如用於遍歷列表。

如果你想確定你的教授究竟是什麼意思，看看.cpp文件，找出那裏實施的東西。

來源

2010-04-07 02:11:46 sth

即與我此ADT^H^H^H ^對象類型的回味同意 - 列表+當前位置 - 回到我的數據結構類（80年代，唉）之前，該單詞被「偷」爲（僅）和SQL結果集緩衝區 – Roboprog 2012-11-20 17:54:41

CursorList是一個鏈接列表的數組版本。本質上，您有一個列表節點數組，但不是每個節點都包含指向鏈接列表中下一項的指針，數組中的每個節點元素都包含下一個節點元素的索引。因此，例如，如果我們想將5, 3, 2, 11, 9存儲在鏈表中，我們將有5 -> 3 -> 2 -> 11 -> 9 -> NULL。插入不是問題，因爲我們只是將最後一個指針更改爲指向插入的節點，並將插入的節點指向NULL。刪除是一樣的，我們只是重新調整指針。然而，必須總是爲新節點動態分配（使用malloc或new）內存可能會有問題。

如果我們要存儲在CursorList中，我們首先聲明數組的最大大小，然後填充它。所以我們說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對象，我們將有一些看起來像這樣經過： CursorList after insertions

現在如果我們要刪除5所有

我們要做的就是更新next索引。所以我們留下了這個： CursorList with 5 removed

一個問題出現了，我們怎麼知道該怎麼設置5的next索引？那麼這就是Freelist（在@Justin Ethier的repsonse中提到）進來的地方。Freelist包含了陣列中仍然有空的索引。所以在創建CursorList之後，Freelist有0-9。當listNode對象被分配給數組的元素時，Freelist將刪除這些索引。當一個數字被刪除（例如上面的例子5）時，索引被添加回Freelist。如果我們想爲CursorList添加一個數字，我們只需更新適當元素的next索引。

來源

2014-12-23 00:36:03 sbru

在遊標實現中，我們自己構建存儲池，將未使用的節點存儲在存儲在數組中的鏈接列表中。

在C和C++，存儲池是由一組由語言提供庫函數來管理。在開始執行時，存儲的適當大的池是從操作系統獲取。當程序需要一個新的節點，從池由語言庫函數獲得的存儲。如果存儲空間不足是在池中可用，庫請求從操作系統額外的池空間。當存儲由程序，語言庫函數它返回到存儲池釋放。光標執行，通常會在系統中作爲一個數組獲得固定的存儲量，並提供類似於新的功能和刪除的應用程序使用

來源

2017-09-17 11:01:03

什麼是光標鏈接列表？ [C++]

回答

相關問題