Latest Lists - C++ help with singly linked lists?

C++ help with singly linked lists?

This is the base code from the book that I am building upon: #include <iostream> using std::cout; using std::endl; struct slistelem { char data; slistelem * next; }; class slist { public: slist() : h(0) {} ~slist() { release(); } void prepend(char c); void del(); slistelem * first() const { return h; } void print() const; void release(); private: slistelem * h; }; void slist::prepend(char c) { slistelem * temp = new slistelem; assert(temp != 0); temp -> next = h; temp -> data = c; h = temp; } void slist::del() { slistelem * temp = h; h = h -> next; delete temp; } void slist::print() const { slistelem * temp = h; while(temp != 0) { cout << temp -> data << " -> "; temp = temp -> next; } cout << endl; } void slist::release() { while(h != 0) del(); } now i am to add the following to the class slist: slist(const char * c); int length() const; int count_c(char c) const; i am to create a string and use it to invoke the conversion constructor slist and print to make sure the list was created properly. length counts the length of the list and count_c will count occurence of the char c in a list this is what i think my output should be but not sure about the proper syntax for calling such functions when used on linked lists: int main() { slist l1("banana"); slist l2("fireblade"); slist l3(""); l1.print(); l2.print(); cout << endl; cout << "List has: " << l1.length() << " elements" << endl; cout << "List has: " << l2.length() << " elements" << endl; cout << "List has: " << l3.length() << " elements" << endl; cout << endl; cout << "List has: " << l1.count_c('a') << " a's" << endl; cout << "List has: " << l2.count_c('d') << " d's" << endl; cout << "List has: " << l2.count_c('x') << " x's" << endl; } right now i am completely stuck as to how to write those 3 functions since i am clueless to how singly linked lists work. if anybody can write the code for the 3 functions and explain a little as to how they work/how linked lists work i'd appreciate it and 10 points

Public Comments

You have most of this done already, there are just a few details that needed to be taken care of. I added the operations you were missing, and a few comments to help explain what's going on. Normally if you're going to separate the class declaration from its implementation, you'd put the class slist { . . . }; in a .h file. This works as-is, but you might consider creating slist.h and moving the class declaration there. One way to count the number of elements in the list is to traverse from head to tail, counting how many nodes you find. I did it a simpler way, just maintaining a length attribute - adding 1 when adding a char, and subtracting 1 when removing a char. Here's a working version of your program: #include <iostream> #include <cassert> using namespace std; struct slistelem { char data; slistelem *next; }; class slist { public: slist() : h(NULL), len(0) {} slist(const char *); ~slist() { release(); } char del(); void prepend(char); void append(char); inline slistelem *first() const { return h; } inline int length() const { return len; } int count_c(char c) const; void print() const; private: void release(); slistelem *h; int len; }; // Full constructor slist::slist(const char *s) : h(NULL), len(0) { const char *p = s; while (*p != '\0') { append(*p++); } } // Insert a char at head of list void slist::prepend(char c) { if (h == NULL) { // // This list is empty, allocate and initialize the // head node. // h = new slistelem; h->data = c; h->next = NULL; } else { // // This list is not empty, insert a new node, // containing the given character, at // the head of the list. // slistelem *temp = new slistelem; temp->data = c; temp->next = h; h = temp; } ++len; } // Add a char to end of list void slist::append(char c) { if (h == NULL) { // // This list is empty, allocate and initialize the // head node. // h = new slistelem; h->data = c; h->next = NULL; } else { // // This list is not empty, add a new node, // containing the given character, at // the end of the list. // slistelem *temp = new slistelem, *p = h; temp->data = c; temp->next = NULL; // Find the end of the list. while (p->next != NULL) { p = p->next; } // Add new node. p->next = temp; } ++len; } // Return count of occurrences of c in this list int slist::count_c(char c) const { slistelem *p = h; int n = 0; while (p != NULL) { if (p->data == c) { ++n; } p = p->next; } return n; } // Print the list void slist::print() const { slistelem *temp = h; while (temp != 0) { cout << temp->data; if (temp->next != NULL) cout << " -> "; temp = temp->next; } cout << endl; } // Delete all nodes in the list void slist::release() { while (h != 0) { del(); } } // Delete the node at the head of the list. Return // the character that was there. char slist::del() { slistelem *temp = h; char c = temp->data; h = h->next; delete temp; --len; return c; } int main(int argc, char *argv[]) { slist l1("banana"); slist *l2 = new slist("fireblade"); slist l3(""); slist l4; slist l5(" eht"); l1.print(); l2->print(); l3.print(); cout << endl; cout << "List 1 has: " << l1.length() << " elements" << endl; cout << "List 2 has: " << l2->length() << " elements" << endl; cout << "List 3 has: " << l3.length() << " elements" << endl; cout << "List 4 has: " << l4.length() << " elements" << endl; cout << "List 5 has: " << l5.length() << " elements" << endl; cout << endl; cout << "List 1: count('a') = " << l1.count_c('a') << endl; cout << "List 2: count('d') = " << l2->count_c('d') << endl; cout << "List 3: count('x') = " << l2->count_c('x') << endl << endl; while (l5.length() > 0) { l2->prepend(l5.del()); } l2->print(); delete l2; return 0; } #if 0 Program output: b -> a -> n -> a -> n -> a f -> i -> r -> e -> b -> l -> a -> d -> e List 1 has: 6 elements List 2 has: 9 elements List 3 has: 0 elements List 4 has: 0 elements List 5 has: 4 elements List 1: count('a') = 3 List 2: count('d') = 1 List 3: count('x') = 0 t -> h -> e -> -> f -> i -> r -> e -> b -> l -> a -> d -> e #endif