Abstract data type Lists C++
ADT in lists in C++ or sequence is an abstract data type that implements a finite ordered collection of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream. Lists are a basic example of containers, as they contain other values. Each instance of a value in the list is usually called an item, entry, or element of the list; if the same value occurs multiple times, each occurrence is considered a distinct item. Lists are distinguished from arrays in that lists only allow sequential access, while arrays allow random access.
ADT List Operations
- Create an empty list
- Destroy a list
- Determine whether a list is empty
- Determine the number of items in a list
- Insert an item at a given position in the list
- Delete the item at a given position in the list
- Retrieve th item at a given position in the list
C++ Classes
Encapsulation( used to refer to one of two related but distinct notions, and sometimes to the combination) combines an ADT’s data with its operations to form an object
- An object is an instance of a class
- A class defines a new data type
- A class contains data members and
- methods (member functions)
- By default all members in a class are private.
- Encapsulation hides implementation details.
Each class definition is placed in a header file Classname.h
The implementation of a class’s methods are placed in an implementation file Classname.cpp
Constructors- Create and initialize new instances of a class. Invoked when you declare an instance of the class. Have the same name as the class. Have no return type, not even void
Destructor- Destroys an instance of an object when the object’s lifetime ends
C++ Namespaces- A mechanism for logically grouping declarations and definitions into a common
Abstract data type list using array-based implementation
Heather file ADT Lists C++
/* * File: lists.h * Author: MyCodingLab * Code: ADT list - array-based implementation * Date: Created on August 26, 2011, 2:59 AM * */ #ifndef LISTS_H #define LISTS_H #include <stdio.h> #include <iostream> const int MAX_SIZE = 10; typedef int ListItemType; class List { public: //Default constructor List(); //Default Destructor would be provided by compiler in this case. //~List(); //List operations: //return True if the list is empty; otherwise returns false bool isEmpty() const; //return the number of items stored in the list. int getSize() const; //Inserts an item into the list at position index. void insert(int index, const ListItemType& newItem); // Deletes an item from the list at a given position. void remove(int index); // Retrieves a list item by position. void retrieve(int index) const; // Output all elements. void print() const; private: // array of list items ListItemType items[MAX_SIZE]; //number of items int size; };//end List //end file. #endif /* LISTS_H */
Implementation file ADT Lists C++
#ifndef LISTS_CPP #define LISTS_CPP #include "lists.h" #include <iostream> using namespace std; List::List() : size(0) { //initial the array for(int k=0; k<MAX_SIZE; k++) items[k]=0; }//end default constructor bool List::isEmpty() const { return size == 0; }//end isEmpty int List::getSize() const { return size; }// end getLength void List::insert(int pos, const ListItemType& newItem) { if( ( pos<0) || (MAX_SIZE<pos ) ) cout<< pos <<" is out of bound "<<endl; else{ items[pos]= newItem; cout<< newItem <<" has been inserted"<< endl; size++; }//end of if }// end insert void List::remove(int pos) { if( ( pos<0) && (MAX_SIZE<pos ) ) cout<< "position is out of bound "<<endl; else{ items[pos]= 0; --size; }// end if }// end remove void List:: print() const { cout<<"List contains: "; for(int k=0; k<MAX_SIZE; k++) cout << items[k]<< " "; cout<< endl; }//end print void List::retrieve(int pos) const { if( ( pos<0) && (MAX_SIZE<pos ) ) cout<< "position is out of bound "<<endl; else{ if (items[pos]==0) cout<< "Cell is empty"<<endl; else cout<< "item at position " << pos << " is: " << items[pos]<<endl; }// end if }// end retrieve // End file. #endif /* LISTS_CPP */
Main file ADT Lists C++
#include "lists.cpp" #include <iostream> using namespace std; int main(int argc, char** argv) { //declare list List testList; //check if list is empty if(testList.isEmpty()==0) cout<< "List is not empty"<<endl; else cout<< "List is empty"<<endl; //insert valueslists testList.insert(4,10); //insert values testList.insert(5,15); testList.insert(7,33); testList.insert(0,86); testList.retrieve(0); // get the size of list cout<< "size is: " << testList.getSize()<< endl; testList.print(); return 0; }//end main
Program Output:
List is empty 10 has been inserted 15 has been inserted 33 has been inserted 86 has been inserted item at position 0 is: 86 size is: 4 List contains: 86 0 0 0 10 15 0 33 0 0
Other posts you may be interested:
Arrays in C++
Dynamic Memory Allocation in C++