CODEWITHSUNDEEP
c++stringlinked-list
user2809124
user2809124

Reputation: 3

c++ linked list storing strings

I am creating a custom linked list class to store strings from a program I created for an assignment. We were given a linked list handout that works for ints and were told to retool it for string storage, however I am running into an error when trying to run it.

I'm getting the error ""terminate called after throwing an instance of 'std::logic_error' what(): basic_string::_S_construct null not valid"" (which I searched around and found it was because of a string being set to null, however I do not know how to fix the error, I'm guessing it is with line 8 but I've toyed around with it to no success.) I've searched around and looked through the similar questions but could not find anything that helped.

    #include <cstdlib>
    #include <iostream>
    #include <string>
    #include <cstdio>
    #include <iomanip>
    using namespace std;

   struct node {
   node(string current) { data=current; next=NULL; }
   string data;
   node *next;
    };

    class list {
    public:
      list(int N=0, string current);
      ~list();
      bool empty() const { return N == 0; }
      void clear();

      void insert(int, const string &);

      void push_front(const string &current);

      friend ostream & operator<<(ostream &out, const list &current);

    private:
      int N;
      node *head;
      node *findnode(int);
      };

    list::list(int M, string current) {
      N = M;
     head = new node;
     for (int i=0; i<N; i++)
       insert(0, current);
    }

   list::~list() {
      clear();
     delete head;
    }


    void list::clear() {
      while (!empty()) remove(0);
    }

    void list::insert(int i, const string &din) {
      node *p = new node(din);
      node *pp = findnode(i-1);
      p->next = pp->next;
      pp->next = p;
      N++;
    }

    inline
    node *list::findnode(int i) {
      if (i == -1)
        return head;
      node *p = head->next; 
      while (i--)
        p = p->next;
      return p;
    }


    void list::push_front(const string &current) {
      head = new node;
      head->next;
    }

    ostream& operator<<(ostream& out, const list& current)
    {
     out << current;
     return out;
   }


    const string rank[] = { "Ace", "2", "3", "4", "5", "6", "7",
                            "8", "9", "10", "Jack", "Queen", "King" }; 
    const string suit[] = { "Clubs", "Diamonds", "Hearts", "Spades" };

    string random_card(bool verbose=false) {
        string card;

        card = rank[ rand()%13 ];
        card += " of ";
        card += suit[ rand()%4 ];

        if (verbose)
          cout << card << "\n";

        return card;
    }

    int main(int argc, char *argv[])
    {
        bool verbose = false;
        int seedvalue = 0;
        string stop_card = "Queen of Hearts";

        for (int i=1; i<argc; i++) {
          string option = argv[i];
          if (option.compare(0,6,"-seed=") == 0) {
            seedvalue = atoi(&argv[i][6]);
          } else if (option.compare(0,6,"-stop=") == 0) {
            stop_card = &argv[i][6];
          } else if (option.compare("-verbose") == 0) {
            verbose = true;
          } else 
            cout << "option " << argv[i] << " ignored\n";
        }

        srand(seedvalue);


        list deck[4];


        while (1) {
          string card = random_card(verbose);
          char first[10];
          char second[10];
          sscanf(card.c_str(), "%s of %s", first,second);

        // reverse engineer card suit and rank

          int index2;

          //suit index
          for(int i=0; i<4; i++){
            if(suit[i]==second){       
              index2=i;
            break;
          }
          }

          deck[index2].push_front(first);

        if (card.compare(stop_card)==0){
          break;
        }

        }


     // print formatted table contents to stdout 
    cout << "Clubs : "; 
       cout << setw(3) <<  deck[0];
     cout << endl;

     cout << "Diamonds : ";
       cout << setw(3) <<  deck[1];
     cout << endl;

     cout << "Hearts : ";
       cout << setw(3) << deck[2];
     cout << endl;

     cout << "Spades :  ";
     cout << setw(3) << deck[3];
     cout << endl;

    }

Upvotes: 0

Views: 12732

Answers (1)

WhozCraig
WhozCraig

Reputation: 66234

The following are significant problems that will either hinder building (read: compile-time bugs) or actual runtime. This makes no claim these are all the bugs, but its certainly worth considering. I should note right off the top that the concept of a "sentinel" head-node allocation is almost- never needed in linked list management, and this code is not one of the exceptions. If the list is "empty" head should be null. If it isn't empty, head should not be null. Its just that simple, and this code would be leaps-and-bounds simpler if that were followed.

With that, read on.

Invalid Code:

list(int N=0, string current);

Reason: C++ requires all arguments following the first argument that is provided a default value to also have default values. This would be valid if N was the second parameter, or if current was also given a default value (or of course ,if neither had default values). All of the following are valid:

list(int N, string current);
list(int N, string current = "");
list(int N=0, string current = "");

As-written, it will fail to compile.

Invalid code: No matching constructor available

head = new node;

Reason: The structure node does not defined a default-compliant constructor (one that either has no parameters, or all parameters with default value provisions) but does specify a non-default constructor (one that requires at least one parameter). As a result, the language-supplied default constructor is not auto-generated and there is no node::node() constructor to be found.

Incorrect Code: Expression result is unused

void list::push_front(const string &current) {
    head = new node;
    head->next; // THIS LINE
}

Reason: This code blindly overwrites whatever is currently occupied in the head pointer with a new (invalid, see above for why) node allocation. Anything that was in head prior is leaked forever, and current is unused whatsoever. Fix this by allocating a new node with current as the value, settings its next pointer to head and head to the new node:

void list::push_front(const string &current) 
{
    node *p = new node(current);
    p->next = head;
    head = p;
}

Infinite Recursion

ostream& operator<<(ostream& out, const list& current)
{
    out << current;
    return out;
}

Reason: This code literally invokes itself. Recursively. Forever (well, until you run out of call-stack space).

NULL Pointer Dereference

inline node *list::findnode(int i) 
{
    if (i == -1)
        return head;
    node *p = head->next;
    while (i--)
        p = p->next;
    return p;
}

Reason: This will walk the list uninhibited by validity checking for i iterations. Now imagine what this does on an empty list (in your case, that means head is non-null, but head->next is null) when passed anything besides -1: It will return NULL for i=0 and is outright undefined behavior for everything else.

NULL Pointer Dereference

void list::insert(int i, const string &din) 
{
    node *p = new node(din);
    node *pp = findnode(i-1);
    p->next = pp->next;
    pp->next = p;
    N++;
}

This assumes pp will never be null on return, and as we already discussed with the prior item, it most certainly can be when head is the sole node in your list, and is therefore "empty". This makes no attempt at checking pp for NULL prior to using it for dereferencing. This kid-gloves handling and the exceptions that have to be accounted for are directly related to maintaining a "sentinel" head node. The simplest way to fix it is to (a) Don't use sentinel nodes; use the universal sentinel value nullptr, and (b) check your return values before using them.

Ambiguous Reference: rank

card = rank[ rand()%13 ];

Reason: The standard library defines a special struct called std::rank used for determining the number of dimensions in a multi-dimension array. With the using namespace std; at the top of your code, the compiler is now forced to choose which one (the one in namespace std or the array you've defined prior to this code), and it cannot do so unequivocally. Thus it will not compile. Note: this is brought in by implicitly including <type_traits>, which is likely included by <string>, <iostream>, <iomanip> or any of a number of other nested includes. You can solve it a number of ways, including (but not limited to) a creative using clause, renaming the rank array to something that doesn't conflict, using a functional wrapper around a local static rank in the function etc.

Implicit conversion from signed to unsigned type (minor)

srand(seedvalue);

Reason: std::srand() takes an unsigned int parameter; you're passing a signed integer. Either static-cast to unsigned int or change the type of seedValue to unsigned int.

Invalid Code

list deck[4];

Reason: Class list does not have a default constructor. Recall the first item in this response. If you fix that, you will fix this as well.

And I didn't even run the code yet. I would strongly advise working on these issues, and give serious consideration to not using a "sentinel" node for your list head. Linked list code practically writes itself once you "know" a null head means the list is empty, a non-null head means it isn't.

I make no claims this is all the bugs. These were just ones I saw while reviewing the code, and all but one of them is significant.

EDIT Sample operator overload

Note: If you fix your linked list to use null as a head value when the list is empty (advised) this will need to change to simply start at head rather than head>next.

std::ostream& operator <<(std::ostream& os, const list& lst)
{
    const node *p = lst.head ? lst.head->next : nullptr;
    while (p)
    {
        os << p->data;
        if ((p = p->next)) // note: assignment intentional
            os << ',';
    }
    return os;
}

Upvotes: 3

Related Questions