0

I need some serious help with understanding Linked Lists in C++ I am suppose to take a program that I wrote a couple weeks ago using array structures and convert them into linked lists and add a couple new functions. My big concern is I do not feel confident in linked lists and have been spending time on here and other sites gaining knowledge on them. But I cannot find a source that helps me relate to the problem I am facing right now.

Here is my original code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

struct YouTubeVideo { 
char video_name[1024];        // YouTube video name
int video_ranking;            // Number of viewer hits
char video_url[1024];         // YouTube URL
};

struct YouTubeVideo Collection[MAX];

int tail = 0;

//-- Forward Declaration --// 
void printall();
void insertion();
void sort();
void branching(char option);        
void menu(); 
void load_file();
void save_file();

int main()
{
char ch; 

load_file();

printf("\n\nWelcome to CSE240: YouTube Classic Hits\n");

do {
     menu();
     fflush(stdin);                 // Flush the standard input buffer 
     ch = tolower(getchar());       // read a char, convert to lower case
     branching(ch);
} while (ch != 'q');

return 0; 
}

void menu()
{
 printf("\nMenu Options\n");
 printf("------------------------------------------------------\n");
 printf("i: Insert a new favorite\n");
 printf("p: Review your list\n"); 
 printf("q: Save and quit\n");
 printf("\n\nPlease enter a choice (i, p, or q) ---> "); 
}

void branching(char option)
{
switch(option)
{
    case 'i':
        insertion();
        sort();
    break;

    case 'p':
        printall();
    break;

    case 'q':
        save_file();
    break;

    default:
        printf("\nError: Invalid Input.  Please try again..."); 
    break;
}
}

void insertion()
{
if(tail < MAX)
{
    printf("\nWhat is the name of the video? (No spaces characters allowed)\n");
    scanf("%s", Collection[tail].video_name);

    printf("\nHow many viewer hits does this video have?\n");
    scanf("%d", &Collection[tail].video_ranking);

    printf("\nPlease enter the URL: ");
    scanf("%s", Collection[tail].video_url);

    tail++;
}
else
{
    printf("\nERROR: Your collection is full. Cannot add new entries.\n");
}
}

void sort()
{
int i = 0, j = 0; 
struct YouTubeVideo temp;

for(i = 0; i < tail; i++)
{
    for(j = i+1; j < tail; j++)
    {
        if(Collection[i].video_ranking < Collection[j].video_ranking)
        {
            temp = Collection[i];
            Collection[i] = Collection[j];
            Collection[j] = temp;
        }
    }
}

//RA: I think it's easier (and faster) to assume your current list is already
//    sorted and then insert your new element into the correct position. (You
//    can show this maintains a sorted list by induction.)

printf("\nSorting Complete...\n");
}

void printall()
{
int i; 

printf("\nCollections: \n"); 

for(i = 0; i < tail; i++)
{
    printf("\nVideo Name: %s", Collection[i].video_name);
    printf("\nRanking (Hits): %d", Collection[i].video_ranking);
    printf("\nURL: %s", Collection[i].video_url);
    printf("\n");
}
}

void save_file() { 
FILE *fileName;                                     // declare a pointer to File type 
char ch; 
int index = 0; 

fileName = fopen("ranking.dbm", "wb");              // "b" for binary mode 
                                                        // ìwî for write


if(fileName != NULL) 
{   
    fwrite(&tail, sizeof(int), 1, fileName);        // Write tail to the     file for later retrieval.

    for(index = 0; index < tail; index++)
    { 
        fwrite(&Collection[index].video_name, 1024, 1, fileName); 
        fwrite(&Collection[index].video_ranking, sizeof(int), 1, fileName);     
        fwrite(&Collection[index].video_url, 1024, 1, fileName);
    } 

    fclose(fileName);
} 
else 
    printf ("ERROR: Could not open file for saving data !\n"); 
}

void load_file() { 
FILE *fileName;                         // declare a pointer     to File type 
int index = 0; 

fileName = fopen("ranking.dbm", "rb");  // "b" for binary mode 
                                    // ìrî           for read

if(fileName != NULL) {   
    fread(&tail, sizeof(int), 1, fileName);

    for(index = 0; index < tail; index++) 
    {
        fread(Collection[index].video_name, 1024, 1, fileName);
        fread(&Collection[index].video_ranking, sizeof(int), 1, fileName);
        fread(Collection[index].video_url, 1024, 1, fileName);
    }

    fclose(fileName);
}
else 
    printf ("ERROR: Could not open file for loading data !\n"); 
}

These are the exact instructions for what I am suppose to do:

Convert the “YouTubeVideo” array structure (Collection) into a linked-list. The program must sort (by “video_name”) the entries as they are inserted into the linked-list. [30 points] (*Note: You will lose 10 points if the linked list is not sorted.)

Now I have given it as good a go as I believe I can with my current understanding but I am running into a problem right now.

Here is the code with my attempt at a solution in it:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

using namespace std;

#define MAX 100

 struct YouTubeVideo
{
char name[1024];        // YouTube video name
int ranking;                // Number of viewer hits
char url[1024];             // YouTube URL
};

struct YouTubeVideo Collection[MAX];

int tail = 0;

//-- Forward Declaration --//
void printall();
void insertion();
void branching(char option);
void menu();


int main()
{
char ch;

// TODO: Add code to load save data from file

cout << "\n\nWelcome to CSE240: YouTube Classic Hits\n";

do {
    menu();
    cin >> ch; // read a char, convert to lower case
    cin.ignore();

    ch = tolower(ch);
    branching(ch);
} while (ch != 'q');

return 0;
}

void menu()
{
cout << "\nMenu Options\n";
cout << "------------------------------------------------------\n";
cout << "i: Insert a new favorite\n";
cout << "p: Review your list\n";
cout << "s: Search\n";
cout << "d: Delete an entry\n";
cout << "q: Save and quit\n";
cout << "\n\nPlease enter a choice (i, p, s, d, or q) ---> ";
}

void branching(char option)
{
switch(option)
{
    case 'i':
        insertion();
        break;

    case 'p':
        printall();
        break;

    case 's':
        // TODO: Add code to search for a particular node by name
        break;

    case 'd':
        // TODO: Add code to remove a node
        break;

    case 'q':
        // TODO: Add code to save data into a file
        break;

    default:
        cout << "\nError: Invalid Input.  Please try again...";
        break;
}
}

void insertion() { // insert a new entry
struct YouTubeVideo *p, *temp;
p = (struct YouTubeVideo *) malloc(sizeof(struct YouTubeVideo)); if (p == 0) {
    printf("out of memory\n"); return; }
printf("Enter Video name, Views, URL: \n"); scanf("%s", p->name); // p->name is array         scanf("%d", &p->phone);
scanf("%s", p->ranking);
temp = head;
if ((head == NULL)||(strcmp(p->name, temp->name) <=0)) {
    p->next = head;
    head = p;
}

else {
    while (temp->next != NULL) {
        if (stricmp(p->name, temp->next->name) <=0) { p->next = temp->next;
            temp->next = p;
            return;
        } else
            temp = temp->next; }
    p->next = NULL;
    temp->next = p;
} }

void printall()
{
int i;

cout << "\nCollections: \n";

for(i = 0; i < tail; i++)
{
    cout << "\nVideo Name: " << Collection[i].name << "\n";
    cout << "\nRanking (Hits): " << Collection[i].ranking << "\n";
    cout << "\nURL: " << Collection[i].url << "\n";
    cout << "\n";
}
}

The problem I am having is with my insertion I am getting error undeclared identifier head and no member named next in YouTubeVideo. I tried placing and declaring them in a bunch of places but cannot seem to fix these errors.

I would really appreciate some help and any possible knowledge you could bestow upon me. I really have given this a big go, but am just stuck fro the moment.

4
  • 3
    This is C, not C++. The only thing that is specific to C++ in this code is the presence of functions in a structure. You have carried over syntax from C which is not required in C++ (i.e., struct YouTubeVideo* p; and are even using malloc and free to allocate your structures (bad idea for non-POD types). Oct 11, 2012 at 21:17
  • 2
    And as an aside, your compiler is of course correct; I don't see head declared anywhere, yet you use it in insertion() Oct 11, 2012 at 21:18
  • 3
    Scratch that; you didn't declare any member functions, I missed a curly. So in fact this is C, not C++. Re-tagged. And again, YouTubeVideo does not declare a member named next. The error message is very clear. Oct 11, 2012 at 21:26
  • where is the correct place to put it then? because I was not able to find a place that if declared, didn't result in an error itself?
    – Slater
    Oct 11, 2012 at 21:43

3 Answers 3

1

You need to actually implement a linked list. This looks like a homework assignment, so im wondering how far into c++ you are. If you arent really doing classes and Object oriented programming yet, the easiest way to fix this is going to be to add a next and previous object to your youtube video struct. like this:

struct YouTubeVideo {   
    char video_name[1024];        // YouTube video name  
    int video_ranking;            // Number of viewer hits 
    char video_url[1024];         // YouTube URL  
    YouTubeVideo* next;
    YouTubeVideo* previous;
};  

next, you will need to add a head declaration. this is going to be of type YouTubeVideo*. When you add the first video, set the head to point at thsi video. then, whenever you add a new video after that, set the next pointer of the head video to point to the new video, and the previous pointer on the new video should point to the head video. Thats the start of your linked list, but your solution is still very messy.

If I was you, I would look at how some Linked List classes are implemented. Here is the header file for the first Linked List class i wrote:

#ifndef LINKEDLIST_H 
#define LINKEDLIST_H

#include "List.h" 

class LinkedList : public List { 
 public: 
  LinkedList();
  virtual double get(int index) const; 
  virtual void add(double item); 
  virtual void insert(int index, double item); 
  virtual double delete_item(int index); 
  virtual int size() const;  
 private:
  class Node;
  Node* first;
  Node* last;
  int listsize;
}; 
class LinkedList::Node{
 public:
  double value;
  Node* next;
};

#endif

You can see that this list has a class Node in it, and this class contains a value double value. If you wanted to use this code, you would have to make your node class have a field that was YouTubeVideo* value.

1

Okay, I'll try my best to give you a quick overview of what a linked list is in C++, while still letting you learn by doing your assignment on your own. Your code was pretty much C, this will be more C++-style, although I'll avoid templates and will sometimes spell things out where a C++ vet might make things terser.

Here's a typical simple node struct for a singly-linked list that holds integers:

struct LinkedListNode
{
  int value;
  LinkedListNode* next;
};

This node holds one integer, plus it holds a pointer to the next node in the list.

Here would be a dumbed-down interface for such a linked list:

struct LinkedList
{
public:
  LinkedList();
  bool isEmpty() const;
  int valueAtBeginning() const;
  void insertAtBeginning(int newValue);

private:
  LinkedListNode* head;
};

This class provides a constructor (a way to make a linked list), a way to insert new items into the list, a way to get the first value in the list, and a way to check if the list is empty. It also keeps (for its own reference) a pointer to the first node in the list.

Let's run through a way to implement these.

Here is the constructor:

LinkedList::LinkedList():
  head(NULL)
{
}

This function initializes the "first item" pointer to be NULL. This will be code for "there is no first item because the list is empty". Speaking of which:

bool LinkedList::isEmpty() const
{
  return (head == NULL);
}

This function says "if the head pointer is null, then the list is empty. Otherwise it's not". Note how the method is marked const, which makes the promise that this code does not modify any part of the list.

This next one's easy, too:

int LinkedList::valueAtBeginning() const
{
  assert(!isEmpty());
  return head->value;
}

This function simply follows the pointer to the first item in the list, and plucks out its value member and returns it. It also asserts that the list is not empty. This will make it easy to find out if you ever make the mistake of asking for something from an empty list. Again, note how the method is marked const because it does not change the list.

Finally, adding new stuff to the beginning:

void LinkedList::insertAtBeginning(int newValue)
{
  LinkedListNode* oldHead = head;
  LinkedListNode* newHead = new LinkedListNode();
  newHead->value = newValue;
  newHead->next = oldHead;
  head = newHead;
}

This is simple enough in concept. We make a new node, and stick it at the front of the list. The old first item becomes the second item. Also, note how I'm using C++ new instead of C malloc here. Quiz: will this work if the list is empty?

Okay, now I'll leave it up to you to store more than just integers. Also, try to figure out how to write a method that removes the first item from the list (using C++ delete, not C free). Then try to write a method that "traverses" the list, printing out each integer as it goes. Once you get that down, try writing methods to add/remove at the end, or in the middle.

0

In simple words, you need to convert an array (of type struct) to a linked list with the same fields.

#include <stdio.h>
#include <stdlib.h>

struct LL
{
    char name[1024];        // YouTube video name
    int ranking;                // Number of viewer hits
    char url[1024];             // YouTube URL

    struct LL *next; // pointer to the next element
};

// this is from your code
#define MAX 100
struct YouTubeVideo
{
    char name[1024];        // YouTube video name
    int ranking;                // Number of viewer hits
    char url[1024];             // YouTube URL
};

// now you have an array of those structs
struct YouTubeVideo Collection[MAX];

// and you can fill it up as you wish

int main(int argc, char**argv)
{
    struct LL *ll = NULL;

    for (int i = 0; i < MaxElements; i++)
    {
        // we have a blob of memo to store your stuff
        x=(struct LL*)calloc(1, sizeof(struct LL));
        if (x != NULL)
    {
        // just run out of memory
        // so handle the error
    }
        else
    {
        // nothing to do just copy fields of Collection[i]
        // to the newly allocated space
        x->name    = strdup(Collection[i].name);
        x->ranking = Collectionp[i].ranking;
        x->url     = strdup(Collection[i].name);
        x->next    = NULL;

        // since you want your result sorted we need to find its
        // location in the linked list

        if (ll == NULL) // if the list is empty
        {
            ll=x;
            // and nothing else to do since a list with a single element
            // is always sorted
        }
        else
        {
            struct LL *p = ll, *q = ll;
            // need to find where in the list should x be inserted
            // p is not null (see the assignment above) so we
            // always can call strcmp on it. also for x

            while (p!=NULL && strcmp(p->name, x->name) < 0)
        // p can become null if your struct is to become the last
        // in the linked list: the order of comparisons are
        // important
        {
            q=p; // we need q, the parent node because it is
                 // the parent node's next pointer needs to be modified
            p=p->next;
        }
            // once we get here p points to an LL structure or NULL if
            // the element to be inserted will be the last in the list
            // q points to the element before p

                // one more trick: if element being inserted is comes earlier than
                // the first element we need to modify ll
                if (q == ll)
                {
                 x->next = ll;
                 ll = x;
                }
                else
                {
                    x->next=q->next;
                    q->next=x;

                // these lines don't fiddle with p
            }
     }
  }

}

You probably want to put the code into a function. Note that inserting into a single linked list is a little more tricky that inserting into a double linked list, but it saves a pointer. And a word of warning: I have not tested this, just typed in the logic of it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.