1 CSC 270 – Survey of Programming LanguagesC++ Lecture #3 – Arrays and Structures Modified from Dr. Robert Siegfried’s Presentation
2 Grouping Data We don’t buy individual eggs; we buy them in units of 12 (“dozens”). We often think in terms of these groups and not the individual members. Examples - classes, baseball teams, encyclopedia sets, etc. It is extremely helpful to be able to group data items that are closely related, e.g., class grades on a test, pay rates for a group of employees, etc.
3 Declaring Arrays Instead of writing: we can write:int x; we can write: int x[10]; the name x refers to the collection (or array) of integer values, which can contain up to 10 values.
4 Using An Array We can assign a value to any element in the array by specify the array by name and its index: x[0] = 87; x[1] = 90; … … … x[9] = 93; lowest index highest index
5 Using An Array (continued)An index can be any integer or character literal, constant, variable or expression: x[6] = x[5] + 4; x[Five] = 34; x[i+1] = x[i] + 3; This is really useful, because we do not want to have to write separate statement to assign values to each array element.
6 Using a Counting Loop To Set An ArrayCounting loops are really useful when manipulating arrays: for (i = 0; i < 10; i++) cin >> x[i];
7 A Program To Find Class Average#include
8 int main(void) { int grades[numgrades], average; getgrades(grades); average = calcaverage(grades); printresults(grades, average); return(0); }
9 void getgrades(int grades[]) { int count; for (count = 0; count < numgrades; count++) { cout << "Enter a grade "; cin >> grades[count]; } int calcaverage(int grades[]) int count, sum = 0; for (count = 0; count < numgrades; count++) sum = sum + grades[count]; return(sum/numgrades);
10 void printresults(int grades[], int mean) { int i; cout << "The grades are:" << endl; for (i = 0; i < 10; i++) cout << grades[i] << endl; cout << "The average is " << mean; cout << " corresponding to a grade of “ << lettergrade(mean) << endl; }
11 char lettergrade(int score) { if (score >= 90) return('A’); if (score >= 80) return('B’); if (score >= 70) return(‘C’); if (score >= 60) return('D’) else return('F'); }
12 Example - A Payroll ProgramLet’s rewrite our payroll so it can use different tax brackets which the user will input.
13 The Revised Payroll Program#include
14 void writecheck(float gross, float tax, float net, float rate, float hours); Bool calcagain(void); // A payroll program that allows the user to // enter the tax brackets int main(void) { float hours, rate; float gross, tax, net, trate; float taxmin[NumBrackets], taxrate[NumBrackets]; boolean again;
15 //Get the tax brackets before processing //any payroll records getbrackets(taxmin, taxrate); do { //Get the inputs, calculate the gross getinput(hours, rate); gross = getgross(hours, rate); //Calculate the tax and subtract it to // get the net tax = gettax(gross, taxmin, taxrate); net = gross - tax;
16 //Write the paycheck writecheck(gross, tax, net, rate, hours); // Does the user want to process another // record? again = calcagain(); } while (again); // If not, quit return(0); }
17 // getbrackets() - Input the tax brackets // There are two different arrays // one stores the minimum gross // for the tax bracket, the other // stores the tax rate void getbrackets(float taxmin[],float taxrate[]) { int i; for (i = 0; i < NumBrackets; i++) { cout << "What is the maximum income" << " for bracket #" << i+1 << '?'; cin >> taxmin[i];
18 cout << "What is the tax rate for bracket " << ” #" << i+1 << '?'; cin >> taxrate[i]; taxrate[i] = taxrate[i]/100; } cout << "\n\n\n";
19 // getinput() - Input the hours worked and pay // rate for each employee void getinput(float &hours, float &rate) { cout << "How many hours worked?"; cin >> hours; cout << "At what rate per hour?"; cin >> rate; }
20 //calcgross() - Calculate the gross pay // including any overtime float getgross(float hours, float rate) { if (hours > 40) // With overtime return(40*rate + 1.5*rate*(hours-40)); else // Without overtime return(rate*hours); }
21 //gettax() - Calculate the tax for the // employee using the tax brackets float gettax(float gross, float taxmin[], float taxrate[]) { int i; // If the employee doesn't make enough for the // lowest bracket the tax is zero if (gross < taxmin[0]) return(0.0);
22 // Find the appropriate bracket for the // employee for (i = 1; i < NumBrackets; i++) { if (gross < taxmin[i]) return(taxrate[i-1]*gross); } //The employee is in the highest bracket return(taxrate[NumBrackets-1]*gross);
23 //writecheck() - Write the paycheck void writecheck(float gross, float tax, float net, float rate, float hours) { // The preliminary formatting cout.setf(ios::showpoint); cout.setf(ios::fixed); cout.precision(1); // Print the input data cout << "Hours = " ; cout.width(4); cout << hours << '\t'; cout.precision(2); cout << "Rate = $";
24 cout.width(6); cout << rate << endl; // Print the gross pay cout << "Gross = $"; cout.width(7); cout << gross << endl; // Print the tax cout << "Tax = $"; cout << tax << endl;
25 // Print the net pay cout << "Net = $"; cout// Print the net pay cout << "Net = $"; cout.width(7); cout << net << "\n\n"; }
26 //calcagain() - Returns true if the user want // to go again//calcagain() - Returns true if the user want // to go again. // Returns false if not boolean calcagain(void) { char answer; do { cout << "Do you want to process another" << " payroll record (y - n)?"; cin >> answer; } while (toupper(answer) != 'Y' && toupper(answer) != 'N');
27 if (toupper(answer) == 'Y') return(true); else return(false); }
28 Sorting 1. For I = 0 to Size-1: 1.1 Find the Ith smallest numberWhat if the brackets are not read in the proper order? Let’s sort them and get them in the right order The Selection Sort Algorithm: 1. For I = 0 to Size-1: 1.1 Find the Ith smallest number 1.2 Place it in slot I
29 Selection Sorting #include
30 sort(a); for (i = 0; i < Size; i++) cout << "a[" << i << "] = " << a[i] << endl; return(0); }
31 // sort() - Sort an array of numbers void sort(int x[]) { int i, j, small, index, temp; // Place the smallest number in the first // position // Place the second smallest in the second // position and so on. for (i = 0; i < Size -1; i++) { small = 32767; index = -1; // Compare each number that is not in // its proper place to the smallest so // far
32 for (j = i; j < Size; j++) if (x[j]
33 Multidimensional ArraysYou can declare a two-dimensional array by writing: int x[NumRows][NumColumns]; E. g., int x[3][6] x[0][0] x[0][1] x[0][2] x[0][3] x[0][4] x[0][5] x[1][0] x[1][1] x[1][2] x[1][3] x[1][4] x[1][5] x[2][0] x[2][1] x[2][2] x[2][3] x[2][4] x[2][5]
34 Implementing Multidimensional Arraysx[0][0] Two-dimensional arrays are stored row-major, which means that the entire row is stored in consecutive memory addresses, with subsequent rows following it. x[0][1] x[0][2] x[0][3] x[0][4] x[0][5] x[1][0] x[1][1] x[1][2] x[1][3] x[1][4] x[1][5] x[2][0]
35 Example: Class Average on a Series of ExamsImagine that students in a class have taken four tests and their grades depends on the average score on this exam. Our data looks like this: each test each student
36 grades.cpp #include
37 // CalcAverages() - Calculate the term// averages for a class // The average is based on // four exams int main(void) { int grades[numstudents][numexams]; int averages[numstudents]; //Get the grades, find the averages and //print them readgrades(grades); findaverages(averages, grades); writegrades(grades, averages); return(0); }
38 // readgrades() - Read the complete set of gradesvoid readgrades(int grades[][numexams]) { int i, j; // Get each students grade for (i = 0; i < numstudents; i++) { //Get the next grade for this student for (j = 0; j < numexams; j++) { cout << "Grade on test #" << j << " for student # " << i << "\t?"; cin >> grades[i][j]; } //Skip one line for clarity cout << '\n';
39 // FindAverages() - Find the average for each// student void findaverages(int averages[], int grades[][numexams]) { int i, j, sum; for (i = 0; i < numstudents; i++) { sum = 0; for (j = 0; j < numexams; j++) sum += grades[i][j]; averages[i] = sum/numexams; }
40 // WriteAverage() - Output the grades and// average for each student void writegrades(int grades[][numexams], int averages[]) { int i, j; // Print a heading cout << "Student Exam1\tExam2\tExam3\tExam4” << \tAverage" << endl;
41 for (i = 0; i < numstudents; i++) {// Number each line, then print the grades // and the average for the enxt student cout << i; for (j = 0; j < numexams; j++) { cout << '\t'; cout.width(4); cout << grades[i][j]; } cout << '\t' << averages[i] << endl;;
42 Limitations of grades.cppThe program has a major limitation: we must know exactly how many students there are. It would be better if we can safely guess our upper limit and count the exact number.
43 Adding and subtracting matrices is easy:A matrix is a two-dimensional array of numbers, used in many types of mathematical problems. Adding and subtracting matrices is easy: ai, j + bi, j = ci, j ai, j - bi, j = ci, j Multiplying matrices is much harder:
44 multmat.cpp #include
45 // multmat() – Read and multiply two matricesint main(void) { int a[numrows][numcolumns], b[numrows][numcolumns], c[numrows][numcolumns]; cout << "Enter matrix a" << endl; readmatrix(a); cout << "Enter matrix b" << endl; readmatrix(b); multmatrix(c, a, b); cout << "The product is:" << endl; writematrix(c); return(0); }
46 //readmatrix() - Read in a matrixvoid readmatrix(int matrix[][numcolumns]) { int i, j; for (i = 0; i < numrows; i++) { cout << "Enter row #" << i+1 << "\t?"; for (j = 0; j < numcolumns; j++) cin >> matrix[i][j]; }
47 // multmatrix() – Multiply a x b to get cvoid multmatrix(int c[][numcolumns], int a[][numcolumns], int b[][numcolumns]) { int i, j, k; for (i = 0; i < numrows; i++) for (j = 0; j < numcolumns; j++) { c[i][j] = 0; for (k = 0; k < numrows; k++) c[i][j] += a[i][k]*b[k][j]; }
48 // writematrix() – Write an i x j matrixvoid writematrix(int matrix[][numcolumns]) { int i, j; for (i = 0; i < numrows; i++) { for (j = 0; j < numcolumns; j++) cout << '\t' << matrix[i][j]; cout << '\n'; }
49 What is a Structure A structure is a heterogeneous collection of data.Even if the data type is the same, it may not belong in an array but in a structure.
50 Declaring A Structure A structure containing the rate of pay and hours worked might look like this: struct { int rate; int hours; int gross; } worker;
51 Declaring A Structure (continued)Alternatively, we can write: struct { int rate, hours, gross; } worker;
52 Declaring A Structure (continued)We can give the structure a name and then declare variables as structures of this type very easily: struct workerstuff { int rate, hours, gross; } ; … … int main(void) { workerstuff worker;
53 Using A Structure To use a field within the structure, you must specify both the structure and the field with a period “.” in between: cin >> worker.rate; cin >> worker.hours; worker.gross = worker.rate * worker.hours;
54 A simple payroll program#include
55 int main(void) { workerstuff worker; cout << "What is the worker\'s rate per " << "hour?\t"; cin >> worker.rate; cout << "How many hours did the worker work " << "last week?\t"; cin >> worker.hours; cout << "What is the worker\'s name?\t"; cin >> worker.name;
56 cout. setf(ios::showpoint); cout. setf(ios::fixed); coutcout.setf(ios::showpoint); cout.setf(ios::fixed); cout.precision(1); cout << worker.name << " worked " << worker.hours << " hours at $"; cout.precision(2); cout << worker.rate << " per hour." << endl; return(0); }
57 Revising the payroll program#include
58 // The prototypes void getbrackets(brackettype brackets[]); void getinput(float &hours, float &rate); float getgross(float hours, float rate); float gettax(float gross, brackettype brackets[]); void writecheck(float gross, float tax, float net, float rate, float hours); boolean calcagain(void);
59 // A payroll program that allows the user to // enter the tax brackets int main(void) { float hours, rate; float gross, tax, net; brackettype brackets[NumBrackets]; boolean again; // Get the tax brackets before processing any // payroll records getbrackets(brackets);
60 do { //Get the inputs, calculate the gross getinput(hours, rate); gross = getgross(hours, rate); //Calculate the tax and subtract it to get //the net tax = gettax(gross, brackets); net = gross - tax; //Write the paycheck writecheck(gross, tax, net, rate, hours); // Does the user want to process another // record? again = calcagain(); } while (again);
61 // Does the user want to process another // record// Does the user want to process another // record? again = calcagain(); } while (again); // If not, quit return(0); }
62 // getbrackets() - Input the tax brackets // There are two different arrays one // stores the minimum gross for the tax // bracket, the other stores the tax // rate void getbrackets(brackettype brackets[]) { int i; for (i = 0; i < NumBrackets; i++) { cout << "What is the maximum income for" << " bracket #" << i+1 << '?'; cin >> brackets[i].minsalary;
63 cout << "What is the tax rate for bracket" << " #" << i+1 << '?'; cin >> brackets[i].taxrate; brackets[i].taxrate = brackets[i].taxrate/100; } cout << "\n\n\n";
64 //gettax() - Calculate the tax for the // employee using the tax brackets float gettax(float gross, brackettype brackets[]) { int i; // If the employee doesn't make enough for the // lowest bracket the tax is zero if (gross < brackets[0].minsalary) return(0.0); // Find the appropriate bracket for the // employee
65 for (i = 1; i < NumBrackets; i++) { if (gross < brackets[i]for (i = 1; i < NumBrackets; i++) { if (gross < brackets[i].minsalary) return(brackets[i-1].taxrate*gross); } //The employee is in the highest bracket return(brackets[NumBrackets-1].taxrate*gross);
66 Structures Containing ArraysA structure can have an array as a field within it. Examples of this include character strings. Our Dean’s List program could use this to include the grades that comprised our students’ g.p.a.
67 Example: Find a Student’s Exam AverageFind a student’s exam average, given the scores on 4 exams. Initial algorithm: 1. Find the student’s exam scores 2. Calculate the student’s average 3. Print the scores and average
68 avggrade.cpp #include
69 // AvgGrade() - Averages the grades on n examsint main(void) { examrec student; float average; // Read the students name and test scores readstudent(student); // Find the average average = findaverage(student); // Print the results writestudent(student, average); return(0); }
70 // ReadStudent() - Read the input about thevoid readstudent(examrec &student) { int i; cout << "First name\t?"; cin >> student.firstname; cout << "Last name\t?"; cin >> student.lastname; for (i = 0; i < numexams; i++) { cout << "Enter grade for exam #” << i+1 << "\t?"; cin >> student.exam[i]; }
71 // FindAverage() - Returns the average of n// exam scores float findaverage(examrec student) { int i, sum = 0; for (i = 0; i < numexams; i++) sum += student.exam[i]; return((float) sum/numexams); }
72 // WriteStudent() - Print the data about the// student including the // average void writestudent(examrec student, float average) { int i; cout << student.firstname << ' ‘ << student.lastname << " scored : " << endl;; for (i = 0; i < numexams; i++) cout << student.exam[i] << '\t'; cout << "\n\twhich resulted in an average of " << average << endl; }