#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 200
#define INVALID -1
#ifndef array_list_h
#define array_list_h
class array_list {
public:
array_list(int sz = 0);
~array_list() { clear(); }
bool isEmpty(void) { return (num == 0); }
bool isInList(int sample);
int getLength(void) { return num; }
int getItem(int pos) { return a[pos]; }
void setItem(int pos, int newItem) { a[pos] = newItem; }
void insert(int pos, int newItem);
void remove(int pos);
void bubbleSort(void);
void insertionSort(void);
void selectionSort(void);
void heapSort(void);
void mergeSort(void) { mergeSortStub(0, num-1); }
void quickSort(void) { quickSortStub(0, num-1); }
int sequentialSearch(int key);
int binarySearch(int key) { return binarySearchStub(0, num-1, key); }
void clear() { for (int i = 0; i < SIZE; i++) a[i] = INVALID; num = 0; }
void display() { for (int i = 0; i < num; i++) cout << a[i] << " "; cout << endl; }
private:
void swap(int& x, int& y) { int temp = x; x = y; y = temp; }
int findMin(int curr, int last);
void fixHeap(int heapsize, int root, int k);
void constructHeap(int root);
int deleteMin(void);
void merge(int start, int last);
void mergeSortStub(int start, int last);
int random(int start, int last) { srand(time(NULL)); return start + rand() % (last-start+1); }
int partition(int start, int last);
void quickSortStub(int start, int last);
int binarySearchStub(int start, int last, int key);
int num;
int a[SIZE];
};
array_list::array_list(int sz)
{
int i;
for (i = 0; i < sz; i++)
a[i] = 0;
for (i = sz; i < 200; i++)
a[i] = INVALID;
num = sz;
}
bool array_list::isInList(int sample)
{
bool check = false;
for (int i = 0; i < num; i++)
if (a[i] == sample) {
check = true;
break;
}
return check;
}
void array_list::insert(int pos, int newItem)
{
if (pos > getLength())
return;
for (int i = num; i > pos; i--)
a[i] = a[i-1];
a[pos] = newItem;
num++;
}
void array_list::remove(int pos)
{
if (pos >= getLength())
return;
for (int i = pos; i < num-1; i++)
a[i] = a[i+1];
a[num-1] = INVALID;
num--;
}
//====================== SORTING ==========================//
void array_list::bubbleSort(void)
{
for (int i = 0; i < num-1; i++)
for (int j = i+1; j < num; j++)
if (a[i] > a[j])
swap(a[i], a[j]);
}
void array_list::insertionSort(void)
{
for (int i = 0; i < num; i++) {
int j = i;
while ((j > 0) && (a[j] < a[j-1])) {
swap(a[j], a[j-1]);
j--;
}
}
}
int array_list::findMin(int curr, int last)
{
if (last - curr == 1) {
if (a[curr] < a[last])
return curr;
else
return last;
}
else {
int rest = findMin(curr+1, last);
if (a[curr] < a[rest])
return curr;
else
return rest;
}
}
void array_list::selectionSort(void)
{
for (int i = 0; i < num-1; i++) {
int j = findMin(i, num-1);
swap(a[j], a[i]);
}
}
void array_list::fixHeap(int heapsize, int root, int k)
{
if (2*root+1 > heapsize) // the root has no child
a[root] = k;
else {
int largerSubHeap;
if (2*root+1 == heapsize) // the root has 1 child
largerSubHeap = 2*root+1;
else // the root has 2 children
largerSubHeap = (a[2*root+1] > a[2*root+2]) ? (2*root+1) : (2*root+2);
if (k >= a[largerSubHeap])
a[root] = k;
else {
a[root] = a[largerSubHeap];
fixHeap(heapsize, largerSubHeap, k);
}
}
}
void array_list::constructHeap(int root)
{
int k = a[root];
if (2*root+1 >= num) // the root has no child
return;
else if (2*root+2 == num) // the root has 1 child
constructHeap(2*root+1);
else { // the root has 2 children
constructHeap(2*root+1);
constructHeap(2*root+2);
}
fixHeap(num, root, k);
}
void array_list::heapSort(void)
{
int heapsize;
constructHeap(0);
for (heapsize = num; heapsize >= 2; heapsize--) {
int currentMax = a[0];
int k = a[heapsize-1];
fixHeap(heapsize-1,0, k);
a[heapsize-1] = currentMax;
}
}
void array_list::merge(int start, int last)
{
int i, j, k;
int aux[SIZE];
int mid = (start + last) / 2;
for (i = start; i <= mid; i++)
aux[i] = a[i];
for (i = mid+1; i <= last; i++)
aux[last+mid+1-i] = a[i];
j = start; k = last;
for (i = start; i <= last; i++)
a[i] = (aux[j] < aux[k]) ? aux[j++] : aux[k--];
}
void array_list::mergeSortStub(int start, int last)
{
if (last > start) {
int mid = (last + start) / 2;
mergeSortStub(start, mid);
mergeSortStub(mid+1, last);
merge(start, last);
}
}
int array_list::partition(int start, int last)
{
swap(a[start], a[random(start, last)]);
int pivot = a[start];
int leftwall = start;
for (int i = start+1; i <= last; i++) {
if (a[i] < pivot) {
leftwall++;
swap(a[i], a[leftwall]);
}
}
swap(a[start], a[leftwall]);
return leftwall;
}
void array_list::quickSortStub(int start, int last)
{
if (last > start) {
int pivot = partition(start, last);
quickSortStub(start, pivot-1);
quickSortStub(pivot+1, last);
}
}
//====================== SEARCHING ==============//
int array_list::sequentialSearch(int key)
{
int i = 0;
while ((i < num) && (a[i] != key))
i++;
if (i == num)
return -1;
else
return i;
}
int array_list::binarySearchStub(int start, int last, int key)
{
if (last < start)
return -1;
else {
int mid = (start + last) / 2;
if (key == a[mid])
return mid;
else if (key < a[mid])
return binarySearchStub(start, mid-1, key);
else
return binarySearchStub(mid+1, last, key);
}
}
البته تابع main رو اینجا نمی بینم!! (هر کی خواست،برای برنامه خودش تابع main رو هم بنویسه)
پاسخ با نقل قول
