Tutorial TwoData Structures
Tutorial Two Data Structures
Data StructuresBasic data types:Integral:integer,character,booleanFloating-point types:float, double, long doubleData structures are methods of organizing large amounts of data.ArrayList, Stack,Queue,DequeueTrees: binary tree, binary search tree,AVL treePriorityQueuesHash tableSetGraphCOMP1200: Data Structures and Algorithms
Data Structures ⚫ Basic data types: ⚫ Integral: integer, character, boolean ⚫ Floating-point types: float, double, long double ⚫ Data structures are methods of organizing large amounts of data. ⚫ Array ⚫ List, Stack, Queue, Dequeue ⚫ Trees: binary tree, binary search tree, AVL tree ⚫ Priority Queues ⚫ Hash table ⚫ Set ⚫ Graph ⚫ COMP1200: Data Structures and Algorithms
Elementary Data Structures Data type is a set of values and a collection ofoperations on those valuesBasic data types in C and C++Integers (ints)short int, int, long int.Floating-point numbers (floats)float, doubleCharacters(chars)charStructure in C and C++
Elementary Data Structures ⚫ Data type is a set of values and a collection of operations on those values ⚫ Basic data types in C and C++ ⚫ Integers (ints) ⚫ short int, int, long int, ⚫ Floating-point numbers (floats) ⚫ float, double ⚫ Characters (chars) ⚫ char ⚫ Structure in C and C++
Example 1: Basic Data Types#include<iostream>Thisprogramcomputerstheaverage#include<stdlib.h>and standard deviationofa#include <math.h>sequenceof integersgeneratedbythelibrary function rand().using namespace std;typedef int Number,Question:howcanyoumoditytheNumber randNumOprogram to handlea sequence ofreturn randO;randomfloating-pointnumbersintherange of [0, 1]?int main(int argc, char *argvl)1int N = atoi(argv[1]),floatml =0.0,m2=0.0;for (int i=O; i<N; i++) (Number x = randNumO;m1 += ((float)x) / N:m2 += ((float)x*x) / N;7cout <<"RAND_MAX.: " <<RAND_MAX <<endlcout<<"Avg.:"<< ml << endl;cout <<"Std. dev.: "<< sqrt(m2 - ml * ml)<< endl:
Example 1: Basic Data Types #include <iostream> #include <stdlib.h> #include <math.h> using namespace std; typedef int Number; Number randNum() { return rand(); } int main(int argc, char *argv[]) { int N = atoi(argv[1]); float m1 = 0.0, m2 = 0.0; for (int i = 0; i < N; i++) { Number x = randNum(); m1 += ((float)x) / N; m2 += ((float)x*x) / N; } cout << "RAND_MAX.: " << RAND_MAX << endl; cout << "Avg.:" << m1 << endl; cout << "Std. dev.: " << sqrt(m2 - m1 * m1) << endl; } This program computers the average and standard deviation of a sequence of integers generated by the library function rand( ). Question: how can you modity the program to handle a sequence of random floating-point numbers in the range of [0, 1]?
Example 2: Structure/*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,/*convert from Cartesian topolarcoordinates */1;mypolar (mypoint p, float *r, float *theta)float mydistance(mypoint, mypoint);3mypolar (mypoint, float *r, float *theta);*r = sqrt(p.x*p.x + p.y*p.y);*theta = atan2(p.y, p.x);int main(int argc, char *argv[l)31struct mypoint a, b,Result:a.x=1.0,a.y=1.0; b.x=4.0; b.y=5.0;cout <<" Distance is "<<mydistance(a, b);[chxw@csr40 cplus]$ ./a.outfloat r, theta,Distance is 5mypolar(a,&r,&theta);r : 1.41421cout<<"r"<<r<<endltheta: 0.cout <<“theta: " << theta << endl;1
Example 2: Structure #include <iostream> #include <stdlib.h> #include <math.h> using namespace std; struct mypoint { float x; float y; }; float mydistance(mypoint, mypoint); mypolar (mypoint, float *r, float *theta); int main(int argc, char *argv[]) { struct mypoint a, b; a.x = 1.0; a.y = 1.0; b.x = 4.0; b.y = 5.0; cout << " Distance is " << mydistance(a, b); float r, theta; mypolar(a, &r, &theta); cout << "r : " << r << endl; cout << “theta: " << theta << endl; } /* 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); } /* convert from Cartesian to polar coordinates */ mypolar (mypoint p, float *r, float *theta) { *r = sqrt(p.x*p.x + p.y*p.y); *theta = atan2(p.y, p.x); } Result: [chxw@csr40 cplus]$ ./a.out Distance is 5 r : 1.41421 theta: 0