Scribd
Upload
6 views6 pages

C Programming: Student Database & Linked List

The document outlines an assignment focused on programming in C, consisting of two main questions. The first question requires creating a student database using structures, where students are sorted by their marks in Physics, Chemistry, and Mathematics. The second question involves implementing operations for a linked list, including creating nodes, appending to the list, searching for nodes, and changing node values.

Uploaded by

summa6summa
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views6 pages

C Programming: Student Database & Linked List

The document outlines an assignment focused on programming in C, consisting of two main questions. The first question requires creating a student database using structures, where students are sorted by their marks in Physics, Chemistry, and Mathematics. The second question involves implementing operations for a linked list, including creating nodes, appending to the list, searching for nodes, and changing node values.

Uploaded by

summa6summa
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment 7

Introduction to programming in C

Question 1
Student Database with Structures
Write a C program that creates a database of students using a struct. Each
student record must contain:
• Name: a string of at most 20 characters (no spaces; input is a single
token).
• Physics marks: an integer in [0, 100].
• Chemistry marks: an integer in [0, 100].
• Mathematics marks: an integer in [0, 100].
The program should:
1. Read the data for n students.
2. Output the list sorted according to:
(a) Higher Physics marks come first.
(b) If Physics marks tie, higher Chemistry marks come first.
(c) If both Physics and Chemistry tie, higher Mathematics marks comes
first.
It is guaranteed that no two students have the same Mathematics mark.

Input Format
• First line: integer n (1 ≤ n ≤ 100).
• Next n lines: name physics chemistry mathematics (space-separated).

Output Format
Print the sorted database in n lines. Each line must be:
name physics chemistry mathematics

1
Constraints
• 1 ≤ n ≤ 100
• Marks are integers in [0, 100]

• Name length ≤ 128 characters

Sample Input
5
alice 90 85 92
bob 90 88 80
charlie 95 70 78
diana 90 85 99
ed 95 65 81

Sample Output
charlie 95 70 78
ed 95 65 81
bob 90 88 80
diana 90 85 99
alice 90 85 92

Solution
1 #i n c l u d e <s t d i o . h>
2 #i n c l u d e < s t r i n g . h>
3 #i n c l u d e < s t d l i b . h>
4
5 s t r u c t Student {
6 c h a r name [ 2 0 ] ;
7 int physics ;
8 int chemistry ;
9 i n t maths ;
10 };
11
12 // comparator f o r q s o r t
13 i n t compare ( c o n s t v o i d ∗a , c o n s t v o i d ∗b ) {
14 s t r u c t Student ∗ s1 = ( s t r u c t Student ∗) a ;
15 s t r u c t Student ∗ s2 = ( s t r u c t Student ∗) b ;
16
17 i f ( s1−>p h y s i c s != s2−>p h y s i c s )
18 r e t u r n ( s2−>p h y s i c s − s1−>p h y s i c s ) ; // h i g h e r p h y s i c s
first
19
20 i f ( s1−>c h e m i s t r y != s2−>c h e m i s t r y )
21 r e t u r n ( s2−>c h e m i s t r y − s1−>c h e m i s t r y ) ; // h i g h e r c h e m i s t r y
first
22
23 r e t u r n ( s2−>maths − s1−>maths ) ; // h i g h e r maths f i r s t

2
24 }
25
26 i n t main ( ) {
27 int n;
28 s c a n f ( ”%d” , &n ) ;
29
30 s t r u c t Student a r r [ 1 0 0 ] ;
31
32 f o r ( i n t i = 0 ; i < n ; i ++) {
33 s c a n f ( ”%s %d %d %d” , a r r [ i ] . name , &a r r [ i ] . p h y s i c s ,
34 &a r r [ i ] . c h e m i s t r y , &a r r [ i ] . maths ) ;
35 }
36
37 q s o r t ( a r r , n , s i z e o f ( s t r u c t S t u d e n t ) , compare ) ;
38
39 f o r ( i n t i = 0 ; i < n ; i ++) {
40 p r i n t f ( ”%s %d %d %d\n” , a r r [ i ] . name ,
41 a r r [ i ] . p h y s i c s , a r r [ i ] . c h e m i s t r y , a r r [ i ] . maths ) ;
42 }
43
44 return 0;
45 }

Question 2
Linked List Operations
In this question, a linked list is partially implemented where each element
in the linked list is a structure of the following format:
s t r u c t node {
int id ;
int priority ;
s t r u c t node ∗ next ;
};
The field priority is a positive integer, which denotes the priority of an
element inside the list.
You have to complete the C code for performing the following operations in
the linked list:

• Create and return a node e with given id and value val


struct node * create node(int id, int val);
• Add an node e to the beginning of the list. Return the new list.
struct node * append(struct node * list, struct node * e);
• Search for a node e with id inside the list. Return a pointer to e if found,
else return NULL.
struct node * search(struct node * list, int id);

3
• Change the value of an element with given id (if found), in the list to the
new value val.
void change priority((struct node *list, int id, int val);

Note: The code for manipulating the input as well as output is given to you.
You only have to write code for the incomplete functions.
Input
A set of lines, each lines containing a character representing the operation
and its inputs.
The operation can be one of the following:
• A < id >< val >
Add an node with id and val to the list, at the start of the list.
• C < id >< val >
Change the value of the element with id to val. If an element with this id
is not found, do nothing.
• S < id >
If an element with the id is in the list print the id and the value and a
newline. Else, print the id and -1 and a newline.
• E
End of input, exit from the program

Output The output of search queries.

Solution
1 #i n c l u d e <s t d i o . h>
2
3 #i n c l u d e < s t d l i b . h>
4
5 s t r u c t node {
6 int id ;
7 int value ;
8 s t r u c t node ∗ n e x t ;
9 };
10
11 s t r u c t node ∗ c r e a t e n o d e ( i n t id , i n t v a l ) {
12 s t r u c t node ∗ new node ;
13 new node = ( s t r u c t node ∗ ) m a l l o c ( s i z e o f ( s t r u c t node ) ) ;
14 new node −> i d = i d ;
15 new node −> v a l u e = v a l ;
16 new node −> n e x t = NULL;
17 r e t u r n new node ;
18 }
19

4
20 s t r u c t node ∗ append ( s t r u c t node ∗ l i s t , s t r u c t node ∗ e ) {
21 i f ( l i s t == NULL)
22 list = e;
23 else {
24 e −> n e x t = l i s t ;
25 }
26 return e ;
27 }
28
29 s t r u c t node ∗ s e a r c h ( s t r u c t node ∗ l i s t , i n t i d ) {
30 w h i l e ( l i s t != NULL) {
31 i f ( l i s t −> i d == i d )
32 return l i s t ;
33 l i s t = l i s t −> n e x t ;
34 }
35 r e t u r n NULL;
36 }
37
38 v o i d c h a n g e v a l u e ( s t r u c t node ∗ l i s t , i n t id , i n t v a l ) {
39 s t r u c t node ∗ e = s e a r c h ( l i s t , i d ) ;
40 i f ( e != NULL)
41 e −> v a l u e = v a l ;
42 }
43
44 i n t f i n d v a l u e ( s t r u c t node ∗ l i s t , i n t i d ) {
45 s t r u c t node ∗ e = s e a r c h ( l i s t , i d ) ;
46 i f ( e != NULL)
47 r e t u r n e −> v a l u e ;
48 r e t u r n −1;
49 }
50
51
52 i n t main ( ) {
53 c h a r op ;
54 i n t id , v a l ;
55 s t r u c t node ∗ l i s t = NULL;
56
57 int flag = 1;
58 do {
59 s c a n f ( ”%c ” , & op ) ;
60 s w i t c h ( op ) {
61 c a s e ’A ’ :
62 s c a n f ( ”%d %d” , & id , & v a l ) ;
63 l i s t = append ( l i s t , c r e a t e n o d e ( id , v a l ) ) ;
64 break ;
65 case ’S ’ :
66 s c a n f ( ”%d” , & i d ) ;
67 p r i n t f ( ”%d %d\n” , id , f i n d v a l u e ( l i s t , i d ) ) ;
68 break ;
69 c a s e ’C ’ :
70 s c a n f ( ”%d %d” , & id , & v a l ) ;
71 c h a n g e v a l u e ( l i s t , id , v a l ) ;
72 break ;
73 c a s e ’E ’ :
74 flag = 0;
75 }
76 } w h i l e ( f l a g == 1 ) ;

5
77 return 0;
78 }

Common questions

Powered by AI

The search function in the linked list uses iteration rather than recursion, traversing nodes starting from the head until the desired id is found or the list ends, which avoids potential stack overflow issues inherent to deep recursion. However, using iteration limits elegance and clarity in smaller codebases compared to the concise nature of recursion, but provides consistency and performance benefits for unbounded list sizes .

The 'next' pointer is initially set to NULL in the create_node function to indicate that the new node is not yet linked to any other nodes and currently is the tail node of the list, representing a single-node list or the start of a new list, which avoids dangling pointer issues and clarifies list termination .

Enhancing the search operation can involve implementing a doubly linked list to traverse backward or using self-balancing trees like AVL or red-black trees to maintain a balanced state for faster searches. Hash tables could also augment searches by providing O(1) average time complexity for lookups, but require extra memory overhead for hash bucket management .

Dynamic memory allocation is used in create_node to allocate memory at runtime for a node, allowing the list to grow as needed without predefined limits, which is crucial for flexibility and efficient memory use . Without dynamic allocation, the program would need pre-allocated memory, potentially wasting space or resulting in overflow if exceeded, limiting the list's scalability and adaptability .

The change_value function in the C linked list program first searches for the node with the given id. If the search function returns NULL, indicating that the node is not found, the function does nothing, effectively handling attempts to change non-existent nodes without altering the list or causing errors .

To append a node to the beginning of a linked list, you first check if the list is NULL. If it is, set the list to the new node. If not, set the new node's next pointer to point to the current head of the list and then update the list to the new node, effectively making it the new head of the list .

The program uses qsort, which is an implementation of the quicksort algorithm, known for its efficient average-case complexity of O(n log n). It is highly adaptive for in-memory sorting due to its divide-and-conquer approach, offering faster partition choices and fewer swaps compared to select or bubble sorts, making it suitable for sorting multiple fields of student records efficiently .

The change_priority function performs no operations when the search for a node with the specified id returns NULL, meaning no node with that id was found in the list. This condition prevents unnecessary operations on non-existent nodes, avoiding errors and maintaining the integrity of the list's existing data .

The comparator function ensures that students are sorted by first comparing the physics marks, returning the difference in marks in descending order so higher marks come first . If the physics marks are equal, it next compares the chemistry marks, again sorting in descending order. If both physics and chemistry marks are the same, it finally uses the mathematics marks to differentiate the students, which is guaranteed to be unique .

The sorting criteria rely on a multi-level comparison: physics marks first, chemistry second, and mathematics third, which ensures that ties in higher levels are broken by higher levels of precision in the next subject mark. This layered approach efficiently differentiates students using a stable tie-breaking order and sorts them distinctly even when marks tie at multiple levels, leveraging the guarantee of unique mathematics marks to maintain order .

You might also like