Sequences (Outline)Storing Objects in Computer MemoryPointers and One-Dimensional ArraysSTL Class VectorTwo-Dimensional ArraysSTL Class MatrixLinked ListsSTL Class ListSequencesTeresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 1/40Storing Objects in Computer MemoryA computer’s memory is a sequence of numbered bytes from 0to the last one.Abytenumberisanaddressofanobjectinthecomputermemory.int main(){int val = 0;char ch = ’A’;string name = "All";}val ch name0 ’A’ "All"01...... ...... ...... 231 2231 1Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 2/40PointersA pointer is a memory addressof an object of a specified type,or it is a variable which keepssuch an address.Typed object(address)1231612316P (pointer)Pointer properties:Apointervalueistheaddressofthefirstbyteofthepointedobject in the memory.Apointerdoesnot know about how many bytes it points to.Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 3/40Pointers (cont)Pointers are used to:create more complex data types such as lists, queues, stacks,trees, or graphsprocess arrayskeep track of allocated memory returned by the operator newinitialize to nothing (no address) denoted by NULL, 0, ornullptr in C++11.deallocate a block of memory by the operator delete or delete[]Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 4/40ArraysAn array of the fix size represents a contiguous sequence ofobjects of the same type allocated on the stack computermemory. It is a very simple data structure often used in sortingand searching operations.The position of an element in the array is called the index.InC++ arrays always begin with the index 0:01 2345 (indices)12 -3 24 65 92 11 (array values)To declare a static one-dimensional array with fixed size atcompile time (in the stack part of computer memory):constexpr max_size = 6;int array[max_size] = {12,-3,24,65,92,11};where max_size is a constant expression, a compile-timeconstant known during compilation.Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 5/40Arrays (cont.)The total number of items inserted into an array is called thelogical size of the array. A special variable must be used tokeep track of the current number of items.The logical size should be not greater than the physical size ofan array (= maximum size of an array).Operations on arraysAn array provides a random access to its elements:array[index] where 0<=index<max_size.C++ does not check the “index-out-of-bounds” condition andit is a programmer’s responsibility to ensure that the indexrange is valid. It is easy to go out of range, e.g., there is noarray item such as array[max_size].There is no possibility of resizing this type of arrays.Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 6/40Arrays (cont.)To initialize all array elements to zero: array[max_size] ={};Reading from the standard input (usually the keyboard) to anarray of size 100:for (int i = 0; i < 100; i++) cin >> array[i];Writing to the standard output (usually the screen) from anarray of size 100:for (int i = 0; i < 100; i++) cout << array[i] << " ";Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 7/40Arrays (cont.)Linear search for a target x:for (int i = 0; i < 100; i++)if (x != array[i]);else return i; // returns an index if x is foundreturn -1; // returns -1 if x is not foundCopying:for (int i = 0; i < 100; i++)other_array[i] = array[i];// assigning other_array = array; is illegalTeresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 8/40Arrays (cont.)Note that the base address of an array in computer memory isthe address of the first element of the array.Asizeofaconstantarraycanbecomputedbyacompiler.const int days_in_month[] ={31,28,31,30,31,30,31,31,30,31,30,31};int num_of_months =sizeof(days_in_month)/sizeof(*days_in_month);// size can be computedThe value of num_of_months will be 12.Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 9/40Enumeration TypeAn example of enumeration type as an index to an array.enum Color {black, white, red, blue};Color balls[4];Color col; // a variable used as an array indexfor (col = black; col <= blue; col = (Color) (col+1))balls[col] = col;Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 10/40Typedef and an ArrayTypedef is used to define a new type from an existing one:constexpr int max_size = 100;typedef double Table[max_size]; // Table is type nameDeclarations of other variables of array type withtypedef-defined type.Table my_table; // the same as double my_table[max_size];Table A[12]; // the same as double A[12][max_size];Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 11/40Passing an Array to a FunctionAn array as an actual argument of a function is passed by as apointer to its first element. The formal argument of form T[]is converted to T* (T is any C++ type).Example// we want to copy elements of the array A to Bint A[10], B[10];... // insert values to Acopy_elems(A, 10, B, 10); // copy A to BHere is the body of the function (possibly we should check ifsize_a <= size_b):void copy_elems(int A[], int size_a, int B[], int size_b){for (int i = 0; i < size_a; i++)B[i] = A[i];}Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 12/40Dynamic Arraysint* a = new int[3];// with elements 10, 20, 30int* aptr = a; // aptr is an alias to aIt allocates 3 contiguous memory locations on the heap (free store)part of memory, each of type int and stores the address of the firstmemory location in a.Notethatthepointervariablea is kept on thestack part of memory.stack heap... a=1000 10 20 30 ...200 1000 1001 1002 (addresses)++a; //move a forward by 1cout<< *a; // prints 20--a; // move a backward by 1cout << *a; // prints 10--a; // out of rangeIt is easy to go out-of-range in the case of static and dynamic arrayswhen operations on pointers are used.Teresa Leyk (CSCE 221) Data Structures & Algorithms – Sequences Fall 2013 13/40Memory DeallocationDeallocation of memory allocated by the operator new:delete [] a; // now a is a dangling pointera=nullptr;Adeepcopyofanarray.Hereaptr is a separate arrayinitialized by the values of a.aptr = new int[10];for (int j = 0; j < 10; j++)aptr[j] = a[j];Adynamicarrayofpointers.int **ptd = new (int *)[10];for (int i = 0; i < 10; i++)ptd[i] = new int(1);Teresa Leyk