Homework 6

Introduction

Before you begin, be sure to review the lecture slides on the topics of structures and linked lists and review the Starter Code

Comparing Two Strings

In one of the programs to write for this homework, you will need to compare two strings to see whether they are identical. While this can be done by comparing character-by-character, a more convenient way is to call a C standard function named strcmp(), which performs exactly such character-by-character comparison. The prototype of this standard function is shown below.

int strcmp(const char *s1, const char *s2);

The strcmp() function compares the lexicographical order between two strings, *s1 and *s2. The return value is determined as follows.

•return negative integer if *s1 < *s2

•return positive integer  if *s1 > *s2

•return 0 if *s1 and *s2 are identical

Homework Requirement and Tasks

Program 1: Creating and sorting a linked list

DESCRIPTION

You are provided a source file, named main1.c, that contains the main() function. The main() function imports from the command line a sequence of pairs of integers  (int1, int2) and store each pair in a struct node, whose type is defined as follow:

typedef struct Pair {
  int num_1, num_2;  // a pair of numbers
  struct Pair *next;
}  Linked_Pair;

The main() function creates a linked list (not necessarily sorted) that links a number of such nodes together. You should read all the statements in main1.c that are involved in defining and creating such a linked list.

The main() function makes a call to a function named sort_sum() whose prototype is shown below:

struct Sum *sort_sum(Linked_Pair *);

The formal parameter is a pointer to the beginning node of the linked list created by the main() function as mentioned above. The return value is a pointer to another structure type, named Sum, that is defined below:

struct Sum {
  int sum; 
  struct Sum *next;
}

The declaration and typedef statements listed above are found in a header file named sort_sum.h, which is also provided to you.

Your task is the following:

Write another source file named sort_sum.c that will be compiled and linked with main1.o to produce the executable file. Inside sort_sum.c, you are to implement the function sort_sum() such that it traverse the linked list accessed from the input parameter and adds the pair of numbers in each node.

The function should then dynamically allocate a struct Sum node for each sum that you have computed and link all such sums in a sorted list, such that the sum decreases from the beginning node to the ending node.

After the construction of such a sorted linked list of sums, return the pointer to its beginning node. (The main() function uses this pointer to print out the sums, which you can inspect to ensure your implementation is correct.)

Program 2: Removing Redundant Nodes in a List

DESCRIPTION

You are provided a source file, named main2.c, that contains the main() function. The main() function imports from the command line a sequence of pairs (integer, name) and store each pair in a struct node, whose type is defined as follow:

typedef struct Student {
  int grade; 
  char *name;
  struct Student *next;
}  Student_Record;

The main() function creates a linked list (not necessarily sorted) that links a number of such nodes together. You should read all the statements in main2.c that are involved in defining and creating such a linked list.

The main() function makes a call to a function named remove_redundant() whose prototype is shown below:

Student_Record *remove_redundant(Student_Record *);

The formal parameter is a pointer to the beginning node of the linked list created by the main() function as mentioned above.

The declaration and typedef statements listed above are found in a header file named remove_redundant.h, which is also provided to you. You should read carefully all statements in this header file in order to make sure.

Your task is the following:

Write another source file named remove_redundant.c, that will be compiled and linked with main2.o to produce the executable file. Inside remove_redundant.c, you are to implement the function remove_redundant() such that it traverse the linked list accessed from the input parameter, from the beginning node to the end, and remove any node whose name field is a string identical to one in an earlier node. (NOTE: We remove such a redundant node even if the grade field is nonidentical to the earlier node whose name field is the same.)

After you remove a redundant node, make sure you update the links such that the remaining nodes still form a linked list in the original order.

After all redundant nodes are removed, return the pointer to the beginning node of the remaining linked list. (The main() function uses this pointer to print out the nodes, which you can inspect to ensure your implementation is correct.)

We will assume the number of pairs passed in as arguments varies from 1 to 100.

Testing

The starter code provides you a makefile for producing both versions of the executable file. Type "make" to generate two executable files, one named sort_sum, and the other named remove_redundant. You can also generate the executables individually: typing "make sort_sum" only compiles sort_sum, and "make remove_redundant" only compiles remove_redundant.

To test your programs, use something like the following:

./sort_sum "(12, 30) (24, 7) (8, 19)"
./remove_redundant "(80, Bob) (30, Allison) (60, Bob)"

Note that the quotes are needed so that Bash understands we are simply inputting strings, not special commands.

Submit

Now that the program is in working order, we can submit it using the Submit button on Vocareum. Make sure the following files are included:

  • sort_sum.c
  • remove_redundant.c

You are also welcome to submit the files you created in the introduction of the assignment, though they will not be graded.