Homework Assignment #7 Course: COP 3223C – Intro to Programming with C Semester:
ID: 3711012 • Letter: H
Question
Homework Assignment #7 Course: COP 3223C – Intro to Programming with C Semester: Spring 2018 Credit Value: 4% of Final Grade Due Date: April 23, 2018; 2:59 PM Linked lists, Searching and Sorting This assignment involves two different and independent programs: The first program (Program A) will (must) build, print and search a linked list. The second program (Program B) will (must) build, print and sort a contiguous list (it is easier to sort a contiguous list than a linked list). A. Write a program (Program A) that creates a linked list of 100 nodes, each containing a random positive integer between 0 and 99. The program must provide the user with four choices: Build the list; Print out the list; Search the list; and Quit. Hint: Use a switch structure in a while loop, where each of the first three choices in the switch leads to a UFD that does the work (Build, Print out or Search the list). Of course, Quit is trivial and does not need a UFD. 1) (1 point) Build the list and assigns a value (random integer between 0 and 99) to each node. 2) (1 point) Prints out the contents of the list to screen. For example: (you can either start from 0 or from 1 – it doesn’t matter) Node #1 contains the value of 71 Node #2 contains the value of 36 Node #3 contains the value of 19 . . . Node #100 contains the value of 27 3) (1 point) Asks the user what number she wishes to find in the list and searches for the first instance of that number. The search must return (i.e., print to screen) the node number in which the entry was found, so the program must keep count of the nodes it has visited. Assume the list is unordered (which of course, it is). If the number is not found in the list, it must say: The search has failed. For output, the program must print out one line indicating that the value sought was found in the nth node. For example: Please enter the number to be sought in the list: >> 15 The number 15 was found in node #81 B. (1 point) Write a second program (Program B) that builds a contiguous list (i.e., array? based), also of 100 elements (cells), each containing a random integer between 0 and 99. You encouraged to re?use as much code from Program A as you wish (this is called code re? sue and it is a good thing). This program must: 1) Build the contiguous list (i.e., the properly populated array). 2) Print out the contents of the list. Use the same output format you used for part A.2 except call it a “cell” and not a “node”. 3) Sort the list using the insertSort algorithm. 4) Print out the list automatically after it has been sorted. Use the same printout format as in part B.2 above. Note: These are to be two separate programs and not one program in two separate files!! The names of the files you submit should be HW7 - - progA.c HW7 - - progB.c Musts: • It should not need to be said, but ….. the programs, of course, must be written in C and compile in the gcc compiler. • The files must be submitted through Canvas by the due date above. Because it is the last assignment of the semester, it cannot be submitted late. • No other musts other than those explicitly stated in the program descriptions above.
Explanation / Answer
A. Below is the program for Build, Print out or Search the linked list in c.
It consists of three user-defined functions:
1.build: create a Linked list of size 100 with random value inserted into it.
2. print: print the Linked list with value at each node.
3. search: search the linked list and return the node at which the number is found.
#include <stdio.h> // printf(), NULL
#include <stdlib.h> // malloc()
#include <time.h> // time()
struct node
{
int number;
struct node * next;
};
// start function: build
// Function to build a linked list
void build(struct node* here){
int i = 0;
srand(time(0)) ; // To set the starting point for producing a series of pseudo-random integers
for (i=1; i<=100; i++)
{
here->next = malloc( sizeof( struct node ) );
here = here->next;
here->number = rand()%100;
}
// return here;
}// end function: build
// start function: print
// Function to print a linked list
void print(struct node* here){
int i = 0;
for (i=1; i<=100; i++)
{
here = here->next;
printf("Node %d contains the value of %d " ,i,here->number);
}
}// end function: print
// start function: search
// Function to search a number in linked list
int search(struct node* here, int number){
int i = 0;
int index;
for (i=1; i<=100; i++)
{
here = here->next;
if(number==here->number)
{
index = i;
break;
}
else
{
index = -1;
}
}
return index;
}// end function: search
// start function: main
int main( void )
{
int number;
int index;
struct node *head = malloc(sizeof( struct node ));
head->next = NULL;
head->number = rand()%100;
struct node *here = head;
build(here);
print(here);
printf("Enter Number to be searched:");
scanf("%d", &number);
index = search(here,number);
if(index>0)
{
printf("The value sought %d was found in the %d th node.",number,index);
}
else{
printf("The search has failed.");
}
return 0;
} // end function: main
B. Below is the program for Build, Print out or sort the contiguous list by insertion sort algorithm in c.
It consists of three user-defined functions:
1.build: create an array of size 100 with random value inserted into it.
2. print: print the array with value at each cell.
3. sort: sort the array based on insertion sort algorithm.
#include <stdio.h> // printf(), NULL
#include <stdlib.h> // malloc()
#include <time.h> // time()
// start function: build
// Function to build a contiguous list
int * build(int *here){
int i = 0;
srand(time(0)) ; // To set the starting point for producing a series of pseudo-random integers
for (i=1; i<=100; i++)
{
here[i] = rand()%100;
}
return here;
}// end function: build
// start function: print
// Function to print a contiguous list
void print(int *here){
int i = 0;
for (i=1; i<=100; i++)
{
printf("Cell %d contains the value of %d " ,i,here[i]);
}
}// end function: print
// start function: sort
// Function to sort the contiguous list
int* sort(int * here){
int i, key, j;
for (i = 0; i <=100; i++)
{
key = here[i];
j = i-1;
while (j >= 0 && here[j] > key)
{
here[j+1] = here[j];
j = j-1;
}
here[j+1] = key;
}
return here;
}// end function: print
// start function: main
int main( void )
{
int clist[100];
build(clist);
print(clist);
sort(clist);
printf("Sorted List is:");
print(clist);
return 0;
} // end function: main
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.