Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
UESTC (HN) 1005
Introductory Programming Lab Manual
Lab Session IV
1.1 Structure
Structures (or structs) in C allow grouping multiple related variables under a single identifier or simply a name. These variables, referred to as “members” of a struct, can be of different data types, making structures incredibly useful for modelling real-world entities and creating more complex data types. In this tutorial, we will explore how to define and use structures in C, unlocking their potential to simplify and organise your code.
Let’s start by defining a simple structure to represent a student.
Code 1.1: student.c
1 struct Student {
2 int id;
3 char name[50];
4 float gpa;
5 };
In the Student structure, id represents the student’s ID, name stores the student’s name as a string, and gpa stores the student’s GPA (grade point average).
Next, we implement functions to perform basic operations on a Student structure, such as creating an instance of it (i.e., a new student) and printing this new student’s details.
Code 1.2: testStudent.c
1 #include <stdio.h>
2 #include <string.h>
3
4 // Define the structure
5 struct Student {
6 int id;
7 char name[50];
8 float gpa;
9 };
10
11 // Function to create a new student
12 struct Student createStudent(int id, const char* name, float gpa) {
13 struct Student s;
14 s.id = id;
15 strcpy(s.name, name);
16 s.gpa = gpa;
17 return s;
18 }
19
20 // Function to print student details
21 void printStudent(struct Student s) {
22 printf("Student ID: %d\n", s.id);
23 printf("Name: %s\n", s.name);
24 printf("GPA: %.2f\n", s.gpa);
25 }
26
27 int main() {
28 // Create a new student
29 struct Student s1 = createStudent(1, "John Doe", 3.8);
30
31 // Print the student's details
32 printf("Student Details:\n");
33 printStudent(s1);
34
35 return 0;
36 }
1.2 Sort
This section will introduce a classic sort algorithm: bubble sort. Bubble sort is a simple sorting algorithm that repeatedly traverses the list, comparing adjacent elements and swapping them if they are out of order. This process continues until the entire list is sorted. The algorithm gets its name because smaller elements gradually “bubble” up to the beginning of the list (or, equiva lently, larger elements “sink” to the end) with each pass. Code 1.3 is an example implementation of bubble sort in C.
Code 1.3: bubbleSort.c
1 // File name: bubbleSort.c
2 // Function to perform Bubble Sort
3 void bubbleSort(int arr[], int n) {
4 int i, j;
5 for (i = 0; i < n-1; i++) {
6 // Last i elements are already in place
7 for (j = 0; j < n-i-1; j++) {
8 if (arr[j] > arr[j+1]) {
9 // Swap arr[j] and arr[j+1]
10 int temp = arr[j];
11 arr[j] = arr[j+1];
12 arr[j+1] = temp;
13 }
14 }
15 }
16 }
Other sort algorithms exist besides bubble sort, including merge sort and quicksort. Different sort algorithms have different performance and code complexity trade-offs. The C standard library comes with an implementation of the quicksort algorithm with the function qsort and is provided as part of stdlib.h. However, you are NOT allowed to use this function to complete the lab exercises.
1.2.1 Exercise 4A
4A - Who Won the Kelvin Bicentenary Programming Competition
Time limit per test: 1 second
Problme Statement
Glasgow College held the Kelvin Bicentenary Programming Competition at the end of November. As part of the challenge, n participants submitted their programs to control a robot to achieve the highest score possible.
The final ranking is based on two main metrics: the score s and the time t spent solving the task. Each robot’s performance is evaluated as follows:
-
s: The final score the participant’s program achieved, representing how well it performed the task (higher means better).
-
t: The time that the participant submit their programs (earlier means better). The competition begins at 14:00.
The ranking criteria are three-fold:
1. The participants are first sorted by s in descending order.
2. If two participants have the same score s, they are then sorted by t in ascending order.
3. If two participants have the same score s and the same time t, they are then sorted by their name in lexicographic order.
Your program is required to input the name, score s, and time t for each participant. The program should then sort the participants following the ranking criteria and output the final ranking of participants by their names only.
Constraint
-
For 20% of test cases, n ≤ 100; For 60% of test cases, n ≤ 300; For 100% of test cases, n ≤ 1000.
-
10000 ≤ s ≤ 200000, 14:00 ≤ t ≤ 17:00.
-
You are NOT allowed to use qsort function to complete the lab exercises. This will be detected in the structure test. If you fail to pass the structure test, the logic test will not be executed.
Input
The input contains n + 1 lines.
-
The first line contains an integer n which represents the number of participants.
-
Each of the following n lines contains a string (the participant’s name) and an integer s and a time t (representing the score and time for that participant).
Output
Print the names of the participants in the final ranking order, one name per line.
Sample Input
5
Alice 74,287 16:16
Bob 74,287 16:43
Charlie 13,864 15:00
David 13,864 15:00
Eve 79,874 16:15
Sample Output
Eve
Alice
Bob
Charlie
David
Explanation
Recall the ranking criteria: participants are first sorted by their score s in descending order. If two participants have the same score, they are sorted by their time t in ascending order. If two participants have the same score and time, they are sorted by their name.
-
Alice and Bob both have a score of 74, 287, but Alice ranks higher because he took less time (as 16:16 < 16:43 ).
-
David and Charlie both have a score of 13, 864 and the same time 15:00, but Charlie ranks higher because his name ranks higher in the lexicographic order.
-
Eve ranks first with the highest score of 79, 874 (so her time does not need to be considered).
Base Code
#include <stdio.h>
//define your structure here
struct {
} Record;
int main() {
return 0;
5Handout 4
UESTC 1005 - Introductory Programming
}
1.3 Linked List
A linked lists is a fundamental data structure in computer science and is valued for its dynamic nature and pointer-based implementation. While not always the most efficient option, linked lists are commonly used in various scenarios requiring flexible memory management.
In this section, we will familiarise you with this data structure by implementing a simple linked list in C, starting with defining the structure for a node in the linked list.
Code 1.4: node.c
1 struct Node {
2 int data;
3 struct Node* next;
4 };
In the Node structure, data represents the value stored in the node and next is a pointer to the next node in the list.
Next, let’s implement functions to perform basic operations on a linked list, such as creating a new node, inserting a node at the beginning, and printing the list. In other words, let us define an interface for interacting with the linked list data structure.
Code 1.5: linkedList.c
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 struct Node* createNode(int data) {
5 struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
6 newNode->data = data;
7 newNode->next = NULL;
8 return newNode;
9 }
10
11 void insertAtBeginning(struct Node** head, int data) {
12 struct Node* newNode = createNode(data);
13 newNode->next = *head;
14 *head = newNode;
15 }
16
17 void printList(struct Node* head) {
18 while (head != NULL) {
19 printf("%d -> ", head->data);
20 head = head->next;
21 }
22 printf("NULL\n");
23 }
24
25 int main() {
26 struct Node* head = NULL;
27
28 insertAtBeginning(&head, 3);
29 insertAtBeginning(&head, 2);
30 insertAtBeginning(&head, 1);
31
32 printf("Linked List: ");
33 printList(head);
34
35 return 0;
36 }
1.3.1 Exercise 4B
4B - Counting Linked List Nodes
Time limit per test: 1 second
Problem Statement
Given a string representation of a linked list, your task is to implement a function that counts the number of nodes in the list. If the list contains a cycle, detect the cycle and avoid counting the nodes within the cycle more than once.
Each node in the linked list has the following structure: (The implementation has been provided in the base code.)
-
An integer value. (Two distinct nodes can have the same value.)
-
A pointer to the next node, or NULL if it is the last node. (If there is a cycle, then there is no NULL.)
You are required to implement the function that calculates the total number of unique nodes in the list.
Constraints
For 50% of the test cases, there is no cycle in the linked list. For 50% of the test cases, there is a cycle in the linked list.
Virtual Input
You do not need to implement a function to input a linked list from the user in this assign ment. Instead, you are asked to complete the implementation of the Count function which counts the number of linked list nodes, with cycle detection, given the input Node* head, i.e., a linked list constructed with Nodes as defined in the exercise template. Each example sample input given below is “virtual input,” meaning it is a text-based representation of the linked list structure.
Output
Print the total number of unique nodes in the linked list.
Sample Virtual Input 1
1 -> 2 -> 3 -> 4 -> 5 -> NULL
Sample Output 1
5
Sample Virtual Input 2
1 -> 2 -> 3 -> 4 -> 5 -> 2
Sample Output 2
5
Explanation
For sample 1, if the list does not contain a cycle, simply count all nodes normally.
For sample 2, the linked list contains 5 unique nodes, including nodes within the cycle. Even if there is a cycle in the list, the cycle nodes should be counted only once.
Base Code
#include "4B.h" // please do not delete this line when you submit
/*
The structure for the linked list node:
typedef struct Node {
int data; // Node data
struct Node* next; // Pointer to the next node
} Node;
*/
int Count(Node* head) {
// implement your solution here
// you can output the linked list use the function printList()
printList(head); // Please delete this line when you submit
}
1.4 File Handling in C
File handling in C allows you to read from and write to files. The standard library provides functions for opening, reading, writing, and closing files. We detail some of the basic steps involved below.
1.4.1 Opening a File
In C, you can open a file using the fopen function, which requires two arguments: the name of the file and the mode in which the file should be opened. The available modes are:
-
r: Open a file for reading. The file must exist.
-
w: Open a file for writing. If the file exists, it is truncated; if it does not exist, a new file is created.
-
a: Open a file for appending. If the file does not exist, it is created.
-
rb, wb, ab: Binary modes for reading, writing, and appending, respectively.
Code 1.6: file.c
1 #include <stdio.h>
2
3 int main(){
4 FILE *file;
5
6 file = fopen("./example.txt", "w");
7
8 //Write to the file if the file exists
9 if (file != NULL) {
10 fprintf(file, "Hello, World!\n");
11 }
12
13 fclose(file);
14
15 return 0;
16 }
1.4.2 Exercise 4C
4C - Pixel Frequency
Time limit per test: 1 seconds
Problem Statement
In digital imaging, an image is composed of a grid of small units called pixels (short for “picture elements”). Each pixel represents the smallest possible piece of the image and contains information about its colour or brightness. Pixels are typically represented using colour models likeRGB, where each colour component (red, green, or blue) is assigned a value, often in the rangeof 0 to 255. These values can be represented in hexadecimal format, where two hexadecimaldigits (ranging from 00 to FF) represent the colour value of a pixel.
In this exercise, you are given a text file containing an image. Each pixel in the image isrepresented by a two-digit hexadecimal number (from 00 to FF). Your task is to read the pixeldata from the file, count the frequency of each pixel value, and output the pixel values with thehighest frequency into another file.
Constraints:
• 1 ≤ w, h ≤ 256 (width and height of the image).
• The pixel values range from 00 to FF.
Input
The input of your program is the name of a file. This file consists of h lines each contain w two-digit hexadecimal numbers, representing the pixel values of the image. Each pixel value is a 2-character hexadecimal number in the range 00 to FF.
Output
Output the pixel value with the highest frequency and its frequency to another file named output.txt. In the case of a tie, i.e., two or more pixel values appear with the same highest frequency in the image, only output the pixel value with the lowest value. If you are given n files, the content of output.txt should be n lines, i.e., run your program n times, once for each input file, and append the output to output.txt.
Sample input 1
image0.txt
The content of image0.txt:
77C0AA6A307134EAFBF9
86E6CDB3887DC9B8E711
12157D28AA6AEE018E73
5C0533066F6377A44D72
9DD3596B86E1E84F99CF
61ACE5DED48F48C390D7
36ECDC69F24CCC69F019
DB8DEC34F87216E0C2AF
B0235B950130244AF3B4
2129A0FD9292495EFB39
Sample Output — “output.txt”
01 2
Although both the pixel value 01 and AA appear 2 times, 01 is smaller than AA. After your program runs with the input of the filename image0.txt, the result should be stored in the file output.txt. When your program runs on the second test case, the results should be appended to the file instead of replacing the existing file.
Sample input 2
image1.txt
The content of image1.txt:
53AABF9E7A025A432C371B784DFF5C6ED836E4AC
06E37DCAE55833E1DC66D62F1195CE8B9828CEC4
5FE93CACE9981AC1CEFE6DD5E1EB9FC643D2A71F
397E4F4A131DD5AB45A36FA48DAB5176446B3712
6AA4E74B8F8712D259B9F2923741DC4B5EB1F6A3
556647E211985855048F686E334FB9C3D6CB9530
8587C2BCC89F072650FEC9A564118775A9DFCBAD
6E331BA282D56559A0FA8925824BE24AEAE9713B
E73AE04B4B68C1F5478CA2B6BFBE584193BD9A33
B72359396F3B845924F5940C2F75577BDD187024
A412DA63D032A563EF3F97A763F0E0D22B642B4F
59C05B8935B30412CB7436708611D3574378BA33
B851DA1B41BAED6C1F18BC78D817010DCA051F96
7956060067D957AA5211DD0A63B725A472121191
2ACD0903E40B10AF1030458A864B8AED24E19776
F27580552CA5FA9EB70B2FE2D839E5BC44F56B54
25B0DEABFB6898204930963CA51791D1BC8B7074
969F566ED83B2B1C30967156474F0142B89A6201
CAF93D6F10CF40CC5AB040F150965F28D18A4502
21B658680559AABDF30DBFBD06FC2C16CB6DE226
Sample Output — “output.txt”
01 2
11 6
Note that the second program output has been appended to output.txt.
Test Environment
Assume that your program is named 4C.c, you can put 4C.c, image0.txt and image1.txt in the same directory. And then run your program 4C.c twice. For the first time, input image0.txt, and, for the second time, input image1.txt. Finally, you can check whether your output.txt is same as the content above.
When you submit your program, you may discore 11 IO Tests in the logic test. Please notice that IO Test 1-10 are not graded. (This means whether these tests are passed or failed will not affect your grade.) Only ”IO Test - Grade” checks whether you output the correct file.
Base Code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char filename[20];
scanf("%s", filename);
return 0;
}