目錄
0 等概率隨機(jī)洗牌：
1 大小寫轉(zhuǎn)換
2 字符串復(fù)制
4 輾轉(zhuǎn)法求最大公約數(shù)
5 交換兩個整數(shù)
6 二分搜索
7 逆向迭代的猴子吃桃問題
8 輸出各基本數(shù)據(jù)類型的內(nèi)存字節(jié)16進(jìn)制值
9 求數(shù)組長度
10 單循環(huán)找出數(shù)組中的最大值和次大值
11 返回某年的1月1號是星期幾
12 數(shù)字字符串轉(zhuǎn)浮點數(shù)
13 用函數(shù)對象求斐波那契數(shù)列：
14 判斷某一整數(shù)是否是2的整數(shù)次冪
15 如何較友好地停住控制臺窗口
16 以某一基準(zhǔn)實現(xiàn)向上舍入，用宏實現(xiàn)*p++
17 如何縮小解空間判斷是否是素數(shù)
18 單詞統(tǒng)計
19 返回某區(qū)間的隨機(jī)數(shù)
20 使用枚舉和共用體組合結(jié)構(gòu)體
21 使用位域和共用體將double分成4部分顯示：
22 算術(shù)運算和位運算模擬比較運算符和條件語句
23 模板遞歸求階乘
24 memmove()實現(xiàn)
25 定義時間延遲函數(shù)
26 歸并排序
26 快速排序
27 堆排序
28 希爾排序
29 鏈表迭代器自定義
30 string自定義
31 自定義vector
32 智能指針模擬
0 等概率隨機(jī)洗牌：
for(int i = n – 1; i >= 0 ; i — ) swap(arr[i], arr[rand(0, i)]) ;// rand(0, i) 生成 [0, i] 之間的隨機(jī)整數(shù)
1 大小寫轉(zhuǎn)換
#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 字符串復(fù)制
#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 求平方根和開整數(shù)次方
double sqrt(double x,double x0)// x是用于求平方根的數(shù)，x0是平方根的估算，可以是x/2{ if(x 1e-5 || x1*x1-x 0) {// 以下4個表達(dá)式來聯(lián)系起來思考 if (n%2 == 1) // n%2 與 n/2 ret=ret * x; // x 會在此會以x^2迭代 x = x * x; n = n/2; } return ret;}
4 輾轉(zhuǎn)法求最大公約數(shù)
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 交換兩個整數(shù)
#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; // 最后一天桃子數(shù) while(days>1) { peaches = (peaches+1)*2; // 倒推遞歸 days–; } return peaches;}int peachCountRecursive(int day) // 遞歸{ if(day == 1) // 最后一天，問題規(guī)模為1時 return 1; else return (peachCountRecursive(–day)+1)*2;}
8 輸出各基本數(shù)據(jù)類型的內(nèi)存字節(jié)16進(jìn)制值
c的指針可以將任意粒度的數(shù)據(jù)控制到字節(jié)。
void printIntBin(unsigned long n) // 輸出unsigned的二進(jìn)制位{ bool r = (01&n); if(n>=2) printIntBin(n>>1); // 遞歸 putchar(r?’1′:’0′);}void showBytes(unsigned char* start, int len) // 輸出len個start開始內(nèi)存的16進(jìn)制編碼{ for(int i=0;i=0;i–) printf(” %.2x”,start[i]); printf(“”); }}
9 求數(shù)組長度
long arr[] = {1,3,5,6,2,4,8}; int n = sizeof arr / sizeof *arr; // 少打幾個字符，*arr即數(shù)組首元素
10 單循環(huán)找出數(shù)組中的最大值和次大值
#include #define N 20// 構(gòu)造一個最小值，用做最大和次大的初始值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; }/* 將下面數(shù)據(jù)粘貼入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 數(shù)字字符串轉(zhuǎn)浮點數(shù)
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 用函數(shù)對象求斐波那契數(shù)列：
利用對象的狀態(tài)。
#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 判斷某一整數(shù)是否是2的整數(shù)次冪
bool is2pow(int m) // m的二進(jìn)制位是否只有一個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 以某一基準(zhǔn)實現(xiàn)向上舍入，用宏實現(xiàn)*p++
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) – 1) & ~(sizeof(int) – 1) ) va_arg(p,type) ( *(type *)((p += _INTSIZEOF(type)) – _INTSIZEOF(type)) )
上面第一個宏可以實現(xiàn)sizeof(int)的向上舍入，表示數(shù)據(jù)對齊；
上面第二個宏在模擬*p++，相當(dāng)于*p; p++; 首先是整體表達(dá)式的值是+_INTSIZEOF(type)－_INTSIZEOF(type)，沒有影響到整體表達(dá)式的值，但p += _INTSIZEOF(type)對p產(chǎn)生了負(fù)作用，相當(dāng)于指針的p++。
17 判斷是否是素數(shù)
暴力枚舉也是盡可能先縮減解空間。
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 單詞統(tǒng)計
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 返回某區(qū)間的隨機(jī)數(shù)
int randInt(int low,int high){ double quo = 1.0/(RAND_MAX+1.0); return int(low+(rand()*quo)*(high-low+1));}
20 使用枚舉和共用體組合結(jié)構(gòu)體
// 存貨記錄的聲明// 零件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; // 小數(shù)位 低32位 unsigned int low20:20; // 小數(shù)位 低33-52位 unsigned int exp11:11; // 指數(shù)位 低53-63位，移碼1023+二進(jìn)制整數(shù)位-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 算術(shù)運算和位運算模擬比較運算符和條件語句
void compareEx(int a,int b) // 算術(shù)運算和位運算模擬比較運算符和條件語句{ 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 模板遞歸求階乘
模板可以被遞歸調(diào)用，在模板遞歸的過程中，可以執(zhí)行兩種編譯期計算：數(shù)值計算和類型計算。
#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的值來具現(xiàn)化主模板，一直到N變?yōu)?，這時選擇Factorial的特化版本template struct Factorial，內(nèi)部的value變?yōu)?，遞歸終止。
24 memmove()實現(xiàn)
#include void * my_memmove(void * dst,const void * src,int count)// 從src開始移動count個字節(jié)到dst{ void * ret = dst; if(dst <= src || ((char *)src + count) <= (char *)dst) // dst在前或src在前但內(nèi)存區(qū)域不重疊 { while(count–) { *(char *)dst = *(char *)src; dst = (char *)dst + 1; src = (char *)src + 1; } } else // (src<dst && (char *)dst < ((char *)src + count)) // src在前且內(nèi)存區(qū)域有重疊 { // 也就是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 定義時間延遲函數(shù)
#include #include //定義時間延遲函數(shù)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; // 前一數(shù)組的起始元素 int j = mid + 1; // 后一數(shù)組的起始元素 while(i <= mid && j <= right)// 從小到大依次放到輔助數(shù)組中 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++)// 將合并后的序列復(fù)制到原來的A數(shù)組 A[left++] = temp[k];}// 遞歸實現(xiàn)的歸并排序(自頂向下)void MergeSortRecursion(int A[], int left, int right) { if(left == right) // 當(dāng)待排序的序列長度為1時，遞歸開始回溯，進(jìn)行merge操作 return; int mid =(left + right) / 2; MergeSortRecursion(A, left, mid); // 參數(shù)迭代：right = mid MergeSortRecursion(A, mid + 1, right); // 參數(shù)迭代：left = mid+1 Merge(A, left, mid, right); // 遞歸返回時執(zhí)行部分 Merge(A, left, mid, right);}// 非遞歸(迭代)實現(xiàn)的歸并排序(自底向上)void MergeSortIteration(int A[], int len) { int left, mid, right;// 子數(shù)組索引,前一個為A[left…mid]，后一個子數(shù)組為A[mid+1…right] for(int i=1; i<len; i*=2) // 子數(shù)組的大小i初始為1，每輪翻倍 { left = 0; while(left + i < len) // 后一個子數(shù)組存在(需要歸并) { mid = left + i – 1; right = (mid+i)<len?mid+i:len-1;// 后一個子數(shù)組大小可能不夠 Merge(A, left, mid, right); left = right + 1; // 前一個子數(shù)組索引向后移動 } }}
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]向下進(jìn)行堆調(diào)整{ int left_child = 2 * i + 1; // 左孩子索引 int right_child = 2 * i + 2; // 右孩子索引 int max = i; // 選出當(dāng)前結(jié)點與其左右孩子三者之中的最大值 if (left_child A[max]) max = left_child; if (right_child A[max]) max = right_child; if (max != i) { Swap(A, i, max); // 把當(dāng)前結(jié)點和它的最大(直接)子節(jié)點進(jìn)行交換 Heapify(A, max, size); // 遞歸調(diào)用，繼續(xù)從當(dāng)前結(jié)點向下進(jìn)行堆調(diào)整 }}int BuildHeap(int A[], int n) // 建堆，時間復(fù)雜度O(n){ int heap_size = n; for (int i = heap_size / 2 – 1; i >= 0; i–) // 從每一個非葉結(jié)點開始向下進(jìn)行堆調(diào)整 Heapify(A, i, heap_size); return heap_size;}void HeapSort(int A[], int n){ int heap_size = BuildHeap(A, n); // 建立一個最大堆 while (heap_size > 1) { // 堆（無序區(qū)）元素個數(shù)大于1，未完成排序 // 將堆頂元素與堆的最后一個元素互換，并從堆中去掉最后一個元素 // 此處交換操作很有可能把后面元素的穩(wěn)定性打亂， // 所以堆排序是不穩(wěn)定的排序算法 Swap(A, 0, –heap_size); Heapify(A, 0, heap_size); // 從新的堆頂元素開始向下進(jìn)行堆調(diào)整，時間復(fù)雜度O(logn) }}
28 希爾排序
void output(int a[], int n){ //輸出數(shù)組元素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.數(shù)據(jù)組成template struct singleList{ singleList* next; T data; singleList() // 創(chuàng)建表頭 { this->next = NULL; } singleList(T data) // 創(chuàng)建節(jié)點 { this->data = data; this->next = NULL; } // 創(chuàng)建節(jié)點+連接節(jié)點的功能 singleList(T data, singleList* next) { this->data = data; this->next = next; }};template class list{public: list() // 構(gòu)造函數(shù)作用:構(gòu)造對象 { // 初始化基本數(shù)據(jù)成員，描述最初狀態(tài) 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() //測試行為：遍歷結(jié)構(gòu)（打印輸出） { 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) // 實現(xiàn)begin對iterator對象的初始化 { // 實質(zhì)初始化對象中的屬性 this->pMove = pMove; } singleList* getData() { return pMove; } bool operator!=(singleList* pMove) { return this->pMove != pMove; } iterator& operator++(int) //i=i+1; //實質(zhì)是鏈表的一個移動指針走到一下一個節(jié)點 { this->pMove = this->pMove->next; return (*this); } T operator*() { return this->pMove->data; } protected: singleList* pMove; // 迭代器就是對容器元素指針的封裝 }; protected: // 抽象數(shù)據(jù)成員 // 遵循的原則：抽象出來的屬性能夠便于描述行為(成員函數(shù)) 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是占坑的代碼，樁代碼給出的實現(xiàn)是臨時性的/待編輯的。{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();}//增加一個塊結(jié)構(gòu)，為了看到對象離開作用域后的析構(gòu)結(jié)果system(“pause”);return 0;}/*output:SmartPtr:Destructoraccess through NULL pointerStub:DestructorStub:printStub:print//以下是離開作用域后的析構(gòu)SmartPtr:DestructorSmartPtr:DestructorStub:DestructorSmartPtr:Destructor*/
-End-
