Data Structures and Algorithms Second Year, First Semester, 2012/2013 List and StringList A list is a sequential data structure, i.e. a collection of items accessible one after another beginning at the head and ending at the tail. It is a widely used data structure for applications which do not need random access. It differs from the stack and queue data structures in that additions and removals can be made at any position in the list.It is used a one-dimensional array or 'vector' to store a list, each element of the array typically being a record containing data on an item. For example the following array, in 'C++', could store a list of students and their marks.Typedef struct person { char name[21];int mark;} PERSON; PERSON student[100]; location student[0] 0 studeni[1] 1 och 336 student[99] 99The main primitive operations of a list are known as: Add adds a new node Set updates the contents of a node Remove removes a node Get returns the value at a specified index IndexOf returns the index in the list of a specified elementAdditional primitives can be defined: IsEmpty reports whether the list is empty IsFull reports whether the list is full Initialise creates/initialises the list Destroy deletes the contents of the list (may be implemented by re-initialising the list)A constructor is required before a list can be used: * constructor List :: List( ); The List has been created and is initialized to be empty. The next operation takes a list that already exists and empties it: + void List :: clear( }; All List entries have been removed; the List is empty. Next come the operations for checking the status of a list: mpty( ) const; n returns true or false according to whether the List is empty or not. bool Lis The functi + bool List :: full() const; The function returns true or false according to whether the List is full or not, + int List :: size( ) const; The function returns the number of entries in the List.The order of items stored in a list using an array is determined by the sequential positioning of the items in memory, ie consecutive items in the list are stored in consecutive memory locations. The use of a static array implies that the list will have a fixed maximum size determined by the variable declaration. This means that the maximum size must be determined in advance and the program written to allow for this even though it may frequently use only a small portion of the array. Alternatively space for a dynamic array can be calculated and allocated at runtime using malloc() before storing the items if the number of records is already known.A more important problem is met when one attempts to add an item to the list whilst preserving the order of the items. for example, to add the name BOB to the following list, it is necessary to copy each array element from student [3] onwards up one position in order to insert the new record. This problem will meet when studying the Insertion Sort algorithm. A similar problem exists when deleting records from the list.student[0] : _ANDY | 90 | ANDY 90 pert 73 Stdentlt] | peat 73 | FRED 84 studentie] | BoB | 62 =| | student[3] FRED 84 itemInitialise Creates the structure — i.e. ensures that the structure exists but contains no elements e.g. Initialise(L) creates a new empty queue ExamplesExample1 * Initialise L * Add e.g. Add(1,X,L) adds the value X to list Lat position 1 (the start of the list is position 0), shifting subsequent elements up * Set e.g. Set(2,Z,L) updates the values at position 2 to be Z + Remove e.g. Remove(Z,L) removes the node with value Z * Get e.g. Get(2,L) returns the value of the third node, i.e. C + Indexof e.g. IndexOf(X,L) returns the index of the node with value X, i.e. 1String Most languages either have a built in string datatype or a standard library, so rare to create own string ADT.A string datatype should have operations to: — Return the nth character in a string. — Set the nth character in a string to c++. — Find the length of a string. — Concatenate two strings. “Alison” + “ Cawsey” = “Alison Cawsey” — Copy a string. — Delete part of a string. (“Alison Cawsey” _ Alison”) — Modify and compare strings in other waysString Processing Algorithms The String processing algorithms are algorithms for processing sequences of characters or symbols eg., — File compression - take a sequence, encode it as a shorter sequence. — Cryptography - take a sequence, encode it so enemies can’t read it! — String search - search for occurrences of one sequence within another. — Pattern matching - find out if sequence matches some pattern. — Parsing - Work out structure of a sequence, in terms of a grammar.Copy sequence of characters from string Copies a sequence of characters from the string content to the array pointed by s. This sequence of characters is made of the characters in the string that start at character position pos and span n characters from there. int main () { size_t length; char buffer[20]; string str ("Test string..."); length=str.copy(buffer,6,5); buffer[length]="\0'; cout << "buffer contains: " << buffer << "\n"; return 0; }String comparison Compares the content of this object (or a substring of it, known as compared (sub)string) to the content of a comparing string, which is formed according to the arguments passed. The member function returns 0 if all the characters in the compared contents compare equal, a negative value if the first character that does not match compares to less in the object than in the comparing string, and a positive value in the opposite case. Notice that for string objects, the result of a character comparison depends only on its character code (i.e., its ASCII code), so the result has some limited alphabetical or numerical ordering meaning.int main (){ string str1 ("green apple"); string str2 ("red apple"); if (str1.compare(str2) != 0) cout << str1 << "is not" << str2 << ""\n"; if (str1.compare(6,5,"apple") == 0) cout << "still, "<< str1 <<" is an apple\n"; if (str2.compare(str2.size()-5,5,"apple") == 0) cout << "and " << str2 << "is also an apple\n"; if (str1.compare(6,5,str2,4,5) == 0) cout << "therefore, both are apples\n"; return O; }String Matching String matching is fundamental to database and text processing applications. Every text editor must contain a mechanism to search the current document for arbitrary strings. Example: -Match a word study * Str1 (input) = You will always have a study, my study, for the study the study is studying as study itself. * Str2 (output) = The matching words are:Clear string The string content is set to an empty string, erasing any previous content and thus leaving its size at 0 characters. int main (){ string str; char c; cout << "Please type some lines of text. Enter a period to finish:\n"; do{ c=cin.get(); str+=c; if ( n') {cout << str; str.clear(); } } while (cl=".'); return O; }String length Returns a count of the number of characters in the string. int main (){ string str ("Test string"); cout << "The length of str is " << str.length() << characters.\n"; return O; }Get C string equivalent Generates a null-terminated sequence of characters (c-string) with the same content as the string object and returns it as a pointer to an array of characters. A terminating null character is automatically appended. int main (){ char * cstr, *p; string str ("Please split this phrase into tokens"); cstr = new char [str.size()+1]; strcpy (cstr, str.c_str()); //cstr now contains a c-string copy of str p=strtok (cstr,""); while (p!=NULL) { cout < #include void main() { string s2 = "string"; string s3 = "this"; cout << s2.length()<< s2+s3 << endl; $3 += s2; s3.insert(4, "is a"); cout << $3; int x = strlen(s2); s3.replace(0, 4, "that"); cout << s3; }The end Any question?