Transcript Linear List - University of Southern Mississippi

Linear List
Array representation
Data structures
• A data structure is a particular way of storing
and manipulating data in a computer so that
it can be used efficiently.
• Simple data types (storing data and
manipulated by build-on operators)
• Structured data types (member variables and
functions)
– Structs
– Classes
Linear Lists
• Each instance of the data structure linear list
(or ordered list) is an collection of ordered
elements.
• Instances of a linear list are of the form
– (e0, e1, e2, …, en-1)
– where ei denotes a list element
– n >= 0 is finite
– list size is n (the number of elements in the list)
Linear Lists
L = (e0, e1, e2, e3, …, en-1)
relationships
e0 is the zero’th (or front) element
en-1 is the last element
Linear List Examples/Instances
StudentsinCSC307=
(Jack, Jill, Abe, Henry, Mary, …, Judy)
ExamsinCSC307=
(exam1, exam2, exam3)
DaysofWeek = (S, M, T, W, Th, F, Sa)
Months = (Jan, Feb, Mar, Apr, …, Nov, Dec)
Linear List Operations—size()
the number of elements in the list
determine list size
L = (a,b,c,d,e)
L.size() is 5
Linear List Operations—get(theIndex)
get element with given index
L = (a,b,c,d,e)
L.get(0) is a
get(2) is c
get(4) is e
Check if the index is valid before get operation
(theIndex >=0 and theIndex<=listSize)
get(-1) is error
get(9) is error
Linear List Operations—
indexOf(theElement)
determine the index of a given element
L = (a,b,d,b,a)
indexOf(d) is 2
indexOf(a) is 0
indexOf(z) is -1 //element is not in the list
The index of a nonexistent element is defined to be –1. When
theElement is in the list an index between 0 and size()-1 is the
result. So –1 would be an invalid index and is used to represent
the case when theElement is not in the list
Linear List Operations—
erase(theIndex)
Remove/delete element with given index
L = (a,b,c,d,e,f,g)
erase(2) removes c
and L becomes (a,b,d,e,f,g)
index of d,e,f, and g decrease by 1
Size of the list decrease by 1
Linear List Operations—erase
Remove/delete element from the list6
L = (a,b,c,d,e,f,g)
erase(indexof(c)) removes c
and L becomes (a,b,d,e,f,g)
L.size() becomes 5
index of d,e,f, and g decrease by 1
Size of the list decrease by 1
Linear List Operations—
erase(theIndex)
Remove/delete element with given
index
L = (a,b,c,d,e,f,g)
Check if theIndex is valid before erase
operation
erase(-1) => error
erase(20) => error
Linear List Operations—
insert(theIndex, theElement)
add an element so that the new element
has a specified index
L = (a,b,c,d,e,f,g)
insert(0,h) => L = (h,a,b,c,d,e,f,g)
index of a,b,c,d,e,f, and g increase by 1
Size of the list increase by 1
Linear List Operations—
insert(theIndex, theElement)
L = (a,b,c,d,e,f,g)
insert(2,h) => L = (a,b,h,c,d,e,f,g)
index of c,d,e,f, and g increase by 1
Check if theIndex is valid before insert
insert(10,h) => error
insert(-6,h) => error
Abstract Data Type (ADT)
• Abstraction: separating the design details
from its use of called abstraction. E.g. how the
car’s engine works is abstraction, how the
car’s engine is designed is implementation
• Abstract Data Type (ADT): a data type that
separates the logical properties from the
implementation details.
• Classes are a convenient way to implement an
ADT.
Data Structure Specification
Language independent
Abstract Data Type
Abstract Data Type (ADT): a data type that separates the logical
properties from the implementation details and is a model for a
certain class of data structures that have similar behavior;
C++
Abstract Class is used for the class of data
structures.
Linear
List
Abstract
Data
Type
AbstractDataType LinearList
{
instances
ordered finite collections of zero or more elements
operations
empty(): return true iff the list is empty, false otherwise
size(): return the list size (i.e., number of elements in the list)
get(index): return the indexth element of the list
indexO f(x): return the index of the first occurrence of x in
the list, return -1 if x is not in the list
erase(index): remove the indexth element,
elements with higher index have their index reduced by 1
insert(theIndex, x): insert x as the indexth element, elements
with theIndex >= index have their index increased by 1
output(): output the list elements from left to right
}
Linear List As C++ Abstract Class
cannot be instantiated.
template<class T>
class linearList
{
public:
virtual ~linearList() {};
virtual bool empty() const = 0;
virtual int size() const = 0;
virtual T& get(int theIndex) const = 0;
virtual int indexOf(const T& theElement) const = 0;
virtual void erase(int theIndex) = 0;
virtual void insert(int theIndex, const T& theElement) = 0;
virtual void output(ostream& out) const = 0;
};
Linear list data store
• Array
• Linked list
Extending A C++ Class
template<class T>
class arrayList : public linearList<T>
{
// code for all abstract methods of linearList must come here
}
If arrayList does not provide an implementation for all abstract
methods of linearList, arrayList also is abstract and so cannot be
instantiated.
Linear List Array Representation
use a one-dimensional array element[]
element[15] = {a,b,c,d,e};
a
b
c
0
1
2
d
e
3
4
5
6
L = (a, b, c, d, e)
Store element i of list in element[i].
14
Data Type Of Array element[]
• Data type of list elements is unknown.
• To use this representation in C++, we must
know/provide a data type and length of the
array element[].
• Use template type T to get a generic class that
works for all data types.
• Define element[] to be of template type T.
Length of Array element[]
Don’t know how many elements will be in list.
Must pick an initial length and dynamically increase as
needed.
Use variable arrayLength to store current length of
array element[].
Increasing Array Length
(length vs size)
What is different between size and length?
Length/size of array element[] is 6.
a
b
c
d
e
f
First create a new and larger array
arrayLength = 15;
T* newArray = new T[arrayLength];
Increasing Array Length
Now copy elements from old array to new one.
a
b
c
d
e
f
a
b
c
d
e
f
copy(element, element + 6, newArray);
Increasing Array Length
Finally, delete old array and rename new array.
delete [] element;
element = newArray;
arrayLength = 15;
element[0]
a
b
c
d
e
f
Change Array Length
template<class T>
void changeLength1D(T*& a, int oldLength, int newLength)
{
if (newLength < 0)
{
cout << “wrong length!\n”; return -1;}
T* temp = new T[newLength];
// new array
int number = min(oldLength, newLength); // number to copy
copy(a, a + number, temp); // function copy from algorithm.h
delete [] a;
// deallocate old memory
a = temp;
}
Class arrayList
template<class T>
class arrayList : public linearList<T>
{
public:
// constructor, copy constructor and destructor
arrayList(int initialCapacity = 10);
arrayList(const arrayList<T>&); //copy constructor
~arrayList();
// ADT methods from class linearList
bool empty() const {return listSize == 0;}
int size() const {return listSize;}
T& get(int theIndex) const;
int indexOf(const T& theElement) const;
void erase(int theIndex);
void insert(int theIndex, const T& theElement);
void output(ostream& out) const;
// additional method
int capacity() const {return arrayLength;}
protected:
void checkIndex(int theIndex) const; // throw illegalIndex if theIndex invalid
T* element;
// 1D array to hold list elements
int arrayLength;
// capacity of the 1D array
int listSize;
// number of elements in list
};
Constructor
arrayList(int initialCapacity = 10);
arrayLength = initialCapacity;
element = new T[arrayLength];
listSize = 0;
Constructor
template<class T>
arrayList<T>::arrayList(int initialCapacity)
{// Constructor.
if (initialCapacity < 1)
{
cout << “wrong intinitial capacity” << endl;
}
arrayLength = initialCapacity;
element = new T[arrayLength];
listSize = 0;
}
constructor
// test constructor
arrayList<double> *x = new arrayList<double>(20);
arrayList<int> y(2), z;
Copy Constructor
arrayList(const arrayList<T>& theList);
Now copy elements from old array to new one.
theList
a
b
c
d
e
f
a
b
c
d
e
f
element
element
arrayLength = theList.arrayLength;
listSize = theList.listSize;
element = new T[arrayLength];
copy(theList.element, theList.element + listSize, element);
Copy constructor
template<class T>
arrayList<T>::arrayList(const arrayList<T>& theList)
{
// Copy constructor.
arrayLength = theList.arrayLength;
listSize = theList.listSize;
element = new T[arrayLength];
copy(theList.element, theList.element + listSize, element);
}
constructor
// test constructor
arrayList<double> *x = new arrayList<double>(20);
arrayList<int> y(2), z;
//test copy constructor
arrayList<int> w(y);
The Method checkIndex
template<class T>
void arrayList<T>::checkIndex(int theIndex) const
{// Verify that theIndex is between 0 and
// listSize - 1.
if (theIndex < 0 || theIndex >= listSize)
{cout << “invalid index” << endl; return ;}
}
The Method get
template<class T>
T& arrayList<T>::get(int theIndex) const
{// Return element whose index is theIndex.
// Throw illegalIndex exception if no such
// element.
checkIndex(theIndex);
return element[theIndex];
}
get(theIndex)
// test get
cout << "Element with index 0 is " << y.get(0)
<< endl;
cout << "Element with index 3 is " << y.get(3)
<< endl;
int indexOf(const T& theElement)
const;
element
a
b
c
d
e
f
•
•
•
•
indexOf(‘c’);
find(element, element + listSize, ‘c’) //algorithm.h
Find Return element+2;
indexOf(‘c’) is (element+2) – element
•
•
•
•
indexOf(‘h’);
find(element, element + listSize, ‘h’)
Return element+listSise;
If indexOf(‘h’) is listSize // no element is in the list;
The Method indexOf
template<class T>
int arrayList<T>::indexOf(const T& theElement) const
{// Return index of first occurrence of theElement.
// search for theElement
int theIndex = (int) (find(element, element + listSize, theElement) element);
// check if theElement was found
if (theIndex == listSize)
return -1; // not found
else
return theIndex;
}
// test indexOf
int index = y.indexOf(‘a’);
if (index < 0) cout << “a not found" << endl;
else cout << "The index of a is " << index << endl;
index = y.indexOf(‘z’);
if (index < 0) cout << “z not found" << endl;
else cout << "The index of z is " << index << endl;
Erase
erase(int theIndex)
erase(2)
element
element
a
a
b
b
c
d
d
e
e
f
f
copy(element + theIndex + 1, element + listSize, element + theIndex);
element[--listSize].~T(); // invoke destructor
The Method erase
template<class T>
void arrayList<T>::erase(int theIndex)
{
// Delete the element whose index is theIndex.
checkIndex(theIndex);
// valid index, shift elements with higher index
copy(element + theIndex + 1, element + listSize, element + theIndex);
element[--listSize].~T(); // invoke destructor
}
// test erase
y.erase(1);
cout << "Element 1 erased" << endl;
cout << "The list is " << y << endl;
y.erase(2);
cout << "Element 2 erased" << endl;
cout << "The list is " << y << endl;
cout << "Size of y = " << y.size() << endl;
cout << "Capacity of y = " << y.capacity() << endl;
if (y.empty()) cout << "y is empty" << endl;
else cout << "y is not empty" << endl;
insert
insert(int theIndex, const T& theElement)
insert(2,’c’)
element
a
b
d
e
f
element
a
b
c
d
e
f
copy_backward(element + theIndex, element + listSize, element + listSize +
1);
element[theIndex] = theElement;
listSize++;
The Method insert
template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement)
{
// Insert theElement.
checkIndex(theIndex) ;
// valid index, make sure we have space
if (listSize == arrayLength)
{// no space, double capacity
changeLength1D(element, arrayLength, 2 * arrayLength);
arrayLength *= 2;
}
// shift elements right one position
copy_backward(element + theIndex, element + listSize, element + listSize +
1);
element[theIndex] = theElement;
listSize++;
}
// test insert
y.insert(0, 2);
y.insert(1, 6);
y.insert(0, 1);
y.insert(2, 4);
y.insert(3, 5);
y.insert(2, 3);
cout << "Inserted 6 integers, list y should be 1 2 3 4 5 6" << endl;
cout << "Size of y = " << y.size() << endl;
cout << "Capacity of y = " << y.capacity() << endl;
if (y.empty()) cout << "y is empty" << endl;
else cout << "y is not empty" << endl;
y.output(cout);
cout << endl << "Testing overloaded <<" << endl;
cout << y << endl;
The Method output
template<class T>
void arrayList<T>::output(ostream& out) const
{
// Put the list into the stream out.
copy(element, element + listSize, ostream_iterator<T>(cout, “ “));
}
Overloading <<
// overload <<
template <class T>
ostream& operator<<(ostream& out, const arrayList<T>& x)
{
x.output(out);
return out;
}
// test output
cout << "Y is printed by output :\n";
y.output(cout);
cout << "Y is printed by << :\n";
cout << y;
Next class – Lab 1 assignment
• See lab1 presentations and material on course
webpage.
• Submit your lab assignment 1 to class email
account on Next Tuesday (2/08) before 1pm.