未排序的链表实现检查已满

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

和实施：

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函数中，为什么指向指针“next”？next不是空指针吗？因为它已在结构中声明为Node*next？

Answer 1

指针（和任何其他基本类型一样）在使用之前都需要初始化。空值仍然是一个值。

你提供的代码似乎很不完整。数据应该是你名单的头号吗？我不知道你如何定义“充实”。如果要测试列表是否为空，可以查看列表的“头”是否为空：

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;
}

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

在你的IsAll函数中，它总是返回false，因为它总是可以创建一个新的Node*。除非您运行内存溢出，这可能更有问题。

您的函数相当混乱，指针工作会导致许多内存泄漏。您可能想在这里查看STL列表对象的设计。

Answer 2

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

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

然而，我根本不知道“check full function”中在哪里使用next，所以这个问题有点让人困惑。

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

Answer 3

默认情况下，指针值没有设置为NULL值，您应该显式地设置为NULL。另外，不要使用NULL，而是选择使用nullptr。