CSCI 101 Fundamentals of Computer Programming Lab 11 Strings Sorts Fall 2005 Project 1 You are going to try running the proj1Solution file from the website during the lab to ensure that you are able to do so To execute the file do the following a Download the proj1Solution file from the website a Right click on the proj1Solution link and select Save Target As b Change the Save as Type to All Files c Make sure the filename is selected as proj1Solution d Save the file to your desktop b In your LabLaunch run CoreFTP a Connect to your aludra account by typing in your username and password b A window will then pop up asking if you would like to save the key Click Yes c Transfer the proj1Solution to your account a Go to your desktop on the left panel of the CoreFTP program b Go to the directory on the right panel where you wish to store the proj1Solution file c Drag the file from the left panel to the right This will initiate the transfer d Running the sample solution a Once you are done transferring go to the directory where you store the file in your aludra account b Type in chmod 700 proj1Solution to change the permissions on the file c Type in proj1Solution to run the program Your TA LA will then demonstrate to you how the program should work Strings There are no string datatypes defined in C and thus it is simulated using character arrays However traditional operators such as the assignment operator addition operator comparisons and so will not work on arrays This is inconvenient as we often come across situations when we would like to perform those operations The string h header file provides an array of predefined functions that simulates such operations on strings The table below describes the more frequently used functions More information can be found at http www cplusplus com ref cstring char s1 10 string 1 char s2 10 string 2 char s3 10 Assignment Concatenation strcpy s3 string 3 strcat s3 concatenated Comparison strcmp s1 s2 S3 string 3 S3 string 3 concatenated 0 if s1 s2 0 if s1 s2 0 if s1 s2 Table of functions in string h The sample program below should clearly illustrate the use of these three functions Note that you would need to include the string h header file at the top of your program You may download this program at http scf usc edu csci101 labs lab11string c include string h include stdio h int main char name1 20 char name2 20 int val printf nNames after initialization n printf name 1 s n name1 printf name 2 s n name2 strcpy name1 Mary strcpy name2 Arthur printf nNames after assignment n printf name 1 s n name1 printf name 2 s n name2 strcat name1 Jane strcat name2 Doyle printf nNames after concatenation n printf name 1 s n name1 printf name 2 s n name2 val strcmp name1 name2 printf nComparison between name1 name2 n printf val d n val return 0 Sorting techniques After the introduction of arrays large amounts of data can now be stored and accessed conveniently However as the amount of data increases so does the complexity in managing them To ease this process sorting techniques need to be introduced You have learnt three types sorting techniques introduced by Professor Ghyam during lecture bubble sort insertion sort and selection sort These three sorting techniques are generally rather intuitive and easy to implement However the efficiency is compromised as they are slower than other sorting techniques that are marginally harder and less intuitive Due to time constraints we will only familiarize ourselves with the bubble sort Like its name sake bubble sort is a sorting technique that bubbles up the smallest number in an array It compares two adjacent elements and swaps them if it is in the wrong order The java applet at http www cs hope edu alganim animator Animator html should clearly illustrate this Feel free to try out the other sorting algorithms especially insertion and selection sort The program below is an example of how bubble sort is implemented You may download it at http scf usc edu csci101 lab11sort c Make sure you understand and able to visualize how the sorting technique works include stdio h int main const int size 10 int array size int i j temp Initializing and printing out an unsorted array printf nUnsorted array for i 0 i size i array i rand 50 printf d array i Sorting the array for i 0 i size i One run of the sort for j 1 j size j if array j 1 array j temp array j array j array j 1 array j 1 temp Printing out the array after every run of the sort printf nRun 2d i 1 for j 0 j size j printf 2d array j Printing out the final sorted array printf nSorted array for i 0 i size i printf d array i printf n n return 0 Exercise For this week s lab exercise you will incorporate both the functions from string h as well as bubble sort to sort a small information database Download the database file from http scf usc edu csci101 labs lab11database dat There are three columns of data where the first column corresponds to the first name the second the last name and the third the ID of the person You are to write a program that does the following a Scans all the data from the file into appropriate data structures b Prompt the user on how he she wants the information sorted by first name last name or ID c Sorts the data according to the request and prints the sorted database out in a legible manner Your TA LA will show you a sample output for this exercise Once you are done show your TA LA your completed program for lab credit Feel free to implement additional features on your program
View Full Document