1CISC181 Introduction to Computer ScienceDr McCoy1Dr. McCoyLecture 13October 13, 2009Repeated Slides• Some of the following slides are repeated from lecture 8 – character strings/character arrays2Storing Strings in Character Arrays• Character arrays may be initialized using a string literal:Char name[ ] = “Jane”;Initializes the char array“name”to hold the3Initializes the char array name to hold the individual characters J-a-n-e plus a special string termination character called the null character writte ‘\0’So, name is a 5 character array.Strings in Character Arrays• An alternative:char name[ ] = {‘J’, ‘a’, ‘n’, ‘e’, ‘\0’};Citkhi h4•Common mistake –when using a char array to hold strings, forgetting to leave the extra spot for the null termination character.54.4 Examples Using Arrays• Strings (more in ch. 5) KFM – note Ch 9 in Savitch– Arrays of characters– All strings end with null ('\0')–Examples 2003 Prentice Hall, Inc. All rights reserved.• char string1[] = "hello";– Null character implicitly added– string1 has 6 elements • char string1[] = { 'h', 'e', 'l', 'l', 'o', '\0’ };– Subscripting is the sameString1[ 0 ] is 'h'string1[ 2 ] is 'l'Reading Character Strings• Character arrays input and output are straightforward. Can read a character string directly from the keyboard:char last_name[20];cin >> last name;6cin >> last_name;NOTE: no indication last_name is an array in the input statement!NOTE: the read-in string must be at most 19 characters long else will have problems!• Character array output:cout << last_name;274.4 Examples Using Arrays• Input from keyboardchar string2[ 10 ];cin >> string2;– Puts user input in string• Stops at first whitespace character•Addsnullcharacter 2003 Prentice Hall, Inc. All rights reserved.•Adds nullcharacter– If too much text entered, data written beyond array• We want to avoid this (section 5.12 explains how)• Printing strings– cout << string2 << endl;• Does not work for other array types– Characters printed until null foundOutline8fig04_12.cpp(1 of 2)1 // Fig. 4_12: fig04_12.cpp2 // Treating character arrays as strings.3 #include <iostream>4 5 using std::cout;6 using std::cin;7 using std::endl;8 9 int main()10 {11 char string1[ 20 ], // reserves 20 characters12 char string2[] = "string literal"; // reserves 15 characters13 14 // read string from user into array string215 cout << "Enter the string \"hello there\": ";Two different ways to declare strings. string2 is initialized, and its size determined automatically .Examples of reading strings from the keyboard and printing them out. 2003 Prentice Hall, Inc.All rights reserved.16 cin >> string1; // reads "hello" [space terminates input]17 18 // output strings19 cout << "string1 is: " << string1 20 << "\nstring2 is: " << string2;21 22 cout << "\nstring1 with spaces between characters is:\n";23 pgOutline9fig04_12.cpp(2 of 2)fig04_12.cppoutput (1 of 1)24 // output characters until null character is reached25 for ( int i = 0; string1[ i ] != '\0'; i++ )26 cout << string1[ i ] << ' '; 27 28 cin >> string1; // reads "there"29 cout << "\nstring1 is: " << string1 << endl;30 31 return 0; // indicates successful termination32 33 } // end mainEnter the string "hello there": hello therestring1 is: hellostring2 is: string literalstring1 with spaces between characters is:Can access the characters in a string using array notation. The loop ends when the nullcharacter is found. 2003 Prentice Hall, Inc.All rights reserved.h e l l ostring1 is: thereSome recursive functions with arrays• Let’s step through some examples• What to watch for:–Programming methodology –starting with understanding of the problem (a function is supposed to handle), writing header with documentation, writing a driver program with simple test cases, writing the function, expand.10Palindromes (D&D 4.32)• A palindrome is a string that is spelled the same way forwards and backwards. Some examples of palindromes are “radar”, “able was I ere I sawelba”(if blanks arewas I ere I saw elba (if blanks are ignored), “billib”, and “a man a plan a canal panama” (if blanks are ignored).11• Write a recursive function testPalindromethat returns true if the string stored in first parameter is a palindrome, and falseotherwiseotherwise.• The function should take 3 arguments – a (const) character array, the index to the left end of the string, the index to the right end of the string.123• Can you write a main program that will enable this function to be used when the string read in actually contains spaces?13Some recursive functions with arrays• From D&D 4.37 – Printing a string backwards.• Write a recursive function stringReversethat takes a character array containing athat takes a character array containing a string as an argument, prints the string backwards, and returns nothing. The function should stop processing and return when the terminating null character is encountered.14BinarySearch D&D 4.34154.8 Searching Arrays: Linear Search and Binary Search• Search array for a key value• Linear search– Compare each element of array with key value16value• Start at one end, go to other– Useful for small and unsorted arrays• Inefficient• If search key not present, examines every element4.8 Searching Arrays: Linear Search and Binary Search• Binary search– Only used with sorted arrays– Compare middle element with key•If equal match found17•If equal, match found• If key < middle– Repeat search on first half of array• If key > middle– Repeat search on last half– Very fast • At most N steps, where 2 > # of elements• 30 element array takes at most 5 steps2>30N5Arguments to Binary Search• The (const) array to be searched• The key (value) to look for• Low_index• High_index184Example• A[0] = 1• A[1] = 2• A[2] = 4• A[3] = 8•A[4]=16A[4] 16• A[5] = 32• A[6] = 64• A[7] = 128• A[8] = 256• A[9] = 51219SelectionSort D&D 4.31• A selection sort searches an array looking for the smallest element in the array. Then, the smallest element is swapped with the first element of the array Thewith the first element of the array. The process is repeated for the subarraybeginning with the second element of the