Data structures and algorithms difference

data structures and algorithms exam questions and data structures and algorithms 1 sorting and searching
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
ECE 250 Algorithms and Data Structures Data Structures and Algorithms Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Data Structures and Algorithms 2 2.2 Outline This topic will describe: – The concrete data structures that can be used to store information – The basic forms of memory allocation • Contiguous • Linked • Indexed – The prototypical examples of these: arrays and linked lists – Other data structures: • Trees • Hybrids • Higher-dimensional arrays – Finally, we will discuss the run-time of queries and operations on arrays and linked listsData Structures and Algorithms 3 2.2.1 Memory Allocation Memory allocation can be classified as either – Contiguous – Linked – Indexed Prototypical examples: – Contiguous allocation: arrays – Linked allocation: linked listsData Structures and Algorithms 4 Memory Allocation Contiguous, adj. Touching or connected throughout in an unbroken sequence. Meriam Webster Touching, in actual contact, next in space; meeting at a common boundary, bordering, adjoining. www.oed.comData Structures and Algorithms 5 2 2.2 .2.1 .1.1 Contiguous Allocation An array stores n objects in a single contiguous space of memory Unfortunately, if more memory is required, a request for new memory usually requires copying all information into the new memory – In general, you cannot request for the operating system to allocate to you the next n memory locationsData Structures and Algorithms 6 Linked Allocation Linked storage such as a linked list associates two pieces of data with each item being stored: – The object itself, and – A reference to the next item • In C++ that reference is the address of the next nodeData Structures and Algorithms 7 Linked Allocation This is a class describing such a node template typename Type class Node private: Type element; Node next_node; public: // ... ;Data Structures and Algorithms 8 Linked Allocation The operations on this node must include: – Constructing a new node – Accessing (retrieving) the value – Accessing the next pointer Node( const Type& = Type(), Node = nullptr ); Type retrieve() const; Node next() const; Pointing to nothing has been represented as: C NULL Java/C null C++ (old) 0 C++ (new) nullptr Symbolically ØData Structures and Algorithms 9 Linked Allocation For a linked list, however, we also require an object which links to the first object The actual linked list class must store two pointers – A head and tail: Node head; Node tail; Optionally, we can also keep a count int count; The next_node of the last node is assigned nullptrData Structures and Algorithms 10 Linked Allocation The class structure would be: template typename Type class List private: NodeType head; NodeType tail; int count; public: // constructor(s)... // accessor(s)... // mutator(s)... ;Data Structures and Algorithms 11 Indexed Allocation With indexed allocation, an array of pointers (possibly NULL) link to a sequence of allocated memory locations Used in the C++ standard template library Computer engineering students will see indexed allocation in their operating systems courseData Structures and Algorithms 12 Indexed Allocation Matrices can be implemented using indexed allocation: 1 2 3   456 Data Structures and Algorithms 13 Indexed Allocation Matrices can be implemented using indexed allocation – Most implementations of matrices (or higher-dimensional arrays) use indices pointing into a single contiguous block of memory Column-major order Row-major order 1 2 3   456  C, Python Matlab, FortranData Structures and Algorithms 14 2.2.2 Other Allocation Formats We will look at some variations or hybrids of these memory allocations including: – Trees – Graphs – Deques (linked arrays) – inodesData Structures and Algorithms 15 Trees The linked list can be used to store linearly ordered data – What if we have multiple next pointers? A rooted tree (weeks 4-6) is similar to a linked list but with multiple next pointersData Structures and Algorithms 16 Trees A tree is a variation on a linked list: – Each node points to an arbitrary number of subsequent nodes – Useful for storing hierarchical data – We will see that it is also useful for storing sorted data – Usually we will restrict ourselves to trees where each node points to at most two other nodesData Structures and Algorithms 17 Graphs Suppose we allow arbitrary relations between any two objects in a container 2 – Given n objects, there are n– n possible relations 2 nn • If we allow symmetry, this reduces to 2 – For example, consider the networkData Structures and Algorithms 18 Arrays Suppose we allow arbitrary relations between any two objects in a container – We could represent this using a two-dimensional array A B C D E F G H I J K L – In this case, the matrix is symmetric A × × × B × × × × × C × × × × × × D × × × E × × F × × G × × × H × × × I × × J × × × K × × × L × × ×Data Structures and Algorithms 19 Array of Linked Lists Suppose we allow arbitrary relations between any two objects in a container – Alternatively, we could use a hybrid: an array of linked lists A B C D E F G H I J K LData Structures and Algorithms 20 Linked Arrays Other hybrids are linked lists of arrays – Something like this is used for the C++ STL deque container For example, the alphabet could be stored either as: – An array of 26 entries, or – A linked list of arrays of 8 entries