Lab 08 - Selected topics from previous lectures

Compile and run the following program. Observe its output and think carefully about why the addresses and values appear as they do.

#include <stdio.h>
 
int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};
    int *p = arr;
 
    printf("Array variable (arr):        %p\n", (void*)arr);
    printf("Address of first element:    %p\n", (void*)&arr[0]);
    printf("Pointer variable (p):        %p\n", (void*)p);
    printf("Address of pointer variable: %p\n", (void*)&p);
 
    printf("\n--- Elements and addresses ---\n");
    for (int i = 0; i < 5; i++) {
        printf("arr[%d] = %d, address = %p\n", i, arr[i], (void*)&arr[i]);
    }
 
    printf("\n--- Pointer arithmetic ---\n");
    for (int i = 0; i < 5; i++) {
        printf("*(p + %d) = %d, address = %p\n", i, *(p + i), (void*)(p + i));
    }
 
    return 0;
}

Complete the program below so that it swaps the values of two integers using pointers. Compile, run, and verify that the values are actually swapped.

#include <stdio.h>
 
void swap(??? a, ??? b);
 
int main(void) {
    int x = 10;
    int y = 20;
 
    printf("Before swap: x = %d, y = %d\n", x, y);
 
    // Call the swap function
    swap(??? , ???);
 
    printf("After swap:  x = %d, y = %d\n", x, y);
 
    return 0;
}
 
// Implement this function
void swap(??? a, ??? b) {
    // Your code here
}

In this lab, you will explore linked lists, pointers, stack vs heap allocation, and basic dynamic memory management.

#include <stdio.h>
#include <stdlib.h>
 
// Node structure
typedef struct Node {
    int value;
    struct Node *next;
} Node;
 
void traverse(Node *head);
 
// Step 1: Create three stack-allocated nodes
Node* create_list_stack(void) {
    Node n1 = {10, NULL};
    Node n2 = {20, NULL};
    Node n3 = {30, NULL};
 
    n1.next = &n2; // n1 is head
    n2.next = &n3;
    n3.next = NULL;
 
    // TODO: Call traverse function to print list
    // traverse(???);
 
    return &n1; // returning pointer to stack-allocated node (unsafe!)
}
 
// Step 2: Traverse function prototype
void traverse(Node *head) {
    // TODO: Implement traversal using a pointer
}
 
// Step 3: Create three heap-allocated nodes
Node* create_list_heap(void) {
    // TODO: Use malloc to create three nodes
    //Node *n1 = ???;
    //Node *n2 = ???;
    //Node *n3 = ???;
 
    // TODO: Assign values and link nodes
 
    // TODO: Return head of the list
    return NULL;
}
 
// Step 4: Insert a new node after a node with given value
void insert_node(Node *head, int value, int after_value) {
    // TODO: Allocate new node using malloc
    //Node *new_node = ???;
 
    // TODO: Find node with after_value
    //Node *current = ???;
 
    // TODO: Insert new_node after current node
    //???;
}
 
// Step 5: Delete a node by value
void delete_node(Node **head_ref, int value) {
    // TODO: Find node to delete
    //Node *current = ???;
    //Node *prev = ???;
 
    // TODO: Update pointers to remove node from list
    //???;
 
    // TODO: Free deleted node
    //???;
}
 
// Step 6: Main function to test everything
int main(void) {
    // Step 1: Test stack-based list
    Node *head_stack = create_list_stack();
    // TODO: Call traverse and observe failure
    // traverse(head_stack);
 
    // Step 2: Test heap-based list
    //Node *head = create_list_heap();
    //traverse(head);
 
    // Step 3: Insert a new node (value 15 after 10)
    //insert_node(head, 15, 10);
    //traverse(head);
 
    // Step 4: Delete node with value 20
    //delete_node(&head, 20);
    //traverse(head);
 
    // Step 5: Free remaining nodes
    // free all heap-allocated nodes
 
    return 0;
}

1. Traversal
   • Implement a function

     void traverse(Node *head)

     that traverses the linked list and prints all node values using a pointer.
2. Heap Allocation
   • Implement a function

     Node * create_list_heap()

     that creates three nodes on the heap using malloc.
   • Link the nodes and return a pointer to the head.
   • Call traverse() to verify the list prints correctly.
3. Insertion
   • Implement a function

     void insert_node(Node *head, int value, int after_value)

     that inserts a new node after a node with the given value.
   • Test insertion by adding a node with value 15 after the node with value 10.
   • Call traverse() to verify the list.
4. Deletion
   • Implement a function

     void delete_node(Node **head_ref, int value)

     that deletes a node with the given value.
   • Pass a pointer to the head pointer to handle deleting the first node if needed.
   • Test deletion by removing the node with value 20.
   • Call traverse() to verify the list.
5. Testing
   • Call all functions from main() and observe that the linked list operations work as expected.
   • Free all heap-allocated memory when done.