目录
0 等概率随机洗牌：
1 大小写转换
2 字符串复制
4 辗转法求最大公约数
5 交换两个整数
6 二分搜索
7 逆向迭代的猴子吃桃问题
8 输出各基本数据类型的内存字节16进制值
9 求数组长度
10 单循环找出数组中的最大值和次大值
11 返回某年的1月1号是星期几
12 数字字符串转浮点数
13 用函数对象求斐波那契数列：
14 判断某一整数是否是2的整数次幂
15 如何较友好地停住控制台窗口
16 以某一基准实现向上舍入，用宏实现*p++
17 如何缩小解空间判断是否是素数
18 单词统计
19 返回某区间的随机数
20 使用枚举和共用体组合结构体
21 使用位域和共用体将double分成4部分显示：
22 算术运算和位运算模拟比较运算符和条件语句
23 模板递归求阶乘
24 memmove()实现
25 定义时间延迟函数
26 归并排序
26 快速排序
27 堆排序
28 希尔排序
29 链表迭代器自定义
30 string自定义
31 自定义vector
32 智能指针模拟
0 等概率随机洗牌：
for(int i = n – 1; i >= 0 ; i — ) swap(arr[i], arr[rand(0, i)]) ;// rand(0, i) 生成 [0, i] 之间的随机整数
1 大小写转换
#include // 用位运算控制低5位（32）#define UPPER(str) for(int i=0; str[i];) str[i++] |= ‘a’-‘A’;#define LOWER(str) for(int i=0; str[i];) str[i++] &= ~(‘a’-‘A’);int main(){ char str[] = “aBcDeF”; //UPPER(str); printf(“%s”,str); LOWER(str); printf(“%s”,str);}
2 字符串复制
#include char* strcpy(char* dst, const char* src){ assert( (dst != NULL) && (src != NULL) ); char* start = dst; while(*dst++ = *src++); return start;}int main(){ char dst[] = “abcdefdd”; char* src = “xydz”; printf(“%s”,scpy(dst,src));}
3 求平方根和开整数次方
double sqrt(double x,double x0)// x是用于求平方根的数，x0是平方根的估算，可以是x/2{ if(x 1e-5 || x1*x1-x 0) {// 以下4个表达式来联系起来思考 if (n%2 == 1) // n%2 与 n/2 ret=ret * x; // x 会在此会以x^2迭代 x = x * x; n = n/2; } return ret;}
4 辗转法求最大公约数
int gcd(int a, int b){ return b ? gcd(b,a%b) : a;}int gcdLoop(int a,int b){ int r; while(b>0) { r=a%b; a=b; b=r; } return a;}
5 交换两个整数
#include void swap(int *a,int *b){ *a = *a + *b; *b = *a – *b; *a = *a – *b;}void swap2(int *a,int *b){ *a = *a * *b; *b = *a / *b; *a = *a / *b;}void swap3(int *a,int *b){ *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b;}int main(){ int a=3,b=4; printf(“%d %d”,a,b); swap(&a,&b); printf(“%d %d”,a,b); swap2(&a,&b); printf(“%d %d”,a,b); swap3(&a,&b); printf(“%d %d”,a,b); getchar();}
6 二分搜索
#include int binsearch(int a[], int x, int low, int high){ int mid; if(low > high) return -1; mid = (low + high) / 2; if(x == a[mid]) return (mid); else if(x < a[mid]) binsearch(a, x, low, mid – 1); else binsearch(a, x, mid + 1, high);}int main(){ int arr[] = {1,3,5,7,9,12,15,19}; int n = sizeof arr / sizeof *arr; int idx = binsearch(arr,9,0,n); printf("%d",idx); // 4 getchar();}
7 逆向迭代的猴子吃桃问题
int peachCount(int days) // 倒推{ int peaches = 1; // 最后一天桃子数 while(days>1) { peaches = (peaches+1)*2; // 倒推递归 days–; } return peaches;}int peachCountRecursive(int day) // 递归{ if(day == 1) // 最后一天，问题规模为1时 return 1; else return (peachCountRecursive(–day)+1)*2;}
8 输出各基本数据类型的内存字节16进制值
c的指针可以将任意粒度的数据控制到字节。
void printIntBin(unsigned long n) // 输出unsigned的二进制位{ bool r = (01&n); if(n>=2) printIntBin(n>>1); // 递归 putchar(r?’1′:’0′);}void showBytes(unsigned char* start, int len) // 输出len个start开始内存的16进制编码{ for(int i=0;i=0;i–) printf(” %.2x”,start[i]); printf(“”); }}
9 求数组长度
long arr[] = {1,3,5,6,2,4,8}; int n = sizeof arr / sizeof *arr; // 少打几个字符，*arr即数组首元素
10 单循环找出数组中的最大值和次大值
#include #define N 20// 构造一个最小值，用做最大和次大的初始值const int min = 1<<31; // -2147483648int main(){ int arr[N] = {0},i; int max,second; for(i=0;isecond && arr[i]!=max) // 比最大小，比次大大 second = arr[i]; printf(“%d %d”,max,second); getchar();getchar(); return 0; }/* 将下面数据粘贴入99 99 99 99 12 14 78 36 99 1256 87 98 56 5422 65 36 48 95*/
11 返回某年的1月1号是星期几
// 公元1年1月1日是周一，365%7 1int weekDay(int y) // 返回某年的1月1号是星期几{ // 星期天返回0，星期1返回1 return (y + (y-1)/400 + (y-1)/4 – (y-1)/100)%7;}
12 数字字符串转浮点数
double stringToDouble( char *p ){ double intPart=0.0, fractionPart=0.0; int multiplier = 1; /* change to -1 if string starts with minus */ /* Find the sign for the entire number */ if( *p == ‘+’ ) p++; if( *p == ‘-‘ ) { multiplier = -1; p++ ; } /* Convert the integer part of the number */ while( *p >= ‘0’ && *p = ‘0’ && *p <= '9' ) { pisor *= 10.0; fractionPart += (*p – '0')/pisor; p++ ; } } /* Put the pieces together */ return (intPart + fractionPart)*multiplier ;}
13 用函数对象求斐波那契数列：
利用对象的状态。
#include class Fib {public: Fib() : a0_(1), a1_(1) {} int operator()() { int temp = a0_; a0_ = a1_; a1_ = temp + a0_; return temp; }private: int a0_, a1_;};int main(){ Fib fib; for(int i=1;i<50;i++) printf("%2d %d",i,fib()); getchar();}
14 判断某一整数是否是2的整数次幂
bool is2pow(int m) // m的二进制位是否只有一个1{ return (m & m-1) == 0;}
15 如何较友好地停住控制台窗口
我们知道，在控制台输入时，scanf非字符时会忽略掉空白字符，输入字符时并不会忽略空白字符。所以有时一个简单的getchar()并不会停住控制台。
void PressEnterToContinue(){ int c; printf( “Press ENTER to continue… ” ); fflush( stdout ); do c = getchar(); while((c != ”) && (c != EOF));}
16 以某一基准实现向上舍入，用宏实现*p++
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) – 1) & ~(sizeof(int) – 1) ) va_arg(p,type) ( *(type *)((p += _INTSIZEOF(type)) – _INTSIZEOF(type)) )
上面第一个宏可以实现sizeof(int)的向上舍入，表示数据对齐；
上面第二个宏在模拟*p++，相当于*p; p++; 首先是整体表达式的值是+_INTSIZEOF(type)－_INTSIZEOF(type)，没有影响到整体表达式的值，但p += _INTSIZEOF(type)对p产生了负作用，相当于指针的p++。
17 判断是否是素数
暴力枚举也是尽可能先缩减解空间。
int isPrime(int n){ if(n<2) return 0; if(n==2) return 1; if(n%2==0) return 0; for(int i=3;i*i<=n;i+=2) if(n%i == 0) return 0; return 1;}
18 单词统计
int countWord(char *str){ bool wordInner = false; int n = 0,i=0; while(str[i]!=”) { if(isspace(str[i])) wordInner = false; else if(wordInner==false && isalpha(str[i])) { n++; wordInner = true; } else wordInner = true; i++; } return n;}
19 返回某区间的随机数
int randInt(int low,int high){ double quo = 1.0/(RAND_MAX+1.0); return int(low+(rand()*quo)*(high-low+1));}
20 使用枚举和共用体组合结构体
// 存货记录的声明// 零件typedef struct { int cost; int supplier; // other information}Partinfo;// 装配件typedef struct { int n_parts; struct SUBASSYPART{ char partno[10]; short quan; }*part;}Subassyinfo;// 存货typedef struct { char partno[10] ; int quan; enum { PART, SUBASSY} type; union{ // 存货不是零件就是装配件 Partinfo *part; Subassyinfo *subassy; }info;}Invrec;
21 使用位域和共用体将double分成4部分显示：
#include typedef struct packed_double { unsigned int low32; // 小数位 低32位 unsigned int low20:20; // 小数位 低33-52位 unsigned int exp11:11; // 指数位 低53-63位，移码1023+二进制整数位-1 unsigned int sign:1; // 符号位} packed_double;typedef union { double d; packed_double b;} packed;int main(){ packed pd; pd.d = -15.75; pd.d = 12.3; printf(“%u %u %u %u”,pd.b.sign,pd.b.exp11,pd.b.low20,pd.b.low32); getchar(); return 0;}/*0 1026 1015808 0*/
22 算术运算和位运算模拟比较运算符和条件语句
void compareEx(int a,int b) // 算术运算和位运算模拟比较运算符和条件语句{ int t = (a-b)>>(sizeof(int)*8-1); // 取首位 if(t == -1) cout<<"a<b"<<endl; if(a-b == 0) cout<<"a==b"<<endl; if(a-b != 0 && t == 0) cout<b"<<endl;}
23 模板递归求阶乘
模板可以被递归调用，在模板递归的过程中，可以执行两种编译期计算：数值计算和类型计算。
#include templatestruct factorial{ enum { value = n * factorial::value };};templatestruct factorial{ // 模板特化终止递归 enum { value = 1 };};int main(){ std::cout << factorial::value << std::endl; // prints "5040"}
在主模板templatestruct factoria的定义中，使用了模板自身struct factorial::value。编译器会一直用不同的N-1的值来具现化主模板，一直到N变为1，这时选择Factorial的特化版本template struct Factorial，内部的value变为1，递归终止。
24 memmove()实现
#include void * my_memmove(void * dst,const void * src,int count)// 从src开始移动count个字节到dst{ void * ret = dst; if(dst <= src || ((char *)src + count) <= (char *)dst) // dst在前或src在前但内存区域不重叠 { while(count–) { *(char *)dst = *(char *)src; dst = (char *)dst + 1; src = (char *)src + 1; } } else // (src<dst && (char *)dst < ((char *)src + count)) // src在前且内存区域有重叠 { // 也就是dst重载了src的后面部分时 dst = (char *)dst + count – 1; src = (char *)src + count – 1; while(count–) { *(char *)dst = *(char *)src; dst = (char *)dst – 1; src = (char *)src – 1; } } return(ret);}int main(){ char src[] = "abcdefghi"; puts((char*)my_memmove(src+3,src,5));// abcdei puts(src); // abcabcdei getchar();}
25 定义时间延迟函数
#include #include //定义时间延迟函数void Dtime(double dt) { time_t current_time; time_t start_time; time(&start_time); // 得到开始时间 do{ // 延迟处理 time( t_time); }while (difftime(current_time,start_time)<dt);}void displayTime(int n){ int i; time_t current_time; char *timep; for(i=0;i<n;i++) { time( t_time); timep=ctime( t_time); system("cls"); //cputs(timep); printf("%s",timep); Dtime(1); }}int main(){ displayTime(10);}
26 快速排序
void quickSort(int arr[],int size,int low,int high){ int i,j,t; if(low<high) { i=low; j=high; t=arr[low]; while(i<j) { while(it) j–; if(i<j) { arr[i] = arr[j]; i++; } while(i<j && arr[i]<=t) i++; if(i<j) { arr[j] = arr[i]; j–; } } arr[i] = t; quickSort(arr,size,low,i-1); quickSort(arr,size,i+1,high); }}
26 归并排序
void Merge(int A[], int left, int mid, int right){ int len = right – left + 1; int *temp = new int[len]; // 辅助空间O(n) int index = 0; int i = left; // 前一数组的起始元素 int j = mid + 1; // 后一数组的起始元素 while(i <= mid && j <= right)// 从小到大依次放到辅助数组中 if(A[i] <= A[j])temp[index++] = A[i++];elsetemp[index++] = A[j++]; while(i <= mid)// 对子序列A[left:mid]剩余的依次处理 temp[index++] = A[i++]; while(j <= right)// 对子序列B[mid+1:right]剩余的依次处理 temp[index++] = A[j++]; for(int k = 0; k < len; k++)// 将合并后的序列复制到原来的A数组 A[left++] = temp[k];}// 递归实现的归并排序(自顶向下)void MergeSortRecursion(int A[], int left, int right) { if(left == right) // 当待排序的序列长度为1时，递归开始回溯，进行merge操作 return; int mid =(left + right) / 2; MergeSortRecursion(A, left, mid); // 参数迭代：right = mid MergeSortRecursion(A, mid + 1, right); // 参数迭代：left = mid+1 Merge(A, left, mid, right); // 递归返回时执行部分 Merge(A, left, mid, right);}// 非递归(迭代)实现的归并排序(自底向上)void MergeSortIteration(int A[], int len) { int left, mid, right;// 子数组索引,前一个为A[left…mid]，后一个子数组为A[mid+1…right] for(int i=1; i<len; i*=2) // 子数组的大小i初始为1，每轮翻倍 { left = 0; while(left + i < len) // 后一个子数组存在(需要归并) { mid = left + i – 1; right = (mid+i)<len?mid+i:len-1;// 后一个子数组大小可能不够 Merge(A, left, mid, right); left = right + 1; // 前一个子数组索引向后移动 } }}
27 堆排序
void Swap(int A[], int i, int j){ int temp = A[i]; A[i] = A[j]; A[j] = temp;}void Heapify(int A[], int i, int size) // 从A[i]向下进行堆调整{ int left_child = 2 * i + 1; // 左孩子索引 int right_child = 2 * i + 2; // 右孩子索引 int max = i; // 选出当前结点与其左右孩子三者之中的最大值 if (left_child A[max]) max = left_child; if (right_child A[max]) max = right_child; if (max != i) { Swap(A, i, max); // 把当前结点和它的最大(直接)子节点进行交换 Heapify(A, max, size); // 递归调用，继续从当前结点向下进行堆调整 }}int BuildHeap(int A[], int n) // 建堆，时间复杂度O(n){ int heap_size = n; for (int i = heap_size / 2 – 1; i >= 0; i–) // 从每一个非叶结点开始向下进行堆调整 Heapify(A, i, heap_size); return heap_size;}void HeapSort(int A[], int n){ int heap_size = BuildHeap(A, n); // 建立一个最大堆 while (heap_size > 1) { // 堆（无序区）元素个数大于1，未完成排序 // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素 // 此处交换操作很有可能把后面元素的稳定性打乱， // 所以堆排序是不稳定的排序算法 Swap(A, 0, –heap_size); Heapify(A, 0, heap_size); // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn) }}
28 希尔排序
void output(int a[], int n){ //输出数组元素for(int i = 0; i get) { A[j + h] = A[j]; j = j – h; } A[j + h] = get;printf(“gap%2d：”,h);output(A,n); } h = (h – 1) / 3; // 递减增量 }}
29 链表迭代器自定义
// 链表迭代器自定义//#include #include #include using namespace std;//1.数据组成template struct singleList{ singleList* next; T data; singleList() // 创建表头 { this->next = NULL; } singleList(T data) // 创建节点 { this->data = data; this->next = NULL; } // 创建节点+连接节点的功能 singleList(T data, singleList* next) { this->data = data; this->next = next; }};template class list{public: list() // 构造函数作用:构造对象 { // 初始化基本数据成员，描述最初状态 sizeList = 0; listHeadNode = listTailNode = NULL; } void push_back(T data) // 基本行为：插入操作 { singleList* newNode = new singleList(data); if (listHeadNode == NULL) listHeadNode = newNode; else listTailNode->next = newNode; listTailNode = newNode; //listTailNode->next=NULL; } void push_front(T data) { singleList* newNode = new singleList(data); if (listHeadNode == NULL) listTailNode = newNode; else newNode->next = listHeadNode; listHeadNode = newNode; } void printList() //测试行为：遍历结构（打印输出） { singleList* pMove = listHeadNode; while (pMove) { cout <data <next; } cout <next; // 表示链表最后那个位置，NULL的位置 } int size() const // 万金油行为 { return sizeList; } bool empty() const { return sizeList == 0; }public: class iterator { public: void operator=(singleList* pMove) // 实现begin对iterator对象的初始化 { // 实质初始化对象中的属性 this->pMove = pMove; } singleList* getData() { return pMove; } bool operator!=(singleList* pMove) { return this->pMove != pMove; } iterator& operator++(int) //i=i+1; //实质是链表的一个移动指针走到一下一个节点 { this->pMove = this->pMove->next; return (*this); } T operator*() { return this->pMove->data; } protected: singleList* pMove; // 迭代器就是对容器元素指针的封装 }; protected: // 抽象数据成员 // 遵循的原则：抽象出来的属性能够便于描述行为(成员函数) singleList* listHeadNode; singleList* listTailNode; int sizeList; // 万金油属性};int main(){ list mylist; mylist.push_back(“I”); mylist.push_back(“Love”); mylist.push_back(“you”); //mylist.printList(); list::iterator myIter; //myIter=mylist.begin(); //cout<data<<endl; for (myIter = mylist.begin(); myIter != mylist.end(); myIter++) { cout << *myIter << " "; } cout << endl; return 0;}
30 string自定义
#include #include class String{public: String(const char* cstr = 0); String(const String& str); String& operator=(const String& str); ~String(){ delete[] m_data; } char* get_c_str() const{ return m_data; }private: char* m_data;};String::String(const char* cstr){ if(cstr) { m_data = new char[strlen(cstr)+1]; strcpy(m_data,cstr); } else { m_data = new char[1]; *m_data = ”; }}String::String(const String& str){ m_data = new char[strlen(str.m_data)+1]; strcpy(m_data,str.m_data);}String& String::operator=(const String& str){ if(this == &str) return *this; delete[] m_data; m_data = new char[strlen(str.m_data)+1]; strcpy(m_data,str.m_data); return *this;}int main(){ String str(“abc”); String str2(str); String str3 = str2; printf(“%s”,str3.get_c_str()); return 0;}
31 自定义vector
#includeusing namespace std;class Vector {public:Vector(int s);int size();double& operator[](int i);private:double* elem; // pointer to the elementsint sz; // the number of elements};Vector::Vector(int s) // construct a Vector{sz = s;elem = new double[s];}double& Vector::operator[](int i) // element access: subscripting{ return elem[i]; } int Vector::size() { return sz; }double read_and_sum(int n){Vector v(n); // make a vector of s elementsfor (int i=0; i!=v.size(); ++i)cin>>v[i]; //read into elementsdouble sum = 0;for (i=0; i!=v.size(); ++i)sum+=v[i]; //take the sum of the elementsreturn sum;}void main(){ cout<< read_and_sum(6)<<endl; system("pause");}/*1 2 3 4.4 5 6.622*/
32 智能指针模拟
#include#includeusing namespace std;#define TEST_SMARTPTRclass Stub // stub code是占坑的代码，桩代码给出的实现是临时性的/待编辑的。{public:void print(){cout<<"Stub:print"<<endl;}~Stub(){cout<<"Stub:Destructor"<(){if(ptr)return ptr;throw std::runtime_error(“access through NULL pointer”);}const T* operator->()const{if(ptr)return ptr;throw std::runtime_error(“access through NULL pointer”);}T &operator*(){if(ptr)return *ptr;throw std::runtime_error(“dereference of NULL pointer”);}const T &operator*()const{if(ptr)return *ptr;throw std::runtime_error(“dereference of NULL pointer”);}~SmartPtr(){decrUse();#ifdef TEST_SMARTPTRstd::cout<<"SmartPtr:Destructor"<print();}catch(const exception&err){cout<<err.what()<print();(*t3).print();}//增加一个块结构，为了看到对象离开作用域后的析构结果system(“pause”);return 0;}/*output:SmartPtr:Destructoraccess through NULL pointerStub:DestructorStub:printStub:print//以下是离开作用域后的析构SmartPtr:DestructorSmartPtr:DestructorStub:DestructorSmartPtr:Destructor*/
-End-
