Computer Science I
Computer Science I COP 3502
University of Central Florida
Popular in Course
Popular in Computer Programming
This 42 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 3502 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/227474/cop-3502-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Computer Science I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
QUEUES A queue is simply a waiting line that grows by adding elements to its end and shrinks by removing elements from the front Compared to stack it re ects the more commonly used maxim in realworld namely first come first served Waiting lines in supermarkets banks food counters are common examples of queues A formal definition of queue as a data structure It is a list from which items may be deleted at one end front and into which items may be inserted at the other end rear It is also referred to as a firstinfirstout FIFO data structure l l front rear Queues have many applications in computer systems Handling jobs in a single processor computer print spooling transmitting information packets in computer networks 0 Primitive ueue 0 erations enqueue q x inserts item X at the rear of the queue q x dequeue q removes the front element from q and returns its value isEmpty q Check to see if the queue is empty isFull q checks to see if there is space to insert more items in the queue Example Consider the following sequence of operations being performed on a queue q which stores single characters enqueueq W enqueueq B enqueueq 039 x dequeueq enqueueq D39 enqueueq E x dequeueq enqueueq H x dequeueq enqueueq J39 The contents of the queue q after these operations would be T T front Fear Array Implementation The array to implement the queue would need two variables indices called from and rear to point to the first and the last elements of the queue f ant reLr Initially q gtrear l q gtfront 1 For each enqueue operation rear is incremented by one and for each dequeue operation from is incremented by one While the enqueue and dequeue operations are easy to implement there is a big disadvantage in this set up The size of the array needs to be huge as the number of slots would go on increasing as long as there are items to be added to the list irrespective of how many items are deleted as these two are independent operations Problems with this representation Although there is space in the following queue we may not be able to add a new item An attempt will cause an over ow 0 1 2 3 4 front rear It is possible to have an empty queue yet no new item can be inserted when from moves to the point of rear and the last item is deleted rear front A solution Circular Array Let us now imagine that the above array is wrapped around a cylinder such that the first and last elements of the array are next to each other When the queue gets apparently full it can continue to store elements in the empty spaces in the beginning of the array This makes efficient use of the array slots It is also referred to as a circular array This enables us to utilize the unavailable slots provided the indices front and rear are handled carefully Here again from refers to the index of the element to be next removed from the queue and rear refers to the index of the last element added to the queue rear front equivalently front rear The queue is implemented on a circular array With each enqueue the rear index is incremented and with each dequeue the from index is incremented The wrap around is achieved by taking the mod function with the capacity of the array The queue is initialized with from rear 0 When the rst element is enqueued the rear index becomes 1 while the from index remains 0 When the second element is enqueued the rear index becomes 2 while the front index remains 0 If we now dequeue the from index becomes 1 and at the next dequeue operation the front index becomes 2 The queue is now empty as two elements were stored and these two were retrieved The index values are front rear 2 In fact at any stage the condition from rear indicates that the queue is empty Consider a queue with 71 slots Suppose the from index is zero and we go on lling up the queue When the last but one slot is lled up the rear index will have value 71 Now if we want to insert another element in the queue the rear index will be 71 But since we do not have the slot 71 it would point to the slot 0 Thus while the queue is actually full we have from rear 0 which is not possible because that is a condition for the queue to be empty Here we are faced with a contradiction To overcome this problem the last element is never lled up in a circular queue and when only a single slot is empty we declare the queue to be full Queue Size The front and rear indices can be used to nd out the current size of the queue that is the number of elements currently in the queue The value rear 7 from gives us the size and when this value is negative we simply add the capacity to this to give us the size Thus in general we have size rear 7 front capacity capacity Engueue and Degueue algorithms Here are the enqueue and the dequeue algorithms It is assumed here that the variables rear front and capacity are globally Visible initially rear 0 front 0 void enqueueint Q int d rearplusl rear1 capacity if rearplusl front print Q fullquot else Qrear d rear rearplusl void dequeue int Q dd iffront rear dd 9999 print Q emptyquot else dd Qfront fron front 1capacity Bucket Sort The idea behind bucket sort is that if we know the range of our elements to be sorted we can set up buckets for each possible element and just toss elements into their corresponding buckets We then empty the buckets in order and the result is a sorted list In implementing this algorithm we can easily use an array to represent our buckets where the value at each array index will represent the number of elements in the corresponding bucket If we have integers on the range 0 max then we set up an array of max 1 integers and initialize all the values to zero We then proceed sequentially through the unsorted array reading the value of each element going to the corresponding index in the buckets array and incrementing the value there Then our function in C is as follows void bucketsortint array int n int max int i j 0 Declare an array of size max l and initialize all values to zero int bucket callocmax l sizeofint Place each element from the unsorted array into its corresponding bucket for i 0 i lt n i bucketarrayi Sequentially empty each bucket back into the original array for i 0 i lt max i whilebucketi arrayj i We immediately see two drawbacks to this sorting algorithm Firstly we must know the maximum value of any element that can be found in the unsorted array Without this information we do know how many buckets to initialize Secondly we must be able to create enough buckets in memory for every element that we might possibly encounter in the unsorted array It may be impossible to declare an array large enough to fulfill this requirement on some systems Accordingly we should augment our function above to determine whether the array was properly allocated at runtime This can be achieved by inserting the following line after the calloc statement if bucket NULL return Thus we see a tradeoff between time and space complexity here The On bucket sort out performs any comparison based sort in terms of its Big Oh notation at least but places a much higher demand on system memory than any of the other sorting algorithms we have seen so far The reader should be aware that there are other variations of bucket sort that rely on buckets that accommodate small ranges of elements rather than single values A discussion of that sort of implementation is available on Wikipedia httpenwikipediaorgwikiBucket sort The notes presented here are loosely based on information from that page Radix Sort The idea behind radix sort is slightly more complex than that of bucket sort although not terribly so The algorithm proceeds as follows 1 Take the least significant digit of each element in the unsorted array 2 Perform a stable sort see below based on that key 3 Repeat the process sequentially with each more significant digit By a stable sort we mean that the original order of the elements is maintained in the event of ties For example supposed we want to sort the list 849 770 67 347 201 618 66 495 13 45 Sorting by the least significant digit ie the ones digit we get 770 201 13 495 45 66 67 347 618 849 Notice that although 495 and 45 as well as 67 and 347 are equal in terms of their least significant digit their order in the original list is preserved ie 495 came before 45 in the original list and so it comes before 45 after sorting by the least significant digit so too for 67 and 347 This is what we mean when we say that the sorting algorithm must be stable We then proceed to sort by the more significant tens digit resulting in the order 201 13 618 45 347 849 66 67 770 495 Notice that we have once again employed a stable sort 347 and 849 are clustered together because they share the same tens digit but the former precedes the latter because it does so in the previous list In our last pass we sort by the most significant digit the hundreds digit In the case of 13 45 66 and 67 we consider the hundreds digit to be zero The result is the following sorted list 13 45 66 67 201 347 495 618 770 849 So far we have ignored the precise sorting mechanism employed at step two in each iteration of the algorithm That39s because radix sort gives us the freedom to choose whichever sorting algorithm we please so long as it is a stable sorting algorithm The runtime analysis will of course depend on the runtime of the sorting algorithm employed at step two of each iteration It is quite common and therefore worth mentioning to use bucket sort for our stable sorting algorithm in radix sort Because we are only sorting by one digit at a time we only have to set up ten buckets 09 to accomplish this goal However the implementation of those buckets will necessarily vary from the one given in the previous section of these notes because each bucket must be able to hold multiple values which will not be equal to the index for that bucket One common solution then is to implement the buckets as queues When using bucket sort in conjunction with radix sort if we have n elements to sort and the maximum length of any of those elements is k then we must perform k iterations of the On bucket sort giving us an overall Big Oh of Onk for this particular implementation of radix sort For instance in the example above we have k 3 since the largest element has three digits and we end up doing three iterations of the bucket sort k is not a constant though It will vary depending on the input though and so it must be included in the Big Oh analysis of the algorithm Further discussion on implementation issues as well as more examples of the radix sort in action are available on Wikipedia httpenwikipediaorgwikiRadix sort The notes presented here are loosely based on information from that page Binary Decimal Octal and Hexadecimal number systems A number can be represented with different base values We are familiar with the numbers in the base 10 known as decimal numbers with digits taking values 01289 A computer uses a Binary number system which has a base 2 and digits can have only TWO values 0 and l A decimal number with a few digits can be expressed in binary form using a large number of digits Thus the number 65 can be expressed in binary form as 1000001 The binary form can be expressed more compactly by grouping 3 binary digits together to form an octal number An octal number with base 8 makes use of the EIGHT digits 0123456 and 7 A more compact representation is used by Hexadecimal representation which groups 4 binary digits together It can make use of 16 digits but since we have only 10 digits the remaining 6 digits are made up of first 6 letters of the alphabet Thus the hexadecimal base uses 01289ABCDEF as digits To summarize Decimal base 10 Binary base 2 Octal base 8 Hexadecimal base 16 Decimal Binary Octal and Hex Numbers Decimal Hexadecimal 0 0 A A OOOOUIJgtUJN 2 3 4 5 6 7 8 9 10 A B C D E F Conversion of binary t0 decimal base 2 to base 10 Each position of binary digit can be replaced by an equivalent power of 2 as shown below 2 1391 211392 23 22 21 20 Thus to convert any binary number replace each binary digit bit with its power and add up Example convert 10112 to its decimal equivalent Represent the weight of each digit in the given number using the above table 2 1391 211392 23 22 21 20 1 O 1 1 Now add up all the powers after multiplying by the digit values 0 or 1 10112 23x1 22x021x12 x1 8 0 2 1 11 Example2 convert 10001002 to its decimal equivalent 26x125x0 24x023x022x121x0 2 x0 64000400 6810 Conversion of decimal to binary base 10 to base 2 Here we keep on dividing the number by 2 recursively till it reduces to zero Then we print the remainders in reverse order Example convert 6810 to binary 682 34 remainder is 0 34 2 17 remainder is 0 172 8 remainder is 1 8 2 4 remainder is 0 4 2 2 remainder is 0 22 1 remainder is 0 1 2 0 remainder is 1 We stop here as the number has been reduced to zero and collect the remainders in reverse order Answer10 0 010 0 Note the answer is read from bottom MSB most signi cant bit to top LSB least signi cant bit as 10001002 You should be able to write a recursive function to convert a binary integer into its decimal eguivalent Conversion of binary fraction to decimal fraction In a binary fraction the position of each digitbit indicates its relative weight as was the case with the integer part except the weights to in the reverse direction Thus after the decimal point the rst digit bit has a weight of 12 the next one has a weight of 1A followed by 18 and so on 20 2 1 2 2 2 3 2 4 1 O 1 1 O O O The decimal equivalent of this binary number 01011 can be worked out by considering the weight of each bit Thus in this case it turns out to be 12x114x o 18 x 1 116 x 1 Conversion of decimal fraction to binary fraction To convert a decimal fraction to its binary fraction multiplication by 2 is carried out repetitively and the integer part of the result is saved and placed after the decimal point The fractional part is taken and multiplied by 2 The process can be stopped any time after the desired accuracy has been achieved Example convert 06810 to binary fraction 068 2 136 integer part is 1 Take the fractional part and continue the process 036 2 072 integer part is 0 072 2 144 integer part is 1 044 2 088 integer part is 0 The digits are placed in the order in which they are generated and not in the reverse order Let us say we need the accuracy up to 4 decimal places Here is the result Answer 0 10 1 Example convert 706810 to binary equivalent First convert 70 into its binary form which is 1000110 Then convert 068 into binary form upto 4 decimal places to get 01010 Now put the two parts together Answer10001101010 Octal Number System Base or radix 8 number system 391 octa1 digit is equivalent to 3 bits Octa1 numbers are 0 to7 see the chart down below Numbers are expressed as powers of 8 See this table 8 1391 8 1392 83 82 81 80 Conversion of octal to decimal base 8 to base 10 Example convert 6328 to decimal 6X823X812X80 6X643X82X1 384242 4101o Conversion of decimal to octal base 10 to base 8 Example convert 17710 to octa1 equivalent 177 8 22 remainder is 1 22 8 2 remainder is 6 2 8 0 remainder is 2 Answer 2 6 1 Note the answer is read from bottom to top as 2618 the same as with the binary case Conversion of decimal fraction to octal fraction is carried out in the same manner as decimal to binary except that now the multiplication is carried out by 8 Example convert 052310 to octal equivalent up to 3 decimal places 0523 X 8 4184 its integer part is 4 0184 X 8 1472 its integer part is 1 0472 X 8 3776 its integer part is 3 So the answer is 04138 Conversion of decimal to binary using octal When the numbers are large conversion to binary would take a large number of division by 2 It can be simpli ed by rst converting the number to octal and then converting each octal into its binary form Example convert 17710 to its binary equivalent using octal form Step 1 convert it to the octal form first as shown above This yields 2 6 Us Step 2 Now convert each octal code into its 3 bit binary form thus 2 is replaced by 010 6 is replaced by 110 and 1 is replaced by 001 The binary equivalent is 010 110 0012 Example convert 17752310 to its binary equivalent up to 6 decimal places using octal form Step 1 convert 177 to its octal form rst to get 2 6 Us and then convert that to the binary form as shown above which is 010 110 0012 Step 2 convert 0523 to its octal form which is 04138 Step 3 convert this into the binary form digit by digit This yields 0100 001 011 Step 4 Now put it all together 010110 001100 0010112 Conversion of binary to decimal using octal First convert the binary number into its octal form Conversion of binary numbers to octal simply requires grouping bits in the binary number into groups of three bits Groups are formed beginning with the Least Signi cant Bit and progressing to the MSB Start from right hand side and proceed to left If the left most group contains only a single digit or a double digit add zeroes to make it 3 digits Thus 111001112 011 100 1112 3 4 78 And 1100 010101010 010 0012 001100 010101010 010 0012 14252218 Now it can be converted into the decimal form Hexadecimal Number System Base or radix 16 number system 391 hex digit is equivalent to 4 bits Numbers are 01289 A B C D E F B is 11 E is 14 Numbers are expressed as powers of 16 160 116116 162 256163 4096164 65536 Conversion of hex t0 decimal base 16 to base 10 Example convert F4C16 to decimal F x 162 4 x 161 C x160 15 x2564x 1612x 1 Conversion of decimal to hex base 10 to base 16 Example convert 4 768 10 to hex 4768 16 298 remainder 0 298 16 18 remainder 10 A 1816 1 remainder 2 1 16 0 remainder 1 Answer 1 2 A 0 Note the answer is read from bottom to top same as with the binary case 384064120 391610 Conversion of binary to hex Conversion of binary numbers to he simply requires grouping bits in the binary numbers into groups of four bits Groups are formed beginning with the LSB and progressing to the MSB 1110 01112E716 01100010101000 01112 0001100010101000 01112 1 8 A 8 716 Trees I Examples of Tree structures De nition of trees Binary tree Height of a tree Tree traversals Finding sum of all elements Finding maximum value Trees You have seen that using linked lists you can represent an ordered collection of values without using arrays Although linked lists require more memory space than arrays as they have to store address at each node they have de nite advantages over arrays Insertion and deletion of items can be carried out with out involving considerable movement of data The ordering relationship amongst a set of values is obtained through use of pointers However we need not restrict ourselves to only linear structures In this chapter we shall extend the use of pointers to de ne a nonlinear structure to model hierarchical relationships such as a family tree In such a tree we have links moving from an ancestor to a parent and links moving from the parent to children We have many other examples of treestructured hierarchies Director Hierarchies In computers les are stored in directories that form a tree The top level directory represents the root It has many subdirectories and les The subdirectories would have further set of subdirectories Organization charts In a company a number of vice presidents report to a president Each VP would have a set of general managers each GM having hisher own set of speci c managers and so on Biological classifications Starting from living being at the root such a tree can branch off to mammals birds marine life etc Game Trees All games which require only mental effort would always have number of possible options at any position of the game For each position there would be number of counter moves The repetitive pattern results in what is known a game tree Tree as a data structure 0 A tree is a data structure that is made of nodes and pointers much like a linked list The difference between them lies in how they are organized o The top node in the tree is called the root and all other nodes branch off from this one 0 Every node in the tree can have some number of children Each child node can in turn be the parent node to its children and so on 0 Child nodes can have links only from a single parent 0 Any node higher up than the parent is called an ancestor node 0 Nodes haVing no children are called leaves 0 Any node which is neither a root nor a leaf is called an interior node 0 The height of a tree is de ned to be the length of the longest path from the root to a leaf in that tree including the path to root Binary Trees A common example of a tree structure is the binary tree De nition A binary tree is a tree in which each node can have maximum two children Thus each node can have no child one child or two children The pointers help us to identify whether it is a left child or a right child Application of a Binary tree Before we discuss any formal algorithms let us look at one possible application of a binary tree Consider a set ofnumbers 256313 7218325967 Suppose we store these numbers in indiVidual nodes of a singly linked list To search for a particular item we have to go through the list and maybe we have to go to the end of the list as well Thus if there were n numbers our search complexity would be On Is it because the numbers are not in any particular sequence Now suppose we order these numbers 1318253259636772 and store in another linked list What would be the search complexity now You may be surprised to discover that it is still On You simply cannot apply binary search on a linked list with Olog n complexity You still have to go through each link to locate a particular number So a linear linked structure is not helping us at all Let us see if we can improve the situation by storing the data using a binary tree structure Consider the following binary tree where the numbers have been stored in a speci c order The value at any node is more than the values stored in the leftchild nodes and less than the values stored in the rightchild nodes With this arrangement any search is taking at most 4 steps For larger set of numbers if we can come up with a good tree arrangement than the search time can be reduced dramatically Examples of binary trees root root o The following are NOT binary trees Mg o The level of a node in a binary tree The root ofthe tree has level 0 The level of any other node in the tree is one more than the level of its parent root I Level 0 Level 1 I Level 2 Level 3 Full Binary Tree 45 AO 37 81 94 How many nodes Level 0 1 node Level 1 2 nodes Level 2 4 nodes Level 3 8 nodes Total number of nodes for this tree 15 Height of the root node 4 n 24 1 15 In general 11 211 1 maximum Maximum Number of nodes in a tree with height h 211 1 Height of a tree with n nodes h log n1 Implementation 0 A binary tree has a natural implementation in linked storage A tree is referenced with a pointer to its root 0 Recursive de nition of a binary tree A binary tree is either Empty or A node called root together with two binary trees called left subtree and the right subtree of the root 0 Each node of a binary tree has both left and right subtrees which can be reached with pointers struct treeinode int data struct treeinode leftichild struct treeinode rightichild leftchild data rightchild Note the recursive definition of trees A tree is a node with structure that contains more trees We have actually a tree located at each node of a tree Traversal of Binary Trees Linked lists are traversed sequentially from first node to the last node However there is no such natural linear order for the nodes of a tree Different orderings are possible for traversing a binary tree Every node in the tree is a root for the subtree that it points to There are three common traversals for binary trees Preorder Inorder Postorder These names are chosen according to the sequence in which the root node and its children are visited Suppose there are only 3 nodes in the tree having the following arrangement n1 n2 n3 In order n2 n1 n3 Preorder n1 n2 n3 Post order n2 n3 n1 With inorder traversal the order is leftchild root node rightchild With preorder traversal the order is root node left child right child With postorder traversal the order is left child right child root node A tree will typically have more than 3 nodes Instead of nodes n2 and n3 there would be subtrees as shown below root subtree subtree With inorder traversal the order is left subtree then the root and nally the right subtree Thus the root is visited inbetween visiting the left and right subtrees With preorder traversal the root node is visited rst then the nodes in the left subtree are visited followed by the nodes in the right subtrees With postorder traversal the root is visited after both the subtrees have been visitedleft subtree followed by right subtree As the structure of a binary tree is recursive the traversal algorithms are inherently recursive Preorder traversal of a binary tree In a preorder traversal we first visit the root node If there is a left child we visit the left subtree all the nodes in preorder fashion starting with that left child If there is a right child then we visit the right subtree in preorder fashion starting with that right child The function may seem very simplistic but the real power lies in the recursive formulation In fact there is a double recursion The real job is done by the system on the runtime stack This simplifies coding while it puts a heavy burden on the system void preorder struct treenode p if p NULL printf dnquot p gtdata preorder p gtleftchild preorder p gtrightchild Take a tree of say height 3 with maybe 6 nodes and try to run the above recursion to nd out the actual order of printing the nodes Example root b e Preorder Traversal a b c d f g e aroot bleft c d f g e right Inorder traversal of a binary tree In the inorder traversal we rst Visit its left subtree all the nodes then we Visit the root node and then its right subtree void inorderstruct treenode p if p NULL inorder p gtleftchild printf dnquot p gtdata inorder p gtrightchild Inorder b afd g c e b1eft ar00t f d g c eright Finding sum of the values of all the nodes of a tree To find the sum add to the value of the current node the sum of values of all nodes of left subtree and the sum of values of all nodes in right subtree int sumstruct treenode p if p NULL returnp gtdata sump gtleftchild sump gtrightchild else return 0 Finding the maximum value in a binary tree int findMax struct treenode p int nodedata leftmax rightmax max max 1 assume all values in the tree are positive integers if p NULL nodedata p gt data leftmax findMaxp gt leftchild rightmax findMaxp gtrightchild find the largest of the tree values if leftmax gt rightmax max leftmax else max rightmax if nodedata gt max max nodedata return max VVhen an argun1entis passed to a func on using the pass by value rnethod essen aHy a copy ofthe argun1ents vahJe 3 passed to the func on ltis impossible for the function to modify the actual argument since it does not know the location of where this argument is stored in the memory it only has a copy of the value that is stored in that location Calling Called function X memory cell ofa 27 y function Y actual copied formal parameter a parameter m 39 4 memory cell of m 27 Memory Figure 1 Con guration at the time Function X calls Function Y Copy of actual parameter a is copied into location of formal parameter m Calling Called function X memory cell of a 27 function Y actual formal parameter aK parameter m memory cell of m 19 1 Figure 2 Con guration while Function Y is in execution Assume Y changes the value of m Calling Called function X memory ceofa 27 function Y actual formal parameter a parameter m Figure 3 Con guration just after Function Y has completed execution Modularity Functions 15 An illustration of hoW the actual parai neter in the calling inction is unchanged by the actions of the called inction Figure 4 PowerPoint slide shown illustrating passbyvalue Parameters in the C language are passed by value This restriction of the C language is in many ways an asset rather than a liability It usually leads to more compact code that contains fewer extraneous variables because the function arguments can be treated as conveniently initialized local variables in the called function Sometimes it is necessary to arrange for a called function to modify a variable in the calling function This requirement means that the argument must be passed by reference In order to achieve the effect of callbyreference in C we must use pointers in the formal parameter list in the function definition and pass addresses of variables as actual parameters in the function call As we will see later this is the only way in which an array can be passed in C ie it is not possible to pass an array by value in C You are already familiar with this technique as this is what we have been doing in the scanf statements that we have been using in our programs to date The function call scanf d ampapha causes an appropriate value to be stored at the address in memory which is identified by the identifier alpha Recall that ampapha is the address or location in memory of the variable alpha An illustration of hoW the actual parai neter in the calling mction can be changed by the actions of the called inction Figure 5 PowerPoint slide show illustrating passbyreference Modularity Functions 16 Pointer variables can be declared in programs and then used to take addresses as values The legal range of values for any pointer includes a special address of O and a set of positive integers that are interpreted as machine addresses int i p i is an integer p is a pointer to an integer p ampi p is assigned the address of i p O p is assigned the address of O p NULL p is assigned address NULL refers to nothing p int 1307 p is assigned address 1307 Note the implication of the declaration of p As with any other variable in C pointers are typed Therefore this declaration defines p as a pointer to an address which is capable of holding a single integer value Addressing and dereferencing pointers is done with the unary operators and amp as we have seen Using some examples we ll illustrate how these work with pointers in C int a b p These declarations cause the compiler to allocate space for the variables two integers and one pointer to an integer At this point the contents of these locations are unknown since we have not assigned values to them a p ampa Now suppose that the assignments shown above are made to these variables Once these are executed the memory will look like the following 7 7 T l l h40duku yFunc ons 17 We can not use the pointer p to access the value stored in the location referred to by a This is done through the dereference or indirection operator The indirection operator is a unary operator with the same precedence as all other unary operators and it associates from righttoleft Since p is a pointer the expression p has the value of the variable to which p points printflt p dnquot p Since p points to the location identified by a and a contains the value 7 the dereferenced value of p is also 7 and this is the value that will be printed by the printf statement shown above No consider the following p 3 printf a dn a What value do you expect will be printed by the printf statement It will print 3 The reason is this The first statement assigns to the location referenced by p the value 3 Since p refers to the location that is identified by a the value of 7 stored at a is ovenvritten with the value 3 Thus when we print the value of a it has been changed through the reference to that location by p p ampb cnanges p to refer to same location as b a b p p 2 p 7 a change value in location referenced by b printf b dn b a b p hloduku yFunc ons 18 Write a function to swap the values of two integers Why doesn t this function work What is the output ofthis program The answer is that the variables in the function including the parameters are local to the function they do not exist after the function executes so a and b are exactly the same before and after the function What we need is the function to have access to the actual locations of a and b and not just their values To do this we must pass the arguments by reference not by value To do this we must declare the formal parameters of the function to be pointers Inside the function we will use the dereferenced pointer to gain access to the actual parameter locations and hence their values So we will be passing not copies of the arguments but rather the address of the argument Modularity Functions 19 function to swap two integer values CORRECT VERSION include ltstdiohgt void swap int int function prototype int main void int a 3 b 7 printf d dn a b swapampa ampb 39 printf d dn a b return 0 void swap int X int y int temp tmp X Shown below are two identical functions to compute the cube of an integer number The first is done using the normal pass by value method and the second used the pass by reference technique int cubeByValue int n return n n n int main int num 5 printf number dn num num cubeByValuenum printf number cubed dn return 0 Modularity Functions 20 int cubeByReference int n n n int main int num 5 printf number dn num num cubeByValueampnum printf number cubed dn return 0 Often you will need a function to return more than one value to the caller This is easily accomplished with parameters that are passed by reference The following example illustrates a function that prompts the user for two integer values to be input function getData prompts the user for two input integers representing the length and width of a rectangle Outputs two integers corresponding to width and length void getData int length int width printf Enter the length scanf d length printf Enter the width scanf d width Calls to the function getData would be ofthe form getData ampthelength ampthewidth Calls to the function getData in the following form are illegal getData 8 7 or getDatathislength thiswidth3 Modularity Functions 21 Execute the following code by hand ie trace the code and show exactly what is produced by each printf statement in the main program as well as in the functions when they execute mystery program you tell me what it does include ltstdiohgt int f1 int a int b inf f2 int a int b intmain inta5b2c7d9 c f1 ampd a printf Main 1 a d bd cd ddn a b c d a f2 cd ampa printf Main 2 a d bd cd ddn a b c d b f1 amp0 8 printf Main 3 a d bd cd ddn a b c d d f2 b ampa printf Main 4 a d bd cd ddn a b c d int f1 int a int b a b 8 b b2 a printf ln f1 a d b dnquot a b return b a int r2 int a int b a b 1 b 37 b printf In f2 a d b dnquot a b return a Before looking at the next page try to trace through this code and see if you get the same output as shown on the next page Modularity Functions 22 Output from program on previous page Trace of the execution of this program that produced this output 1 2 L00 CDU I OOI G Execution begins in main with a 5 b 2 c 7 and d 9 Call function f1 passing address ofd and 5 value of a 1 In function f1 2 location referenced by a gets 58 3 3 b 52 3 13 4 print value at location a 3 value of b 13 5 returns into c the value b a 13 3 16 In Main print value of a 5 value of b 2 value of c 16 value of d 3 Call function f2 passing cd and address of a 1 In function f2 2 a value at location b same as a 51 6 3 value at location b 37 value at location b 375 32 4 print value of a 6 local value a location b 32 5 returns into a the value of local a 6 In Main print value of a 6 value of b 2 value of c 16 value ofd 3 Call function f1 passing address of c and value 8 1 In function f1 2 location referenced by a gets 88 O 3 b 82 O 16 4 print value at location a 0 value of b 16 5 returns into c the value 1616 O In Main print value of a 6 value of b 16 value of c 0 value ofd 3 Call function f2 passing 16 and address of a 1 In function f2 2 a value at location b 1 61 7 3 value at location b same as a 37 6 31 4 print value of a 7 local value at location b 31 5 returns into d the value of local a 7 In Main print value of a 31 value of b 16 value of c 0 value ofd 7 Modularity Functions 23