CptS 122 – Data Structures

Lab 3: Data Structures and Dynamic Linked Lists in C

Assigned: Week of September 10, 2012

Due: At the end of the lab session

I. Learner Objectives:

At the conclusion of this programming assignment, participants should be able to:

• Design, implement and test a dynamic linked list in C

II. Prerequisites:

Before starting this programming assignment, participants should be able to:

• Analyze a basic set of requirements for a problem
• Compose a small C language program
• Compile a C program using Microsoft Visual Studio 2008
• Create test cases for a program
• Apply and implement arrays and strings in C
• Apply and implement recursion in C
• Apply and implement structs in C
• Apply and implement pointers in C
• Apply and implement dynamic memory in C

III. Overview & Requirements:

This lab, along with your TA, will help you navigate through designing, implementing, and testing a dynamic linked list. For this project you must create at least one header file (.h) and two source files (.c).

Labs are held in a “closed” environment such that you may ask your TA questions. Please use your TAs knowledge to your advantage. You are required to move at the pace set forth by your TA. Please help other students in need when you are finished with a task. You may work in pairs if you wish. However, I encourage you to compose your own solution to each problem. Have a great time! Labs are a vital part to your education in CptS 122 so work diligently.

Tasks:

Linked lists may be used to implement many real world applications. Recall, linked lists are data structures, which represent collections of nodes that may be accessed sequentially via a pointer to the first node. A node contains data and a pointer to the next node in sequence. When the last node in the list is reached, its next pointer is NULL. A logical view of a linked list of integers is illustrated below:

Write a C program for merging two linked lists of integers. Consider you have two linked lists pointed to by two independent pointers and you wish to merge the two lists into a third sorted list. While carrying out this merging ensure that those elements which are common to both the lists occur only once in the third list. Assume that within a list all the elements are unique. 

1. In this program as usual you can begin by building a structure to accommodate the data and link which together represent a node. You can use pointers first, second and third to point to the three linked lists. Begin with three empty linked lists and initialize these pointers to NULL.  Write a function addNode() and call it repeatedly to build two linked lists, one being pointed to by first and other by the pointer second. Finally, write a mergeNode() function and call it to merge the two lists into one. This merged list is pointed to by the pointer third. While merging the two lists make sure that the lists themselves are in ascending order. While building the two lists the addNode() function makes sure that when a node is added the elements in the lists are maintained in ascending order. While merging the two lists the mergeNode() functions accounts for the possibility of any of the two lists being empty. 

You can have the following function prototypes to implement this. 

/*adds node to an ascending order linked list*/
addNode (struct node **q, int num)

/*displays the contents of the linked list*/
display (struct node *q)

/*counts the number of nodes present in the linked list*/
count (struct node *q)

/*merges the two linked lists, restricting the common elements to occur only once in the final list*/
mergeNode (struct node *p, struct node *q, struct node **s)

2. In the same project, create one source file main.c. In main.c you can have the following codes.

//Declare the three pointers first, second and third

//Initialize those pointers to NULL

//Call addNode() function multiple times to build linked list 1

printf("First Linked List: "); 

display (first); 

printf ("\n No. of Elements in First Linked List: %d", count(first));

//Call addNode() function multiple times to build linked list 2

printf("\n\n Second Linked List: "); 

display (second); 

printf ("\n No. of Elements in First Linked List: %d", count(second));

//Call mergeNode() function to merge two linked lists

printf("The concatenated list: "); 

display (third); 

printf ("\n No. of Elements in Merged Linked List: %d", count(third));

IV. Submitting Labs:

• You are not required to submit your lab solutions. However, you should keep them in a folder that you may continue to access throughout the semester. You should not store your solutions to the local C: drive on the Sloan 353 machines. These files are erased on a daily basis.

V. Grading Guidelines:

• This lab is worth 100 points. Your lab grade is assigned based on completeness and effort. To receive full credit for the lab you must show up on time and continue to work on the problems and complete all the problems until the TA has dismissed you.