Lab 7 – Sequence template using linked list 1 Introduction In this lab we will c
ID: 3862777 • Letter: L
Question
Lab 7 – Sequence template using linked list
1 Introduction
In this lab we will create a simplified version of the Standard Template Library’s vector class. A sequence holds a
collection of values. Values may be added and removed from the sequence. The values in a sequence are associated
with an index but a value’s index may change as items are added or removed from the sequence.
Unlike the previous lab, this sequence class needs to:
use a linked list to store the sequence items
be a template class (so value
type below is a generic type)
2 Walk through
Below is a sample program that demonstrates the effect of most of the operations that we can perform on a sequence.
s e q u e n c e < int > s 1 ; / / []
s 1 . a d d ( 5 ) ; / / [5]
s 1 . a d d ( 9 ) ; / / [5 ,9]
s 1 . a d d ( 2 ) ; / / [5 ,9 ,2]
s 1 . i n s e r t ( 1 , 1 5 ) ; / / [5 ,15 ,9 ,2]
s 1 . r e m o v e ( 0 ) ; / / [15 ,9 ,2]
c o u t << s 1 . g e t ( 0 ) << e n d l ; / / would p r i n t 15
c o u t << s 1 . s i z e ( ) << e n d l ; / / would p r i n t 3
s 1 . i n s e r t ( 0 , 3 ) ; / / [3 ,15 ,9 ,2]
s 1 . i n s e r t ( 0 , 2 2 ) ; / / [22 ,3 ,15 ,9 ,2]
for ( i n t i = 0 ; i < s . s i z e ( ) ; i + + )
c o u t << s 1 . g e t ( i ) << ” ” ; / / p r i n t s 22 3 15 9 2
s e q u e n c e < int > s 2 ;
s 2 . a d d ( 7 ) ; / / s2 = [7]
s 2 . a d d ( 5 ) ; / / s2 = [7 ,5]
s e q u e n c e s 3 = s 1 + s 2 ; / / s3 = [22 ,3 ,15 ,9 ,2 ,7 ,5]
s e q u e n c e s 4 ;
s 4 . a d d ( 1 ) ; / / s4 = [1]
s 4 += s 2 ; / / s4 = [1 ,7 ,5]
s e q u e n c e < s t r i n g > s 3 ;
s 3 . a d d ( ” f o o ” ) ;
s 3 . a d d ( ” b a r ” ) ;
c o u t << s 3 . g e t ( 0 ) << e n d l ; / / foo
3 Files
Create a class named sequence and units tests in sequence tests.cpp.
4 Unit tests
All of your original sequence tests should work fine (with small modification since this is a template class) for this version of sequence. An exception would be a test that references the capacity of the sequence.
5 Operations
Implement the operations below. Use assert to check preconditions.
sequence () – construct an empty sequence
sequence(const sequence& other) – copy constructor
sequence () – destruct the sequence
size type size () const – return the number of items stored in the sequence
value type get ( size type i ) const – (precondition: i > = 0 && i <size () ) return the item at position i in the sequence
void add( const value type & value) – add the specified value to the end of the sequence
void insert ( size type index , const value type & value) – (precondition: index > = 0 && index < = size()) insert the specified value at the specified index, shifting values to higher indexes if needed. If index == size this operation is the same as add.
void remove( size type index ) – (precondition: index > = 0 && index <
size()) remove the value at the specified index, shifting other values down as needed.
sequence operator +( const sequence& s1, const sequence& s2) – free function (you may implement this as a member function if you prefer) return a new sequence that is the result of appending s2 on to the end of s1
void operator +=( const sequence& other) – append other onto the end of this sequence
void operator =( const sequence& other) – assignment operator
Explanation / Answer
Solution:
LinkedList.h
#include <iostream>
#include <string.h>
using namespace std;
template <class T>
struct node
{
T data;
struct node<T> *next;
};
template <class T>
class LinkedList
{
int count;
struct node<T> *root;
public:
LinkedList()
{
root=NULL;
count=0;
}
node<T>* createnewNode(T data)
{
struct node<T> *temp;
temp=new(struct node<T>);
temp->data=data;
temp->next=NULL;
return temp;
}
void insert_end(T data)
{
struct node<T> *temp=createnewNode(data);
struct node<T> *tem=root;
if(tem==NULL)
root=temp;
else
{
while(tem->next!=NULL)
{
tem=tem->next;
}
tem->next=temp;
}
count++;
}
void insertValue(size_t index, T data)
{
struct node<T> *temp=createnewNode(data);
struct node<T> *tem=root;
size_t ind=0;
if(tem==NULL)
root=temp;
else if(index>count-1)
{
cout<<"Greater index"<<endl;
return;
}
else
{
while(tem)
{
if(ind==index-1)
break;
tem=tem->next;
ind++;
}
temp->next=tem->next;
tem->next=temp;
}
count++;
}
void removeValue(size_t index)
{
struct node<T> *temp;
struct node<T> *tem=root;
size_t ind=0;
if(root==NULL)
{
cout<<"Empty"<<endl;
return;
}
else if(count==1)
{
temp=tem->next;
root=NULL;
}
else
{
while(tem)
{
if(ind==index-1)
break;
tem=tem->next;
ind++;
}
temp=tem->next;
tem->next=temp->next;
}
free(temp);
count--;
}
void display()
{
struct node<T> *temp=root;
while(temp)
{
cout<<temp->data<<endl;
temp=temp->next;
}
}
void getElement(size_t index)
{
size_t ind=0;
struct node<T> *temp=root;
while(temp)
{
if(ind==index)
break;
temp=temp->next;
}
return temp->data;
}
};
Source.cpp
#include <iostream>
#include <string.h>
#include"LinkedList.h"
using namespace std;
template <class T>
class Sequence:public LinkedList<int>
{
size_t si;
public:
Sequence():LinkedList()
{
si=0;
}
size_t size()
{
return si;
}
T get(size_t index) const
{
return getElement(index);
}
void add(const T & value)
{
insert_end(value);
si++;
}
void insert (size_t index, const T & value)
{
insertValue(index,value);
si++;
}
void remove(size_t index)
{
removeValue(index);
si--;
}
void print()
{
display();
}
};
int main() {
Sequence<int> s1;
s1.add(21);
s1.print();
for(int i=0; i<10; i++)
s1.add(i);
s1.print();
s1.remove(3);
s1.print();
s1.insert(4, 34);
s1.print();
system("pause");
return 0;
}
Output:
21
21
0
1
2
3
4
5
6
7
8
9
21
0
1
3
4
5
6
7
8
9
21
0
1
3
34
4
5
6
7
8
9
Press any key to continue . . .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.