Abstract data type General Array:

 

class GeneralArray

 {

// objects: A set of pairs <index, value> where for each value of index in IndexSet there

// is a value of type float. IndexSet is a finite ordered set of one or more dimensions,

// for example, {0, …, n-1} for one dimension, {(0, 0), (0, 1), (0, 2),(1, 0), (1, 1), (1, 2), (2, 0),

// (2, 1), (2, 2)} for two dimensions, etc.

public:

  GeneralArray(int j; RangeList list, float initValue = defatultValue);

  // The constructor GeneralArray creates a j dimensional array; the range of

  // the kth dimension is given by the kth element of list. For each index i in the index

  // set, insert <i, initValue> into the array.

 

  float Retrieve(index i);

  // if (i is in the index set of the array) return the value associated with i

  // in the array; else signal an error

  void Store(index i, float x);

  // if (i is in the index set of the array) delete any pair of the form <i, y> present

  // in the array and insert the new pair <i, x>; else signal an error.

}; // end of GeneralArray

Arrays- Introduction:

C-Style One-Dimensional Arrays:

• Boundary checking:

    C++ (or C) does not check an array index to ensure that it belongs to the range for which the array is defined.

 

  ☺Some Important points:

int list[5], *plist[5];

list[5]:   five integers

             list[0], list[1], list[2], list[3], list[4]

*plist[5]: five pointers to integers

            plist[0], plist[1], plist[2], plist[3], plist[4]

• implementation of 1-D array

  list[0]  base address = a

  list[1]    a + sizeof(int)

  list[2]    a + 2*sizeof(int)

  list[3]    a + 3*sizeof(int)

  list[4]    a + 4*size(int)

• Compare int *list1 and int list2[5] in C.
• Same:  list1 and list2 are pointers.
• Difference:  list2 reserves five locations.
• Notations:
• list2 - a pointer to list2[0]
• (list2 + i) - a pointer to list2[i] (&list2[i])
• *(list2 + i) - list2[i]

Abstract Data Type (ADT):

• Abstraction

–Separating data from implementation

–Generalization

• ADT

–A collection of related data items together with basic operations between them and operations to be performed on them

• Implementation of an ADT:

Data Structures & Algorithms:

          ☻Data Structure:

• Goal: organize data
• Criteria: facilitate efficient 
• –storage of data
• –retrieval of data
• –manipulation of data
• Process: 
• –select and design appropriate data type

☻Need to run computer eficiently?

Efficient Management or Storage of Data → Data Structure

Efficient Sequence of Actions(i.e Manipulation & Retrieval)→Algorithms

Examples:

Tradeoff:



Tips for Good Programming:

Good Programming Practices are:

·       Programs and subprograms should be well structured.

·       Use a modular approach for a complex problem.

·       Use the basic control structures when developing each code segment.

·       Sequence, selection, repetition

·       Use local variables within subprograms.

·       Use parameters to pass information to and from subprograms.

·       Avoid global Variables.

·       To prevent arguments that should not be modified by a subprogram, declare the corresponding parameters to be value parameter or constant reference parameters rather than reference parameters.

·       Do not use “ magic numbers”.

·       Strive for simplicity and clarity.

·       Identify any preconditions (assumptions) and postconditions a program or subprogram has, and check them.

·       All source code should be documented.

·       Each program should include opening documentation.

·       Each subprogram should be documented in a manner similar to programs.

·       Comments should be used to explain key code segments and / or segments whose purpose or design is not obvious.

·       Use meaningful identifiers.

·       Source code shuld be asthetic; it should be formated in a style that enhances its readability. 

·       Put each statement of the program on a separate line.

·       Use uppercase and lowercase letters in a way that contributes to program readibility.

·       Put each { and } on separate lines.

·       Align each { and corresponding }.

·       When a statement is continued from one line to another, indent the continued line(s).

·       Align the identifiers in each constant and variable declaration, placing each on a separate line.

·       Insert blank lines between declarations and statements and between blocks of statements to make clear the structure of the program.

·       Separate the operators and operands in an expression with spaces to make the expression easy to read.

·       Declare constants at the beginning of a function. Declare variable near their first use.

·       Label all output produced by a program. 

Data Structure, Outline:

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.
Data Structures evolve arround:

• Introduction to Algorithms

• ADTs

• Searching and sorting Techniques

• Arrays

• Stacks

• Recursion

• Queues

• Lists and its variations

• Trees

• Hashing

• Graphs