SOLUTION: Abstract Data Types | My Assignment Tutor

1Abstract Data TypesWeek 11Overview:1. What is Data Abstraction? What is ADT?2. Model for an Abstract Data Type3. Complex Number ADT Example4. How Well are ADTs Supported in C?5. C++6. ADT vs Object-Oriented Programming221.1 What is Data Abstraction? Concept of “Abstraction” Allows us to consider the high-level characteristics ofsomething without getting bogged down in the details For example: Process abstraction in proceduralprogramming like C, we can use (pre-defined)functions without concern how they really worksinside. Data Abstraction We know what a data type can do How it is done is hidden31.2 What is an Abstract DataType? Abstract Data Type (ADT) Defines a particular data structure in terms of data andoperations Offers an interface of the objects (instances of an ADT) An ADT consists of Declaration of data Declaration of operations Encapsulation of data and operations : data is hiddenfrom user and can be manipulated only by means ofoperations 431.3 ADT Implementation Implementaion of an Abstract Data Type (ADT)Hidden from the userSame ADT may be implemented in different waysin different languagesSome languages offer built-in ADTs and/orfeatures to be used to implement ADTs (userdefine types) ADTs support modular design which is veryimportant in software development52.1 Model for an ADT6Interface – OperationsData StructureSystem design with ADTs Problem definitonIdentification of ADTs(identify data or attributes) Specify ADT interactions Specify ADT operationsImplement ADTsIdentify object hierarchy (if using OOP)42.2 Clients and Manufacturers7implementationinterfaceADTmanufacturer’sresponsibilityclientclientclientuseTypes of Data structureData structure are classified into two type such as linearor non-linear.Linear: A data structure is said to be linear if its elementsform a sequence. The elements of linear data structurerepresents by means of sequential memory locations. Theother way is to have the linear relationship between theelements represented by means of pointers or links. ExArray and Link List.Non-linear: A data structure is said to be non-linear if itselements a hierarchical relationship between elementssuch as trees and graphs. All elements assign the memoryas random form and you can fetch data elements throughrandom access process. 85Operations that can be performed on thedata structures:9 1. Traversing- It is used to access each data item exactlyonce so that it can be processed. 2. Searching- It is used to find out the location of the dataitem if it exists in the given collection of data items. 3. Inserting- It is used to add a new data item in the givencollection of data items. 4. Deleting- It is used to delete an existing data item fromthe given collection of data items. 5. Sorting- It is used to arrange the data items in someorder i.e. in ascending or descending order in case ofnumerical data and in dictionary order in case ofalphanumeric data. 6. Merging- It is used to combine the data items of twosorted files into single file in the sorted form.2.3 Benefits Manufacturer Benefits:easy to modify, maintainprofitablereusable Client Benefits:simple to use, understandfamiliarcheapcomponent–based1063. Complex Number ADTExample A complex number has a real part and an imaginarypart. e.g.: 2+4i Interface (operations) ? create a complex number add, subtract, multiply, divide print a complex number test to see if something is complex etc.11Declare a complex number Interface:Complex c1, c2, c3; Possible Implementation (in C language ):struct complex {double real,imag;}typedef struct complex Complex;127Create a complex number Interface:c1 = create_complex(2, 3);/* conceptually, c1 = 2+3i */13Implementation:Complex create_complex(double real,double imag){ Complex c;c.real = real;c.imag = imag;return c;}148Add two complex numbers Interface:c3 = add_complex(c1, c2);/* conceptually, c3 = c1 + c2*/15Implementation:Complex add_complx(Complex c1,Complex c2){ Complex csum;csum.real = c1.real + c2.real;csum.imag = c1.imag + c2.imag;return csum;}169Using the Complex Number ADT#include /* type implementation */struct complex {double real,imag;typedef struct complex Complex;/* operation interface */Complex create_complex(double,double);Complex add_complex(Complex, Complex);/* other Complex prototypesprint_complex() . . .*/17continuedUsing the Complex Number ADTint main ( ){ Complex c1, c2, c3;c1 = create_complex(2,-3);c2 = create_complex(2,-3);c3 = add_complex(c1,c2);print_complex(c3);return 0;}/*Implementation of Complex functions */:18104. How Well are ADTs Supported in C? Does C enforce the use of the ADTs interface and thehiding of its implementation? No195. C++ and OOP C++ is a superset of C, which has addedfeatures to support object orientedprogramming (OOP) C++ offers STL (Standard Templates Library)providing a set generic data structures whichallow programmers to easily implementstandard data structures like queues, lists, andstacks. C++ supports classesthings very like ADTs Other OOP languages such as Java, Smalltalk20116. ADT vs Object-Oriented Programming (OOP) ADTs are not a part of a particular programminglanguage Rather they are implemented by a programmer to solvea particular problem or some class of problems In OOP, an ADT can be easily modeled as a class An instance as an object Data of ADT as properties or fields of a class Operations as methods ADT ≠ OOP Classes in OOP offers more features than ADTs :Inheritance (Superclass-Subclass), Polymorphisms, etc.21Books you can refer Wirth, N. (2004) Algorithms and Data Structures.Oberon. Cormen, T. (1990) Introduction to Algorithms. MIT Labs. Lafore, R. (2002) Data Structures and Algorithms inJava, second edition, Sams publisher, ISBN-13: 978-067232453622