Lab – 9 Dynamic Data Structures

60-141 – Introduction to Programming II
Objective: In this Lab you will practice implementing and using dynamically allocated data structures.
Background:.
The problem of not having enough space to store data, or wasting space by having too much of it using a static data structure (such as an array), can be overcome easily by using dynamic data structures that can grow or shrink in size at run time.
A linked-list is a simple dynamic data structure that is based on self-referential C structures. In this lab you will use such a self-referential structure Student, as defined below, to implement and manipulate a simple linked-list called SLIST.
struct student {
int ID;
char name[40];
struct student *next;
};
typedef struct student Student;
Work to do:
You are going to define the following functions (at a minimum – you may design and define additional functions if you find it useful):
1. Student *addToList(Student *SLIST);
– “addToList” will ask for the ID and name of a new student from the user, dynamically create a new Student structure, assign the values for the members, add the new student structure at the END of the student list “SLIST” and return the modified list.
2. void printList(Student *SLIST);
– “printList” will traverse through the list from the beginning to the end and will print info for each student in the format “ID Name\n”.
3. void printListRR(Student *SLIST);
– “printListRR” will print the list, RECURSIVELY, starting from the END of the list, in the format “ID Name\n”.
4. void searchList(Student *SLIST);
– “searchList” will ask the user to enter a student’s ID, search the list for the student having that ID and will print the data in the format “ID Name\n”. If failed, it will print “ID “ID” not found”.
For your convenience, a partial program (Lab9_W2017.c) with the function prototypes and the main() function with a menu option is given. Document the whole program and define the other functions required, as stated above.
It should be noted that this exercise illustrates simple aspects of a more general problem called
Resource Management. For a single computer running under a single operating system, the
programming required to manage dynamic allocation and recovery of memory resources is a
challenging problem. Scaling the problem upwards to distributed resource sets under shared
ownership and control (e.g. grid, cloud computing) introduces huge and challenging problems for
research and businesses alike.
Summary of the lab requirements: You must write one program for this lab, namely Lab9.c.
The program must contain definitions of the four functions specified above (as a minimum –
you may have more functions). Be prepared to demonstrate the program with appropriate test
input examples.

Answer:

/*
Title: Lab #9: Dynamic Data Structure
Objective: This program uses a simple dynamic data structure that based on self-referential
structure Student to implement and manipulate a simple linked-list call SLIST
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct student {
   int ID;
   char name[40];
   struct student *next;
};
typedef struct student Student;

int getChoice();
Student *addToList(Student *List);//This function is used to create a new Student structure, assign the values
void printList(Student *List);//This function is used to traverse through the list from the beginning to the end
void printListRR(Student *List);//This function is used to print the list recursively starting from the END of the list
void searchList(Student *List);//This function is used to search the list for the student having that ID

int main() {
    int choice = 0;
    Student *SLIST = NULL;

    choice = getChoice();

    while(choice >= 0) {
        switch(choice) {
            case 0 : printf("Bye...\n"); exit(0);
            case 1 : SLIST = addToList(SLIST); break;
            case 2 : printList(SLIST); break;
            case 3 : printListRR(SLIST); break;
            case 4 : searchList(SLIST); break;
            default: printf("That is not a valid choice\n");
        }
        choice = getChoice();
    }

    if(SLIST) free(SLIST);
    return 0;
}

int getChoice() {
    int choice = 0;

    printf("\n****** MENU ******\n");
    printf("1. Add new student to list.\n");
    printf("2. Print the student list, beginning to end.\n");
    printf("3. Recursively print the student list from the end.\n");
    printf("4. Search the list for a student.\n");
    printf("0. Quit.\n");
    printf("\nEnter your choice: ");
    scanf("%d", &choice);

    return choice;
}

/*
Objective: This function is used to create a new Student structure, assign the values
for the members and add the new student structure at the end of the student list
Input: Student's ID and name
Output: Return the modified list
*/
Student *addToList(Student *List) {
	Student *stdPtr = (Student *) malloc(sizeof(Student));
	 printf("Please enter student's ID number: ");
    scanf("%d",&(stdPtr->ID));
    printf("Please enter student's name: ");
    scanf(" %[^\n]",stdPtr->name);

    if (List == '\0') 
		return stdPtr;
    Student *pStudent = List;

    while(pStudent->next != '\0')
        pStudent = pStudent->next;
    pStudent->next = stdPtr;
	
    return List;
}

/*
Objective: This function is used to traverse through the list from the beginning to the end
Input: Student's list
Output: Print info for each student in the format "ID Name\n"
*/
void printList(Student *List) {
    while(List != '\0'){
		printf("student id: %d, name: %s\n", List -> ID, List -> name);
		List = List -> next;
	}
}

/*
Objective: This function is used to print the list recursively starting from the END of the list
Input: Student's list
Output: Print info for each student in the format "ID Name\n"
*/
void printListRR(Student *List) {
    if(List == '\0') return;
    printListRR(List->next);
   printf("student id: %d, name: %s\n", List -> ID, List -> name);
}

/*
Objective: This function is used to search the list for the student having that ID
Input: Student's ID
Output: Print info of the list in the format "ID Name\n" if failed it will print "ID "ID" not found"
*/
void searchList(Student *List) {
    int sid;
    printf("Please enter student's ID number: ");
    scanf("%d", &sid);

    while(List != '\0') {
        if(List->ID == sid){
           printf("student id: %d, name: %s\n", List -> ID, List -> name);
            return;
        }
        List = List->next;
    }
    printf("Can not find ID %d ", sid);
}