0

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

规格：

#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 不是空指针，因为它已在 struct 中声明为 Node* next 吗？

4

3 回答 3

0

默认情况下，指针值未设置为 NULL 值，您应显式设置为 null。也不要使用 NULL，而是选择使用 nullptr。

于 2013-05-20T20:24:51.503 回答
0

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

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

但是，我根本看不到“检查完整功能”中使用 next 的位置，所以这个问题有点令人困惑。

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

于 2013-05-20T20:37:13.720 回答
0

指针（与任何其他基本类型一样）需要在使用前进行初始化。NULL 值仍然是一个值。

您提供的代码似乎很不完整。data应该是你名单的首位吗？我不确定你如何定义“丰满”。如果要测试列表是否为空，可以查看列表的“头”是否为空：

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* 成员变量。跟踪列表的开始和结束位置是一个好主意。

在你的IsFull函数中，它总是会返回 false，因为它总是可以创建一个新的 Node*。除非你的内存用完了，这可能更成问题。

您的函数相当混乱，并且您的指针工作会留下许多内存泄漏。您可能想在此处查看 STL 列表对象设计。

于 2013-05-20T21:34:43.820 回答