C++ Programming: Lists and Strings

Chapter 13: Applied Arrays - Lists and Strings

Meaning of a List

• A list is a variable-length, linear collection of homogeneous elements.
• Linear means each element (except the first) has a unique predecessor, and each element (except the last) has a unique successor.

ADT Operations

Basic Kinds of ADT Operations

• Constructors: Create a new instance (object) of an ADT.
• Transformers: Change the state of one or more data values of an instance.
• Observers: Allow the client to observe the state of one or more data values of an instance without changing them.
• Iterators: Allow the client to access the data values in sequence.

ADT List Operations

• Transformers
  • Insert
  • Delete
  • Sort
• Observers
  • IsEmpty
  • IsFull
  • Length
  • IsPresent
• Iterator
  • Reset: Prepares for iteration.
  • GetNextItem: Returns the next item in sequence.
  • No transformer can be called between calls to GetNextItem (to maintain the integrity of the iteration).

ADT Unsorted List

• Data Components
  • length: Number of elements in the list.
  • data[0..MAX_LENGTH - 1]: Array of list elements.
  • currentPos: Used in iteration.

Array-Based List Class

• Includes functions like Reset, IsFull, Length, IsPresent, Delete, IsEmpty, Insert, GetNextItem, and SelSort.
• Private data members: length, data, and currentPos.

List Implementation (list.h)

• Specification file for array-based list.
• MAX_LENGTH is defined as 50.
• ItemType is defined as int.
• Class List is declared.
• Public member functions:
  • List(): Constructor.
  • bool IsEmpty() const
  • bool IsFull() const
  • int Length() const: Returns the length of the list.
  • void Insert(ItemType item)
  • void Delete(ItemType item)
  • bool IsPresent(ItemType item) const
  • void SelSort()
  • void Reset()
  • ItemType GetNextItem()
• Private data members:
  • int length: Number of values currently stored.
  • ItemType data[MAX_LENGTH]
  • int CurrentPos: Used in iteration.

Sorted and Unsorted Lists

• Unsorted List: Elements are placed into the list in no particular order.
• Sorted List: List elements are sorted in some way (either numerically or alphabetically).

List Implementation (list.cpp)

• Implementation file for array-based list.
• Includes <list.h> and <iostream>.
• Uses namespace std.
• Length() function returns the length.
  
  int List::Length() const {
  return length;
  }
  
• IsFull() function returns true if length is equal to MAX_LENGTH, and false otherwise.
  
  bool List::IsFull() const {
  return (length == MAX_LENGTH);
  }
  
• List() constructor sets length to 0.
  
  List::List() {
  length = 0;
  }
  
• Insert() function inserts an item at the end of the list and increments length.
  
  void List::Insert(ItemType item) {
  data[length] = item;
  length++;
  }
  
• IsEmpty() function returns true if length is equal to zero, and false otherwise.
  
  bool List::IsEmpty() const {
  return (length == 0);
  }
  
• IsPresent() function searches the list for an item and returns true if found, false otherwise.
  
  bool List::IsPresent(ItemType item) const {
  int index = 0;
  while (index < length && item != data[index])
  index++;
  return (index < length);
  }
  
• Delete() function deletes the first occurrence of an item from the list and decrements length.
  
  void List::Delete(ItemType item) {
  int index = 0;
  while (index < length && item != data[index])
  index++;
  if (index < length) {
  data[index] = data[length - 1];
  length--;
  }
  }
  
• Reset() function initializes currentPos to 0.
  
  void List::Reset() {
  currentPos = 0;
  }
  
• GetNextItem() function returns the next item in sequence.
  
  ItemType List::GetNextItem() {
  ItemType item;
  item = data[currentPos];
  if (currentPos == length - 1)
  currentPos = 0;
  else
  currentPos++;
  return item;
  }
  

Selection Sort

• Examines the entire list to select the smallest element.
• Places that element where it belongs (with array subscript 0).
• Examines the remaining list to select the smallest element from it, and so on.
• Algorithm:
  
  FOR passCount going from 0 through length - 2
  Find minimum value in data[passCount .. length-1]
  Swap minimum value with data[passCount]
  

    void List::SelSort() {
        ItemType temp;
        int passCount;
        int sIndx;
        int minIndx;

        for (passCount = 0; passCount < length - 1; passCount++) {
            minIndx = passCount;
            for (sIndx = passCount + 1; sIndx < length; sIndx++)
                if (data[sIndx] < data[minIndx])
                    minIndx = sIndx;
            temp = data[minIndx];
            data[minIndx] = data[passCount];
            data[passCount] = temp;
        }
    }

Sorted List

Specification File (slist.h)

• Similar to the unsorted list, but maintains elements in sorted order.
• Includes functions like Insert and Delete that must ensure the list remains sorted.

Implementation Considerations

• Insert and Delete member functions must be modified to maintain the sorted order.

Insert Algorithm for SortedList ADT

• Create space for the new item by shifting down all the larger list elements.
• Put the new item in the list.
• Increment length.

Implementing SortedList Member Function Insert

    void SortedList::Insert(ItemType item) {
        int index;
        index = length - 1;
        while (index >= 0 && item < data[index]) {
            data[index + 1] = data[index];
            index--;
        }
        data[index + 1] = item;
        length++;
    }

Delete Algorithm for SortedList ADT

• Find the position of the element to be deleted.
• Eliminate space by shifting up all the larger list elements.
• Decrement length.

Implementing SortedList Member Function Delete

    void SortedList::Delete(ItemType item) {
        bool found;
        int position;
        int index;
        BinSearch(item, found, position);
        if (found) {
            for (index = position; index < length - 1; index++)
                data[index] = data[index + 1];
            length--;
        }
    }

Improving Member Function IsPresent

• For unsorted lists, a sequential search is used.
• For sorted lists, a binary search can be used to improve efficiency.

Binary Search

• Examines the middle element of the array.
• If it's the sought item, stop searching.
• If the middle element is too small, look in the second half of the array.
• If the middle element is too large, look in the first half of the array.
• Repeat until the item is found or there's nowhere else to look.

    void SortedList::BinSearch(ItemType item, bool& found, int& position) const {
        int middle;
        int first = 0;
        int last = length - 1;
        found = false;

        while (last >= first && !found) {
            middle = (first + last) / 2;
            if (item < data[middle])
                last = middle - 1;
            else if (item > data[middle])
                first = middle + 1;
            else
                found = true;
        }
        if (found)
            position = middle;
    }

Implementing More Efficient IsPresent

    bool SortedList::IsPresent(ItemType item) const {
        bool found;
        int position;
        BinSearch(item, found, position);
        return found;
    }

Comparison of Sequential and Binary Searches

Order of Magnitude of a Function

• Describes the complexity of an algorithm according to the highest order of N that appears in its complexity expression; also known as Big-O notation.

Common Orders of Magnitude

• O(1) - constant time
• O(log_2N) - logarithmic time
• O(N) - linear time
• O(N^2) - quadratic time
• O(N^3) - cubic time

Big-O Comparison of List Operations

C Strings

• C++ also has another library of string functions for C strings that can be accessed by #include <cstring>. In addition to the string class from the standard library accessed by #include <string>.
• A C string is a char array terminated by the null character 0 (with ASCII value 0).
• Example initializations:
  cpp char message[8] = { 'H', 'e', 'l', 'l', 'o', '\0' }; char message[8] = "Hello";

Char vs. C String

• 'A' has data type char and is stored in 1 byte.
• "A" is a C string of 2 characters and is stored in 2 bytes ('A' and '\0').

Aggregate C String I/O in C++

• I/O of an entire C string is possible using the array identifier with no subscripts and no looping.
• Example:
  cpp char message[8]; cin >> message; cout << message;

Extraction Operator >>

• Skips leading whitespace characters.
• Reads successive characters into the array.
• Stops at the first trailing whitespace character (which is not consumed).
• Adds the null character to the end of the string.

Function get()

• inFileStream.get(str, count + 1)
• Does not skip leading whitespace characters.
• Reads successive characters (including blanks) into the array.
• Stops when it has read count characters or reaches the newline character '\n', whichever comes first.
• Appends the null character to str.
• If newline is reached, it is not consumed but remains waiting in the input stream.

Function ignore()

• ignore can be used to consume any remaining characters up to and including the newline '\n' left in the input stream by get.
  cpp cin.get(string1, 81); cin.ignore(30, '\n'); cin.get(string2, 81);

String Function Prototypes in <cstring>

• int strlen(char str[]): Returns the integer length of string str (not including '\0').
• int strcmp(char str1[], char str2[]):
  • Returns a negative value if str1 precedes str2 lexicographically.
  • Returns a positive value if str1 follows str2 lexicographically.
  • Returns 0 if str1 and str2 characters are the same through '\0'.
• char *strcpy(char toStr[], char fromStr[]):
  • Copies characters in string fromStr to string toStr, up to and including '\0', overwriting contents of string toStr.
  • Returns the base address of toStr (usually ignored).

Using typedef with Arrays

    typedef char String20[21];
    String20 myName;
    String20 yourName;
    bool isSeniorCitizen;