MFC - 連結串列

上一頁
下一頁

連結串列是一種線性資料結構，其中每個元素都是一個單獨的物件。列表的每個元素（我們稱之為節點）包含兩個專案——資料和指向下一個節點的引用。最後一個節點的引用為 null。

連結串列是一種資料結構，由一組節點組成，這些節點共同表示一個序列。它是一種使用結構儲存資料的方法，這樣程式設計師可以在需要時自動建立一個新的資料儲存位置。它的一些主要特點是：

  • 連結串列是一系列包含專案的連結。

  • 每個連結都包含到另一個連結的連線。

  • 列表中的每個專案都稱為節點。

  • 如果列表至少包含一個節點，則一個新節點將被定位為列表中的最後一個元素。

  • 如果列表只有一個節點，則該節點表示第一個和最後一個專案。

連結串列有兩種型別：

單鏈表

單鏈表是一種資料結構。在單鏈表中，列表中的每個節點都儲存節點的內容以及指向列表中下一個節點的指標或引用。

Single Linked List

雙向連結串列

雙向連結串列是一種連結串列資料結構，它由一組稱為節點的順序連結的記錄組成。每個節點包含兩個欄位，它們分別引用序列中前一個節點和下一個節點。

Double Linked List

CList 類

MFC 提供了一個名為CList的類，它是一個模板連結串列實現，並且執行良好。CList 列表的行為類似於雙向連結串列。POSITION 型別的變數是列表的關鍵。您可以使用 POSITION 變數作為迭代器來順序遍歷列表，並作為書籤來儲存位置。

以下是 CList 物件的不同操作：

建立 CList 物件

要建立 CList 值或物件的集合，必須首先確定集合的值的型別。您可以使用現有的原始資料型別，例如 int、CString、double 等，如下面的程式碼所示。

CList<double, double>m_list;

新增專案

要新增專案，可以使用 CList::AddTail() 函式。它在列表末尾新增一個專案。要在列表開頭新增元素，可以使用 CList::AddHead() 函式。在 OnInitDialog() 中，建立 CList 物件並新增四個值，如下面的程式碼所示。

CList<double, double>m_list;

//Add items to the list
m_list.AddTail(100.75);
m_list.AddTail(85.26);
m_list.AddTail(95.78);
m_list.AddTail(90.1);

檢索專案

POSITION 型別的變數是列表的關鍵。您可以使用 POSITION 變數作為迭代器來順序遍歷列表。

步驟 1 - 要從列表中檢索元素，我們可以使用以下程式碼，該程式碼將檢索所有值。

//iterate the list
POSITION pos = m_list.GetHeadPosition();
while (pos) { 
   double nData = m_list.GetNext(pos);
   CString strVal;
   strVal.Format(L"%.2f\n", nData);
   m_strText.Append(strVal);
}

步驟 2 - 以下是完整的 CMFCCListDemoDlg::OnInitDialog() 函式。

BOOL CMFCCListDemoDlg::OnInitDialog() {
   CDialogEx::OnInitDialog();

   // Set the icon for this dialog. The framework does this automatically
   // when the application's main window is not a dialog
   SetIcon(m_hIcon, TRUE);             // Set big icon
   SetIcon(m_hIcon, FALSE);             // Set small icon

   // TODO: Add extra initialization here
   CList<double, double>m_list;

   //Add items to the list
   m_list.AddTail(100.75);
   m_list.AddTail(85.26);
   m_list.AddTail(95.78);
   m_list.AddTail(90.1);

   //iterate the list
   POSITION pos = m_list.GetHeadPosition();
   while (pos) {
      double nData = m_list.GetNext(pos);
      CString strVal;
      strVal.Format(L"%.f\n", nData);
      m_strText.Append(strVal);
   }

   UpdateData(FALSE);
 
   return TRUE; // return TRUE unless you set the focus to a control
}

步驟 3 - 編譯並執行上述程式碼後，您將看到以下輸出。

Retrieve

在中間新增專案

要在列表中間新增專案，可以使用 CList::InsertAfter() 和 CList::InsertBefore() 函式。它接受兩個引數——第一個是位置（可以在其中新增），第二個是值。

步驟 1 - 讓我們插入一個新專案，如下面的程式碼所示。

BOOL CMFCCListDemoDlg::OnInitDialog() {
   CDialogEx::OnInitDialog();
   
   // Set the icon for this dialog. The framework does this automatically
   // when the application's main window is not a dialog
   SetIcon(m_hIcon, TRUE);             // Set big icon
   SetIcon(m_hIcon, FALSE);          // Set small icon

   // TODO: Add extra initialization here
   CList<double, double>m_list;

   //Add items to the list
   m_list.AddTail(100.75);
   m_list.AddTail(85.26);
   m_list.AddTail(95.78);
   m_list.AddTail(90.1);

   POSITION position = m_list.Find(85.26);
   m_list.InsertBefore(position, 200.0);
   m_list.InsertAfter(position, 300.0);

   //iterate the list
   POSITION pos = m_list.GetHeadPosition();
   while (pos) {
      double nData = m_list.GetNext(pos);
      CString strVal;
      strVal.Format(L"%.2f\n", nData);
      m_strText.Append(strVal);
   }

   UpdateData(FALSE);

   return TRUE; // return TRUE unless you set the focus to a control
}

步驟 2 - 您現在可以看到我們首先檢索了值 85.26 的位置，然後在其之前和之後插入了一個元素。

步驟 3 - 編譯並執行上述程式碼後，您將看到以下輸出。

Adding Item

更新專案值

要更新陣列中間的專案，可以使用 CArray::SetAt() 函式。它接受兩個引數——第一個是位置，第二個是值。

讓我們將列表中的 300.00 更新為 400，如下面的程式碼所示。

BOOL CMFCCListDemoDlg::OnInitDialog() {
   CDialogEx::OnInitDialog();

   // Set the icon for this dialog. The framework does this automatically
   // when the application's main window is not a dialog
   SetIcon(m_hIcon, TRUE);              // Set big icon
   SetIcon(m_hIcon, FALSE);            // Set small icon

   // TODO: Add extra initialization here
   CList<double, double>m_list;

   //Add items to the list
   m_list.AddTail(100.75);
   m_list.AddTail(85.26);
   m_list.AddTail(95.78);
   m_list.AddTail(90.1);

   POSITION position = m_list.Find(85.26);
   m_list.InsertBefore(position, 200.0);
   m_list.InsertAfter(position, 300.0);

   position = m_list.Find(300.00);
   m_list.SetAt(position, 400.00);

   //iterate the list
   POSITION pos = m_list.GetHeadPosition();
   while (pos) {
      double nData = m_list.GetNext(pos);
      CString strVal;
      strVal.Format(L"%.2f\n", nData);
      m_strText.Append(strVal);
   }

   UpdateData(FALSE);

   return TRUE; // return TRUE unless you set the focus to a control
}

編譯並執行上述程式碼後，您將看到以下輸出。您現在可以看到 300.00 的值已更新為 400.00。

Updating Item

刪除專案

要刪除任何特定專案，可以使用 CList::RemoveAt() 函式。要從列表中刪除所有元素，可以使用 CList::RemoveAll() 函式。

讓我們刪除值為 95.78 的元素。

BOOL CMFCCListDemoDlg::OnInitDialog() {
   CDialogEx::OnInitDialog();

   // Set the icon for this dialog. The framework does this automatically
   // when the application's main window is not a dialog
   SetIcon(m_hIcon, TRUE);              // Set big icon
   SetIcon(m_hIcon, FALSE);             // Set small icon

   // TODO: Add extra initialization here
   CList<double, double>m_list;

   //Add items to the list
   m_list.AddTail(100.75);
   m_list.AddTail(85.26);
   m_list.AddTail(95.78);
   m_list.AddTail(90.1);

   POSITION position = m_list.Find(85.26);
   m_list.InsertBefore(position, 200.0);
   m_list.InsertAfter(position, 300.0);
   
   position = m_list.Find(300.00);
   m_list.SetAt(position, 400.00);

   position = m_list.Find(95.78);
   m_list.RemoveAt(position);

   //iterate the list
   POSITION pos = m_list.GetHeadPosition();
   while (pos) {
      double nData = m_list.GetNext(pos);
      CString strVal;
      strVal.Format(L"%.2f\n", nData);
      m_strText.Append(strVal);
   }
   UpdateData(FALSE);
   
   return TRUE; // return TRUE unless you set the focus to a control
}

編譯並執行上述程式碼後，您將看到以下輸出。您現在可以看到值 95.78 不再是列表的一部分。

Removing Item
列印頁面
上一頁
下一頁
廣告