C++ Linked Lists Practice No documentation (commenting) is required for this ass

Question

C++ Linked Lists Practice

No documentation (commenting) is required for this assignment.

Use linked lists to implement a sequence class.

Specification

The specification of the class is below. There are 9 member functions (not counting the big 3) and 2 types to define. The idea behind this class is that there will be an internal iterator, i.e., an iterator that the client cannot access, but that the class itself manages. For example, if we have a sequence object named s, we would use s.start() to set the iterator to the beginning of the list, and s.advance() to move the iterator to the next node in the list.

(I'm making the analogy to iterators as a way to help you understand the point of what we are doing. If trying to think in terms of iterators is confusing, just forget about iterators and focus on following the specification below.)

You are required to implement all of these functions except for attach() and remove_current(). You are also not required to implement the big-3.

Also, your class should be placed in a namespace "cs_sequence".

Here is an example of a simple client program, to give you an idea about how sequences might be used. You can also use this to test your class, but it's far from exhaustive. Keep in mind as you write your class that you should test each member function after you write it.

This client program will print the numbers 5 4 3 2 1 0. (They are backward because insert() inserts each new item at the front of the list.)

Implementation

We will be using the following implementation of type sequence, which includes 5 data members.

o0o numItems. Stores the number of items in the sequence.

o0o headPtr and tailPtr. The head and tail pointers of the linked list. If the sequence has no items, then these pointers are both NULL. The reason for the tail pointer is the attach function. Normally this function adds a new item immediately after the current node. But if there is no current node, then attach places its new item at the tail of the list, so it makes sense to keep a tail pointer around.

o0o cursor. Points to the node with the current item (or NULL if there is no current item).

o0o precursor. Points to the node before current item, or NULL if there is no current item or if the current item is the first node. Note that precursor points to NULL if there is no current item, or, to put it another way, points to NULL whenever cursor points to NULL. Can you figure out why we propose a precursor? The answer is the insert function, which normally adds a new item immediately before the current node. But the linked-list functions have no way of inserting a new node before a speci- fied node. We can only add new nodes after a specified node. Therefore, the insert function will work by adding the new item after the precursor node -- which is also just before the cursor node.

You must use this implementation. That means that you will have 5 data members, you won't have a header node, and precursor must be NULL if cursor is NULL. (What is a header node? If you don't know what it is, you probably aren't using it and shouldn't worry about it. It's not the same thing as a headPtr data member, which you WILL be using in this assignment.)

You should implement nodes using the same technique shown in the lecture videos and in the examples in the written lesson. In other words, there should not be a node class; rather, a node struct should be defined inside the sequence class.

Many students make the mistake of thinking that this assignment will very closely track with the examples done in lecture. In this assignment perhaps more than any other so far I am expecting you to use the concepts taught in the lesson and text to implement a class that is very different from the ones done in the lessons and the text (instead of implementing a class that is pretty similar to the ones done in the lesson and text).

I am providing my solution to the insert() function. This should make it easier to get started: you can use this insert() function and do all of this week's functions (default constructor, size(), start(), advance(), current(), and is_item()) and then write a client program to test what you have so far.

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

/* Link list node */
struct Node
{
int data;
struct Node* next;
};

/* Given a reference (pointer to pointer) to
the head of a list and an int, push a
new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Takes head pointer of the linked list and index
as arguments and return data at index*/
int GetNth(struct Node *head,int n)
{
int count = 1;

//if count equal too n return node->data
if(count == n)
return head->data;

//recursively decrease n and increase
// head to next pointer
return GetNth(head->next, n-1);
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
  
/* Use push() to construct below list
1->12->1->4->1 */
push(&head, 1);
push(&head, 4);
push(&head, 1);
push(&head, 12);
push(&head, 1);  
  
/* Check the count function */
printf("Element at index 3 is %d", GetNth(head, 3));  
getchar();
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.