首页 > 代码库 > 算法之美_源码公布（1）
算法之美_源码公布（1）
本文辑录了《算法之美——隐匿在数据结构背后的语言》（电子工业出版社2016年出版）一书第1~2章之代码（P1~P61）。全文文件夹、“45个算法”文件夹、“22个经典问题文件夹”，以及有奖捉虫活动详情请见例如以下链接：http://blog.csdn.net/baimafujinji/article/details/50484348
附录中的经典笔试、面试问题參考答案请见：
http://blog.csdn.net/baimafujinji/article/details/50484683
探秘算法世界。求索数据结构之道；汇集经典问题，畅享编程技法之趣；点拨求职热点，敲开业界名企之门。
网上书店：
京东链接：http://item.jd.com/10111000454.html
http://item.jd.com/10111372484.html
China-pub中国互动出版网：http://product.china-pub.com/4911922
亚马逊：http://www.amazon.cn/%E7%AE%97%E6%B3%95%E4%B9%8B%E7%BE%8E-%E9%9A%90%E5%8C%BF%E5%9C%A8%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%83%8C%E5%90%8E%E7%9A%84%E5%8E%9F%E7%90%86-%E5%B7%A6%E9%A3%9E/dp/B01AGNUIE8/ref=sr_1_8?ie=UTF8&qid=1453527399&sr=8-8&keywords=%E5%B7%A6%E9%A3%9E
电子工业出版社官方链接：http://www.phei.com.cn/module/goods/wssd_content.jsp?bookid=44441
假设你是该书的读者。请务必加算法学习群（495573865），内有很多其它资源等你，而你在读书中遇到的疑问也将得到我第一时间的解答。
很多其它关注本博客，我将陆续公布该书所有源码至本博客。
P2：C++中的原子数据类型与它们所占的存储空间
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
cout << "bool: " << sizeof(bool) << endl;
cout << "char: " << sizeof(char) << endl;
cout << "short: " << sizeof(short) << endl;
cout << "int: " << sizeof(int) << endl;
cout << "long: " << sizeof(long) << endl;
cout << "float: " << sizeof(float) << endl;
cout << "double: " << sizeof(double) << endl;
return 0;
}
P25：变量与地址
#include "stdafx.h"
#pragma runtime_checks( "", off )
int _tmain(int argc, _TCHAR* argv[])
{
int a = 97;
int b = 98;
int c = 99;
return 0;
}
P29：使用指针变量
#include "stdafx.h"
#include "iostream"
#pragma runtime_checks( "", off )
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int a = 5;
unsigned int *pint = NULL;
cout << "&a = " << &a << endl << " a = " << a << endl;
cout << " &pint = " << &pint << endl << " pint = " << pint << endl;
cout << " &(*pint) = " << &(*pint) << endl << endl;
pint = &a;
cout << "&a = " << &a << endl << " a = " << a << endl;
cout << " &pint = " << &pint << endl << " pint = " << pint << endl;
cout << " &(*pint) = " << &(*pint) << endl << endl;
*pint = 10;
cout << "&a = " << &a << endl << " a = " << a << endl;
cout << " &pint = " << &pint << endl << " pint = " << pint << endl;
cout << " &(*pint) = " << &(*pint) << endl << endl;
system("PAUSE");
return 0;
}P32：函数的參数传递——按值传递
#include <iostream>
using namespace std;
void fun(int x)
{
cout<< “x = ”<<x<<endl;
x++;
cout<< “x = ”<<x<<endl;
}
int main(int argc, char** argv) {
int x = 0;
cout<<"x = " <<x<<endl;
fun(x);
cout<<"x = " <<x<<endl;
return 0;
}
P33：按值传递对象
#include <iostream>
using namespace std;
class Student {
string name;
int age;
public:
Student() : name(""), age(0) {}
void set_age(int age) {this->age = age;}
int get_age() { return age;}
void set_name(string name) {this->name = name;}
string get_name() { return name;}
};
void increment_age(Student s) {
s.set_age(s.get_age() + 1);
}
int main(int argc, char** argv) {
Student s;
s.set_name("Wumingshi");
s.set_age(20);
increment_age(s);
cout << s.get_age() << endl;
return 0;
}
P34：函数的參数传递——指针传递
#include <iostream>
using namespace std;
void fun(int* p)
{
cout<< "*p = "<<*p<<endl;
(*p)++;
cout<< "*p = "<<*p<<endl;
}
int main(int argc, char** argv){
int x = 0;
cout<<"x = " <<x<<endl;
fun(&x);
cout<<"x = " <<x<<endl;
return 0;
}
P35：函数的參数传递——引用传递
#include <iostream>
using namespace std;
void fun(int& r)
{
cout<< "r = "<<r<<endl;
r++;
cout<< "r = "<<r<<endl;
}
int main(int argc, char** argv){
int x = 0;
cout<<"x = " <<x<<endl;
fun(x);
cout<<"x = " <<x<<endl;
return 0;
}
P36：採用引用传递方式来传递指针
#include <iostream>
using namespace std;
void first_bigger(int*& p, int threshold) {
while (*p <= threshold) {
p++;
}
}
int main(int argc, char** argv) {
int numbers[] = {0, 12, 32, 44, 33, 5, 85, 45, 100, 75};
int* result = &numbers[0];
cout <<"Begin at: "<< *result << endl;
first_bigger(result, 60);
cout <<"Result is: "<< *result << endl;
return 0;
}
P39-1：数组的使用（数组元素求和）
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
int a[10] = {1, 32, 65, 2, 100, 34, 33, 21, 10, 1};
int sum = 0;
for(int i = 0; i < 10; i++){
sum = sum + a[i];
}
cout << "数组中元素的和为 " << sum<< endl;
return 0;
}
P39-2：数组的越界訪问
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
int a[5] = {1, 2, 3, 4, 5};
int b[5] = {6, 7, 8, 9, 10};
cout << b[6] << endl;
return 0;
}
P41：矩阵转置
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
int a[4][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}, {12, 13, 14, 15}};
int i = 0;
int j = 0;
int tmp = 0;
for(i =0; i < 4; i++)
{
for(; j < 4; j++)
{
tmp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = tmp;
}
j=i+1;
}
for(i = 0; i < 4; i++)
{
for(j = 0; j < 4; j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
P42：数组与指针的关系
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int * p;
p = &a[0];
cout<< a[0] <<endl;
cout<< &a[0]<<endl;
cout<< &a<<endl;
cout<< a <<endl;
cout<< p <<endl;
cout<< *p<<endl;
return 0;
}
P43：自加运算符与指针
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int * p;
p = &a[0];
cout<< *(p++)<<endl;
p = &a[0];
cout<< *p++<<endl;
p = &a[0];
cout<< *(++p)<<endl;
return 0;
}
P44：指针訪问多维数组
#include <iostream>
using namespace std;
int main(int argc, char* argv[]){
int a[3][3] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
int * p;
p = &a[0][0];
for(int i = 0; i<9; i++)
cout<<*p++<<endl;
return 0;
}
P46：数组的抽象数据类型
头文件
#ifndef ARRAY_H
#define ARRAY_H
#include <iostream>
using namespace std;
const int DefaultSize = 20;
template <class Type>
class Array
{
Type *elements; //数组存放空间
int ArraySize; //当前长度
public:
Array(int Size=DefaultSize); //构造函数
Array(const Array<Type>& x); //拷贝构造函数
~Array() {delete []elements;} //析构函数
Array<Type> & operator = (const Array<Type> & rhs); //数组复制
Type& operator [] ( int i ); //取元素值
int Length () const { return ArraySize; } //取数组长度
void ReSize (int sz); //扩充数组
};
template <class Type>
Array<Type>& Array<Type >::operator= (const Array<Type >& rhs)
{
int n = rhs. ArraySize; // 取rhs的数组大小
if (ArraySize != n)
{
delete [] elements; // 删除数组原有内存
elements = new Type[n]; // 又一次分配n个元素的内存
if (elements == NULL) //假设分配内存不成功，输出错误信息
{
ArraySize = 0;
cerr << "存储分配错误！" << endl;
exit(1);
}
ArraySize = n; //记录本对象的数组大小
}
// 从rhs向本对象复制元素
Type* destptr = elements;
Type* srcptr = rhs. elements;
while (n--)
*destptr++ = *srcptr++;
return *this; // 返回当前对象的引用
}
template <class Type>
Array<Type> :: Array (int sz)
{
if ( sz <= 0 ) {
ArraySize = 0;
cerr << "非法数组大小" << endl;
return;
}
elements = new Type[sz];
if (elements == NULL) {
ArraySize = 0;
cerr << "存储分配错误！" << endl;
exit(1);
}
ArraySize = sz;
}
template <class Type>
Array<Type> :: Array (const Array<Type> & x )
{
int n = x.ArraySize;
ArraySize = n;
elements = new Type[n];
if ( elements == NULL ) {
ArraySize = 0;
cerr << "存储分配错" << endl;
exit(1);
}
Type *srcptr = x.elements;
Type *destptr = elements;
while ( n-- ) * destptr++ = * srcptr++;
}
template <class Type>
Type& Array<Type> :: operator [] (int i){
if ( i < 0 || i > ArraySize-1 ) {
cerr << "数组下标超界" << endl;
exit(1);
}
return elements[i];
}
template <class Type>
void Array<Type> :: ReSize (int sz) {
if (sz >= 0 && sz != ArraySize) {
Type * newarray = new Type[sz]; //创建新数组
if (newarray == NULL) {
cerr << "存储分配错" << endl;
return;
}
int n = (sz <= ArraySize) ? sz : ArraySize; //按新的大小确定传送元素个数
Type *srcptr = elements; //源数组指针
Type *destptr = newarray; //目标数组指针
while (n--) * destptr++ = * srcptr++;
delete [] elements;
elements = newarray;
ArraySize = sz;
}
}
#endif
測试程序
#include <iostream>
#include <iomanip>
#include "Array.h"
using namespace std;
int main(int argc, char** argv) {
Array<int> A(10);
int n;
int primecount = 0, i, j;
cout << "Enter a value >= 2 as upper limit for prime numbers: ";
cin >> n;
A[primecount++] = 2; // 2是一个质数,[]下标运算
for(i = 3; i < n; i++) {
if (primecount == A.Length()) A.ReSize(primecount + 10);
if (i % 2 == 0) continue;
j = 3;
while (j <= i/2 && i % j != 0) j += 2;
if (j > i/2) A[primecount++] = i;
}
for (i = 0; i < primecount; i++) {
cout << setw(5) << A[i];
if ((i+1) % 10 == 0) cout << endl;
}
cout << endl;
return 0;
}P49：Z字形编排问题
请參见博文——ZigZag排列问题与经典笔试面试题目解析
（链接地址：http://blog.csdn.net/baimafujinji/article/details/50388584）
P51：大整数乘法问题
#include <iostream>
#include <memory.h>
#define SIZE 14
using namespace std;
// 返回位数为size1+size2
int* multi(int* num1, int size1, int* num2, int size2)
{
int size = size1 + size2;
int* ret = new int[size];
int i = 0;
memset(ret, 0, sizeof(int) * size);
for (i = 0; i < size2; ++i)
{
int k = i;
for (int j = 0; j < size1; ++j)
ret[k++] += num2[i] * num1[j];
}
for (i = 0; i < size; ++i)
{
if (ret[i] >= 10)
{
ret[i+1] += ret[i] / 10;
ret[i] %= 10;
}
}
return ret;
}
int main(int argc, char** argv) {
int num1[SIZE] = {1,2,3,4,5,6,7,8,9,1,1,1,1,1};//第一个大整数 11111987654321
int num2[SIZE] = {1,1,1,2,2,2,3,3,3,4,4,4,5,5};//第二个大整数 55444333222111
int* ret = multi(num1, SIZE, num2, SIZE);
for (int i = SIZE*2-1; i >= 0; i--)
cout << ret[i];
delete[] ret; //释放内存
return 0;
}P52：九宫格问题
#include <iostream>
#include <iomanip>
#include <memory.h>
using namespace std;
int main()
{
cout<<"请输入幻方的大小n（n是一个大于1的奇数）：";
int n=1;
cin>>n;
cout<<endl;
int **a = new int*[n];
for(int i=0; i<n; ++i){
a[i]=new int[n];
memset(a[i], 0, n*sizeof(int));
}
int row=0;
int col=n/2;
for(int i=1; i<=n*n; i++) {
a[row][col]=i;
row--;
col++;
if(row<0&&col>=n)
{
col--;
row+=2;
}
else if(row<0)
{
row=n-1;
}
else if(col>=n)
{
col=0;
}
else if(a[row][col]!=0)
{
col--;
row+=2;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<setw(6)<<a[i][j];
}
cout<<endl;
}
for(int i = n; i > 0;)
delete[] a[--i];
delete[] a;
return 0;
}
P55：用new来创建对象
#include <iostream>
using namespace std;
class Point
{
int x;
int y;
public:
Point()
{
x = 0;
y = 0;
};
Point(int xx, int yy)
{
x = xx;
y = yy;
};
~Point(){cout<<"END"<<endl;};
int getX(){return x;};
int getY(){return y;};
void setX(int newX){x = newX;};
void setY(int newY){y = newY;};
};
int main(int argc, char** argv) {
Point * point1 = new Point;
Point * point2 = new Point(3, 5);
cout<<point1->getX()<<endl;
cout<<point2->getX()<<endl;
delete point1;
delete point2;
return 0;
}
算法之美_源码公布（1）