Open main menu

Applied Programming/Lists and Tuples

Objectives and SkillsEdit

Objectives and skills for this lesson include:

ReadingsEdit

MultimediaEdit

ExamplesEdit

ActivitiesEdit

  1. Download Northwind Customers. Write a program to read the file and create a customers list, where each element in the list is a customer list or tuple.
  2. Provide an interface for the program above that allows the user to:
    • Display company name, contact name, and phone number for all customers sorted by company name.
    • Display contact name, company name, and phone number for all customers sorted by contact name.
    • Search for a given company name or part of a name and display matching records with fields labeled.
    • Search for a given contact name or part of a name and display matching records with fields labeled.
  3. For each of the above, use separate functions for each type of processing. Reuse functions where possible, such as in sorting and searching. Avoid using global variables by passing parameters and returning results. Include appropriate data validation and parameter validation. Add program and function documentation, consistent with the documentation standards for your selected programming language.

Lesson SummaryEdit

  • A data structure is a means to organize and store data for later retrieval and modification. It's typically implemented as a contiguous, homogeneous container of elements, either dynamic or fixed in size.[1]
  • Data structures include:
    • Arrays[1]
    • Lists or linked lists[1]
    • Records[1]
    • Unions[1]
    • Tagged unions, also called variant records, as well as discriminated or disjoint unions[1]
    • Classes[1]
  • An array holds elements that can be randomly accessed through the use of an index—without the need for sequential traversal.[2]
    • Typically, this index is zero-based, since the index is used to calculate an offset from the base address.[2]
  • A one-dimensional array is a type of linear array where access is limited to just one subscript which can either represent a row or column index.[2]
  • For a multidimensional array, the element with indices i, j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.[2]
  • Arrays are used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. Many databases, small and large, consist of (or include) one-dimensional arrays whose elements are records.[2]
    • Arrays can be used to implement other data structures, such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.[2]
  • Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms.[1]
  • A list can often be constructed by writing the items in sequence, separated by commas, semicolons, and/or spaces, within a pair of delimiters such as parentheses, brackets, braces, or angle brackets. Lists are then able to expand and shrink. They are stored dynamically in memory.[3]
  • A list is an abstract data type—a mathematical model for implementing a concrete representation—that holds a finite number of items or elements.[3]
    • Often, this is realized through the use of a linked list data structure, where each node contains not just data but also a link to the next (and sometimes previous) node.[3]
    • Lists can hold data, but they can also contain any number of sublists, which are capable of having their own sublists further down the chain.[3]
  • A record is a data structure that collects together different variables, usually of different types.[4]
  • A record may sometimes have a key (or several). This key is a field or set of fields in the record that serves as the record's identifier. A unique key is often called the primary key, or simply the record key.[4]
    • If you were storing employee records, you could use the unique company ID field to look-up employees without knowing any other information (remember that even names may conflict).[4]
  • Modern computer languages usually allow the programmer to define their own record type.[4]
  • When you define a record type, you specify the data type of each field and the associated identifier through which it can be accessed.[4]
  • Records may exist in any medium, but they are often written to persistent storage devices such as magnetic tapes or hard disks. Records are fundamental components of many data structures, especially linked data structures.[4]
  • Record operations include but are not limited to:
    • Declaration of a new record, including the relative position in the record, type, and name of each field.
    • Declaration and construction of a variable as belonging to a given record type.[4]
    • Selection of a record field by using an explicit name.[4]
    • Assignment of a record to another.[4]
    • Comparison of two records for equality.[4]
  • You could even view the parameters of a function as record fields which receive values (the arguments).[4]
  • In Python, tuples are much like a list; the important distinction is that tuples are immutable, whereas lists are not.[5]
    • The values stored in Python tuples can be of any type; elements are indexed by non-negative integers.[5]

Key TermsEdit

array
A container of elements stored in contiguous space, typically of the same data type.[1]
class
A data structure that contains members, like a record, as well as various methods which operate on these members.[1]
data structure
A collection of related values, often organized in lists, dictionaries, tuples, etc.[6]
field
A variable which is one of multiple parts of a record.[4]
member
A single datum of a record; for example, the 'Name' field of a 'Person' record.[4]
hash table (hash map)
is a data structure which implements an associative array abstract data type, a structure that can map keys to values.[7]
heap
Is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.[8]
linked list
A collection of elements called nodes, where each node has a value and points to the next node in the list (and sometimes the previous).[1]
list
A list is an abstract data type—a mathematical model for implementing a concrete representation—that holds a finite number of items or elements.[3]
record
A structure used to collect multiple variables, often of different types stored as fields.[4]
struct
Another word for a record.[4]
tuple
Fundamentally similar data structures that usually collect heterogeneous, yet related values or 'fields' into one container.[4]
tagged union
A union that contains one additional field indicating the current type for enhanced type safety.[1]
union
A data structure where a number of primitive types may be stored in concert, similar to a struct or a record.[1]

See AlsoEdit

ReferencesEdit

  1. 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 Wikipedia: Data structure
  2. 2.0 2.1 2.2 2.3 2.4 2.5 Wikipedia: Array data structure
  3. 3.0 3.1 3.2 3.3 3.4 Wikipedia: List (abstract data type)
  4. 4.00 4.01 4.02 4.03 4.04 4.05 4.06 4.07 4.08 4.09 4.10 4.11 4.12 4.13 4.14 4.15 Wikipedia: Record (computer science)
  5. 5.0 5.1 Python: Tuples
  6. "Chapter 10 | Python For Everyone | Trinket". books.trinket.io. Retrieved 2018-07-10.
  7. Wikipedia: Hash table
  8. Wikipedia: Heap (data structure)