遍歷 C++ 中的列表

1. C++ 中的列表
2. 遍歷 C++ 中的列表

這個簡短的程式設計教程將討論 C++ 中廣泛使用的資料結構，即 List。在 C++ 標準模板庫 (STL) 中，我們有一個可用於此資料結構的類 list。

裡面打包了一堆函式，可以用來對列表執行多個操作。在本文後面，我們將討論如何遍歷列表並檢視或編輯列表。

C++ 中的列表

列表，或稱連結列表，是一種線性資料結構，可以作為資料容器，將資料儲存在記憶體中。與向量和陣列不同，列表中的資料不儲存在連續的記憶體位置。

相反，資料儲存在隨機記憶體位置。插入列表中的每個元素稱為節點。

列表中的每個節點都包含一個指向列表下一個元素的指標。這就是為什麼列表的元素沒有儲存在連續位置的原因；因此，它也被稱為連結串列。

列表可以分為兩種型別：

1. 單連結串列
2. 雙向連結串列

單連結串列

在這種型別的連結串列中，所有的節點有 2 個部分，一個用於資料，一個用於儲存指向下一個節點的指標。第二部分儲存列表的下一個節點的地址。

雙向連結串列

在這種型別的連結串列中，所有節點都有 3 部分，第一部分是指向前一個節點的指標，第二部分是儲存資料，第三部分包含引用連結串列下一個元素的指標。

STL 中的 list 類包含一個雙向連結串列。像陣列一樣，這種列表型別的插入和刪除需要線性時間。

但是，列表不需要傳染性記憶體塊。此外，通過一次附加單個列表節點來增長列表比重新分配整個動態陣列（如向量所做的）更容易和更合理。

因此，它被認為是比陣列和向量等其他資料結構更靈活的資料結構。

另一種資料結構 forward_list 只能遍歷一個方向並且是一個單連結串列。與其他資料結構相比，列表和前向列表的主要缺點是我們不能像在陣列中一樣通過給出其位置來直接訪問任何列表元素。

例如，要訪問列表中的第 5 個元素，必須從某個端點開始，無論是開始還是結束到該位置，這需要線性時間。列表還使用額外的 RAM 來儲存每個元素的連線資訊。

遍歷 C++ 中的列表

我們可以使用標準模板庫 C++ 的 iterator 類來遍歷列表元素。其語法如下：

std::list<int>::iterator itr;

列表中有不同的迭代方法：

讓我們看看下面的程式碼，它使用了列表類的不同功能。

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

void displaylist(list<int> l)  // print function to show list
{
  list<int>::iterator myitr;
  for (myitr = l.begin(); myitr != l.end(); ++myitr) cout << "  " << *myitr;
  cout << endl;
}
int main() {
  list<int> mylist1;
  for (int a = 0; a < 10; ++a) {
    int r = 1 + (rand() % 50);
    mylist1.push_back(r);
  }
  cout << "\nData of List 1 : ";
  displaylist(mylist1);
  cout << "\nList first element : " << mylist1.front();
  cout << "\nAfter we pop first element: ";
  mylist1.pop_front();
  displaylist(mylist1);

  cout << "\nWhen we sort the list: ";
  mylist1.sort();
  displaylist(mylist1);

  return 0;
}

輸出：

Data of List 1 :   34  37  28  16  44  36  37  43  50  22

List first element : 34
After we pop first element:   37  28  16  44  36  37  43  50  22

When we sort the list:   16  22  28  36  37  37  43  44  50