编程中的基本数据结构与算法思想 _算法

编程的关键在于选择数据结构和算法，数据结构用于描述问题，算法用于描述解决问题的方法和步骤。
描述问题的数据除了各数据元素本身，还要考虑各元素的逻辑关系，主要是一对一的线性关系，一对多的树型关系和多对多的图形关系。另外，内存中对各数据元素的存储只有顺序存储和链式存储两种方式，所以数据结构还要考虑数据的存储结构，并考虑逻辑结构与数据结构如何有效地结合到一起。
用算法描述问题，当问题比较复杂时，通常的思路是分而治之，并辅以适当的数据结构。
1 分治法Divide and Conquer分治法通常描述为以下三步：

Divide the problem into more subproblems（分解问题为众多的子问题）;
Conuqe(solve) the subproblems（解决各子问题）;
Combine(merge) the solution of subproblems(if need)（合并各子问题的解（如果需要））.

如用分治法来计算2^10?
2^10＝2^5*x^5=2^2*x^3*x^5=32*32=1024
相对于顺序查找，二分查找有更高的效率，前提是二分查找需要事先排好序：
int binarySearchLoop(int arr[], int len, int findData){ if(arr==NULL || len <=0)return -1; int start = 0; int end = len-1; while(start<=end) {int mid = start+(end-start)/2;if(arr[mid] == findData)return mid;else if(findData < arr[mid])end = mid-1;elsestart = mid+1; } return -1;}2 枚举法也是一种暴力缩小问题规模的算法简单的枚举算法也是可以优化的，即尽可能缩小搜索的空间，如判断质数：

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

判断质数的函数：
int isPrime(int n){ if(n<= 1)// 小于等于1的整数不可能是素数return 0; if(n == 2); // 2 是素数return 1; if(n%2 == 0); // 能被2整除的其他整数都不是素数return 0; int limit = (int)sqrt((double)n)+1; for(int i = 3; i <= limit; i=i+2) {if(n % i == 0)return 0; } return 1;}isPrime()没有必要枚举所有的因子。
I 只要发现任何一个大于1小于n的因子，就能停下来报告n不是素数。
II 如果n能被2整除，直接报告n不是素数。如果n不能被2整除，那么它也不可能被4或6或其他偶数整除。因此， isPrime只需要检查2和奇数（由3开始，步长为2）。但注意有个特例， 2能被2整除，但2是素数。
III 如果n不是素数，则必有一个因子小于√n。因此不需要检查到n为止。只需检查到√n（n=√n*√n）。
因为如果n能被2~n-1之间任一整数整除，其二个因子必定有一个小于或等于√n ，另一个大于或等于√n 。例如24可以表示为：2*12、3*8、4*6 ，前面的因子小于√24 ，后面的因子大于√24 ，检验出了小因子，即可判断n是否为素数，就像逻辑运算的短路求值。
3 程序的模块化分治法在程序思想中的应用就是实现程序的模块化，包括面向过程的函数化和面向对象的对象化。
许多原因都促使我们将应用程序分解成函数，下面仅列举其中三个：
函数一般小而具体。用一系列函数来写程序，胜于一气呵成写完整个程序。这称为“分而治之” ，使你的精力一次集中在一个函数上。
包含许多小函数的应用程序比单一的长程序更容易阅读和调试。
函数可以重用。函数写好后可在程序的其他任何地方调用。这减少了编码量，提高了开发效率。
4 函数调用与栈首先讨论一个从a点出发去f点，然后回到a点的问题（中间的b、c、d、e都有多个分岔口）：
a→b2→c1→d3→e2→f ，每个分岔口都有一个信封，告诉你应该走哪一个分支，为了能够正确地回到起点a ，正确的做法是拿到一个信封后，即将这个信封叠在上一次拿到的信封的上面，回去时，依次从上面拿取信封，按提示即可正确返回。
其做法就是依次放入，依次取出，信封之间是顺序关系，只在一端操作，也就是不管是放入还是取出都不在中间操作。这样一种思路在计算机上用数据来描述就是后进先出的栈，函数的调用、返回，递归、回溯算法都需要使用栈这种数据结构（由程序员或递归时由编译器来实现）。