Учебники

MFC — связанные списки

Октябрь 18, 2018

Связанный список — это линейная структура данных, где каждый элемент является отдельным объектом. Каждый элемент (назовем его узлом) списка состоит из двух элементов — данных и ссылки на следующий узел. Последний узел имеет ссылку на ноль.

Связанный список — это структура данных, состоящая из группы узлов, которые вместе представляют последовательность. Это способ хранения данных со структурами, позволяющий программисту автоматически создавать новое место для хранения данных при необходимости. Некоторые из его характерных особенностей —

  • Связанный список — это последовательность ссылок, которая содержит элементы.

  • Каждая ссылка содержит ссылку на другую ссылку.

  • Каждый элемент в списке называется узлом.

  • Если список содержит хотя бы один узел, то новый узел позиционируется как последний элемент в списке.

  • Если в списке есть только один узел, этот узел представляет первый и последний элемент.

Связанный список — это последовательность ссылок, которая содержит элементы.

Каждая ссылка содержит ссылку на другую ссылку.

Каждый элемент в списке называется узлом.

Если список содержит хотя бы один узел, то новый узел позиционируется как последний элемент в списке.

Если в списке есть только один узел, этот узел представляет первый и последний элемент.

Есть два типа списка ссылок —

Единственный связанный список

Односвязные списки являются типом структуры данных. В односвязном списке каждый узел в списке хранит содержимое узла и указатель или ссылку на следующий узел в списке.

Единый связанный список

Двусвязный список

Двусвязный список — это структура связанных данных, которая состоит из набора последовательно связанных записей, называемых узлами. Каждый узел содержит два поля, которые являются ссылками на предыдущий и следующий узел в последовательности узлов.

Двойной связанный список

Класс CList

MFC предоставляет класс CList, который является реализацией связанного списка шаблонов и работает отлично. Списки CList ведут себя как двусвязные списки. Переменная типа POSITION является ключом для списка. Вы можете использовать переменную POSITION в качестве итератора для последовательного обхода списка и в качестве закладки для хранения места.

AddHead

Добавляет элемент (или все элементы в другом списке) к заголовку списка (создает новый заголовок).

AddTail

Добавляет элемент (или все элементы в другом списке) в конец списка (создает новый хвост).

найти

Получает позицию элемента, указанного значением указателя.

FindIndex

Получает положение элемента, указанного индексом, начинающимся с нуля.

GetAt

Получает элемент в заданной позиции.

GetCount

Возвращает количество элементов в этом списке.

GetHead

Возвращает элемент заголовка списка (не может быть пустым).

GetHeadPosition

Возвращает позицию элемента заголовка списка.

GetNext

Получает следующий элемент для итерации.

GetPrev

Получает предыдущий элемент для итерации.

GetSize

Возвращает количество элементов в этом списке.

GetTail

Возвращает хвостовой элемент списка (не может быть пустым).

GetTailPosition

Возвращает позицию хвостового элемента списка.

InsertAfter

Вставляет новый элемент после заданной позиции.

InsertBefore

Вставляет новый элемент перед заданной позицией.

Пустой

Проверяет состояние пустого списка (без элементов).

Удалить все

Удаляет все элементы из этого списка.

RemoveAt

Удаляет элемент из этого списка, указанный положением.

RemoveHead

Удаляет элемент из заголовка списка.

RemoveTail

Удаляет элемент из хвоста списка.

Установлен на

Устанавливает элемент в заданной позиции.

Ниже приведены различные операции над объектами 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 — Когда приведенный выше код скомпилирован и выполнен, вы увидите следующий вывод.

извлекать

Добавить товары в середине

Чтобы добавить элемент в середину списка, вы можете использовать функции 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 — Когда приведенный выше код скомпилирован и выполнен, вы увидите следующий вывод.

Добавление предмета

Обновить значение элемента

Чтобы обновить элемент в середине массива, вы можете использовать функцию 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.

Обновление товара

Удалить элементы

Чтобы удалить любой конкретный элемент, вы можете использовать функцию 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 больше не является частью списка.

53
Share: