【C/C++学院】0907-象棋五子棋代码分析/寻找算法以及排序算法

编译代码报错：

错误 1 error MSB8031: Building an MFC project for a non-Unicode character set is deprecated. You must change the project property to Unicode or download an additional library. See http://go.microsoft.com/fwlink/p/?LinkId=286820 for more information. C:\Program Files\MSBuild\Microsoft.Cpp\v4.0\V120\Microsoft.CppBuild.targets 369 5 chess

安装vc_mbcsmfc.exe。

Pdb格式不兼容报错：

插值查找.cpp

#define _CRT_SECURE_NO_WARNINGS

#include stdio.h 

#include stdlib.h 

int Bin_Search(int *a, int key, int n)

 int low, high, mid;

 low = 0;

 high = n - 1;

 while (low = high)

 mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); //此处于二分查找不同,套用插值公式 

 if (a[mid] key) //如果key比插值小,把高位调整为插值下标的下一位 

 high = mid - 1;

 else if (a[mid] key)

 low = mid + 1;

 else

 return mid;

 return -1;

int mainA()

 int a[] = { 1, 5, 17, 25, 33, 38, 46, 55, 69, 75, 99 };

 int key;

 int len = sizeof(a) / sizeof(*a);

 printf("请输入要查找的值:\n");

 scanf("%d", key);

 int pos = Bin_Search(a, key, len);

 if (pos != -1)

 printf("在数组的第%d个位置找到:%d\n", pos + 1, key);

 else

 printf("未在数组中找到元素:%d\n", key);


//斐波那契查找算法的明显优点在于它只涉及加法和减法运算，而不用除法。

//因为除法比加减法要占去更多的机时，因此，斐波那契查找的平均性能要比折半查找好。

void fibonacci(int *f)

 f[0] = 1;

 f[1] = 1;

 for (int i = 2; i MAXSIZE; ++i)

 f[i] = f[i - 2] + f[i - 1];

int fibonacci_search(int *a, int key, int n)

 int low = 0, high = n - 1;

 int mid = 0;

 int k = 0;

 int F[MAXSIZE];

 fibonacci(F);

 while (n F[k] - 1) //计算出n在斐波那契中的数列 

 ++k;

 for (int i = n; i F[k] - 1; ++i) //把数组补全 

 a[i] = a[high];

 while (low = high)

 mid = low + F[k - 1] - 1; //根据斐波那契数列进行黄金分割 

 if (a[mid] key)

 high = mid - 1;

 k = k - 1;

 else if (a[mid] key)

 low = mid + 1;

 k = k - 2;

 else{

 if (mid = high) //如果为真则找到相应的位置 

 return mid;

 else

 return -1;

 return -1;

int main14()

 int a[MAXSIZE] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 };

 int k;

 printf("请输入要查找的数字:\n");

 scanf("%d", 

 int pos = fibonacci_search(a, k, 13);

 if (pos != -1)

 printf("在数组的第%d个位置找到元素:%d\n", pos + 1, k);

 else

 printf("未在数组中找到元素:%d\n", k);


/**把数组分为两部分，轴pivot左边的部分都小于轴右边的部分**/

template typename Comparable 

int partition(vector Comparable 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 typename Comparable 

void quicksort1(vector Comparable 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 typename Comparable 

void quicksort2(vector Comparable vec, int low, int high){

 stack int 

 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 int 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 iostream 

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;


/* 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

#include stdio.h 

#include stdlib.h 

#include malloc.h 

#include time.h 

static void PrintArr(int *pnArr, int nLen)

 for (int i = 0; i nLen; i++)

 printf("%d ", pnArr[i]);

 printf("\n");

void CountSort(int *pnArr, int nArrR[], int nLen, int k)

 int *pnArrTmp = (int *)malloc(sizeof(int) * k);

 for (int i = 0; i i++)

 pnArrTmp[i] = 0;

 for (int i = 0; i nLen; i++)

 pnArrTmp[pnArr[i]] = pnArrTmp[pnArr[i]] + 1;

 PrintArr(pnArrTmp, k);

 for (int i = 1; i i++)

 pnArrTmp[i] = pnArrTmp[i] + pnArrTmp[i - 1];

 PrintArr(pnArrTmp, k);


 nArrR[pnArrTmp[pnArr[i]] - 1] = pnArr[i];

 pnArrTmp[pnArr[i]] = pnArrTmp[pnArr[i]] - 1;

int main9()

 int nArr[11] = { 0, 2, 1, 3, 2, 6, 9, 7, 4, 8, 6 };

 int nArrR[11]; //存放排序后的结果

 PrintArr(nArr, 11);

 CountSort(nArr, nArrR, 11, 10);

 PrintArr(nArrR, 11);

 system("pause");

 return 0;

}

快速.cpp

#include iostream 

using namespace std;

int a[200001], n;

void swap(int a, int b){

 int tmp = a;

 a = b;

 b = tmp;

int partition(int p, int r){

 int rnd = rand() % (r - p + 1) + p;

 swap(a[rnd], a[r]);

 int pvt = r, i = p - 1;

 for (int j = i + 1; j j++)

 if (a[j] a[pvt])

 swap(a[j], a[++i]);

 swap(a[++i], a[pvt]);

 return i;

void qsort(int p, int r){

 if (p r){

 int q = partition(p, r);

 qsort(p, q - 1);

 qsort(q + 1, r);

int main5()

 cin n;

 for (int i = 0; i i++)

 cin a[i];

 qsort(0, n - 1);

 for (int i = 0; i i++)

 cout a[i];

 system("pause");

 return 0;

}

冒泡.cpp

#include iostream 

#include stdlib.h 

using namespace std;

int main1()

 int a[10];

 for (int i = 0; i i++)

 a[i] = rand() % 100;

 for (int i = 0; i i++)

 for (int j = 0; j 10 - i; j++)

 if (a[j] a[j + 1])

 int temp = a[j];

 a[j] = a[j + 1];

 a[j + 1] = temp;

 for (int i = 0; i i++)

 cout a[i] " ";

 system("pause");

 return 0;

}

木桶.cpp

#include stdio.h 

#include stdlib.h 

#define SIZE 100

void bucket_sort(unsigned *, int);//桶排序函数的原型

void print(unsigned *, int);//打印函数的原型

int main8()

 unsigned array[SIZE];

 int i = 0;

 //为数组元素随机赋值

 for (i = 0; i SIZE; ++i)

 array[i] = rand();

 printf("排序前\n");

 print(array, SIZE);

 //排序

 bucket_sort(array, SIZE);

 printf("排序后\n");

 print(array, SIZE);

 system("pause");

 return 0;

void bucket_sort(unsigned * arr, int len)

 unsigned *buckets[10];//指针数组

 unsigned n = 1;//用于取整数各位上的值

 int index;//数组下标计数索引

 int indexs[10];//各个桶下标计数索引

 int i, j;

 //分配动态内存作为桶

 for (i = 0; i ++i)

 buckets[i] = (unsigned *)malloc(sizeof(unsigned)*len);

 while (1)

 //计数索引清零

 index = 0;

 for (i = 0; i ++i)

 indexs[i] = 0;

 //数组至桶

 for (i = 0; i len; ++i)

 buckets[arr[i] / n % 10][indexs[arr[i] / n % 10]++] = arr[i];

 //桶至数组

 for (i = 0; i ++i)

 for (j = 0; j indexs[i]; ++j)

 arr[index++] = buckets[i][j];

 //为取元素的下一位做准备

 n *= 10;

 //判断是否该结束

 for (i = 0; arr[i] n i len; ++i);

 if (i == len) break;

 //释放动态内存

 for (i = 0; i ++i)

 free(buckets[i]);

void print(unsigned * arr, int len)

 int i = 0;

 for (i = 0; i len; ++i)

 printf("%8d", arr[i]);

 //5个元素一行

 if ((i + 1) % 5 == 0)

 printf("\n");

}

希尔.cpp

#include iostream 

#include stdlib.h 

using namespace std;

const int N = 10;

void shell_sort(const int len, int *array)

 int j, i, key;

 int gap = 0;

 if (len = 0 || array == NULL)

 return;

 while (gap = len)

 gap = gap * 3 + 1;

 while (gap 0)

 for (i = gap; i len; i++)

 j = i - gap;

 key = array[i];

 while ((j = 0) (array[j] key))

 array[j + gap] = array[j];

 j = j - gap;

 array[j + gap] = key;

 //display_array(len,array,gap);

 gap = (gap - 1) / 3;

// 3 5 18 29 35 24 12 0

// 3 12 

// 5 0

// 3 0 18 29 35 24 12 5

//3 24

// 0 12

// 18 5

//3 0 5 29 35 24 12 18

//3 35

// 0 24

// 5 12

// 29 18

//3 0 5 18 35 24 12 29 

//3 18 12

// 0 35 29

// 5 24

//3 0 5 12 29 24 18 35

//3 5 29 18

// 0 12 24 35

//3 0 5 12 18 24 29 35

//0 3 5 12 18 24 29 35

int main4()

 int array[N];

 for (int i = 0; i i++)

 array[i] = rand() % 100;

 cout array[i] " ";

 shell_sort(N - 1, array);

 cout endl;

 for (int i = 0; i i++)

 cout array[i] " ";

 system("pause");

 return 0;

}

选择.cpp

#include iostream 

using namespace std;

void main2()

 int a[10];

 for (int i = 0; i i++)

 a[i] = rand() % 100;

 for (int i = 0; i i++)

 for (int j = i; j 10 - i; j++)

 if (a[j] a[i])

 int temp = a[j];

 a[j] = a[i];

 a[i] = temp;

 for (int i = 0; i i++)

 cout a[i] " ";

 system("pause");

}