Objectives Objectives (continued)Why You Need to Know About…Data StructuresData Structures ArraysHow An Array Works How An Array Works (continued)Multidimensional Arrays Uses Of ArraysListsLinked lists Linked Lists (continued)Linked Lists (continued)Linked Lists (continued) Stacks Stacks (continued)QueuesQueues (continued)Trees Trees (continued) Searching a Binary TreeSearching a Binary Tree (continued)Sorting AlgorithmsSelection Sort Bubble Sort Other Types Of Sorts Other Type of Sorts (continued)One Last Thought SummarySummary (continued)Summary (continued)Connecting with Computer Science2Objectives • Learn what a data structure is and how it is used• Learn about single and multidimensional arrays and how they work• Learn what a pointer is and how it is used in data structures• Learn that a linked list allows you to work with dynamic informationConnecting with Computer Science3Objectives (continued)• Understand that a stack is a linked list and how it is used• Learn that a queue is another form of a linked list and how it is used• Learn that a binary tree is a data structure that stores information in a hierarchical order• Be introduced to several sorting routinesConnecting with Computer Science4Why You Need to Know About…Data Structures• Data structures organize the data in a computer– Efficiently access and process data• All programs use some form of data structure • Many occasions for using data structuresConnecting with Computer Science5Data Structures• Data structure: way of organizing data• Types of Data structures– Arrays, lists, stacks, queues, trees for main memory– Other file structures for secondary storage • Computer’s memory is organized into cells– Memory cell has a memory address and content– Memory addresses organized consecutively– Data structures hide physical implementationConnecting with Computer Science6Arrays• Array– Simplest memory data structure – Consists of a set of contiguous memory cells– Memory cells store homogeneous data– Data stored may be sorted or left as entered • Usefulness – Student grades, book titles, college courses, etc.– One variable name for large number of similar itemsConnecting with Computer Science7Connecting with Computer Science8How An Array Works• Declaration (definition): provide data type and size • Java example: int[ ] aGrades = new int[5];– “int[ ]” tells the computer array will hold integers– “aGrades” is the name of the array– “new” keyword specifies new array is being created– “int[5]” reserves five memory locations– “=” sign assigns aGrades as “manager” of the array– “;” (semicolon) indicates end of statement reached• Hungarian notation: standard used to name “aGrades”Connecting with Computer Science9Connecting with Computer Science10How An Array Works (continued)• Dimensionality– Dimensions: rows/columns of elements (memory cells)– aGrades has one dimension (like a row of mailboxes)• Manipulating one-dimensional arrays – First address (position) is lower bound: zero (0) – Next element offset by one from starting address– Index (subscript): integer placed in “[ ]” for access• Example: aGrades[0] = 50;– Upper bound “off by one” from size: four (4)Connecting with Computer Science11Connecting with Computer Science12Connecting with Computer Science13Multidimensional Arrays• Multidimensional arrays– Consists of two or more single-dimensional arrays– Multiple rows stacked on top of each other• Apartment building mailboxes• Tic-tac-toe boards • Definition: char[ ][ ] aTicTacToe = new char[3][3]; • Assignment: aTicTacToe[1][1] = ’X’; – place X in second row of the second column • Arrays beyond three dimensions difficult to manageConnecting with Computer Science14Connecting with Computer Science15Connecting with Computer Science16Connecting with Computer Science17Uses Of Arrays• Array advantages– Allows sequential access of memory cells– Retrieve/store data with name and data – Easy to implement – Simplifies program writing and reading• Limitations and disadvantages– Unlike classes, cannot store heterogeneous items– Lack ability to dynamically allocate memory – Searching unsorted arrays not efficientConnecting with Computer Science18Lists• List: dynamic data structure– Examples: class enrollment, cars being repaired, e-mail in-boxes – Appropriate whenever amount of data unknown or can change• Three basic list forms:– Linked lists– Queues– StacksConnecting with Computer Science19Linked lists• Linked list– Structure used for variable data set– Unlike an array, stores data non-contiguously – Maintains data and address of next linked cell– Examples: names of students visiting a professor, points scored in a video game, list of spammers • Linked lists are basis of advanced data structures– Queues and stacks– Each of these constructs is pointer basedConnecting with Computer Science20Linked Lists (continued)• Pointers: memory cells containing address as data– Address: location in memory• Illustration: Linked List game– Students sit in a circle with piece of paper– Paper has box in the upper left corner and center– Upper left box indicates a student number– Center box divided into two parts– Students indicate favorite color in left part of center– Professor has a piece of paper with a number onlyConnecting with Computer Science21Connecting with Computer Science22Linked Lists (continued)• Piece of paper represents a two-part node – Data (the first part, the color) – Pointer: where to go next (the student ID number)• Professor’s piece: head pointer with no data• Last student: pointer’s value is NULL• Inserting new elements– Unlike array, no resizing needed – Create new “piece of paper” with dual node structure– Realign pointers to accommodate new node (paper)Connecting with Computer Science23Connecting with Computer Science24Linked Lists (continued) • Similar procedure for deleting items – Modify pointer of element preceding target item– Students deleted from list without moving elements• Dynamic memory allocation – Linked lists more efficient than arrays– Memory cells need not be contiguousConnecting with Computer Science25Connecting with Computer Science26Stacks• Stack: Special form of a list – To store new items, “push” them onto the list – To retrieve current
View Full Document
Unlocking...