ADT implementation in C of integer list

Question

I need to do a home assignment in VC++, which uses ADT to do several operations on an integer list. For now, we're not allowed to use classes, so I need to use struct.

I don't quite understand how ADTs work, so I'm not sure where to start, because all tutorials on the internet use classes, which I don't want to.

So are there any tutorials on the net that: 1. explain the concept of Abstract Data Types and 2. Provide an example of implementation (preferably in C++ and not using class, but struct instead).

Answer 1

I will give a try for an answer that is more what is my understanding.

1. What is an abstract datatype? Always my first shot: Look at http://en.wikipedia.org/wiki/Abstract_data_type

My "practical" understanding of this is: There is some idea of an object that is defined by the object, its variables (or data) and the operations that are defined on this object. For your case the object is a list of integers. The operations are something like insert a new integer, remove an integer, get the number of integers stored in the list and so on. When implementing this datatype you have to write this operations as functions. To provide this functions you will have to make up some structure to save the data to operate on.

1. Provide an example of implementation.

Well I won't do your homework so I will do some pseudocode:

struct ListElement {
   int value;
   type NextElement; //i leave the type to you
};

void insertBehind(ListElement &element, int newValue)//this is one way to do this
{
  ListElement newElement(newValue); //create the new element (use new instead, don't want to "spoiler" the type to you)
  newElement.nextElement = element.nextElement; //set the next element of this new one
  element.NextElement = newElement; //set the new element
}

...