Lab 02: Self-referential Structures in C

To understand and demonstrate the use of pointers to structures in C programming by constructing and executing a simple C program. This lab will help students grasp how pointers can be used to reference and manipulate data within structures.

Instructions

Repo

Go to s-m-quadri/geca-labs repository.
Switch branch to CSPC2005/02 corresponding to current lab.
Click on CODE, then Codespaces, then Create, to setup in-browser IDE.
Wait until VS Code gets open.
Write program from scratch, compile, execute. Then only tally with already available solution.
IMP: Make sure to delete after completion of lab. Otherwise your monthly free-hours limit can exhaust. It can be achieved by:
1. Closing in-browser VS Code tab.
2. Click on CODE, then Codespaces, then Delete, to delete virtual space.

Here’s a comprehensive lab guide for implementing a C program using self-referential structures.

To understand the concept of self-referential structures in C. To learn how to create and manipulate linked structures. To implement a simple program using a self-referential structure to manage a list of items.

1. Define the Self-Referential Structure

Create a self-referential structure. A typical example is a linked list node.


struct Node {
    int data;          // Data part
    struct Node* next; // Pointer to the next node
};

2. Create Functions

Implement the following functions:

Create a new node:
- This function will allocate memory for a new node and set its data.


struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Insert a node at the end:
- This function will insert a new node at the end of the linked list.


void insertEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

Display the list:
- This function will print all the nodes in the linked list.


void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

3. Main Function

Implement the main() function to test your self-referential structure.


int main() {
    struct Node* head = NULL;
 
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
 
    printf("Linked List: ");
    displayList(head);
 
    return 0;
}

4. Compile and Run

Save your program as self_ref_struct.c.
Open the terminal and navigate to the directory where your file is located.

Compile the program using the command:


gcc self_ref_struct.c -o self_ref_struct

Run the program:
```
./self_ref_struct
```

Expected Output

When you run the program, you should see the following output:


Linked List: 10 -> 20 -> 30 -> NULL

Explanation

Self-Referential Structure: The Node structure contains a pointer to another Node, allowing the creation of linked lists.
Dynamic Memory Allocation: Memory for nodes is allocated dynamically using malloc().
Insertion and Traversal: The program demonstrates how to insert nodes into a linked list and how to traverse it to display its contents.

Spoiler (Full Source Code)

Here’s the complete source code for the lab:

(Full source code) Do not copy-paste


#include <stdio.h>
#include <stdlib.h>
 
// Self-referential structure
struct Node {
    int data;          // Data part
    struct Node* next; // Pointer to the next node
};
 
// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// Function to insert a new node at the end
void insertEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}
 
// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
 
// Main function
int main() {
    struct Node* head = NULL;
 
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
 
    printf("Linked List: ");
    displayList(head);
 
    return 0;
}

Conclusion

In this lab, you learned about self-referential structures in C, specifically how to implement a simple linked list. This concept is fundamental in data structures and allows for dynamic memory management.

Key Takeaways

Self-referential structures are useful for creating complex data types like linked lists.
Memory management is crucial when dealing with dynamic structures in C.
Functions can be used to modularize code for better readability and maintainability.

Exercises

Modify the program to include a function that deletes a node from the linked list.
Implement a function to reverse the linked list.
Create a program using a self-referential structure to implement a stack.

References

“The C Programming Language” by Brian W. Kernighan and Dennis M. Ritchie.
C programming documentation: cplusplus.com .
Online resources on linked lists and data structures.

💡