Выполнение несвязанного связанного списка проверка полностью

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.In конструктора, поэтому не следует назначать currentPos в нуль?
2.In функция IsInTheList, Почему указывает на указатель «next»? Не следующий ли это нулевой указатель, поскольку он был объявлен в struct как Node * next?

Answer 1

Значение указателя не установлено равным NULL по умолчанию, вы должны явно указать значение null. Кроме того, вместо использования NULL выберите значение nullptr.

Answer 2

Этот код является довольно неполным, поэтому сложно ответить на ваши вопросы.

Это не содержит код для вставки элемента в список, где я ожидаю, что будут установлены как следующие, так и указатели currentPos. Однако это основано на ряде предположений.

Однако я не вижу, где следующий используется в «полной проверке функции», так что вопрос немного запутан.

Я также укажу, что этот код имеет яркую утечку памяти. Первая строка в IsInTheList выделяет память для нового узла, который сразу же теряется с location = data.

Answer 3

Указатели (как и любой другой базовый тип) должны быть инициализированы перед использованием. Значение 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; 
} 

Пожалуйста, обратите внимание, что я использовал Узла * переменной члена называется хвост. Хорошая идея - следить за тем, как начинается и заканчивается список.

В вашей функции IsFull он всегда будет возвращать false, так как он всегда может создать новый узел *. За исключением, может быть, если у вас заканчивается память, что, вероятно, более проблематично.

Ваши функции довольно запутанны, а работа с указателем оставляет много утечек памяти. Возможно, вам захочется просмотреть проект объекта списка STL here.