1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

template <class Elem> class List {
public:
    virtual void clear() = 0;
    virtual bool insert(const Elem&) = 0;
    virtual bool append(const Elem&) = 0;
    virtual bool remove(Elem&) = 0;
    virtual bool getValue(Elem&) const = 0;
    virtual bool setPos(int pos) = 0;
    virtual void setStart() = 0;
    virtual void setEnd() = 0;
    virtual void prev() = 0;
    virtual void next() = 0;
    virtual int leftLength() const = 0;
    virtual int rightLength() const = 0;
    virtual void print() const = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

template <class Elem> class Stack {
public:
    // Reinitialize the stack
    virtual void clear() = 0;
    // Push an element onto the top of the stack.
    virtual bool push(const Elem&) = 0;
    // Remove the element at the top of the stack.
    virtual bool pop(Elem&) = 0;
    // Get a copy of the top element in the stack
    virtual bool topValue(Elem&) const = 0;
    // Return the number of elements in the stack.
    virtual int length () const = 0;
};

1
2
3
4
5
6
7
8

template <class Elem> class Queue {
public:
    virtual void clear() = 0;
    virtual bool enqueue(const Elem&) = 0;
    virtual bool dequeue(Elem&) = 0;
    virtual bool frontValue(Elem&) const = 0;
    virtual int length() const = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Template  <class Elem>  class BinNode {
public:
    virtual Elem& val( ) =0;
    virtual void setVal( const Elem& ) = 0;
    virtual BinNode* left( ) const = 0;
    virtual void setLeft( BinNode* ) = 0;
    virtual BinNode* right( ) const = 0;
    virtual void setRight( BinNode* ) = 0;
    virtual bool isLeaf( ) = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// General tree node ADT
template <class Elem> class GTNode {
public:
    GTNode(const Elem&); // Constructor
    ~GTNode();           // Destructor
    Elem value();        // Return value
    bool isLeaf();       // TRUE if is a leaf
    GTNode* parent();    // Return parent
    GTNode* leftmost_child(); // First child
    GTNode* right_sibling();  // Right sibling
    void setValue(Elem&);     // Set value
    //insert first child
    void insert_first(GTNode<Elem>* n);
    //insert right sibling
    void insert_next(GTNode<Elem>* n);
    void remove_first(); // Remove first child
    void remove_next();  // Remove sibling
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// General tree ADT
template <class Elem> class GenTree {
public:
    GenTree();               // Constructor
    ~GenTree();              // Destructor
    void clear();            // Send nodes to free store
    GTNode* root();          // Return the root

    void print(GTNode*); // Print function
};

1
2
3
4
5
6
7

template <class Elem>
void inssort(Elem A[], int n) {
    for (int i=1; i<n; i++)
        for (int j=i; (j>0) &&
              (A[j]< A[j-1])); j--)//插入第i个元素
            swap(A, j, j-1);
}

1
2
3
4
5
6
7

template <class Elem>
void bubsort(Elem A[], int n) {
    for (int i=0; i <n-1; i++)
        for (int j=n-1; j>i; j--)
            if (A[j]< A[j-1])
                swap(A, j, j-1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

template <class Elem>
void selsort(Elem A[], int n) {
    for (int i=0; i<n-1; i++) {
   // select the minial values in [i,n-1]
        int lowindex = i; // lowindex指向较小的元素
        for (int j=n-1; j>i; j--) // Find least
            if (A[j]< A[lowindex])
                lowindex = j;
        swap(A, i, lowindex); // Put it in place
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Modified version of Insertion Sort
template <class Elem>
void inssort2(Elem A[], int n, int from, int incr)
{
  for (int i= from + incr; i<n; i+=incr)
    for (int j=i; (j> from &&
           A[j]< A[j-incr]); j-=incr)
       swap(A, j, j-incr);
}

template <class Elem>
void shellsort(Elem A[], int n) { // Shellsort
  for (int i=n/2; i>=1; i/=2)  // For each incr
    for (int j=0; j<i; j++)   // Sort sublists
      inssort2<Elem>(A, n, j, i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

template <class Elem>
void qsort(Elem A[], int i, int j) {
  if (j <= i) return;     // List too small
  int pivot = findpivot(A, i, j);
  swap(A, pivot, j);  // Put pivot at end

  int k = partition<Elem>(A, i, j, A[j]);
  swap(A, k, j);         // Put pivot in place
  qsort<Elem>(A, i, k-1);
  qsort<Elem>(A, k+1, j);
}

template <class Elem>
int findpivot(Elem A[], int i, int j)
  { return (i+j)/2; }

template <class Elem>
int partition(Elem A[], int l, int r,Elem& pivot) {
  do {
    while (A[l] < pivot) l++;
    while ((r > l) && A[r] >=pivot)
       r--;

    swap(A, l, r); // Swap out-of-place values
  } while (l < r); // Stop when they cross
  return l;       // Return first pos on right
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#best: 每次都均匀分成两段

   --------
   ---- ----
  -- -- -- --
- - - - - - - -

#worst
--------
- -------
  - ------
    - -----
      - ----
        - ---
          - --
            - -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

template <class Elem>
void mergesort(Elem A[], Elem temp[],
               int left, int right) {
  int mid = (left+right)/2;
  if (left == right) return;

  mergesort<Elem>(A, temp, left, mid);
  mergesort<Elem>(A, temp, mid+1, right);

  for (int i=left; i<=right; i++) // Copy
    temp[i] = A[i];
  int i1 = left; int i2 = mid + 1;
  for (int curr=left; curr<=right; curr++) {
    if (i1 == mid+1)      // Left exhausted
      A[curr] = temp[i2++];
    else if (i2 > right)  // Right exhausted
      A[curr] = temp[i1++];
    else if (temp[i1] < temp[i2])
      A[curr] = temp[i1++];
    else A[curr] = temp[i2++];
  }
}