测试MRU-列表与标准列表

Question

任务是测试移动到前线链接列表与标准链接列表的好处。它还旨在实践继承和指针。

标准功能在LinkedList中，派生的MTFList代替contains()将目标移动到前面。

由于我迟交了我的解决方案，我不确定这个糟糕的成绩是因为我错过了上课的最后期限，还是在思考我的解决方案。不管怎样，我不知道我可能犯了哪些错误。

我希望一些更有经验的眼睛能评价我对指针的使用。我的构造函数和析构函数是否正常工作，或者是否允许内存链接。

LinkedListStats.cpp

// Brandon Hoffman
// 10-21-2021
// Test program to evaluate linked list performance
// Written 10/4/19 by Michael Stiber
//

#include <iostream>
#include <string>
#include <random>
#include <vector>
#include <cassert>

// Replace the following include with alternative linked list class
//#include "LinkedList.h"
#include "MTFList.h"

using namespace std;

int main()
{
  // Alter the following declaration to change the linked list class
  // name.
  MTFList theList;

  const int numValues = 1000;
  const int numAccesses = 100000;

  // Create a linked list of the numbers 0..numValues-1
  for (int i = numValues-1; i >= 0; i--)
    theList.add(i);

  // Reset the traversal counter, just in case
  theList.resetTraverseCount();

  // Now, access the elements randomly many times
  int theNumber;
  default_random_engine generator;
  uniform_int_distribution<int> uniform(0, numValues-1);
  normal_distribution<double> normal(numValues/2.0, numValues/5.0);

  // As the statistic of comparison, we use a uniform
  // distribution. For sequential search, even a "smart" algorithm
  // shouldn't be able to improve performance.
  for (int i = 0; i < numAccesses; i++) {
    // Access a random item by value
    theNumber = uniform(generator);
    assert(theList.contains(theNumber));
  }

  cout << "Average number of nodes traversed per access (uniform): "
       << theList.getTraverseCount()/double(numAccesses)
       << endl;

  // Reset the traversal counter.
  theList.resetTraverseCount();

  // We use a normal distribution so that some values are accessed
  // much more frequently. It will be peaked around numValues/2 and fall off
  // rapidly above and below. Note that there is some chance of
  // generating a number outside the legal range, so we test and get a
  // new number if that happens (this is because a uniform
  // distribution goes to +/- infinity). A smart algorithm could in
  // principle take advantage of the higher frequency of access of
  // certain items to lower the average access time. On the other hand,
  // without any "smarts", the mean number of nodes traversed should still
  // be the mean of the distribution, the same as for the uniform distribution.
  for (int i = 0; i < numAccesses; i++) {
    theNumber = 0;
    do {
      theNumber = int(normal(generator));
    } while ((theNumber<0) || (theNumber>=numValues));

    assert(theList.contains(theNumber));
  }

  cout << "Average number of nodes traversed per access (normal): "
       << theList.getTraverseCount()/double(numAccesses)
       << endl;

}  // end LinkedListStats

MTFList.cpp

// LinkedList.cpp
// Brandon Hoffman
// 10-21-2021
// Contains all of the functionality from members of MTFList.h

#include "MTFList.h"

//Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
//search of anEntry, increases traverseCount by 1. Overwites functionality from Linked List
//Now moves node with first occurrence of anEntry match to become new first node
bool MTFList::contains(int anEntry) {
   Node *p = first;
   Node *q = nullptr;

   while(p != nullptr) {
      this->incrementTraverseCount();

      if(anEntry == p -> data) {
         if (q != nullptr) {
            q -> next = p -> next;
            p -> next = first;
            first = p;
         }
         return true;
      }
      q = p;
      p = p -> next;
   }
   return false;
}

MTFList.h

// LinkedList.h
// Brandon Hoffman
// 10-21-2021
// Contains the declarations for the MTFList.h class inheriteing from LinkedList.h

#ifndef MTF_LIST_
#define MTF_LIST_

#include "LinkedList.h"

class MTFList : public LinkedList
{
   public:
      //Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
      //search of anEntry, increases traverseCount by 1. Overwites functionality from Linked List
      //Now moves node with first occurrence of anEntry match to become new first node
      virtual bool contains(int anEntry);
};

#endif

LinkedList.cpp

// LinkedList.cpp
// Brandon Hoffman
// 10-21-2021
// Contains all of the functionality from members of LinkedList.h


#include <iostream>
#include <string>

#include "LinkedList.h"

//constructor
//takes an array an int n to denote the length of the array
//this is for manual testing purposes only
LinkedList::LinkedList(int A[], int n)
{
   Node *t;
   int i = 0;

   first = new Node;
   first -> data = A[0];
   first -> next = nullptr;
   last = first;

   for(i = 1; i < n; i++) {
      t = new Node;
      t -> data = A[i];
      t -> next = nullptr;
      last -> next = t;
      last = t;
   }
};

//destructor
//The destructor deallocates all of the dynamic storage (each Node) and deletes the Node.
LinkedList::~LinkedList()
{
   this->clear();
}

//displays data in each Node for manual testing purposes
void LinkedList::display()
{
   Node *p = first;

   while(p) {
      std::cout << p -> data << " ";
      p = p -> next;
   }
   std::cout << std::endl;
}

// Returns currentSize, the current number of nodes in the linked List.
int LinkedList::getCurrentSize() const
{
   return currentSize;
}

//returns True if LinkedList is empty i.e. first is pointed nullptr
bool LinkedList::isEmpty() const
{

   if (first == nullptr) {
      return true;
   }
   else {
      return false;
   }
}

//Creates a new Node (dynamically allocated) with data = newEntry, adds it to the back of the
//List, and increases currentSize by 1.Returns true if the new Node with newEntry was added
//successfully, otherwise returns false.
bool LinkedList::add(int newEntry)
{
   Node *temporary;
   temporary = new Node;
   temporary -> data = newEntry;
   temporary -> next = nullptr;

   if (first==nullptr) {
      first = last = temporary;
   }
   else {
      last -> next = temporary;
      last = temporary;
   }

   this -> incrementCurrentSize();
   return true;
}


//Searches and removes the first occurrence of anEntry in the List and decreases numItems by 1.
//Deallocates memory for the removed Node. Returns true if anEntry was removed successfully,
//otherwise returns false (if anEntry was not found in the List or the List was empty).
//calls decrementCurrentSize method to reduce currentSize by 1
bool LinkedList::remove(int anEntry)
{
   Node *p = first;
   Node *q = nullptr;

   while (p != nullptr) {

      if(anEntry == p -> data){
         if (q == nullptr) {
            q = first;
            first = first -> next;
            delete q;
         }
         else {
            q -> next = p -> next;
            delete p;
         }
         this->decrementCurrentSize();
         return true;
         ;
      }
      q = p;
      p = p -> next;
   }
   return false;
}

//Removes all items from the List and resets currentSize to 0. Deallocates memory for each Node removed.
void LinkedList::clear()
{
   Node *p = first;
   while (first) {
      first = first -> next;
      delete p;
      p = first;
   }
   this->resetCurrentSize();
}

//Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
//search of anEntry, increases traverseCount by 1.
bool LinkedList::contains(int anEntry)
{
   Node *p = first;
   while(p != nullptr) {
      this->incrementTraverseCount();
      if(anEntry == p -> data) {
         return true;
      }
      p = p -> next;
   }
   return false;
}

LinkedList.h

// LinkedList.h
// Brandon Hoffman
// 10-21-2021
// Contains the declarations for the LinkedList class
#ifndef LINKED_LIST_
#define LINKED_LIST_

#include "IList.h"

class LinkedList: public IList
{
   public:
      //constructor
      //The constructor initializes an empty LinkedList by setting both currentSize and traverseCount to
      //0 and setting first and lst to nullptr.
      //two constructors, first is standard for assignment, 2nd takes an array for testing purposes
      LinkedList(){first=nullptr; last=nullptr; traverseCount=0; currentSize=0;}
      LinkedList(int A[], int n);

      //destructor
      //The destructor deallocates all of the dynamic storage (each Node) and deletes the Node.
      virtual ~LinkedList();

      //accessors
      //displays data in each Node for manual testing purposes
      void display();

      // Returns currentSize, the current number of nodes in the linked List.
      virtual int getCurrentSize() const;

      //mutators
      //Sets traverseCount to 0.
      void resetTraverseCount() {traverseCount=0;}


      //Creates a new Node (dynamically allocated) with data = newEntry, adds it to the back of the
      //List, and increases currentSize by 1.Returns true if the new Node with newEntry was added
      //successfully, otherwise returns false.
      virtual bool add(int newEntry);


      //Searches and removes the first occurrence of anEntry in the List and decreases numItems by 1.
      //Deallocates memory for the removed Node. Returns true if anEntry was removed successfully,
      //otherwise returns false (if anEntry was not found in the List or the List was empty).
      //calls decrementCurrentSize method to reduce currentSize by 1
      virtual bool remove(int anEntry);

      //Removes all items from the List and resets currentSize to 0. Deallocates memory for each Node removed.
      virtual void clear();

      //Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
      //search of anEntry, increases traverseCount by 1.
      virtual bool contains(int anEntry);

      //returns True if LinkedList is empty i.e. first is pointed nullptr
      virtual bool isEmpty() const;

 protected:
   //standard Node structure
   struct Node
   {
      int data;
      struct Node *next;
   };

   struct Node *first, *last;
   int currentSize = 0;

   //mutators
   void incrementCurrentSize() {currentSize++;}

   void decrementCurrentSize() {currentSize--;}

   void resetCurrentSize() {currentSize=0;}

   void incrementTraverseCount() {traverseCount++;}

   bool isValidEntry();



};

#endif

IList.h

//  Modified from code created by Frank M. Carrano and Timothy M. Henry.
//  Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.

#ifndef I_LIST_
#define I_LIST_

class IList
{
public:
   /** Constructor */
   IList () : traverseCount(0) { }

   /** Destroys object and frees memory allocated by object.
    (See C++ Interlude 2) */
   virtual ~IList () { }

   /** Gets the current number of entries in this list.
    @return The integer number of entries currently in the list. */
   virtual int getCurrentSize() const = 0;

   /** Sees whether this list is empty.
    @return True if the list is empty, or false if not. */
   virtual bool isEmpty() const = 0;

   /** Adds a new entry to this list.
    @post  If successful, newEntry is stored in the list and
       the count of items in the list has increased by 1.
    @param newEntry  The object to be added as a new entry.
    @return  True if addition was successful, or false if not. */
   virtual bool add(int newEntry) = 0;

   /** Removes one occurrence of a given entry from this list,
       if possible.
    @post  If successful, anEntry has been removed from the list
       and the count of items in the list has decreased by 1.
    @param anEntry  The entry to be removed.
    @return  True if removal was successful, or false if not. */
   virtual bool remove(int anEntry) = 0;

   /** Removes all entries from this list.
    @post  List contains no items, and the count of items is 0. */
   virtual void clear() = 0;

   /** Tests whether this list contains a given entry.
    @param anEntry  The entry to locate.
    @return  True if list contains anEntry, or false otherwise. */
   virtual bool contains(int anEntry) = 0;

   /** Get the count of number of nodes traversed.
    @return  The integer number of nodes traversed since last time the count was reset. */
    virtual int getTraverseCount() const { return traverseCount; }

   /** Reset the count of nodes traversed to zero. */
    virtual void resetTraverseCount() { traverseCount = 0; }

protected:
    int traverseCount;
}; // end IList

#endif

Answer 1

• if (第一次== nullptr) {返回真；} else {返回false；}是返回第一个== nullptr的很长的一段时间；
• 当您向列表中添加一个新条目时，无论发生什么，它都会变成last。显式: if (first==nullptr) { first =临时；}{末后-> next =临时；} last =临时；
• remove也是。p/q删除逻辑看起来很复杂。我们只想删除我们找到的节点，即p，对吗？相反，如果(p ==优先){ first = first -> next；} -> next =p -> next；}删除p；
• 这些行是临时的->数据= newEntry；临时的-> next = nullptr；尖叫是在Node构造函数中。
• 对add的介绍性评论是误导性的。它声称，如果添加失败，该方法将返回false。我没有看到它返回false。我也看不出失败的可能性，除非new Node抛出一个bad_alloc，但是无论如何，所有的赌注都取消了。
• remove和contains (特别是MTFList::contains)共享了很多功能。Node * detach说，如果您有一个帮助方法，您的状态会更好。考虑LinkedList：：删除(int条目){ Node *r=detach(条目)；if (r) {删除r；}返回r != nullptr；}MTFList:包含(int条目){ Node *r=detach(条目)；if (r) { r->next = first；first = r；incrementCurrentSize()；)返回r != nullptr；}当然，incrementCurrentSize在这里看起来不合适。这是一个强烈的指示，表明prepend方法希望实现。另一个非常有用的帮助方法是findPredecessor。它将使您可以合并remove和LinkedList::contains。

Answer 2

别写using namespace std;。

但是，您可以在CPP文件(而不是H文件)或函数中放置单独的using std::string;等(参见SF.7)。

const int numValues = 1000;

记住"constexpr是新的static const“。这应该是constexpr。你应该用哪种类型的？

for (int i = numValues-1; i >= 0; i--)

太残忍了，只是为了循环无数次。你知道iota的事吗？有关计数，请参见这篇文章，并注意到std::ranges::iota_view是与标准库一起提供的C++20。

通常，您不应该编写显式循环；您应该使用算法。

while(p != nullptr) {

不要针对nullptr编写显式测试。您将使用各种类型的智能指针，而不仅仅是原始指针(希望，通常不是原始指针)，并且这些指针具有高效的explicit operator bool。在C++中直接使用指针的真值是非常惯用的，尽管编写显式比较不再像以前那样低效(自C++11以来)。

this->incrementTraverseCount();

不要显式地使用this->。在成员函数中，其他成员在范围内。

#ifndef MTF_LIST_
#define MTF_LIST_

这些名字太短了，太近了，所以它们可能会在一个真正的项目中发生碰撞，这个项目由不同的作者使用多个库。只需使用#pragma once，如果必须使用#define机制，则生成一个UUID。在看到不接受#include的编译器之前，您可能已经停止使用#pragma once了。模块不存在与经典#include文件相同的问题。

⧺SL.io.50不要使用endl。

IList () : traverseCount(0) { }

编写它最好是将内联初始化器提供给traverseCount成员，然后完全不要自己实现默认构造函数。那是,

       ⋮
    int traverseCount { 0 };
       ⋮
    IList() = default;

LinkedList::LinkedList(int A[], int n)

• ⧺I.13不将数组作为单个指针传递(包括讨论中的指针和计数参数)
• ⧺R.14避免[]参数，更倾向于span
• ⧺F.24使用span<T>或span_p<T>指定半开序列。

在实际代码中，您不希望被限制在一个值数组中，而是应该能够为它提供任何类型的范围。看看标准库函数如何接受它们的参数。我承认，通用编程可能超出了到目前为止您已经讨论过的范围，但是您不应该养成以奇怪或糟糕的方式处理事情的习惯。在这里，您应该使用std::span。

将简单的函数实现直接放在头文件中。例如，应该在类中定义析构函数：

       ⋮
    virtual ~LinkedList()  { clear(); }
       ⋮
    int getCurrentSize() const {  return currentSize;  }
    bool isEmpty() const  {  return !first;  }

为什么大小是int而不是size_t？就这件事而言，没有什么是按照惯例命名的！看看标准库：size，empty。说出人们所期望的东西，这样其他人就会知道如何使用它，而不必学习你自己的特殊词汇。

我看到了更多的"fat界面“的例子。为什么display是一个成员函数？它应该是一个非会员，它使用通用功能遍历列表，并对集合中的每个值执行任何代码所需的操作。

我不知道为什么要在派生类中创建virtual并添加一个函数。我不知道如果您真的对节点使用多态性，这会有多好的效果。

任务的目的是练习继承和指针。

这似乎不是一个与继承有任何关系的好例子。

因此，标准功能在LinkedList类中，然后MTFList类继承该功能，并在搜索和找到特定整数值时更改class方法以将节点移动到前面。

搜索特性不需要是列表的成员。它可以是只使用公共功能对列表进行操作的非会员。您可以有一个普通的find，和另一个功能，确实找到-和移动-到前面。

如果您查看标准库，您将看到链表 (几乎从未使用过，BTW)没有任何类型的find成员函数。

搜索容器-任何容器-都是用发现算法完成的。

编辑

我不知道你的课程到底是关于什么的，大纲是什么，学生需要达到什么程度的熟练程度。但我对2021年的C++教学有一些一般性的想法。

“正常”规则之一是⧺C.149 --没有裸体的new或delete。类似地，您应该使用标准容器进行正常编码，不要使用原始指针，使用标准算法等等。实现容器是一个高级主题。

了解链接列表、树、哈希表和其他东西是如何工作的，以及它们是如何编写的，这与学习编程语言是不同的。数据结构和算法类确实会让您编写基本的类似容器的数据集合的基本实现，并实现代码来完成诸如在集合中排序和查找元素之类的工作。这个班的学生应该能够集中精力于这些细节，而不必学习一门语言或收集基本的编码能力。

同样，在关于C++语言和/或学习编写代码的类中，不应该要求您编写非典型性的、bizzare的或公然反对最佳实践的代码。它不应该要求你天真地使用什么应该是高级的主题。它应该为你编写真实世界的代码做好准备。