本篇文章主要介绍了"0907-象棋五子棋代码分析/寻找算法以及排序算法"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：
象棋五子棋代码分析编译代码报错：错误 1 error MSB8031: Building an MFC project for a non-Unicode ch...
#include
using namespace std;
#define MAX 20
void PrintArray(int a[], int len){
for (int i = 0; i < len; i++)
cout << a[i] << " ";
cout << endl;
}
void BinInsertSort(int a[], int len){
int *d = (int *)malloc(len*sizeof(len));
for (int i = 0; i < len; i++)
d[i] = 0;
int first = 0, final = 0;
d[0] = a[0];
for (int i = 1; i < len; i++){
if (a[i] <= d[first]){
first = (first - 1 + len) % len;
d[first] = a[i];
}
else if (a[i] >= d[final]){
final = final + 1;
d[final] = a[i];
}
else{
int j = final++;
while (a[i] < d[j]){
d[(j + 1) % len] = d[j];
j = (j - 1 + len) % len;
}
d[j + 1] = a[i];
}
}
cout << "辅助数组中排序结果为：";
PrintArray(d, len);
}
int main10(){
int a[MAX], len;
cout << "请输入待排序的元素个数：";
cin >> len;
cout << "请输入待排序的元素：";
for (int i = 0; i < len; i++)
cin >> a[i];
BinInsertSort(a, len);
system("pause");
return 0;
}
非递归快速排序.cpp
#include
#include
#include
#include
#include
using namespace std;
/**把数组分为两部分，轴pivot左边的部分都小于轴右边的部分**/
template
int partition(vector &vec, int low, int high){
Comparable pivot = vec[low]; //任选元素作为轴，这里选首元素
while (low < high){
while (low < high && vec[high] >= pivot)
high--;
vec[low] = vec[high];
while (low < high && vec[low] <= pivot)
low++;
vec[high] = vec[low];
}
//此时low==high
vec[low] = pivot;
return low;
}
/**使用递归快速排序**/
template
void quicksort1(vector &vec, int low, int high){
if (low < high){
int mid = partition(vec, low, high);
quicksort1(vec, low, mid - 1);
quicksort1(vec, mid + 1, high);
}
}
/**使用栈的非递归快速排序**/
template
void quicksort2(vector &vec, int low, int high){
stack st;
if (low < high){
int mid = partition(vec, low, high);
if (low < mid - 1){
st.push(low);
st.push(mid - 1);
}
if (mid + 1 < high){
st.push(mid + 1);
st.push(high);
}
//其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行partition操作
while (!st.empty()){
int q = st.top();
st.pop();
int p = st.top();
st.pop();
mid = partition(vec, p, q);
if (p < mid - 1){
st.push(p);
st.push(mid - 1);
}
if (mid + 1 < q){
st.push(mid + 1);
st.push(q);
}
}
}
}
int main11(){
int len = 1000000;
vector vec;
for (int i = 0; i < len; i++)
vec.push_back(rand());
clock_t t1 = clock();
quicksort1(vec, 0, len - 1);
clock_t t2 = clock();
cout << "recurcive " << 1.0*(t2 - t1) / CLOCKS_PER_SEC << endl;
//重新打乱顺序
random_shuffle(vec.begin(), vec.end());
t1 = clock();
quicksort2(vec, 0, len - 1);
t2 = clock();
cout << "none recurcive " << 1.0*(t2 - t1) / CLOCKS_PER_SEC << endl;
return 0;
}
归并.cpp
#include
using namespace std;
const int N = 10;
int anthor[N];
void MergeSort(int *array, int begin, int end)
{
if (end - begin > 1)
{ //
MergeSort(array, begin, (begin + end) / 2);
MergeSort(array, (begin + end) / 2 + 1, end);
int i = begin;
int j = (begin + end) / 2 + 1;
int k = begin;
while (i <= (begin + end) / 2 && j <= end)//合并时，把一个串全部并入另一个串放在一个新串，剩下的直接放在尾部
{
if (array[i] > array[j]) //小的值进入，并将索引后移
anthor[k++] = array[j++];
if (array[i] < array[j])
anthor[k++] = array[i++];
}
while (i <= (begin + end) / 2)
{
anthor[k++] = array[i++];
}
while (j <= end)
{
anthor[k++] = array[j++];
}
for (k = begin; k <= end; k++) //排序好重新拷贝回数组
array[k] = anthor[k];
}
else //相邻则直接交换
{
if (array[end] < array[begin])
{
int temp = array[end];
array[end] = array[begin];
array[begin] = temp;
}
}
}
int main6()
{
int array[N];
for (int i = 0; i < 10; i++)
{
array[i] = rand() % 100;
cout << array[i] << " ";
}
MergeSort(array, 0, N - 1);
cout << endl;
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
system("pause");
return 0;
}
红黑树.cpp
// 红黑树.cpp : 定义控制台应用程序的入口点。
#include
#include
#include
typedef int key_t;
typedef int data_t;
typedef enum color_t
{
RED = 0,
BLACK = 1
}color_t;
typedef struct rb_node_t
{
struct rb_node_t *left, *right, *parent;
key_t key;
data_t data;
color_t color;
}rb_node_t;
/* forward declaration */
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
rb_node_t* rb_search(key_t key, rb_node_t* root);
rb_node_t* rb_erase(key_t key, rb_node_t* root);
int main()
{
int i, count = 90;
key_t key;
rb_node_t* root = NULL, *node = NULL;
//srand(time(NULL));
for (i = 1; i < count; ++i)
{
key = rand() % count;
if ((root = rb_insert(key, i, root)))
{
printf("[i = %d] insert key %d success!\n", i, key);
}
else
{
printf("[i = %d] insert key %d error!\n", i, key);
exit(-1);
}
if ((node = rb_search(key, root)))
{
printf("[i = %d] search key %d success!\n", i, key);
}
else
{
printf("[i = %d] search key %d error!\n", i, key);
exit(-1);
}
if (!(i % 10))
{
if ((root = rb_erase(key, root)))
{
printf("[i = %d] erase key %d success\n", i, key);
}
else
{
printf("[i = %d] erase key %d error\n", i, key);
}
}
}
return 0;
}
static rb_node_t* rb_new_node(key_t key, data_t data)
{
rb_node_t *node = (rb_node_t*)malloc(sizeof(struct rb_node_t));
if (!node)
{
printf("malloc error!\n");
exit(-1);
}
node->key = key, node->data = data;
return node;
}
/*-----------------------------------------------------------
| node right
| / \ ==> / \
| a right node y
| / \ / \
| b y a b
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)
{
rb_node_t* right = node->right;
if ((node->right = right->left))
{
right->left->parent = node;
}
right->left = node;
if ((right->parent = node->parent))
{
if (node == node->parent->right)
{
node->parent->right = right;
}
else
{
node->parent->left = right;
}
}
else
{
root = right;
}
node->parent = right;
return root;
}
/*-----------------------------------------------------------
| node left
| / \ / \
| left y ==> a node
| / \ / \
| a b b y
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root)
{
rb_node_t* left = node->left;
if ((node->left = left->right))
{
left->right->parent = node;
}
left->right = node;
if ((left->parent = node->parent))
{
if (node == node->parent->right)
{
node->parent->right = left;
}
else
{
node->parent->left = left;
}
}
else
{
root = left;
}
node->parent = left;
return root;
}
static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root)
{
rb_node_t *parent, *gparent, *uncle, *tmp;
while ((parent = node->parent) && parent->color == RED)
{
gparent = parent->parent;
if (parent == gparent->left)
{
uncle = gparent->right;
if (uncle && uncle->color == RED)
{
uncle->color = BLACK;
parent->color = BLACK;
gparent->color = RED;
node = gparent;
}
else
{
if (parent->right == node)
{
root = rb_rotate_left(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
parent->color = BLACK;
gparent->color = RED;
root = rb_rotate_right(gparent, root);
}
}
else
{
uncle = gparent->left;
if (uncle && uncle->color == RED)
{
uncle->color = BLACK;
parent->color = BLACK;
gparent->color = RED;
node = gparent;
}
else
{
if (parent->left == node)
{
root = rb_rotate_right(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
parent->color = BLACK;
gparent->color = RED;
root = rb_rotate_left(gparent, root);
}
}
}
root->color = BLACK;
return root;
}
static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root)
{
rb_node_t *other, *o_left, *o_right;
while ((!node || node->color == BLACK) && node != root)
{
if (parent->left == node)
{
other = parent->right;
if (other->color == RED)
{
other->color = BLACK;
parent->color = RED;
root = rb_rotate_left(parent, root);
other = parent->right;
}
if ((!other->left || other->left->color == BLACK) &&
(!other->right || other->right->color == BLACK))
{
other->color = RED;
node = parent;
parent = node->parent;
}
else
{
if (!other->right || other->right->color == BLACK)
{
if ((o_left = other->left))
{
o_left->color = BLACK;
}
other->color = RED;
root = rb_rotate_right(other, root);
other = parent->right;
}
other->color = parent->color;
parent->color = BLACK;
if (other->right)
{
other->right->color = BLACK;
}
root = rb_rotate_left(parent, root);
node = root;
break;
}
}
else
{
other = parent->left;
if (other->color == RED)
{
other->color = BLACK;
parent->color = RED;
root = rb_rotate_right(parent, root);
other = parent->left;
}
if ((!other->left || other->left->color == BLACK) &&
(!other->right || other->right->color == BLACK))
{
other->color = RED;
node = parent;
parent = node->parent;
}
else
{
if (!other->left || other->left->color == BLACK)
{
if ((o_right = other->right))
{
o_right->color = BLACK;
}
other->color = RED;
root = rb_rotate_left(other, root);
other = parent->left;
}
other->color = parent->color;
parent->color = BLACK;
if (other->left)
{
other->left->color = BLACK;
}
root = rb_rotate_right(parent, root);
node = root;
break;
}
}
}
if (node)
{
node->color = BLACK;
}
return root;
}
static rb_node_t* rb_search_auxiliary(key_t key, rb_node_t* root, rb_node_t** save)
{
rb_node_t *node = root, *parent = NULL;
int ret;
while (node)
{
parent = node;
ret = node->key - key;
if (0 < ret)
{
node = node->left;
}
else if (0 > ret)
{
node = node->right;
}
else
{
return node;
}
}
if (save)
{
*save = parent;
}
return NULL;
}
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root)
{
rb_node_t *parent = NULL, *node;
parent = NULL;
if ((node = rb_search_auxiliary(key, root, &parent)))
{
return root;
}
node = rb_new_node(key, data);
node->parent = parent;
node->left = node->right = NULL;
node->color = RED;
if (parent)
{
if (parent->key > key)
{
parent->left = node;
}
else
{
parent->right = node;
}
}
else
{
root = node;
}
return rb_insert_rebalance(node, root);
}
rb_node_t* rb_search(key_t key, rb_node_t* root)
{
return rb_search_auxiliary(key, root, NULL);
}
rb_node_t* rb_erase(key_t key, rb_node_t *root)
{
rb_node_t *child, *parent, *old, *left, *node;
color_t color;
if (!(node = rb_search_auxiliary(key, root, NULL)))
{
printf("key %d is not exist!\n");
return root;
}
old = node;
if (node->left && node->right)
{
node = node->right;
while ((left = node->left) != NULL)
{
node = left;
}
child = node->right;
parent = node->parent;
color = node->color;
if (child)
{
child->parent = parent;
}
if (parent)
{
if (parent->left == node)
{
parent->left = child;
}
else
{
parent->right = child;
}
}
else
{
root = child;
}
if (node->parent == old)
{
parent = node;
}
node->parent = old->parent;
node->color = old->color;
node->right = old->right;
node->left = old->left;
if (old->parent)
{
if (old->parent->left == old)
{
old->parent->left = node;
}
else
{
old->parent->right = node;
}
}
else
{
root = node;
}
old->left->parent = node;
if (old->right)
{
old->right->parent = node;
}
}
else
{
if (!node->left)
{
child = node->right;
}
else if (!node->right)
{
child = node->left;
}
parent = node->parent;
color = node->color;
if (child)
{
child->parent = parent;
}
if (parent)
{
if (parent->left == node)
{
parent->left = child;
}
else
{
parent->right = child;
}
}
else
{
root = child;
}
}
free(old);
if (color == BLACK)
{
root = rb_erase_rebalance(child, parent, root);
}
system("pause");
return root;
}
基数.cpp
