ArraysArray is the most fundamental data structureAn array is a fixed collection of same-type data that arestored contiguously and are accessible by an indexIt is the responsibility of the programmer to use indices thatare nonnegative and smaller than the array sizeTwo waysto createan arrayStatic allocation:size known to and set bythe programmerDynamic allocation:size unknowntothe programmer and setbytheuserattheexecutiontime
Arrays ⚫ Array is the most fundamental data structure ⚫ An array is a fixed collection of same-type data that are stored contiguously and are accessible by an index ⚫ It is the responsibility of the programmer to use indices that are nonnegative and smaller than the array size ⚫ Two ways to create an array ⚫ Static allocation: size known to and set by the programmer ⚫ Dynamic allocation: size unknown to the programmer and set by the user at the execution time
Example: Sieve ofEratosthenes#include<iostream>Sieveof Eratosthenes is a classicalusing namespace std;method tocalculatethetableof primenumbers.staticconstintN=1000:int main()1Basic idea:int i, a[N];Set alil to 1 ifi is prime, and o ifiis not/*initialization*/a prime.for (i= 2; i<N; i++)a[i] = 1,for (i=2; i<N; i++)if(a[i]) /* sieve i's multiples up to N-1*/for(int j= i, j*i<N; j++)a[i*j] = 0;for (i=2;i<N; i++)if (a[i])cout <<"" <<i;cout << endl;1
Example: Sieve of Eratosthenes #include <iostream> using namespace std; static const int N = 1000; int main( ) { int i, a[N]; /* initialization */ for (i = 2; i < N; i++) a[i] = 1; for (i = 2; i < N; i++) if (a[i] ) /* sieve i’s multiples up to N-1*/ for(int j = i; j*i < N; j++) a[i*j] = 0; for (i = 2; i < N; i++) if (a[i]) cout << " " << i; cout << endl; } Sieve of Eratosthenes is a classical method to calculate the table of prime numbers. Basic idea: Set a[i] to 1 if i is prime, and 0 if i is not a prime
Dynamic Memory Allocation·C languagemalloc() and free()C++ languagerdeleteuse operator new and operatorint main(int argc, char *argv)1int N = atoi(argv[1]);int *a = new int[N];if (a == O) { cout <<“out of memory " << endl; return 0; )delete a,7
Dynamic Memory Allocation ⚫ C language ⚫ malloc( ) and free( ) ⚫ C++ language ⚫ use operator new and operator delete int main(int argc, char *argv[]) { int N = atoi(argv[1]); int *a = new int[N]; if (a == 0) { cout << “out of memory " << endl; return 0; } . delete [] a; }
Array of Structures/*returnthedistancebetweentwopoints*#include<iostream>float mydistance(mypoint a, mypoint b)#include<stdlib.h>1#include <math.h>float dx = a.x - b.x,float dy = a.y - b.y,using namespace std,return sqrt(dx*dx + dy*dy);struct mypoint 9float x, float y,;/*returnarandomnumberbetween 0and1*/float mydistance(mypoint, mypoint)float randfloat()float randfloat( );1int main(int argc, char *argv[l)return 1.0 *randO /RAND MAX:13float d = atof(argv[2]);int i, cnt = O, N = atoi(argv[1]);mypoint *a = new mypoint[N];Thisprogramcalculatesthenumberfor(i= 0; i<N; i++) (of pairofpointswhosedistanceisa[i].x = randfloatO; a[i].y = randfloatO;shorterthanathreshold.7for(i=0;i<N; i++)for(int j=i+1;j<N; j++)if (mydistance(a[i], alil) <d) cnt++:cout << cnt <<" pairs within " <<d << endl;delete a;3
Array of Structures #include <iostream> #include <stdlib.h> #include <math.h> using namespace std; struct mypoint { float x; float y; }; float mydistance(mypoint, mypoint); float randfloat( ); int main(int argc, char *argv[]) { float d = atof(argv[2]); int i, cnt = 0, N = atoi(argv[1]); mypoint *a = new mypoint[N]; for( i = 0; i < N; i++) { a[i].x = randfloat(); a[i].y = randfloat(); } for( i = 0; i < N; i++) for(int j = i+1; j < N; j++) if (mydistance(a[i], a[j]) < d) cnt++; cout << cnt << " pairs within " << d << endl; delete [] a; } /* return the distance between two points */ float mydistance(mypoint a, mypoint b) { float dx = a.x - b.x; float dy = a.y - b.y; return sqrt(dx*dx + dy*dy); } /* return a random number between 0 and 1 */ float randfloat( ) { return 1.0 * rand() / RAND_MAX; } This program calculates the number of pair of points whose distance is shorter than a threshold
List. A general list of elements: A1, A2, ..., Anassociated with a set of operations:Insert: add an elementDelete: remove an elementFind: find the position of an element (search)FindKth: find the kth elementEach element has a fixed positionTwo different implementations:Array-based listLinked list
List ⚫ A general list of elements: A1 , A2 , ., AN, associated with a set of operations: ⚫ Insert: add an element ⚫ Delete: remove an element ⚫ Find: find the position of an element (search) ⚫ FindKth: find the kth element ⚫ Each element has a fixed position ⚫ Two different implementations: ⚫ Array-based list ⚫ Linked list