CSCI 210 Data Structures & Algorithms

CSCI 210 Data Structures & Algorithms

CSCE 210 Data Structures and Algorithms Prof. Amr Goneid AUC Part R3. Dictionaries(1): Key Tables and Lists Prof. Amr Goneid, AUC 1 Dictionaries(1):Key Tables and Lists The Key Table ADT Key Table The Key Table Class Definition

Key Table Class implementation Example Application The Linked List ADT Linked List The Linked List Class Definition Linked List Class implementation Example Application Prof. Amr Goneid, AUC 2

1. The Key Table Key Table Abstraction: Key Table: a container of data in the form of a linear configuration of elements in which we can insert and delete nodes in any order. It also supports search by content (key), and can represent a dictionary ADT. Element: a container for one key and associated data item Current Element: special element in the table, indicated by a pointer to the current position. EmptyKey: a special key value to indicate that the table

slot is empty. Initially all table positions are empty. Prof. Amr Goneid, AUC 3 Ordered Key Table Class We will construct a class Ktable whose objects are key tables. They will be implemented as dynamic arrays. The data members will be the elements and a pointer to these elements. An element contains a key field and a data field. Search is by content (key) The table will be ordered on the key field.

Prof. Amr Goneid, AUC 4 (a) ADT Key Table Key Table Data Members Elements. Each element has: 1. Data or information field of type dataType. 2. A key of type keyType Others: T, a pointer to a dynamic array of elements; P, a pointer to the current element; MaxSize, The maximum size (Capacity) of the table

csize, The current size of table (no. of filled slots) Empty, A special key value to indicate an empty slot Prof. Amr Goneid, AUC 5 Element Specification // The element structure can be specified as a Class // in the private part of the main Ktable class. class element // Hidden from user { public: keyType key; // key dataType data;

// Data }; // end of class element declaration Prof. Amr Goneid, AUC 6 Key Table Operations construct: Create table emptyTable (E): Initialize table and fill with empty symbol tableIsEmpty bool : return True if table is empty tableIsFull bool : return True if table is full occupancy int : return the current no. of

elements in the table Prof. Amr Goneid, AUC 7 Key Table Operations updateData (d) : to update the data portion of the current element to contain d; assume the current position is nonempty. retrieveData (d): to return the data (d) in the current element; assume the current position is nonempty. deleteCurrent : delete the current element. Assume the current position is nonempty initially. Prof. Amr Goneid, AUC

8 Key Table Operations search (k) bool : Search the table for the slot with key part that matches (k). If found, set p to the slot and return True, else return false orderInsert (k,d) : insert an element in a position that maintains an ascending order of the key portion. traverse: traverse table to print key and info fields. Prof. Amr Goneid, AUC 9

(b) Key Table Class Definition // File: Ktable.h // Definition of Ktable Template Class #ifndef KTABLE_H #define KTABLE_H // Specification of the class template class Ktable { public: Prof. Amr Goneid, AUC 10 Key Table Class Definition

// Member Functions Ktable(int nelements = 128); // Constructor ~Ktable(); // Destructor // Functions Prototype Definitions void emptyTable(const keyType & ); bool tableIsEmpty() const; bool tableIsFull() const; Prof. Amr Goneid, AUC 11 Key Table Class Definition int occupancy() const; void updateData(const dataType & ); void retrieveData(dataType &) const;

void deleteCurrent(); bool search(const keyType & ); bool orderInsert(const keyType &, const dataType & ); void traverse() const; Prof. Amr Goneid, AUC 12 Key Table Class Definition private: // Element Class class element { public: keyType key; // key

dataType data; // Data }; // end of class element declaration Prof. Amr Goneid, AUC 13 Key Table Class Definition element *T; // Pointer to Storage Array int p; // Pointer to current element // Maximum and Current Sizes int MaxSize, csize; keyType Empty; // Empty symbol }; // end of Ktable Class definition #endif // KTABLE_H #include "Ktable.cpp" Prof. Amr Goneid, AUC

14 (c) Implementation Files Full implementation of the Key Table class is found at: http://www.cse.aucegypt.edu/~csci210/co des.zip Prof. Amr Goneid, AUC 15 Key Table Class Implementation Note: Since the keys are kept in ascending

order, it is possible to use the binary search algorithm in the search function. The implementation of this option is left as an exercise. Prof. Amr Goneid, AUC 16 (d) Example Application An ordered list of characters and their frequencies in a string: Given a string, build a List of characters and their count in the string. The list is ordered alphabetically on the characters. Prof. Amr Goneid, AUC

17 Ordered List // File: KTabletest.cpp // Applies Ktable Class #include #include using namespace std; #include "Ktable.h int main() { Ktable ctable; string s; char c; int i, count; bool keyfound;

Prof. Amr Goneid, AUC 18 Ordered List // Read a string cout << "Enter a string:" << endl; getline(cin,s); cout << s << endl; // display it ctable.emptyTable(char(126)); for (i = 0; i < s.length(); i++) // for every character { c = toupper(s.at(i)); // Search for character in the table keyfound = ctable.search (c); Prof. Amr Goneid, AUC

19 Ordered List if (keyfound) // if found { ctable.retrieveData(count); // get data count++; // increment count ctable.updateData(count); // store back } // Not found, a new node is inserted else ctable.orderInsert(c,1); } Prof. Amr Goneid, AUC

20 Ordered List // print characters and their frequencies ctable.traverse(); cout << ctable,occupancy() << endl; // current table size // empty table ctable.emptyTable(char(126)); // the size now should be zero cout << ctable.occupancy() << endl; return 0; } Prof. Amr Goneid, AUC 21

Sample Output Enter a string: The Rain in Spain The Rain in Spain 3 A2 E1 H1 I 3 N3 P1 R1 S1 T1 10 0 Press any key to continue

Prof. Amr Goneid, AUC 22 2. The Linked List Linked List Abstraction: Linked List: a container of data in the form of a linear configuration of nodes in which we can insert and

delete nodes in any order. Each Node is linked to its successor in the list. If it also supports search by contents, it can represent a dictionary ADT. Node: a container for one data item and has a direct relationship with at most two other nodes, its predecessor (if any) and its successor (if any). Head node or first node is the only node without a predecessor. Current node: special node in the list, indicated by the current position. Previous Node: the predecessor of the current node Prof. Amr Goneid, AUC 23 Ordered Linked List Class

We will construct a class List whose objects are linked lists. They will be implemented as dynamic lists. The data members will be the nodes and the pointers to these nodes. A node contains a key field and a data field. Search is by content (key) The list will be ordered on the key field. Prof. Amr Goneid, AUC 24 (a) ADT Linked List Linked List Data Members

Nodes. Each node has: 1. Data or information field of type dataType. 2. A key of type keyType 3. Link field (next) , a pointer to next node Pointers: head, a pointer to the first node; cursor, a pointer to the current node; prev, a pointer to the previous node. Prof. Amr Goneid, AUC 25

Data Members Current head Last NULL First prev key data cursor next

Prof. Amr Goneid, AUC 26 Node Specification // The linked structure for a node can be // specified as a Class in the private part of // the main linked list class. class node // Hidden from user { public: keyType key; // key dataType data; // Data

node *next; // pointer to next node }; // end of class node declaration typedef node * NodePointer; // Pointers NodePointer head, cursor, prev; Prof. Amr Goneid, AUC 27 Linked List Operations Notation Meaning head the head pointer

cursor pointer to current node prev pointer to predecessor node pnew pointer to a new node d item with the same type as the data portion of a node k item with type as the key portion of the node

b boolean value L Length of list Prof. Amr Goneid, AUC 28 Linked List Class Operations construct & initialize list to empty listIsEmpty b : return True if list is empty curIsEmpty b : return True if current position is empty toFirst : to make the current node the first node; if list is empty, the current position is still empty

atFirst b : to return True if the current node is the first node or if the list and the current position are both empty. Prof. Amr Goneid, AUC 29 Linked List Class Operations advance : to advance to next node. Assume the current position is nonempty initially.

toEnd : to make the current node the tail node; if list is empty, the current position is still empty atEnd b : to return True if the current node is the tail node or if the list and the current position are both empty. listSize L : to return the size of the list updateData (d) : to update the data portion of the current node to contain d; assume the current position is nonempty. Prof. Amr Goneid, AUC 30 Linked List Class Operations retrieveData d: to return the data in the current node; assume the current position is nonempty.

insertFirst (k,d) : insert a node with key (k) and data (d) at the head of the list; the new node becomes the current node. insertAfter (k,d) : insert a node after the current node without changing the current position; assume the current position is nonempty in a non-empty list. insertBefore (k,d) : insert a node before the current node ; current position becomes the new node Prof. Amr Goneid, AUC 31 Linked List Class Operations insertEnd(k,d): insert a node at the end of the list,

current position becomes the new node. deleteNode : delete the current node and set the current position to the next node; if the current node is the last node initially, the current position becomes empty; assume the current position is nonempty initially. deleteFirst: delete the first node and set the current position to the next node; if it was initially the only node, the current position becomes empty; Prof. Amr Goneid, AUC 32 Linked List Class Operations deleteEnd: delete the last node and set the

current position to empty. makeListEmpty : delete whole list search (k) b : search the list for the node with key part that matches (k). If found, set cursor to the node and return True, else return false and the current position becomes empty. Prof. Amr Goneid, AUC 33 Linked List Class Operations orderInsert (k,d) : insert a node in a position that maintains an ascending order of the key portion of the nodes.

traverse: traverse list to print key and info fields. The Linked List will be implemented as a template class to allow different types for the key and data fields. Prof. Amr Goneid, AUC 34 (b) Linked List Class Definition // File: List.h // Definition of Simple Linked List Template Class #ifndef LIST_H #define LIST_H // Specification of the class template class List

{ public: Prof. Amr Goneid, AUC 35 List Class Header File // Member Functions // Create an empty List List(); // Class Destructor ~List(); // Functions Prototype Definitions bool listIsEmpty() const; bool curIsEmpty() const; void toFirst();

bool atFirst() const; void advance(); Prof. Amr Goneid, AUC 36 List Class Header File void toEnd(); bool atEnd() const; int listSize() const; void updateData (const dataType & ); void retrieveData (dataType &) const; void insertFirst (const keyType &, const dataType & ); void insertAfter (const keyType &, const dataType & ); void insertBefore (const keyType &, const dataType & ); void insertEnd (const keyType &, const dataType & );

void deleteNode(); void deleteFirst(); Prof. Amr Goneid, AUC 37 List Class Header File void deleteEnd(); void makeListEmpty(); bool search (const keyType & ); void orderInsert(const keyType &, const dataType & ); void traverse(); Prof. Amr Goneid, AUC 38

List Class Header File private: key data next // Node Class class node { public: keyType key; // key dataType data; // Data node *next; // pointer to next node }; // end of class node declaration

Prof. Amr Goneid, AUC 39 List Class Header File typedef node * NodePointer; // Pointers NodePointer head, cursor, prev; }; // End of class List declaration #endif // LIST_H #include "List.cpp" Prof. Amr Goneid, AUC 40 (c) Implementation Files

Full implementation of the Linked List class is found at: http://www.cse.aucegypt.edu/~csci210/co des.zip Prof. Amr Goneid, AUC 41 (d) Example Application An ordered list of characters and their frequencies in a string: Given a string, build a List of characters and their count in the string. The list is ordered alphabetically on the characters. Prof. Amr Goneid, AUC

42 Ordered List // File: ListAppl.cpp // Applies List Class: Ordered linked list #include #include using namespace std; #include "List.h" int main() { List clist; string s; char c; int i, count; bool keyfound;

Prof. Amr Goneid, AUC 43 Ordered List // Read a string cout << "Enter a string:" << endl; getline(cin,s); cout << s << endl; // display it for (i = 0; i < s.length(); i++) // for every character { c = toupper(s.at(i)); // convert to upper case // Search for character in the list keyfound = clist.searchForKey(c); Prof. Amr Goneid, AUC

44 Ordered List if (keyfound) // if found { clist.retrieveData(count); // get data in node count++; // increment count clist.storeData(count); // store back } // Not found, a new node is inserted else clist.orderInsert(c,1); } Prof. Amr Goneid, AUC

45 Ordered List // print characters and their frequencies clist.traverse(); cout << clist.listSize() << endl; // current list size //clist.makeListEmpty(); // empty list, or clist.~List(); // free memory // the size now should be zero cout << clist.listSize() << endl; return 0; } Prof. Amr Goneid, AUC 46

Sample Output Enter a string: The Rain in Spain The Rain in Spain 3 A2 E1 H1 I 3 N3 P1 R1 S1 T1 10 0 Press any key to continue

Prof. Amr Goneid, AUC 47 Learn on your own about: Array-based implementation of Linked Lists Prof. Amr Goneid, AUC 48

Recently Viewed Presentations

  • Dissolved Gas Analysis - swedeus.org

    Dissolved Gas Analysis - swedeus.org

    DGA: WHAT and WHY. DGA is the study of the dissolved gases in transformer oil generated by normal operation and fault conditions. As the equipment operates it will create gases within the oil that can be analyzed to determine the...
  • Chapter 8 Early Civilizations in Africa

    Chapter 8 Early Civilizations in Africa

    8 Early Civilizations in Africa
  • Primer on Ethics Standards for District of Columbia Employees

    Primer on Ethics Standards for District of Columbia Employees

    Although all D.C. government employees are now covered by the Local Hatch Act, those employees whose salaries are paid in whole or in part with federal funds ("covered District employees") are also covered by specific provisions in the federal Hatch...
  • Text Summarization: News and Beyond Kathleen McKeown Department

    Text Summarization: News and Beyond Kathleen McKeown Department

    Text Summarization: News and Beyond Kathleen McKeown Department of Computer Science Columbia University
  • Aa - Loudoun County Public Schools

    Aa - Loudoun County Public Schools

    Letters and letter soundscreated by: Jennifer Wyant. Kindergarten Teacher. Rolling Ridge Elementary School. August 2010. This slide show is to assist students in learning the letters and their sounds.
  • Cardiovascular: Circulation

    Cardiovascular: Circulation

    Times New Roman Arial Default Design Cardiovascular System: Circulation Pathways and BP Regulation Blood Vessels Types Capillary Capillary Types Capillary Bed Forces Affecting Bulk Flow across the Capillary Wall Artery vs. Vein Pressure Changes down CV tree Elastic Recoil and...
  • Intro

    Intro

    Intro "The medium is the message" Marshall McLuhan Hva handler emnet om? 1) Overskrifter de siste ukene: "Norsk «Counter-Strike»-sensasjon" "Pokerfeberen herjer på nett" "DVD-Jon hacket Google Video" "Google truer rikets sikkerhet" "Web-tv redder Bokbadet" "Chatte-blotter var pappaen hennes" Hva handler...
  • SEMINAR  1 (Interim presentation) Cold formed steel sections

    SEMINAR 1 (Interim presentation) Cold formed steel sections

    Press brake operation . 3. Bending brake operation. 1) Cold Roll Forming:- ... If the beam is provided with lateral restraints, capable of resisting a lateral force of 3% of the maximum force in the compression flange, the beam may...