Моя цель - реализовать перегруженные операторы - = и - в моем классе связанного списка. Код и вопрос взяты из книги под названием «СТРУКТУРЫ ДАННЫХ И ДРУГИЕ ОБЪЕКТЫ, использующие C ++ 4th by MICHAEL MAIN, WALTER SAVITCH», стр. 149, вопрос 2.
До сих пор у меня был некоторый успех с работающим кодом, но не с правильным Результаты. Сейчас я остановился с нарушением прав чтения. Мне кажется, что указатель указывает на нулевую переменную, но я не знаю, где. Это может быть связано с моим - = перегруженным оператором , поскольку это единственная из известных мне функций, которая влияет на ошибку (я закомментировал это тело функции, и она работает с неверными результатами). Вы увидите main_savitch_5 :: для каждой функции в моем "наборе инструментов. cpp" из-за их функций, не являющихся членами.
Это сообщение об ошибке из моего кода:
Это заголовок набора инструментов.
#ifndef TOOLKIT_H
#define TOOLKIT_H
#include <cstdlib>
namespace main_savitch_5
{
class node {
public:
// TYPEDEF
typedef double value_type;
// CONSTRUCTOR
node(
const value_type& init_data = value_type(),
node* init_link = NULL
) {
data_field = init_data;
link_field = init_link;
}
// Member functions to set the data and link fields:
void set_data(const value_type& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// Constant member function to retrieve the current data:
value_type data() const { return data_field; }
// Two slightly different member functions to retreive
// the current link:
const node* link() const { return link_field; }
node* link() { return link_field; }
private:
value_type data_field;
node* link_field;
};
// FUNCTIONS for the linked list toolkit
std::size_t list_length(const node* head_ptr);
void list_head_insert(node*& head_ptr, const node::value_type& entry);
void list_insert(node* previous_ptr, const node::value_type& entry);
node* list_search(node* head_ptr, const node::value_type& target);
const node* list_search
(const node* head_ptr, const node::value_type& target);
node* list_locate(node* head_ptr, std::size_t position);
const node* list_locate(const node* head_ptr, std::size_t position);
void list_head_remove(node*& head_ptr);
void list_remove(node* previous_ptr);
void list_clear(node*& head_ptr);
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
}
#endif // TOOLKIT_H
это источник набора инструментов файл
#include <cstdlib>
#include <assert.h>
#include "toolkit.h"
using namespace main_savitch_5;
using namespace std;
std::size_t main_savitch_5::list_length(const node* head_ptr) {
int length = 0;
const node* trav = head_ptr;
while (trav != NULL) {
length++;
trav = trav->link();
}
return length;
}
void main_savitch_5::list_head_insert(node*& head_ptr, const node::value_type& entry) {
node* new_node = new node();
new_node->set_data(entry);
new_node->set_link(head_ptr);
head_ptr = new_node;
}
void main_savitch_5::list_insert(node* previous_ptr, const node::value_type& entry) {
node* new_node = new node(entry);
new_node->set_link(previous_ptr->link());
previous_ptr->set_link(new_node);
}
node* main_savitch_5::list_search(node* head_ptr, const node::value_type& target) {
node* trav = head_ptr;
// the first part of the condition guards the second part
while ((trav != NULL) && (trav->data() != target)) {
trav = trav->link();
}
// examine the results
// if trav is NULL, we didn't find it, so return NULL
// if trav is not NULL then trav->data() == target, so return trav
return trav;
}
const node* main_savitch_5::list_search
(const node* head_ptr, const node::value_type& target) {
const node* trav = head_ptr;
// the first part of the condition guards the second part
while ((trav != NULL) && (trav->data() != target)) {
trav = trav->link();
}
// examine the results
// if trav is NULL, we didn't find it, so return NULL
// if trav is not NULL then trav->data() == target, so return trav
return trav;
}
node* main_savitch_5::list_locate(node* head_ptr, std::size_t position) {
if (position == 1) {
return head_ptr;
}
else if (head_ptr == NULL) {
return NULL;
}
else {
return list_locate(head_ptr->link(), position - 1);
}
}
const node* main_savitch_5::list_locate(const node* head_ptr, std::size_t position) {
const node* trav = head_ptr;
int count = position;
while ((trav != NULL) && (count > 1)) {
trav = trav->link();
count--;
}
return trav;
}
void main_savitch_5::list_head_remove(node*& head_ptr) {
assert(head_ptr != NULL);
node* tmp = head_ptr; /// first node, soon to be removed
head_ptr = head_ptr->link(); // head_ptr now points at the second node
delete tmp;
}
void main_savitch_5::list_remove(node* previous_ptr)
{
node* remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
void main_savitch_5::list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
// Library facilities used: cstdlib
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list.
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it.
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list.
source_ptr = source_ptr->link();
while (source_ptr != NULL)
{
list_insert(tail_ptr, source_ptr->data());
tail_ptr = tail_ptr->link();
source_ptr = source_ptr->link();
}
}
void main_savitch_5::list_clear(node*& head_ptr) {
while (head_ptr != NULL) {
// we know that head_ptr is not NULL
// so head_ptr points at the first node of the rest of the list
node* rest = head_ptr->link();
delete head_ptr; // get rid of first node
head_ptr = rest;
}
}
Это заголовок моей сумки.
// FILE: bag3.h
// CLASS PROVIDED: bag (part of the namespace main_savitch_5)
//
// TYPEDEFS for the bag class:
// bag::value_type
// is the data type of the items in the bag. It may be any
// of the C++ built-in types (int, char, etc.), or a class with a default
// constructor, a copy constructor, an assignment
// operator, and a test for equality (x == y).
//
// bag::size_type
// is the data type of any variable that keeps track of how many items are
// in a bag
//
// CONSTRUCTOR for the bag class:
// bag( )
// Postcondition: The bag is empty.
//
// MODIFICATION MEMBER FUNCTIONS for the bag class:
// size_type erase(const value_type& target)
// Postcondition: All copies of target have been removed from the bag.
// The return value is the number of copies removed (which could be zero).
//
// bool erase_one(const value_type& target)
// Postcondition: If target was in the bag, then one copy of target has
// been removed from the bag; otherwise the bag is unchanged. A true
// return value indicates that one copy was removed; false indicates that
// nothing was removed.
//
// void insert(const value_type& entry)
// Postcondition: A new copy of entry has been inserted into the bag.
//
// void operator +=(const bag& addend)
// Postcondition: Each item in addend has been added to this bag.
//
// CONSTANT MEMBER FUNCTIONS for the bag class:
// size_type size( ) const
// Postcondition: Return value is the total number of items in the bag.
//
// size_type count(const value_type& target) const
// Postcondition: Return value is number of times target is in the bag.
//
// value_type grab( ) const
// Precondition: size( ) > 0.
// Postcondition: The return value is a randomly selected item from the bag.
//
// NONMEMBER FUNCTIONS for the bag class:
// bag operator +(const bag& b1, const bag& b2)
// Postcondition: The bag returned is the union of b1 and b2.
//
// VALUE SEMANTICS for the bag class:
// Assignments and the copy constructor may be used with bag objects.
//
// DYNAMIC MEMORY USAGE by the bag:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: The constructors, insert, operator +=, operator +, and the
// assignment operator.
#ifndef BAG3_H
#define BAG3_H
#include <cstdlib> // Provides size_t and NULL
#include "toolkit.h" // Provides node class
namespace main_savitch_5
{
class bag
{
public:
// TYPEDEFS
typedef std::size_t size_type;
typedef node::value_type value_type;
// CONSTRUCTORS and DESTRUCTOR
bag();
bag(const bag& source);
~bag();
// MODIFICATION MEMBER FUNCTIONS
size_type erase(const value_type& target);
bool erase_one(const value_type& target);
void insert(const value_type& entry);
void operator +=(const bag& addend);
void operator -=(const bag& subtrahend);
void operator =(const bag& source);
// CONSTANT MEMBER FUNCTIONS
size_type size() const { return many_nodes; }
size_type count(const value_type& target) const;
value_type grab() const;
private:
node* head_ptr; // List head pointer
size_type many_nodes; // Number of nodes on the list
};
// NONMEMBER FUNCTIONS for the bag class:
bag operator +(const bag& b1, const bag& b2);
bag operator -(const bag& b1, const bag& b2);
}
#endif
Это источник моей сумки
// FILE: bag3.cxx
// CLASS implemented: bag (see bag3.h for documentation)
// INVARIANT for the bag ADT:
// 1. The items in the bag are stored on a linked list;
// 2. The head pointer of the list is stored in the member variable head_ptr;
// 3. The total number of items in the list is stored in the member variable
// many_nodes.
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL, rand, size_t
#include "toolkit.h" // Provides node and the linked list functions
#include "bag3.h"
using namespace std;
using namespace main_savitch_5;
bag::bag()
// Library facilities used: cstdlib
{
head_ptr = NULL;
many_nodes = 0;
}
bag::bag(const bag& source)
// Library facilities used: node1.h
{
node* tail_ptr; // Needed for argument of list_copy
list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}
bag::~bag()
// Library facilities used: node1.h
{
list_clear(head_ptr);
many_nodes = 0;
}
bag::size_type bag::count(const value_type& target) const
// Library facilities used: cstdlib, node1.h
{
size_type answer;
const node* cursor; // Use const node* since we don't change the nodes.
answer = 0;
cursor = list_search(head_ptr, target);
while (cursor != NULL)
{
// Each time that cursor is not NULL, we have another occurrence of
// target, so we add one to answer, and move cursor to the next
// occurrence of the target.
++answer;
cursor = cursor->link();
cursor = list_search(cursor, target);
}
return answer;
}
bag::size_type bag::erase(const value_type& target)
// Library facilities used: cstdlib, node1.h
{
size_type answer = 0;
node* target_ptr;
target_ptr = list_search(head_ptr, target);
while (target_ptr != NULL)
{
// Each time that target_ptr is not NULL, we have another occurrence
// of target. We remove this target using the same technique that
// was used in erase_one.
target_ptr->set_data(head_ptr->data());
target_ptr = target_ptr->link();
target_ptr = list_search(target_ptr, target);
list_head_remove(head_ptr);
--many_nodes;
++answer;
}
return answer;
}
bool bag::erase_one(const value_type& target)
// Library facilities used: cstdlib, node1.h
{
node* target_ptr;
target_ptr = list_search(head_ptr, target);
if (target_ptr == NULL)
return false; // target isn't in the bag, so no work to do
target_ptr->set_data(head_ptr->data());
list_head_remove(head_ptr);
--many_nodes;
return true;
}
bag::value_type bag::grab() const
// Library facilities used: cassert, cstdlib, node1.h
{
size_type i;
const node* cursor; // Use const node* since we don't change the nodes.
assert(size() > 0);
i = (rand() % size()) + 1;
cursor = list_locate(head_ptr, i);
return cursor->data();
}
void bag::insert(const value_type& entry)
// Library facilities used: node1.h
{
list_head_insert(head_ptr, entry);
++many_nodes;
}
void bag::operator +=(const bag& addend)
// Library facilities used: cstdlib, node1.h
{
node* copy_head_ptr;
node* copy_tail_ptr;
if (addend.many_nodes > 0)
{
list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
copy_tail_ptr->set_link(head_ptr);
head_ptr = copy_head_ptr;
many_nodes += addend.many_nodes;
}
}
void bag::operator -=(const bag& subtrahend) //Code giving me exception.
{
node* temp_head_ptr = head_ptr;
node* tail_ptr = NULL;
int n = many_nodes;
while (temp_head_ptr != NULL)
{
node* prev_ptr = NULL;
node* temp_head_ptr2 = subtrahend.head_ptr;
while (temp_head_ptr2 != NULL)
{
if (temp_head_ptr->data() == temp_head_ptr2->data()) {
n--;
if (prev_ptr == NULL) {
list_head_remove(temp_head_ptr2);
}
else
{
list_remove(prev_ptr);
}
}
else
{
prev_ptr = temp_head_ptr2;
temp_head_ptr2 = temp_head_ptr2->link();
}
}
tail_ptr = temp_head_ptr;
temp_head_ptr = temp_head_ptr->link();
}
many_nodes = n;
}
void bag::operator =(const bag& source)
// Library facilities used: node1.h
{
node* tail_ptr; // Needed for argument to list_copy
if (this == &source)
return;
list_clear(head_ptr);
many_nodes = 0;
list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}
bag main_savitch_5::operator +(const bag& b1, const bag& b2)
{
bag answer;
answer += b1;
answer += b2;
return answer;
}
bag main_savitch_5::operator-(const bag& b1, const bag& b2)
{
bag answer;
answer += b1;
answer -= b2;
return answer;
}
Тестовый файл
//
//
// test -= and - on bag
/*
This program will print informative messages if something goes wrong
in either creating and filling bags or in getting the diffference
between bags.
If all goes well, only the final message prints.
*/
#include <iostream>
#include "bag3.h"
using namespace std;
using namespace main_savitch_5;
int main() {
int size = 5;
// how many of each value to put in each bag
// one 0 will be put in b1
// two 1's will be put in b1
// five 0's will be in b2 ...
int num1[] = { 1, 2, 3, 4, 5 };
int num2[] = { 5, 4, 3, 2, 1 };
bag b1;
bag b2;
// insert data into bags
for (int i = 0; i < size; i++) {
for (int j = 0; j < num1[i]; j++) {
b1.insert(i);
}
for (int j = 0; j < num2[i]; j++) {
b2.insert(i);
}
}
for (int i = 0; i < size; i++) {
if (num1[i] != b1.count(i)) {
cout << "value " << i << " has bad count in b1: "
<< b1.count(i) << " rather than " << num1[i] << endl;
}
if (num2[i] != b2.count(i)) {
cout << "value " << i << " has bad count in b2: "
<< b2.count(i) << " rather than " << num2[i] << endl;
}
}
bag b3 = b1 - b2;
for (int i = 0; i < size; i++) {
int d = num1[i] - num2[i];
d = (d >= 0) ? d : 0;
if (b3.count(i) != d) {
cout << "value " << i << " has bad count in b3: "
<< b3.count(i) << " rather than " << d << endl;
}
}
b1 -= b1;
for (int i = 0; i < size; i++) {
if (0 != b1.count(i)) {
cout << "value " << i << " has bad count in b1: "
<< b1.count(i) << " rather than " << 0 << endl;
}
}
cout << "no news is good news!" << endl;
}