[SOLVED] CS代写 Abstract Data Types: Lists 1

Abstract Data Types: Lists 1
The List ADT
A List interface and its implementation: Array List
Structured Programming 1110/1140/6710

Copyright By PowCoder代写加微信 assignmentchef

Abstract Data Types: Lists A1
Abstract Data Types (ADTs)
Abstract data types describe the behaviour (semantics) of a data type without specifying its implementation. An ADT is thus abstract, not concrete.
A container is a very general ADT, serving as a holder of objects. A list is an example of a specific container ADT.
An ADT is described in terms of the semantics of the operations that may be performed over it.
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
The List ADT
The list ADT is a container known mathematically as a finite sequence of elements. A list has these fundamental properties:
• duplicatesareallowed • order is preserved
A list may support operations such as these:
• create: construct an empty list
• add: add an element to the list
• is empty: test whether the list is empty
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
Our List Interface
We will explore lists using a simple interface:
public interface List { void add(T value);
T get(int index);
int size();
T remove(int index);
void reverse(); }
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
void add(T value); T get(int index); int size();
T remove(int index); void reverse(); String toString();
ABCD4 A B CD C DA B DCA
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
List Implementation
– Fast lookup of any element
– A little messy to grow and contract
• Linkedlist
– Logical fit to a list, easy to grow, contract
– Need to traverse list to find arbitrary element
Structured Programming 1110/1140/6710

Abstract Data Types: Lists 2
A List interface and its implementation: Linked List
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A2
List Implementation: Linked Lists
– Fast lookup of any element
– A little messy to grow and contract
• Linkedlist
– Logical fit to a list, easy to grow, contract
– Need to traverse list to find arbitrary element
public class LinkedList { private class LLNode {
LLNode next;
LLNode start;
LLNode end;
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A2
Linked List Reversal
CBA start end
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A2
Linked List Reversal
Pointer reversal
reverse end
ABCD start
Structured Programming 1110/1140/6710

Abstract Data Types: Sets
The Set ADT A Set Interface
Structured Programming 1110/1140/6710

Abstract Data Types: Sets A3
The Set ADT
The set ADT corresponds to a mathematical set. A set has these fundamental properties:
• duplicatesarenotallowed • order is not preserved
A set may support operations such as these:
• create:constructanemptyset
• add:addanelementtotheset
• contains:doesthesetcontainagivenelement • remove: remove an element from the set
Structured Programming 1110/1140/6710 23

Abstract Data Types: Sets A3
Our Set Interface
We will explore sets using a simple interface :
public interface Set { boolean add(T value); boolean contains(T value); int size();
boolean remove(T value); }
Structured Programming 1110/1140/6710 24

Abstract Data Types: Hash Tables
Hash Table Implementation of a Set 1
Structured Programming 1110/1140/6710

Abstract Data Types: Hash Table A4
Hash Tables
A hash table stores (key, value) pairs, using a hash function to map a key into a table. Key challenges are: a) dealing with hash collisions, and b) dealing with load (how big to make the table).
Two broad approaches: • Separate chaining
– Hash table entries are lists. (key, values) are in lists.
• Openaddressing
– Hash table entries are (key, value) pairs.
– Collisions resolved by probing – e.g. find next empty slot
Structured Programming 1110/1140/6710 28

Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710

Abstract Data Types: Hash Table A4
fruit.add(“apobaoparerppnaralnarieg”cn”oae)e)”t”)”))
Structured Programming 1110/1140/6710

fruit.contains(“fmoiraangg”no)ge”)”)
Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710

Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710 32

Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710 33

Abstract Data Types: Hash Table A4
fruit.contains(“gfoiraga”npge)”e”))
Structured Programming 1110/1140/6710 34

Abstract Data Types: Trees
The Tree ADT Implementation of a Set 2
Introduction to Software Systems 1110/1140/6710

Abstract Data Types: Trees A5
The Tree ADT
The tree ADT corresponds to a mathematical tree. A tree is defined recursively in terms of nodes:
• Atreeisanode
• Anodecontainsavalueandalistoftrees. • Nonodeisduplicated.
Introduction to Software Systems 1110/1140/6710 14

Abstract Data Types: Trees A5
Binary Search Tree
A binary search tree is a tree with the following additional properties: • Eachnodehasatmosttwosub-trees
• Nodesmaycontain(key,value)pairs(orjustkeys)
• Keysareorderedwithinthetree:
– The left sub-tree only contains keys less than the node’s key
– The right sub-tree only contains keys greater than the node’s key
Introduction to Software Systems 1110/1140/6710 15

Abstract Data Types: Trees A5
peach fruit
Introduction to Software Systems 1110/1140/6710 16

Abstract Data Types: Trees A5
Introduction to Software Systems 1110/1140/6710 17

Abstract Data Types: Trees A5
fruit.contains(“fgoirga”pn)eg”e)”)
Introduction to Software Systems 1110/1140/6710 18

Abstract Data Types: Maps
The Map ADT
A Map interface and its implementation ADT Recap
Structured Programming 1110/1140/6710

Abstract Data Types: Maps A6
First-principles implementation of three Java container types: • List
– ArrayList, LinkedList implementations (A1, A2) • Set
– HashSet, BSTSet implementations (A3, A4, A5) • Map
– HashMap, BSTMap implementations (A6) Introduced hash tables, trees (A4, A5)
Structured Programming 1110/1140/6710 12

Abstract Data Types: Maps A6
The Map ADT (A.K.A. Associative Array)
A map consists of (key, value) pairs
• Each key may occur only once in the map
• Values are retrieved from the map via the key • Values may be modified
• Key, value pairs may be removed
Structured Programming 1110/1140/6710 13

Abstract Data Types: Maps A6
Our Map Interface
We will explore maps using a simple interface:
public interface Map { V put(K key, V value);
V get(K key);
V remove (K key);
int size(); }
Structured Programming 1110/1140/6710 14

Abstract Data Types: Maps A6
fruit.pgpueut(“oagrpraranipgceeo””t,,”)73..0500))
Structured Programming 1110/1140/6710 15

Abstract Data Types: Maps A6
fruit.pgpueut(“oagrpraranipgceeo””t,,”)73..0500))
Structured Programming 1110/1140/6710 16

程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]