Data Structure

Hoang-Giang Cao (高黃江)

Fall - 2024

MIDTERM - Data Structure

• Mid-term: Monday 04 November 2024
• 90 mins - On-site programing - 4-6 coding problems
• Topics:
• Basic C++ programming (Function, If, Else, For-While)
• Function with array
• min,max, avg, sum
• positive, negative, divisible, conditioned number, etc

​

Notes when doing exam/hw/quiz

1. Many submissions have no comment the studentID
2. Wrong function name:

​

​

• Some students copy code from ChatGPT
• Some students copy code from other students

​

int sum_even_except_ten(int N){...}

int SumEvenExceptTen(int N){}

X

✓

Exercises Basic C++

File Handling

File Handling

• Text file handling
• Write text file
• Read text file

Note:

• Basic file read/write to support Data Structures
• Focus on practical, not detailed
• For more details about file handling, please refer to additional resources or explore it in other courses. (C/C++ programming)

Input - Output in C++

• Currently:
• we take input from keyboard
• Output to screen(console)
• Now, we will learn
• Input from file
• Output to file

File Handling

• #include <fstream> // library for file handling

Define variable

​

​

fstream fVar;

Write/append

Read

​

fVar.open(“filename.txt”, ios:in);

fVar.open(“filename.txt”, ios:app);

fVar.open(“filename.txt”, ios:out);

Close file

​

fVar.close();

Open()

• fstream fVar;
• fVar.open(filename, mode);
• Filename: text file. txt or csv (Comma-separated values)

Write to file

Writing to file

• fstream fVar;
• fVar.open(“out.txt”, ios::out);

Writing to a file

Create a new file my_file.txt in the same directory as the demo_write_file.cpp file.

demo_write_file.cpp

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

fstream fVar;

fVar.open("my_file.txt", ios::out);

return 0;

}

​

.

No output, because we don’t write anything to console

Writing to a file

• Write (string) to a file similar to print to console.

demo_write_file.cpp

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

fstream fVar;

fVar.open("my_file.txt", ios::out);

fVar << "Hello" << endl;

fVar << "1. 1st line" << endl;

fVar << "2. 2nd line\n";

fVar << "3. 3rd line" << endl;

fVar.close();

return 0;

}

​

​

• Using operator <<
• Newline : << endl;
• Newline : << "\n";

Writing to a file

• Write (string) to a file similar to print to console.

demo_write_file.cpp

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

fstream fVar;

fVar.open("my_file.txt", ios::out);

fVar << "Hello" << endl;

fVar << "1. 1st line" << endl;

fVar << "2. 2nd line\n";

fVar << "3. 3rd line" << endl;

fVar.close();

return 0;

}

​

​

fVar.close()to close the file to not conflict to other program.

​

Other program CANNOT USE the file if you are using it (not close it yet)

Writing to a file

• Write (number) to a file similar to print to console.

demo_write_file.cpp

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

int a = 2; float b = 2.5; char c = 'A';

fstream fVar;

fVar.open("my_file.txt", ios::out);

fVar << "Hello" << endl;

fVar << "a = " << a << endl;

fVar << "b = " << b << endl;

fVar << "c = " << c << endl;

fVar << "number " << 12345 << endl;

fVar.close();

return 0;

}

​

​

​

​

​

​

Writing to a file

• Write an array to a file.

demo_write_file.cpp

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

int arr[] = {1,3,5,7,9};

int size = sizeof(arr)/sizeof(int);

fstream fVar;

fVar.open("my_file.txt", ios::out);

for (int i =0; i < size; i++)

fVar << arr[i] << endl;

fVar.close();

return 0;

}

​

​

​

​

​

​

Writing to a file

• Write an array to a file.

demo_write_file.cpp

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

int arr[] = {1,3,5,7,9};

int size = sizeof(arr)/sizeof(int);

fstream fVar;

fVar.open("my_file.txt", ios::out);

for (int i =0; i < size; i++)

fVar << arr[i] << " ";

fVar.close();

return 0;

}

​

​

​

​

​

​

Same line, separated by space

Writing to a file

• Write an array to a file. Write as a function.

#include <iostream>

#include <fstream>

using namespace std;

​

void write_file(char* file_name, int arr[], int N){

fstream fVar;

fVar.open(file_name, ios::out);

for (int i =0; i < N; i++)

fVar << arr[i] << endl;

fVar.close();

}

​

int main (){

int arr[] = {1,3,5,7,9};

int size = sizeof(arr)/sizeof(int);

write_file("output.txt",arr,size);

return 0;

}

​

​

​

​

​

​

​

​

​

​

​

• char* is a input as kind of “string”

Newline \n character

• Newline ‘\n’
• At the end of line.
• “Invisible” - not showing when we see the file
• But it is actually there

1. 1st line

2. 2nd line

3. 3rd line

​

​

4. 4th line

1. 1st line\n

2. 2nd line\n

3. 3rd line\n

\n

\n

4. 4th line\n

​

A file look like this

It actually like this

Exercises

• Save all number user enter from keyboard to “output.txt”
• Until user enter number zero

Hint: Using while loop

Exercises

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

fstream fVar;

fVar.open("out.txt", ios::out);

​

int number = -1;

while (number!=0){

cout <<"Enter a number: ";

cin >> number;

// write to file:

fVar << number << endl;

}

fVar.close();

cout << "Thank you. Bye bye!";

return 0;

}

​

​

​

​

​

​

​

​

​

​

Writing to a file

​

​

​

​

​

​

​

1

​

2

​

3

​

4

​

​

5

​

​

​

6

​

code

1. Open a new file for writing

​

2. Init a number different from ZERO

​

3. While number is not 0, means that the user has not enter number 0

​

4. Take the input from the user

​

​

5. Write to the file

​

​

6. Close the file

​

#include <iostream>

#include <fstream>

using namespace std;

​

int main (){

fstream fVar;

fVar.open("out.txt", ios::out);

​

int number = -1;

while (number!=0){

cout <<"Enter a number: ";

cin >> number;

// write to file:

fVar << number << endl;

}

fVar.close();

cout << "Thank you. Bye bye!";

return 0;

}

​

​

​

​

​

​

​

​

​

​

​

Writing to a file - write in a function

​

​

​

​

​

​

1

​

2

​

3

​

4

​

​

5

​

​

​

6

​

code

1. Open a new file for writing

​

2. Init a number different from ZERO

​

3. While number is not 0, means that the user has not enter number 0

​

4. Take the input from the user

​

​

5. Write to the file

​

​

6. Close the file

​

#include <iostream>

#include <fstream>

using namespace std;

​

void write_file(){

fstream fVar;

fVar.open("out.txt", ios::out);

​

int number = -1;

while (number!=0){

cout <<"Enter a number: ";

cin >> number;

// write to file:

fVar << number << endl;

}

fVar.close();

cout << "Thank you. Bye bye!";

​

}

​

int main (){

write_file()

return 0;

}

​

​

​

​

​

​

​

​

Append to File

Writing to a file - write in a function

code

#include <iostream>

#include <fstream>

using namespace std;

​

void write_file(){

fstream fVar;

fVar.open("out.txt", ios::app);

​

int number = -1;

while (number!=0){

cout <<"Enter a number: ";

cin >> number;

// write to file:

fVar << number << endl;

}

fVar.close();

cout << "Thank you. Bye bye!";

​

}

​

int main (){

write_file()

return 0;

}

​

​

​

​

​

​

​

​

Run it to see the result

​

​

Keep writing to the file

Writing to file

• fstream fVar;
• fVar.open(“out.txt”, ios::out);

Alway create new file, overwrite existing content.

Writing to file

• fstream fVar;
• fVar.open(“out.txt”, ios::app);

Read from File

Reading from file

• fstream fVar;
• fVar.open(“in.txt”, ios::in);

Txt file

Home

Song by Michael Bublé

​

Another summer day

Has come and gone away

In Paris and Rome

But I wanna go home, mmm

May be surrounded by

A million people I

Still feel all alone

Just wanna go home

Baby, I'm done

I gotta go home

Let me go home

It'll all be all right

I'll be home tonight

I'm coming back home

​

home.txt

Read file (string)

#include <iostream>

#include <fstream>

using namespace std;

​

​

​

int main (){

fstream fVar;

fVar.open("home.txt",ios::in);

string line;

while (getline(fVar,line)){

cout << line << endl;

}

fVar.close();

return 0;

}

For a string: using getline() function. For getting a line

Output from screen

Read file (string)

#include <iostream>

#include <fstream>

using namespace std;

​

​

​

int main (){

fstream fVar;

fVar.open("home.txt",ios::in);

string line;

while (fVar >> line){

cout << line << endl;

}

fVar.close();

return 0;

}

fVar >> line will get word by word, separated by space

While not fVar >> line?

Read file (string)

• getline(fVar,line)
• Will get the full line (multiple words with space_
• fVar >> line
• will get word by word, separated by space

Read file (number)

1 2 3 4

5 6 7 8

10 20 30 40

50 60 70 80 90 100

​

data.txt

Read file (number)

#include <iostream>

#include <fstream>

using namespace std;

​

​

​

int main (){

fstream fVar;

fVar.open("data.txt",ios::in);

int number;

while (fVar >> number){

cout << number << endl;

}

fVar.close();

return 0;

}

Using fvar >> number; to get one by one number

Also work with new line. New line has no effect

Output (screen)

Read file -> add into array?

#include <iostream>

#include <fstream>

using namespace std;

​

void print_array(int arr[], int N){

for (int i =0; i < N; i++)

cout << arr[i] << endl;

}

​

​

int main (){

fstream fVar;

fVar.open("data.txt",ios::in);

int arr[10000];

int size = 0;

int number;

while (fVar >> number){

arr[size] =number;

size+=1;

}

print_array(arr,size);

fVar.close();

return 0;

}

​

• Create a blank array with MAXSIZE
• Create variable as the current index (position) of the array
• Read number from file, add into array in the next position
• Update the current index

​

The size of the array = the last index

When we can read file and create an array accordingly

We can run any algorithm on the array

​

Finding min,max, sum, avg, Finding conditioned number, etc

#include <iostream>

#include <fstream>

using namespace std;

​

void print_array(int arr[], int N){

for (int i =0; i < N; i++)

cout << arr[i] << endl;

}

​

​

int main (){

fstream fVar;

fVar.open("out.txt",ios::in);

int arr[10000];

int size = 0;

int number;

while (fVar >> number){

arr[size] =number;

size+=1;

}

print_array(arr,size);

fVar.close();

return 0;

}

​

Exercises 1

• file data.txt store several integer numbers.
• Reading number from file data.txt and store in an array
• Then, write to the file output.txt in the structure:
• First number is the number of element N in array
• The next N line is the element in the array

Exercises 1

#include <iostream>

#include <fstream>

using namespace std;

​

int main() {

//read from file

ifstream inputFile("data.txt");

​

int number; // temporary number for ready from file

int arr[1000]; // declare the array with max 1000 elements.

int N = 0; // save the size, also the current index of the array

​

// Read numbers from file and store in array

while (inputFile >> number) {

inputFile >> number; // input to a temporary variable

arr[N] = number; // assign to current element in the array (index N)

N++; // increase the current index (also the size)

}

inputFile.close(); // close file

//writing to file

ofstream outputFile("output.txt");

​

outputFile << N << "\n"; // Write the number of elements

​

for (int i =0; i < N; i++) {

outputFile << arr[i] << "\n"; // Write the array in to file, line by line

}

​

outputFile.close(); // close file

cout << "DONE"; // indicator finish the task

return 0;

}

1 2 3 4

5 6 7 8

10 20 30 40

50 60 70 80 90 100

​

data.txt

9

2

4

6

8

20

40

60

80

100

output.txt

Exercises 2

• file data.txt store value of an integer array, which has N elements
• The first element is number N, the number of elements
• The next N elements is the data for the array
• Reading the data from data.txt and store into an integer array.
• Finding the average value of the array.

Exercises 1

#include <iostream>

#include <fstream>

using namespace std;

​

float calculate_avg (int arr[], int N){

float sum = 0;

for ( int i=0; i < N; i++)

sum += arr[i];

float avg = sum/N;

return avg;

}

​

int main() {

//read from file

ifstream inputFile("output.txt");

​

int number; // temporary number for ready from file

int arr[1000]; // declare the array with max 1000 elements.

int N; // save the size, also the current index of the array

​

// Read numbers from file and store in array

inputFile >> N ; // get the number of elements

for (int i =0; i < N; i++){

inputFile >> number;

arr[i] = number;

}

float avg = calculate_avg(arr,N);

cout <<"AVG of array: " << avg;

return 0;

}

​

​

​

9

2

4

6

8

20

40

60

80

100

output.txt

Function for calculate avg

Reading from the file based on the structure

Exercises 1 (reference)

#include <iostream>

#include <fstream>

using namespace std;

​

​

int reading_file(int arr[]){

ifstream inputFile("output.txt");

​

int number; // temporary number for ready from file

int N; // save the size, also the current index of the array

​

// Read numbers from file and store in array

inputFile >> N ; // get the number of elements

for (int i =0; i < N; i++){

inputFile >> number;

arr[i] = number;

}

return N;

}

​

float calculate_avg (int arr[], int N){

float sum = 0;

for ( int i=0; i < N; i++)

sum += arr[i];

float avg = sum/N;

return avg;

}

​

int main() {

//read from file

int arr[1000];

int N = reading_file(arr);

float avg = calculate_avg(arr,N);

cout <<"AVG of array: " << avg;

return 0;

}

​

​

​

9

2

4

6

8

20

40

60

80

100

output.txt

Function for calculate avg

- Reading from the file based on the structure.

- Arr passing as reference

- Return size of arr

Exercises 3

• file data.txt store value of an integer array, which has N elements
• The first element is number N, the number of elements
• The next N elements is the data for the array
• Reading the data from data.txt and store into an integer array.
• Write function to find min, max, sum, average of the array

Exercises 4

• file data.txt store value of an integer array, which has N elements
• The first element is number N, the number of elements
• The next N elements is the data for the array
• Reading the data from data.txt and store into an integer array.
• Write functions to count number of
• Odd number
• Even number
• Divisible by 5 or 3

Data Structure

​

Good luck to you with this course!

​

Any questions?