未排序链表实现检查完毕

Question

我目前正在检查未排序的链表，以下是我的规范和实现。

规范:

#ifndef UNSORTEDLIST_H
#define UNSORTEDLIST_H
#include <iostream>
using namespace std;
struct Node {
  float element;
  Node* next;
};
class UnsortedList
{
    public:
    UnsortedList();
    bool IsEmpty();
    bool IsFull();
    void ResetList();
    void MakeEmpty();
    int LengthIs();
    bool IsInTheList(float item);
    void InsertItem(float item);
    void DeleteItem(float item);
    float GetNextItem();
    private:
      Node* data;
      Node* currentPos;
      int length;
};
#endif

和implemetation:

UnsortedList::UnsortedList()
{
    length = 0;
    data = NULL;
    currentPos = NULL;
}
bool UnsortedList:: IsEmpty(){
    if(length == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool UnsortedList::IsFull(){
    Node* ptr = new Node();
    if(ptr == NULL)
      return true;
    else
    {
      delete ptr;
      return false;
    }
}
void UnsortedList::ResetList(){
   currentPos = NULL;
}
void UnsortedList::MakeEmpty()
{
   Node* tempPtr = new Node();
   while(data != NULL)
   {
     tempPtr = data;
     data = data->next;
     delete tempPtr;
   }
   length = 0;
}
int UnsortedList::LengthIs(){
    return length;
}
bool UnsortedList:: IsInTheList(float item){
Node* location = new Node();
location = data;
bool found = false;
while(location != NULL && !found)
{
    if(item == location->element)
        found = true;
    else
        location = location->next;
}
   return found;
}
void UnsortedList:: InsertItem(float item){
    Node* location = new Node();
    location->element = item;
    location->next=data;
    data = location;
    length++;
}
void UnsortedList:: DeleteItem(float item){
Node* location = data;
Node* tempPtr;
if(item == data->element){
    tempPtr = location;
    data = data->next;
}
else{
  while(!(item == (location->next) ->element) )
    location = location->next;
    tempPtr = location->next;
    location->next = (location->next)->next;
}
  delete tempPtr;
  length--;
}
float UnsortedList::GetNextItem(){
   if(currentPos == NULL)
    currentPos = data;
   else
    currentPos = currentPos->next;
   return currentPos->element;
}

1。在构造函数中，为什么不将currentPos赋值为null?
2.在IsInTheList函数中，为什么指向指针"下一个"?是不是下一步是一个空指针，因为它已在结构体声明为节点*下一步?

Answer 1

指针值默认不设置为NULL值，需要显式设置为NULL。另外，不要使用NULL，而是使用nullptr。

Answer 2

这段代码相当不完整，因此很难回答您的问题。

不包含在列表中插入项的代码，这是我希望设置next和currentPos指针的地方。然而，这是基于一些假设。

然而，我根本没有看到next在"check full function"中使用的地方，所以这个问题有点令人困惑。

我还要指出这段代码有明显的内存泄漏。IsInTheList中的第一行为新节点分配内存，这些内存会在location = data中立即丢失。

Answer 3

指针(和其他基本类型一样)在使用前需要初始化。NULL仍然是一个值

您提供的代码似乎非常不完整。data应该是你清单上的第一个吗?我不知道你是怎么定义"丰满"的。如果你想测试列表是否为空，你可以看看列表的"head"是否为空:

bool UnsortedList::IsEmpty() {
  if (data == NULL) {return true;}  // if there is no first element, empty
  else {return false;}              // if there is ANY element, not empty
}

或者更简洁:

bool UnsortedList::Empty() {
  return (data == NULL);
}

当一个节点被添加到链表中时，我们通常将该节点作为一个整体添加，并修改它前面的元素。例如，我们可以创建一个新节点，并使用如下代码添加它:

// implementation file
void UnsortedList::InsertItem(const float& item) {
  if (data == NULL) {  // no elements in list, so new node becomes the head
    data          = new Node;        // allocate memory for new node
    data->element = item;            // fill with requested data
    data->next    = NULL;            // there is no element after the tail
  }
  else {
    new_node          = new Node;    // allocate memory
    new_node->element = item         // set data
    new_node->next    = NULL;        // new end of the list, so it points to nothing
    tail->next = new_node;           // have the OLD end node point to the NEW end
    tail       = new_node;           // have the tail member variable move up
  }
}
// driver file
int main() {
  UnsortedList my_list;
  float pie = 3.14159;
  my_list.AddNode(pie);
  return 0;
}

请注意，我使用了Node*成员变量tail。跟踪列表的开始和结束位置是一个好主意。

在你的IsFull函数中，它总是返回false，因为它总是可以创建一个新的Node*。除非内存耗尽，否则可能会更有问题。

你的函数相当混乱，你的指针工作留下了许多内存泄漏。您可能需要在这里查看STL列表对象的设计。