C++ Programming: Lists and Strings

Flashcards covering key concepts from a C++ programming lecture on lists, arrays, and strings.

List

A variable-length, linear collection of homogeneous elements.

Linear (in the context of a list)

Each list element (except the first) has a unique predecessor, and each element (except the last) has a unique successor

Constructors

Create a new instance (object) of an ADT.

Transformers

Change the state of one or more of the data values of an instance.

Observers

Allow client to observe the state of one or more of the data values of an instance without changing them.

Iterators

Allow client to access the data values in sequence.

List Transformer Operations

Insert, Delete, Sort

List Observer Operations

IsEmpty, IsFull, Length, IsPresent

List Iterator Operations

Reset, GetNextItem

Reset (Iterator)

Prepares for the iteration.

GetNextItem (Iterator)

Returns the next item in sequence.

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.

Selection Sort Algorithm

Find minimum value in data[passCount . . length-1] and swap minimum value with data[passCount]

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, and increment the length.

Delete Algorithm for SortedList ADT

Find the position of the element to be deleted from the sorted list, eliminate space occupied by the item being deleted by shifting up all the larger list elements, and decrement length.

Binary Search

Examines the element in the middle of the array to determine if the sought item, then continues accordingly.

Order of Magnitude (Big-O notation)

Describes the complexity of an algorithm according to the highest order of N that appears in its complexity expression.

O(1)

constant time

O(log2N)

logarithmic time

O(N)

linear time

O(N^2)

quadratic time

O(N^3)

cubic time

C String

A char array terminated by the null character ‘\0’.

Extraction operator >> (for C strings)

Skips any leading whitespace characters such as blanks and newlines, then reads successive characters into the array, stopping at the first trailing whitespace character, and adds the null character to the end of the string.

Function get() (for C strings)

Does not skip leading whitespace characters, reads successive characters (including blanks) into the array, stops when it either has read count characters, or it reaches the newline character ‘\n’, appends the null character to str. If newline is reached, it is not consumed by get, but remains waiting in the input stream.

Function ignore()

Can be used to consume any remaining characters up to and including the newline ‘\n’ left in the input stream by get.

strlen (C string function)

Integer length of string str (not including ‘\0’).

strcmp (C string function)

Negative, if str1 precedes str2 lexicographically; positive, if str1 follows str2 lexicographically; 0, if str1 and str2 characters same through ‘\0’.

strcpy (C string function)

Base address of toStr (usually ignored). Characters in string fromStr are copied to string toStr, up to and including ‘\0’, overwriting contents of string toStr.

typedef char String20[21]

Names String20 as an array type.