math.ucla.edu
#include <cstdlib>
#include <iostream>
using std::cout;
using std::cin;
void print_list(int *list, int size)
{
for(int i = 0; i < size; i++) {
cout << list[i] << " ";
}
cout << "\n";
}
void bubble_sort(int *list, int size)
{
for(int i = 0; i < size - 1; i++) {
for(int j = 0; j < size - 1 - i; j++) {
int t = list[j];
if (t > list[j + 1]) {
list[j] = list[j + 1];
list[j + 1] = t;
}
}
}
}
int main()
{
int size;
int *list;
cout << "Please enter the size of the list: ";
cin >> size;
list = new int[size];
for(int i = 0; i < size; i++) {
list[i] = rand() % 100;
}
if (size < 30) {
cout << "List before sorting:\n";
print_list(list, size);
}
cout << "Sorting (bubble)...\n";
bubble_sort(list, size);
if (size < 30) {
cout << "\nList after sorting:\n";
print_list(list, size);
}
delete [] list;
return 0;
}
void quick_sort(int *list, int size)
{
int i, j, c, t, pos;
if (size < 2) return;
pos = rand() % size;
c = list[pos];
i = 1, j = size - 1;
if (pos != 0) {
list[pos] = list[0];
list[0] = c;
}
while(i < j) {
t = list[i];
if (t <= c) i++;
else {
list[i] = list[j];
list[j--] = t;
}
}
if (i > 1) {
list[0] = list[i - 1];
list[i - 1] = c;
quick_sort(list, i - 1);
}
quick_sort(&list[i], size - i);
}
void merge_sort_aux(int *list, int *temp, int beg, int end)
{
int i, j, k, mid = (beg + end) / 2;
for(i = beg; i <= end; i++) temp[i] = list[i];
if (mid > beg) merge_sort_aux(temp, list, beg, mid);
if (mid + 1 < end) merge_sort_aux(temp, list, mid + 1, end);
j = beg; k = mid + 1;
for(i = beg; i <= end; i++) {
if (j <= mid) {
if (k <= end) {
if (temp[j] < temp[k]) {
list[i] = temp[j++];
} else {
list[i] = temp[k++];
}
} else {
list[i] = temp[j++];
}
} else {
list[i] = temp[k++];
}
}
}
void merge_sort(int *list, int size)
{
if (size < 2) return;
int *temp = new int[size];
merge_sort_aux(list, temp, 0, size - 1);
delete [] temp;
}
void sift_down(int *heap, int start, int end)
{
int root = start;
while(2 * root + 1 <= end) {
int child = 2 * root + 1;
int swap = root;
if (heap[swap] < heap[child])
swap = child;
if (child < end && heap[swap] < heap[child + 1])
swap = child + 1;
if (swap != root) {
int t = heap[root];
heap[root] = heap[swap];
heap[swap] = t;
root = swap;
} else return;
}
}
void heapify(int *heap, int count)
{
int start = count / 2 - 1;
while(start >= 0) {
sift_down(heap, start, count - 1);
start = start - 1;
}
}
void heap_sort(int *list, int size)
{
if (size < 2) return;
heapify(list, size);
int end = size - 1;
while(end > 0) {
int t = list[end];
list[end] = list[0];
list[0] = t;
sift_down(list, 0, end - 1);
end--;
}
}
#include <iostream>
using namespace std;
void print_board(int b[9][9])
{
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << b[i][j] << " ";
cout << endl;
}
}
int board_used(int b[9][9], int i, int j, bool used[10])
{
int row, column, k;
for (k = 0; k < 10; k++) used[k] = false;
for (row = 0; row < 9; row++) {
if (row == i) continue;
used[b[row][j]] = true;
}
for (column = 0; column < 9; column++) {
if (column == j) continue;
used[b[i][column]] = true;
}
int minor_row = 3 * (i / 3);
int minor_column = 3 * (j / 3);
for (row = minor_row; row < 3 + minor_row; row++) {
for (column = minor_column; column < 3 + minor_column; column++) {
if (row == i && column == j) continue;
used[b[row][column]] = true;
}
}
int count = 0;
for (k = 1; k <= 9; k++)
if (used[k]) count++;
return count;
}
bool solve_sudoku(int b[9][9], int level)
{
bool used[10];
int i, j, r, bi, bj, br;
br = -1;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
if (b[i][j] == 0) {
r = board_used(b, i, j, used);
if (r > br) {
bi = i; bj = j; br = r;
}
}
if (br == -1) return true;
board_used(b, bi, bj, used);
for (int k = 1; k <= 9; k++) {
if (used[k]) continue;
b[bi][bj] = k;
if (solve_sudoku(b, level + 1)) return true;
}
b[bi][bj] = 0;
return false;
}
int main(int argc, char **argv)
{
int b[9][9];
cout << "Please type the board numbers: " << endl;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cin >> b[i][j];
cout << endl;
if (solve_sudoku(b, 0)) {
cout << "Solution found: " << endl;
print_board(b);
} else {
cout << "No solution found!" << endl;
}
return 0;
}
#ifndef __LIST_H
#define __LIST_H
template<class T>
class List;
template<class T>
class Node {
private:
T data;
Node<T> *next, *prev;
public:
friend class List<T>;
Node()
{
next = NULL;
prev = NULL;
}
Node(const Node<T> &obj) : next(obj.next), prev(obj.prev)
{
}
};
template <class T>
class List {
private:
Node<T> *head, *tail;
Node<T> *free;
Node<T> *newNode();
void freeNode(Node<T> *n);
void copyList(const List<T> &obj);
public:
List() : head(NULL), tail(NULL), free(NULL)
{
}
List(const List<T> &obj);
~List();
void makeEmpty();
List<T>& operator=(const List<T> &right);
bool isEmpty() const
{
return head == NULL;
}
void addItemToHead(const T& item);
void addItemToTail(const T& item);
void removeFirst();
void removeLast();
const T& getFirst() const;
const T& getLast() const;
};
#endif /* __LIST_H */
#include <iostream>
#include "list.h"
template<class T>
Node<T> *List<T>::newNode()
{
if (this->free == NULL)
{
this->free = new Node<T>();
}
Node<T> *n = this->free;
this->free = n->next;
return n;
}
template<class T>
void List<T>::freeNode(Node<T> *n)
{
n->next = this->free;
this->free = n;
}
template<class T>
List<T>::List(const List<T> &obj)
{
this->copyList(obj);
}
template<class T>
void List<T>::copyList(const List<T> &obj)
{
this->makeEmpty();
this->head = this->tail = this->free = NULL;
if (obj->head != NULL)
{
Node<T> *n, *c;
c = this->head = this->newNode();
c->data = obj.head->data;
c->prev = NULL;
for(n = obj.head->next; n != NULL; n = n->next)
{
c->next = this->newNode();
c->next->prev = c;
c = c->next;
c->data = n->data;
}
c->next = NULL;
this->tail = c;
}
}
template<class T>
List<T>::~List()
{
this->makeEmpty();
Node<T> *n, *nn;
for(n = this->free; n != NULL; n = nn)
{
nn = n->next;
delete n;
}
}
template<class T>
void List<T>::makeEmpty()
{
Node<T> *n, *nn;
for(n = this->head; n != NULL; n = nn)
{
nn = n->next;
this->freeNode(n);
}
this->head = this->tail = NULL;
}
template<class T>
List<T>& List<T>::operator=(const List<T> &right)
{
this->copyList(right);
return *this;
}
template<class T>
void List<T>::addItemToHead(const T &item)
{
Node<T> *n = this->newNode();
n->data = item;
n->next = this->head;
n->prev = NULL;
this->head = n;
if (n->next == NULL)
{
this->tail = n;
}
else
{
n->next->prev = n;
}
}
template<class T>
void List<T>::addItemToTail(const T &item)
{
Node<T> *n = this->newNode();
n->data = item;
n->next = NULL;
n->prev = this->tail;
this->tail = n;
if (n->prev == NULL)
{
this->head = n;
}
else
{
n->prev->next = n;
}
}
template<class T>
void List<T>::removeFirst()
{
if (!this->isEmpty())
{
if (this->head == this->tail)
{
this->freeNode(this->head);
this->head = this->tail = NULL;
}
else
{
Node<T> *n = this->head;
this->head = n->next;
this->head->prev = NULL;
this->freeNode(n);
}
}
}
template<class T>
void List<T>::removeLast()
{
if (!this->isEmpty())
{
if (this->head == this->tail)
{
this->freeNode(this->head);
this->head = this->tail = NULL;
}
else
{
Node<T> *n = this->tail;
this->tail = n->prev;
this->tail->next = NULL;
this->freeNode(n);
}
}
}
template<class T>
const T& List<T>::getFirst() const
{
if (this->head != NULL)
{
return this->head->data;
}
throw "empty list";
}
template<class T>
const T& List<T>::getLast() const
{
if (this->tail != NULL)
{
return this->tail->data;
}
throw "empty list";
}
using namespace std;
int main(int argc, char **argv)
{
List<int> lista;
lista.addItemToHead(12);
cout << lista.getFirst() << endl;
lista.makeEmpty();
lista.addItemToHead(13);
cout << lista.getFirst() << endl;
return 0;
}