Code

有时，我们希望从一组三个以上的点集求出平面方程，这种点集最常见的例子就是多边形顶点。在这种情况下，这些顶点绕多边形顺指针或逆时针地列出。（顺序很重要，因为要依据它决定哪边是"正面"哪边是"反面"。） 一种糟糕的方式是任选三个连续的点并用这三个点计算平面方程。毕竟所选的三个点可能共线，或接近共线。因为数值精度的问题，这将非常糟糕。或者，多边形可能是凹的，所选的点恰好在凹处，从而构成了逆时针（将导致法向量方向错误）。又或者，多边形上的顶点可能不是共面的，这可能是由数值上的不精确，或错误的生成多边形的方法所引起的。我们真正想要的是从点集中求出"最佳"平面的方法，该平面综合考虑了所有的点。 这里提供一个通用且效率较高的算法，计算一组有序点集（顺时针或逆时针）的最佳法向量。 计算公式，其中Pn+1== P1 ： 算法实现代码（C++实现）： #include <cstdio> #include <cmath> #include <vector> using std::vector; struct point { double x; double y; double z; point():x(0),y(0),z(0) {} point(double i, double j, double k):x(i),y(j),z(k) {} void normalize() { double len = sqrt(x*x + y*y + z*z); x /= len; y /= len; z /= len; } void display() { printf("x=%5.2f, y=%5.2f, z=%5.2f\n",x,y,z); } }; int main() { vector<point> pts; pts.push_back(point(0,100,0)); pts.push_back(point(10,100,10)); pts.push_back(point(20,100,100)); pts.push_back(point(0,100,100)); if(pts.size()<=3) { printf("oops\n exit!\n"); return 0; } point pre = *(pts.end()-1); point ans = point(); vector<point>::iterator itr = pts.begin(); while(itr!=pts.end()) { point cur = *itr; ans.x += (pre.z+cur.z)*(pre.y-cur.y); ans.y += (pre.x+pre.x)*(pre.z-cur.z); ans.z += (pre.y+cur.y)*(pre.x-cur.x); pre = cur; ++itr; } ans.normalize(); ans.display(); return 0; } PS:本算法的通用性较高，甚至可以用于不共面的点集。 ...

在对线性表的操作中，经常需要查找一个元素在表中的位置。通常最坏的办法是遍历整个线性表，以找到某元素的位置或者不在表中。 但是如果线性表是有序的，比如由小到大递增（完全可以是自定义的比较方法），那么在这种情况下使用二分查找法会是首选。当然，这么重要的函数，一般的库都会提供，比如： C provides bsearch() in its standard library. C++’s STL provides algorithm functions binary_search, lower_bound and upper_bound. Java offers a set of overloaded binarySearch() static methods in the classes Arrays and Collections in the standard > java.util package for performing binary searches on Java arrays and on Lists, respectively. They must be arrays of > primitives, or the arrays or Lists must be of a type that implements the Comparable interface, or you must specify a > custom Comparator object. ...

向map中添加或更新元素通常有两个办法：map::operator[] 和 成员函数map::insert()。在数据量很小和元素比较简单的情况的情况下，通常两种方法不会有效率上的差异，但是，一旦数据量很大，或元素很复杂（自定义的比较复杂的类）时，就会出现效率上的差异。因此向map中添加元素通常有这么一个原则： 当向map中添加元素时，应优先选用insert(), 而不是operator[]; 当更新已经在map中的元素时，应优先选用operator[]. 首先解决一个问题：insert()更新元素？怎么用啊？确实可以用，就是看着很别扭而且效率不高。看下面的代码 map<int,double> m; m[1]=10.0; //赋值 m[2]=11.0; //赋值 m[3]=12.0; //赋值 m[2]=18.0; //更新 map<int, double> m2; m2.insert(make_pair(1,10.0)); //赋值 m2.insert(make_pair(2,11.0)); //赋值 m2.insert(make_pair(3,12.0)); //赋值 m2.insert(make_pair(2,18.0)).first->second = 18; //更新 其次,有必要定义一个函数,实现向map中高效的添加或更新元素. template<typename MapType,typename KeyArgType,typename ValueArgType> typename MapType::iterator effecient_add_update(MapType &m, KeyArgType const& k, ValueArgType const & v) { typename MapType::iterator itrLB = m.lower_bound(k); if (itrLB != m.end() && !(m.key_comp()(k,itrLB->first)) ){ itrLB->second = v; return itrLB; } else{ return m.insert(itrLB,make_pair(k,v)); } } 这个算法真的很有趣, 首先是算法的高效性, 其次是形式上的优美. ...

质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数(也可定义为包含1和本身的因子等于2个)。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。(From wikipedia) 下面提供判断一个整数是否是质数的简单C实现: #include <stdio.h> #include <stdlib.h> #include <math.h> int Prime(int num) { num = abs(num); if ((num==0)&&(num==1)) return 0; /*int k = num/2;*/ int k =(int)sqrt(num); while((k>1)&&(num%k)) { --k; } return 1==k; } int main() { int num; printf("Please input an integer (Ctrl-Z to exit) : "); while(scanf("%d",&num)) { if (Prime(num)){ printf("\n%d is a Prime.\n",num); } else printf("\n%d is not a Prime.\n",num); printf("\nPlease input an integer (Ctrl-Z to exit) : "); } } 算法逻辑： Prime函数用来判断某个整数num是否是质数，是则返回非零整数，否则返回零。 Prime函数内部，首先定义一个num的中间数k，可以是num的一半，可以是num的平方根，当然也可以是原数，这里选取平方根，因为这样做效率更高。然后拿这个数k 与 num相除，同时k递减。如果num是质数，那么k在递减的过程中都不会整除num，直到k==1 ; 而如果num不是质数，那么就会找到num的一个非1的因数。

用C实现简单循环队列结构 /* * 用C实现简单循环队列结构 * * 循环队列的类型定义如下： * typedef struct{ * valuetype data[MAXSIZE]; [>数据的存储区<] * int font, rear; [>队首队尾<] * int num; [>队列中元素的个数<] * }Circular_Queue; * 循环队列常用函数如下： * （1）Circular_Queue * Init_CirQueue(): 初始化队列 * （2）int In_CirQueue(Circular_Queue *q, valuetype x): 将元素x插入队列q的队尾，若成功返回1，否则返回0 * （3）int Out_CirQueue(Circular_Queue *q, valuetype *x): 取出队列q队首位置的元素，若成功返回1，否则返回0 */ /*程序代码：*/ #include <stdio.h> #include <malloc.h> #define MAXSIZE 100 typedef int valuetype; typedef struct{ valuetype data[MAXSIZE]; /*数据的存储区*/ int font, rear; /*队首队尾*/ int num; /*队列中元素的个数*/ }Circular_Queue; Circular_Queue * Init_CirQueue() { Circular_Queue *q = (Circular_Queue*)malloc(sizeof(Circular_Queue)); q->font = q->rear = MAXSIZE-1; q->num = 0; return q; } int In_CirQueue(Circular_Queue *q, valuetype x) { if(q->num == MAXSIZE) return 0; /*队满，不能入队*/ else { /*q->rear = (q->rear+1)%MAXSIZE;*/ q->data[q->rear] = x; q->rear = (q->rear+1)%MAXSIZE; q->num++; return 1; } } int Out_CirQueue(Circular_Queue *q, valuetype *x) { if(q->num == 0) return 0; /*队空*/ else{ *x = q->data[q->font]; q->font = (q->font+1)%MAXSIZE; q->num--; return 1; } } int main() { Circular_Queue *queue = Init_CirQueue(); int x=0; for(int i=0;i<10;++i) { if(!In_CirQueue(queue, i)) break; } while(Out_CirQueue(queue, &x)) printf("%d ",x); printf("\n"); return 0; }

八皇后问题递归回溯算法实现 /* * 八皇后问题递归回溯算法实现 * * 八皇后问题或N皇后问题描述为： * 求解如何在N*N的棋盘上无冲突地排放N个皇后棋子。其中，皇后的移动方式规定为水平、竖直及45°斜线方向。因此，在任意一个皇后所在位置的水平、竖直和45°方向上都不能出现其他的皇后棋子。 * * 回溯法的基本思想是：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一个结点时，要先判断该结点是否包含问题的解，如果包含，就从该节点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该节点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程又叫做解空间树的剪枝操作。 * * 八皇后问题可以有很多解法，其中之一是回溯法。 * 用回溯法求解八皇后问题，可以按列试探可能的解，一旦该列找不到任何可能的解那么就要向后回溯。 */ /*程序代码如下：*/ #include <stdio.h> #define NUM 8 /*棋盘用NUM*NUM的矩阵Q描述，其中，里面的元素如果是1表示可以放置皇后，如果为0表示不能放置皇后，另外，(i,j)表示矩阵的第(i,j)个元素*/ /*判断能否在(i,j)位置放置皇后*/ int isOK(int i, int j, int (*Q)[NUM]) { int s=0, t=0; for(s=i,t=0;t<NUM;++t) /*判断行*/ if(t!=j && Q[s][t]==1) return 0; for(s=0,t=j;s<NUM;++s) /*判断列*/ if(s!=i && Q[s][t]==1) return 0; for(s=i-1,t=j-1;s>=0&&t>=0;--s,--t) /*判断左上方*/ if(Q[s][t]==1) return 0; for(s=i+1,t=j-1;s<NUM&&t>=0;++s,--t) /*判断左下方*/ if(Q[s][t]==1) return 0; /* Thank @ewitt*/ /* 下面的东西没用 */ /* for(s=i-1,t=j+1;s>=0&&t<NUM;--s,++t) //判断右上方 * if(Q[s][t]==1) * return 0; * for(s=i+1,t=j+1;s<NUM&&t<NUM;++s,++t) //判断右下方 * if(Q[s][t]==1) * return 0; */ return 1; } void Queen(int j, int (*Q)[NUM]) { if(j==NUM) /*找到一个解*/ { for(int i=0;i<NUM;++i) { for(int k=0;k<NUM;++k) printf("%d ",Q[i][k]); printf("\n"); } printf("\n"); return; } else{ for(int i=0;i<NUM;++i) { if(isOK(i,j,Q)) /*如果可以*/ { Q[i][j]=1; Queen(j+1,Q); /*深度优先探索解空间树*/ Q[i][j]=0; } } } } /*test program*/ int main() { int Q[NUM][NUM]; int i=0, j=0; for(i=0;i<NUM;++i) for(j=0;j<NUM;++j) Q[i][j] = 0; /*初始化*/ Queen(0,Q); return 0; }

##用C语言实现简单链式队列结构 /* * 用链式结构实现的队列称为链队。根据队列的FIFO原则，为了操作上的方便，可以用带头指针font和尾指针rear的单链表来实现队列。链队结构描述： * typedef struct node * { * valuetype data; * struct node *next; * }QNode; [>链队结点的类型<] * typedef struct * { * QNode *font, *rear; * }LQueue; [>将头尾指针封装在一起的链队<] * * 设q是一个指向链队的指针，即LQueue *q. 各函数的功能如下： * （1）LQueue * Init_LQueue(): 创建并返回一个带头尾结点的空链队 * （2）int Empty_LQueue(LQueue *q): 判断链队是否为空 * （3）void In_LQueue(LQueue *q, valuetype x) : 将数据x压入链队q * （4）int Out_LQueue(LQueue *q, valuetype *x) : 弹出链队q的第一个元素x, 若成功则返回1否则返回0 * By Guv 2011.06.10 */ /*程序代码：*/ #include <stdio.h> #include <malloc.h> typedef int valuetype; typedef struct node { valuetype data; struct node *next; }QNode; typedef struct { QNode *font, *rear; }LQueue; LQueue * Init_LQueue() { LQueue *q; QNode *p; q = (LQueue*)malloc(sizeof(LQueue)); /*申请链队指针*/ p = (QNode*)malloc(sizeof(QNode)); /*申请头尾指针结点*/ p->next = NULL; q->font = q->rear = p; return q; } int Empty_LQueue(LQueue *q) { if(q->font != q->rear) return 0; else return 1; } void In_LQueue(LQueue *q, valuetype x) { QNode *p = (QNode *)malloc(sizeof(QNode)); /*申请新结点*/ p->data = x; p->next = NULL; q->rear->next = p; q->rear = p; } int Out_LQueue(LQueue *q, valuetype *x) { if(Empty_LQueue(q)) return 0; /*空链队*/ else{ QNode *p = q->font->next; *x = p->data; q->font->next = p->next; free(p); if (q->font->next == NULL) q->rear = q->font; return 1; } } int main() { LQueue *queue = Init_LQueue(); for (int i=0;i<10;++i) { In_LQueue(queue, i); } while(!Empty_LQueue(queue)) { int k=0; Out_LQueue(queue, &k); printf("%d ",k); } printf("\n"); return 0; }

把数组的前k位逆置 /* * 逆置数组arr的前k位: * (1)递归实现 * (2)迭代实现 * PS.通常递归算法能解决一些不能直接解决的问题， * 但是递归算法通常要做出效率上的牺牲 * By Guv 2011.06.04 * */ #include <stdio.h> /*递归实现*/ void invert(int arr[], int k) { if(k>1){ invert(arr+1,k-2); int tmp = arr[0]; arr[0] = arr[k-1]; arr[k-1] = tmp; } } /*迭代*/ /* void invert(int arr[], int k) { int tmp=0, mid = k/2; if (k<2) return; for(int i=0;i<mid;++i){ tmp = arr[i]; arr[i] = arr[k-1-i]; arr[k-1-i] = tmp; } } */ /*testing*/ int main() { int array[] = {1,2,5,9,8,7,6,3,5,6,7,8,9,5,6,4,1,5,2,6,3,5}; int num = sizeof(array)/sizeof(int); printf("before inverted:"); for(int i=0;i<num;++i){ if (i%5==0) printf("\n"); printf("%d, ", array[i]); } invert(array, num); printf("\nafter inverted:"); for(int i=0;i<num;++i){ if (i%5==0) printf("\n"); printf("%d, ", array[i]); } }

C语言实现简单的链式栈结构 /* * 用链式存储结构实现的栈称为链栈。若链栈元素的数据类型为valuetype,以LinkStack记链栈结构，其类型定义为： * typedef struct node * { * valuetype data; * struct node * next; * } StackNode, *LinkStack; * * 由于栈的主要操作都是在栈顶进行的，因此把链表的头部作为栈顶。设top为栈顶指针，即：LinkStack top. * 下面为各函数的功能说明： * （1）LinkStack Init_LinkStack() : 建立并返回空的链栈 * （2）int Empty_LinkStack(LinkStack top) : 判断top所指链栈是否为空 * （3）LinkStack Push_LinkStack(LinkStack top, valuetype x) : 将数据x压入top所指的栈顶，并返回新栈指针 * （4）LinkStack Pop_LinkStack(LinkStack top, valuetype *x) : 弹出top所指链栈的栈顶元素x,返回新栈指针 * */ #include <stdio.h> #include <malloc.h> typedef int valuetype; typedef struct node { valuetype data; struct node * next; } StackNode, *LinkStack; LinkStack Init_LinkStack() { return NULL; } int Empty_LinkStack(LinkStack top) { if (top==NULL) return 1; else return 0; } LinkStack Push_LinkStack(LinkStack top, valuetype x) { StackNode *s = (StackNode *)malloc(sizeof(StackNode)); s->data = x; s->next = top; return s; } LinkStack Pop_LinkStack(LinkStack top, valuetype *x) { StackNode *p; if (top==NULL) return NULL; else { *x = top->data; p = top->next; free(top); return p; } } int main() { LinkStack linkstack = Init_LinkStack(); int i=0; int x=0; for (i=0;i<10;++i) { linkstack = Push_LinkStack(linkstack, i); } while(linkstack) { linkstack = Pop_LinkStack(linkstack, &x); printf("%d ",x); } printf("\n"); }

用C语言实现一个简单链表数据结构 /* * 本程序实现了一个简单的单向链表，其中 * （1）函数 first_insert()的功能是在已知链表的首表元之前插入一个指定值的表元 * （2）函数 reverse_copy()的功能是把已知链表，按照逆序复制出一个新链表 * （3）函数 print_link()用来输出链表中各表元的值 * （4）函数 free_link()用来释放链表的全部表元 * By linccn 2011.06.06 * */ #include <stdio.h> #include <malloc.h> typedef struct node{ int val; struct node *next; }NODE; void first_insert(NODE ** p, int v) { NODE *q = (NODE *)malloc(sizeof(NODE)); q->val = v; q->next = *p; *p = q; } NODE *reverse_copy(NODE *p) { NODE *u; for (u=NULL;p!=NULL;p=p->next) first_insert(&u, p->val); return u; } void print_link(NODE *p) { for (;p!=NULL;p=p->next) printf("%d, ", p->val); printf("\n"); } void free_link(NODE *p) { NODE *u; while(p!=NULL){ u = p->next; free(p); p = u; } } int main() { NODE *link1, *link2; int i; link1 = NULL; for(i=1;i<10;++i) first_insert(&link1, i); link2 = reverse_copy(link1); print_link(link2); free_link(link1); free_link(link2); return 0; }