Introduction to Programming with C
Introduction to Programming with C COP 3223
University of Central Florida
Popular in Course
Popular in Computer Programming
This 16 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 3223 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 45 views. For similar materials see /class/227470/cop-3223-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Introduction to Programming with C
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
Introduction to C Program 5 Use of Strings DNA Testing Assigned 33004 Tuesday Due Date 4604 Tuesday Objective To give students practice using C strings and more practice using input les The Problem DNA Testing DNA contains sequences of four possible base pairs AdenineA ThymineT GuanineG and CytosineC A vast majority of the cells of a human being contain nearly identical copies of the whole sequence of DNA for the individual Due to the vast number of base pairs in the entire DNA sequence it is pretty much impossible for two different human beings that aren t identical twins to have sequences of DNA that match very closely or identically For this program you will take an input le that contains a small sequence of DNA found in a sample along with several candidates for matches In essence you are trying to identify which if any of the candidates has the same DNA as found in the sample If a perfect match is found then your program should output which candidate was the perfect match If no perfect match is found your program should simply output the best possible match of the candidates with a score of how good the match is Input File Format The first line of the input file will contain the sample sequence of DNA that we are attempting to match This sample along with all other DNA sequences in the file will be represented as a string with capital letters A T G and C with no spaces on a line by itself The second line in the input file will contain a single positive integer n indicating the number of candidates to match the sample listed in the file The following n lines will contain the sample DNA of each of the n candidates one candidate to a line Here is a sample input file quotinputltXtquot AACT GGT GCAGATACT GT T GA 3 AACT GGT GCAGATACT GCAGA CAGT T TAGAG CAT CAT CAT CAT CAT CAT CAT How to Determine and Score Matches A perfect match must be between two samples of the exact same length that contain the exact same corresponding letters If a match isn39t a perfect match it should get a score The score will range in between 0 and 100 inclusive Here is how to score the closeness of a match between two sequences of DNA 1 Initialize score to 0 2 Determine the length of the shorter or the two sequences Let this be L 3 For the first L characters in each sequence check to see if two corresponding characters in the same position in their respective strings are equal or not If they are add 3 to score If the two characters are part of a matching base pair but aren39t equal either if they are 39A39 and 39T or C39 and G39 then add 1 to score Otherwise add nothing to score 4 Take score multiply it by 100 and divide by 3L in this order using an integer divide This will be the score of a match between two DNA sequences Output Your program should simply output a single line to the screen If there is a perfect match you should output a message of the following format Candidate X is a perfect match X should be the candidate number that matched the sample DNA perfectly If there isn39t a perfect match output a message of the following format The best match is Candidate X with a score of Y X should be the candidate number that matched the sample DNA with the highest score of all the candidates and Y should be the score of the X39s match with the sample If two or more candidates match with the sample with the exact same score you may output any of these candidates You are guaranteed that each candidate s sequence of DNA will be distinct from all the other candidates Thus two candidates will never be perfect matches References Textbook Chapter 10 Notes Lecture on Strings Restrictions Name the file you create and turn in dnac Although you may use other compilers your program must compile and run using gcc If you use your olympus account to work on this assignment please follow the steps shown in class to create compile and test your program Your program should include a header comment with the following information your name course number section number assignment title and date You should also include comments throughout your code when appropriate If you have any questions about this please see a TA Input Speci cation Assume that the user always enters the name of a valid input le that is formatted correctly according to the speci cation in this problem set Output Speci cation Your output should follow the examples on the following pages Deliverables A single source le named dnac turned in through WebCT Sample Output 1 For this sample assume that quotinputltXtquot is the same le provided in the quotInput File Formatquot section of this assignment What file stores the DNA test cases input1txt The best match is Candidate 1 with a score of 92 Sample Output 2 For this example assume that the contents of the le quotinput2tXtquot is as follows GATAGTGCGTA ACGATTAGAGAGGGA AAAAAA GGGGGG CCCCCC TTTTTT GATAGTGCGTA ACGTACGTACGTACGT GCAGATAGA GATTACA GATACAT What file stores the DNA test cases input2txt Candidate 6 is a perfect match Note The methodology described in this assignment is NOT how DNA matches are made The algorithm was simply made up so that the class could get some practice with string manipulation on a type of problem that could have practical applications Linked List Linked List The simplest form of a linked structure It consists of a chain of data locations called nodes Each node holds a piece of information AND a link to the next node We can think of each node as a record The first part of the record is a field that stores the data and the second part of the record is a field that stores a pointer to a node Here is a picture of what a simple linked list that stores Num values looks like Here is a struct we would use to define a record that stores one of these nodes struct ll int data struct 11 next Now to actually use this record we would have to define a variable of type 11 as follows struct ll mylist How to access nodes of a linked list Let s assume we already have mylist initialized to look like this Don t worry how this occurred we ll go through that in a bit Now one of the most common errors dealing with pointers is moving the head of the list Consider if we made mylist point to the second node we have listed In this case we would have NO way to access that data value in the first record Rather than do this what we need is a temporary ll pointer to help us move through the list We can define one as follows struct ll helpptr Now our picture looks like this As we can see help ptr is uninitialized Just as it isn t a good practice to leave variables uninitialized it isn t good to leave pointers the same way The default value that a pointer is initialized to is NULL and can be done like the following helpptr NULL Now if we want to use help ptr to move around the list pointed to by mylist we could start off with the following line helpptr mylist This makes our picture look like Now to access say the data field of the first record in the list we could refer to it in either of these ways mylist data OR helpptr data mylist gtdata OR helpptr gtdata A few things to notice here First both of these expressions refer to the same exact variable since mylist and help ptr are pointing to the same exact 11 Next in order to access that first 11 through either of the pointers we MUST dereference the pointer using the symbol Finally we use the dot operator to refer to a field within the record as we learned before Notice that the expression mylistdata is syntactically incorrect because mylist IS NOT a of type 11 and we are only allowed to access the data field of a 11 Also notice that the arrow gt provides an valid alternative syntax Consider now using the pointer help ptr to traverse the list pointed to by mylist We could do something like helpptr helpptr gtnext Note that the syntax here is correct because both sides of the assignment statement are pointers to 1139s Here is how this statement would change our picture Then we could refer to the data field in the second 11 as helpptr gtdata We can repeatedly use helpptr in this fashion to iterate through this list We could also modify the values in the list with a statement like helpptr gtdata 10 This sort of manipulation will be handy for editing lists Applying this to a segment of code that prints out a linked list Assume that mylist is already pointing to a valid list of values struct ll helpptr helpptr mylist while helpptr NULL printfquotd quot helpptr gtdata helpptr helpptr gtnext If you carefully look at the linked list code example posted on the web you39ll see that no temporary pointer is used Why is this okay How to add a node to a list This is how to create a ListNode to be added to a list struct ll temp tempstruct llmallocsizeofstruct 11 temp gtdata 7 temp gtnext NULL The picture of this looks like this There are a couple of things going on here Note that temp here is a pointer to a 11 not a 11 itself and that first statement implicitly creates a 11 that the pointer temp is pointing to Once we do that all we have to do is dereference our pointer to initialize the newly created 11 By having this capability of created ll39s like this on the fly and then adding them to a list we have the ability to store information dynamically Now to finally add this node to an end of a list assume that the ListNode pointer help ptr is pointing to the last node in the list Then all we have to do to connect the entire list is helpptr gtnext temp Now let39s go over the other functions in the handout Functions and Structured Programming Tenets of Structured Programming Make ow of control as easily understood as possible Build your program from the topdown Decompose the problem into smaller and smaller pieces Avoid repeating the same code can x code in one place 2112m1 COP 323 r C ngammm V D CYDSSmiE 1 Functions and Structured Programming Function a piece of code that performs a task and returns a result Functions allow you to do a topdown esign printf and scanf are actually functions You understand how to use them and don39t really care about the actual code inside 2112Dm Con 3223 r c Pttuvamminur D Cmssmiev 2 Main Your quotmainquot is a function Programs always start in the quotmainquot int mainvoid code here 2112m1 COP 323 r C ngammm V D CYDSSmiE 3 Function Invocation When the program encounters a function name followed by O the function is called or invo e After the function does it work flow of control returns to the calling code Functions can accept arguments which are copies of variables for the function to use This makes the function more programmable and useful to you the programmer 2112Dm Con 3223 r c Pttuvamminur D Cmssmiev 4 A new function include ltstdioh gt void printtitle void prototype int main void printtitle invocation void printtitle void de nition printf quotThis is a headernquot printf ll nquot 2112m1 COP 323 r C ngammm V D CYDSSmiE 5 Function Definition type functionname parameter type list arguments values in pass defarafion5 to the function go here or use void for nothing statements Function de nition header Everything prior to the is the hmder Everything inside the curly braoes is the function de nition ody 2112um Con 3223 r c mismmingr D Cmssmiev s i printtitle with an argument Let39s make printtitle smart enough to know how many times to print itself We will modify the printtitle function adding an argument 2112m1 OF 323 r C ngammm V D CYDSSmlE printtitle oinciude ltstdiohgt void printtitle int count int main void in n printf quotHow many titles quot scanf quotnadquot ampn printtiden remm o void printtitle int count int i for i o i lt count i printf quotThis is a headernquot ailmm cop 3223 r c Pituiammingr D Cmssmiei printtitle Dissected include ltstdiohgt We want to use printf and scanf a function prototype tells the compiler all about the arguments and the return value of a function stdioh has the function prototypes for printf and scanf 2112m1 OF 323 r C ngammm V D CYDSSmlE 9 printtitle Dissected cont void printtitle int count This is the prototype for our function It tells the compiler to expect a function named printtitle that has one argument of type int that does not return a value note the at the end 2112Dm cop 3223 r c mismmingr D Cmssmiei 1D i printtitle Dissected cont int main void Function definition for main You don39t have to supply a prototype for main although you may 2112m1 OF 323 r C ngammm V D CYDSSmlE 11 printtitle Dissected cont int n printf quotHow many titles quot scanf quotdquot ampn Declare an integer variable named n print out a prompt for the number of titles to print read the requested number into n 2112Dm cop 3223 r c mismmingr D Cmssmiei 12 i printtitle Dissected cont printtitlen call or invoke the function named printtitle pass the current value of n as an argument flow moves to printtitle 2112m1 cop 32237 c Pingammim V D Crussrnia printtitle Dissected cont void printtitle int count Function definition for printtitle Think of count as representing the value of the actual argument when printtitle was called In this case n 2112um cop 3223 r c Piturarnrninur D Crussmiev printtitle Dissected cont void printtitle int count inti39 for i o i lt count i printf quotThis is a header nquot this invocation count 2 one per ine flow returns to main when it reaches the 2112m1 OF 3223 r C ngammm V D Cmssmia The call from main passed in n 2 so for result is quotThis is a headerquot is printed twice printtitle Dissected cont printtitlen return 0 Flow returns to the statement after the call to printtitle return 0 exits main to the olympusl command prompt Flow returns here 2112um cop 3223 r c Piturarnrninur D Crussmiev i printtitle Dissected cont We called printtitle only once in main We could have called it as many times as we wanted with different values for the count argument 2112m1 OF 3223 r C ngammm V D Cmssmia return Statement return return expression Passes flow of control immediately back to the calling environment If you supply expression the value of the expression is returned also 2112um cop 3223 r c Piturarnrninur D Crussmiev i return statement examples return 0 I return return a return 13 If you don39t provide a return control is still passed back to the caller 2112m1 OF 323 r C ngammm V D CYDSSmiE 19 minimum program Write a program to compute the minimum of two given integers Create a function to determine the minimal value 2112Dm cop 3223 r c Pitaummingr D Cmssmiev 2D minimum program cont include ltstdiohgt int min int 3 int b intmain mid topdown design I quotU I m wrote main w pn39ntf quotInput two integers quot writing min yet scanfquotddquot ampj ampk39 m minj k pn39ntf quotnd is the minimum of d and dquot 2112m1 OF 323 r C ngammm V D CYDSSmiE 21 minimum program cont int min int a int b if a lt b return a else return b 2112Dm cop 3223 r c Pitaummingr D Cmssmiev 22 maximum function int max int a int b if a gt b return a else return b 2112m1 OF 323 r C ngammm V D CYDSSmiE 23 Random number program Illustrates random number function stdlibh provides the prototype for a function named rand random numbers are useful to generate test number sets games and probability simulations topdown design further use of min and max functions 2112Dm cop 3223 r c Pitaummingr D Cmssmiev 24 Random number program zinclude ltsmiohgt zinclude ltsmlibhgt void primRandant count int mainv0id int n printf quotHow many random numbers quot f39 quotndquot ampn scan primRandsm return 0 2112m1 OF 323 r c Piogammm V D cvossrnie z Random number program r o inti r biggest smallest Usmg o to printa r iggest smallest randO newline prior to Drintf n7d r r r every 7th output f l 01quot lt CW V Makes a nioe table ironD720 h h h f pr n uw T IIS is w y t e irst r ra d print is ou th biggest magtltr biggest for loop srn iie 7 min r smallest printf 7d r printf riris5dns5dns5dnn H H ME Coun count Ximum biggest Minimum smallest 2nl2um co 3222 r c Programmian o Ciossmiei 2s Output from Random program Olympuslgtgcc printkands cc Olympuslgtatou How many random numbers 23 16838 5758 10113 17515 31051 5627 23010 7419 16212 4086 49 12767 9084 12060 32225 17543 25089 21183 25137 25566 26966 0495 N 4 um 23 Maximum 32225 Minimum 2749 2112m1 OF 323 r c Piogammm V D cvossrnie 27 Function Definition Order Two styles use function prototypes function order doesn39t matter order function de nition so that they are seenquot by the compiler before use 2112um cop 3223 r c Programme 0 Ciossmiei 2a Using Function Prototypes oinciude ltsmiongt int min int a intb void main v0id m mi int min int a int b 2112m1 OF 323 r c Piogammm V D cvossrnie 29 Without Function Prototypes oinciude ltstdi0hgt Compiler pmcsses in int min int a int b fmm the begmnlngr as long as min is kn n if a lt b either by a function return a Prototype or the I eise function declaration it remm b will oompile void main void m min2 3 2112um cop 3223 r c Programme 0 Ciossmiei an i Which is better Using function prototypes are better in my opinion You don39t have to worry about the order of the functions in your source code Allows you to easily migrate to larger programs that use multiple source les Lets you put the main at the top 2112m1 OF 3223 r C ngammm r D CYDSSmiE 31 Large Programs Big programs are usually build in a separate directory or folder collection of h and c les each c file is individually compiled c files hold function de nitions h files hold common prototypes include e39s directives and defln h files act as quotgluequot prototypes defines etc 2112Dm cop 3223 r c Pitavamminur D Cmssmiev 32 mainc fctc utilc include quotpgmhquot include quotpgmhquot include quotpgmhquot 211sz copazarcpmgammmrD Cmssmia 33 Large Programs example Migrate the minmax program using multiple files put minmax functions in utilc put main in appc create a apph that holds the prototypes 2112Dm cop 3223 r c Pitavamminur D Cmssmiev 34 apph include ltstdiohgt int maxint 3 int b int minint 3 int b 2112m1 OF 3223 r C ngammm r D CYDSSmiE 35 utilc zinclude quota phquot int min int a int b if a lt b return a lse return b int max int a int b if a gt b return a lse return b 2112Dm cop 3223 r c Pitavamminur D Cmssmiev 35 appc include quotapphquot int main void M m printfquotInput two integers quot scanfquotddquot ampj ampk min 39 39 printf nd is the minimum of d and dquot m j k return 0 2112m1 OF 3223 r C Progammm V D CYDSSmlE Callbyvalue Arguments passed to all functions in C are always sent via callbyvalue Callbyvalue means that a copy of the variable is sent to the function the original is not modified 2112um cop 3223 r c mismmlng39 D CYDSSmlEY i Callbyvalue example zinciude ltsmiohgt void mstint i int main 0 inti test i printf quotMain i quotmmquot i void mst int i i printf quotTest i quotmmquot i 2112m1 OF 3223 r C Progammm V D CYDSSmlE Style Functions should do a specific task and not be too long too long is subjective a page or two is a good rule of thumb if you fnd yourself running out of indention room to the right you probably are 39t using enough functions 2112um cop 3223 r c mismmlng39 D CYDSSmlEY