- 顺序检索。逐个查看每个数据元素是不是要找的那一个。顺序检索非常简单，但是它的工作量与被检索数据的数目成正比。这种检索也成为线性检索。
- 二分检索。做检索的表格本身必须是排好序的，程序还必须知道表格的长度。算法复杂度：log(n)。 // lookup: binary search for value in arr; returen it's index int lookup(int arr[], int length, int val) { int index = -1; int low = 0; int high = length - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (val < arr[mid]) { high = mid - 1; } else if ( val > arr[mid]) { low = mid + 1; } else { index = mid; break; } } return index; }
- 最好的排序算法之一是快速排序(quicksort)，其工作方式就是在数组中划分出小的和大的元素：
把其他元素分为两组：
“小的” 是那些小于基准值的元素；
“大的” 是那些大于基准值的元素。
递归地对这两个组做排序。
快排的一种简单实现如下：
#include "stdafx.h" #include
快排的算法复杂度： nlogn。但是，如果执行中经常出现不平均的划分，算法的运行时间可能接近于按 n^2增长。如果数组里所有的值都一样，就会使算法的运行时间达到与n^2成比例。
更多排序见 排序小结。
3. 库
C和C++的标准库里已经包含了排序函数。
- C函数库(stdlib.h)中排序函数是qsort，在调用qsort时必须为它提供一个比较函数，以为在排序中需要比较两个值。由于这里的值可以是任何类型，所以参数是两个void*指针。比较函数传递的是数组元素的地址。
char * str[N]; qsort(str, N, sizeof(str[0]), scmp);
eg:
int icmp(const void * p1, const void * p2) { int v1, v2; v1 = *(int *) p1; v2 = *(int *) p2; if (v1 > v2) return 1; else if (v1 == v2) return 0; else return -1; } int _tmain(int argc, _TCHAR* argv[]) { int cqsortArr[8] = {10, 1, 7, 5, 8, 4, 30, 0}; qsort(cqsortArr, NELEMS(cqsortArr), sizeof(cqsortArr[0]), icmp); //#define NELEMS(arr) ( sizeof(arr)/sizeof(arr[0]) ) return 0; }
- 标准C++库(algorithm)里有一个名字为sort的类属算法，保证O(nlogn)的执行性质。使用非常简单，不需要强制转换，也不需要知道元素的大小。对于已知的类型，甚至不要求比较函数。
int cppsortArr[8] = {10, 1, 7, 5, 8, 4, 30, 0}; sort(cppsortArr, cppsortArr + NELEMS(cppsortArr));
4. 一个Java快速排序
Java和C、C++有一个重要的差别：在这里不能把比较函数传递给另一个函数，因为这里没有函数指针。作为替代品，需要建立一个界面，其中仅有的内容就是一个函数，它完成两个Object的比较。这种方法有个限制，只能对所有由Object导出的并带有该机制的类型做排序工作，所以无法用到各种基本类型，如int或double上。对应实现如下：
interface Cmp { int cmp(Object x, Object y); } //Icmp: Integer comparision class Icmp implements Cmp { public int cmp(Object o1, Object o2) { int i1 = ((Integer)o1).intValue(); int i2 = ((Integer)o2).intValue(); if(i1 < i2) return -1; else if(i1 == i2) return 0; else return 1; } } class Quicksort { static Random rgen = new Random(); // sort: quicksort v[left]..v[right] static void sort(Object[] v, int left, int right, Cmp cmp) { int i, last; if(left >= right) // nothing to do return; swap(v, left, rand(left, right)); // move pivot elem last = left; // to v[left] for(i = left + 1; i <= right; i++) //partition { if(cmp.cmp(v[i], v[left]) < 0) swap(v, ++last, i); } swap(v, left, last); // restore pivot elem sort(v, left, last - 1, cmp); // recursively sort sort(v, last + 1, right, cmp); // each part } // swap: swap v[i] and v[j] static void swap(Object[] v, int i, int j) { Object temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } // rand: returen random integer in [left, right] including left and right. static int rand(int left, int right) { return left + Math.abs(rgen.nextInt())%(right - left + 1); } } class TestQuickSort { public static void main(String[] args) { int i; int[] arr = {10,2,5,3,11,9,0}; Integer[] integerArr = new Integer[arr.length]; for (i = 0; i < integerArr.length; i++) { integerArr[i] = new Integer(arr[i]); } Quicksort.sort(integerArr, 0, integerArr.length - 1, new Icmp()); for (i = 0; i < integerArr.length; i++) { System.out.println(integerArr[i]); } } }
对应的C#实现如下：
public interface IComp { int cmp(object o1, object o2); } public class Int32Comp : IComp { public Int32 cmp(object o1, object o2) { Int32 i1 = Convert.ToInt32(o1); Int32 i2 = Convert.ToInt32(o2); if (i1 < i2) { return -1; } else if (i1 == i2) { return 0; } else { return 1; } } } public class Quicksort { private static Random rd = new Random(); public static void Sort
5. 大O记法
我们常需要描述特定算法?相对于n(输入元素的个数)需要做的工作量。人们提供一中标准的记法，成为“大O记法”。在描述中使用的基本参数是n，即问题的规模，把复杂性或运行时间表达为n的函数。这里的复杂性应该看作是算法的时间或空间开销的一种抽象。
我们还应该区分算法的最坏情况的行为和期望行为。例如，快速排序的最坏情况运行时间是O(n^2)，但期望时间是O(nlogn)。
下面是些常见算法的时间复杂度：
记法 名字 例子
O(1) 常数 下标数组访问
O(logn) 对数 二分检索
O(n) 线性 字符串比较
O(nlogn) nlogn 快速排序
O(n^2) 平方 简单排序算法
O(n^3) 立方 矩阵乘法
O(2^n) 指数 集合划分
6. 可增长数组
我们常常需要记录一个包含某些东西的变量的变化情况，对此数组仍然是一种选择。为减小重新分配的代价，数组应当以成块的方式重新确定大小。C++和Java标准库里可以找到具有这种性质的类，在C中可以通过struct实现。
typedef struct Nameval Nameval; struct Nameval { char * name; int value; }; struct NVtab { int nval; /* current number of values */ int max; /* allocated number of values */ Nameval * nameval; /* array of name-value pairs */ }nvtab; enum {NVINIT = 1, NVGROW = 2}; /* addname: add new name and value to nvtab */ int addname(Nameval newname) { Nameval * nvp; if(nvtab.nameval == NULL) // first time { nvtab.nameval = (Nameval *) malloc(NVINIT * sizeof(Nameval)); if(nvtab.nameval == NULL) { return -1; } nvtab.max = NVINIT; nvtab.nval = 0; } else if(nvtab.nval >= nvtab.max) // grow { nvp = (Nameval *) realloc(nvtab.nameval, (NVGROW * nvtab.max) * sizeof(Nameval)); if(nvp == NULL) { return -1; } nvtab.max *= NVGROW; nvtab.nameval = nvp; } nvtab.nameval[nvtab.nval] = newname; return nvtab.nval++; }
函数addname返回刚加入数组的小标，出错返回-1.
对realloc调用将把数组增长到一个新的规模，并保持已有的元素不变。该函数返回指向新数组的指针；当存储不够时返回NULL。由于重新分配，数组的位置可能改变，程序其他部分对数组元素的访问必须通过下标进行，而不能通过指针。
上面代码如果采用下面的方式：
nvtab.nameval = (Nameval *) realloc(nvtab.nameval, (NVGROW * nvtab.max) * sizeof(Nameval));
如果采用这种方式，当重新分配失败时原来的数组就会丢失。
按说realloc的返回值不必强制转换到最后的类型，因为C能自动完成对void*的提升。而C++中就不同，必须做类型强制转换。
强制转化 ==> 清晰而认真
不做强制转化 ==> 强制转化可能掩盖真正的错误。
我们选择强制转化，因为这种写法能同时使用于C和C++，付出的代价就是减少了编译器检出错误的可能性。
删除name需要点技巧，因为要决定怎样填补删除后数组中留下的空隙。如果数组顺序并不重要，最简单的方法就是把数组最后的元素复制到这。如果还要保持原有顺序，只能把空洞后所有的元素向前移一个位置：
/* delname: remove the first matching nameval from nvtab */ int delname(char * name) { int i; for (i = 0; i < nvtab.nval; i++) { if (strcmp(nvtab.nameval[i].name, name) == 0) { memmove(nvtab.nameval + i, nvtab.nameval + i + 1, (nvtab.nval - (i + 1)) * sizeof(Nameval)); nvtab.nval--; return 1; } } return 0; }
memmove是标准库函数，用于复制任意大小的存储区块。
void * _cdecl memmove(void * _Dst, const void * _Src, size_t _Size)
在ANSI C 的标准库中定义了两个相关函数： memcpy 的速度快，但是如果源位置和目标位置重叠，有可能覆盖掉存储区中的某些部分；memmove函数的速度可能慢，但总能保证复制的正确完成。尽量使用memmove以避免很容易犯的复制顺序错误。
也可以采用其他方法，不做数组元素移动。例如把被删除数组元素标记为未用。随后要插入元素时，先检索是否有无用位置。
数组是组织数据的最简单方式。数组使用非常简单，提供对元素的O(1)访问，能很好的使用二分检索和快速排序，空间开销也比较小。如果保证数据不太多，数组就是最佳选择。但事情也有另一面，在数组里维护一组不断变化的数据代价很高。所以，如果元素数量无法预计，或者可能会非常多，选择其他的数据结构可能更合适。
7. 表
除了数组之外，链表是典型程序里使用最多的数据结构。C++和Java里已经由程序库实现了，在C语言中必须自己实现。
一个单链表包含一组项，每个项都包含了有关数据和指向下一个项的指针。表的头就是一个指针，指向第一个元素，表的结束则用空指针表示。
数组和表之间的差别：首先，数组具有固定的大小，而表则具有恰好能容纳其所有内容的大小，在每个项目里都需要一个指针的附加存储开销。第二，通过修改指针，表里的各种情况很容易重新进行安排，与数组里需要做大范围的元素移动相比，修改几个指针的代价要小得多。最后，当有某些项被插入或删除时，其他的项都不必移动。
如果一个数据集合里的项经常变化，特别是如果项的数目无法预计时，表是一种可行的存储方式。数组更适合存储相对静止的数据。
表的一些基本操作： 在表前或最后加入一个新项，检索一个特定项，在制定项之前或之后插入一个新项，可能还有删除一个项等等。
无法在编译时初始化一个非空的链表，表应该完全动态构造起来。
下边的例子包括了节点定义，在链表的头或尾添加新节点，以及查找节点：
#define eprintf(...) fprintf (stderr, __VA_ARGS__) /* emalloc: malloc and report if error */ void * emalloc(size_t n) { void * p; p = malloc(n); if(p == NULL) { eprintf("malloc of %u bytes failed:", n); } return p; } typedef struct Node Node; struct Node { int value; Node * next; }; Node * newnode(int value) { Node * newN; newN = (Node *) emalloc(sizeof(Node)); newN->value = value; newN->next = NULL; return newN; } /* addfront: add newN to front of listp */ Node * addfront(Node * listp, Node * newN) { newN->next = listp; return newN; } /* addend: add newN to end of listp */ Node * addend(Node * listp, Node * newN) { if(listp == NULL) { return newN; } Node * p; for(p = listp; p->next != NULL; p = p->next) ; { p->next = newN; } return listp; } /* lookup: senquential search for val in listp*/ Node * lookup(Node * listp, int val) { for(; listp != NULL; listp = listp->next) { if(listp->value == val) { return listp; } } return NULL; } // testing in main method int _tmain(int argc, _TCHAR* argv[]) { Node * listp = NULL; listp = addfront(listp, newnode(1)); listp = addfront(listp, newnode(2)); listp = addend(listp, newnode(3)); Node * p = listp; while(p != NULL) { cout << p->value << " "; p = p->next; } cout << endl; Node * nptr = lookup(listp, 1); cout << nptr->value << endl; }
注：emalloc 调用malloc，如果分配失败，报告一个错误并结束程序。
如果要打印表里所有元素，可以直接写个函数，遍历整个链表并打印元素；要计算表的长度，遍历整个表时递增一个计数器；如此等等。这里提供另一种解决问题的方式，可以定义一个apply函数，遍历表并对每个元素调用另一个函数。
/* apply: execute fn for each element of listp */ void apply(Node * listp, void (* fn)(Node *, void *), void * arg) { for(; listp != NULL; listp = listp->next) { (*fn)(listp,arg); } } /* printnv: print value using format in arg */ void printnv(Node * p, void * arg) { char * fmt; fmt = (char *) arg; printf(fmt, p->value); } /* inccounter: increment counter *arg */ void inncounter(Node * p, void * arg) { int * ip; ip = (int *) arg; (*ip)++; } int _tmain(int argc, _TCHAR* argv[]) { int i; Node * listp = NULL; listp = addfront(listp, newnode(1)); listp = addfront(listp, newnode(2)); listp = addend(listp, newnode(3)); apply(listp, printnv, "%x\n"); int n = 0; apply(listp, inncounter, &n); printf("the length of listp is %x\n", n); }
在销毁一个链表时要特别小心：
/* freeall: free all elements of listp */ void freeall(Node * & listp) { Node * p = listp; Node * next; for(; p != NULL; p = next) { next = p->next; free(p); } listp = NULL; }
注：1). 通过指针引用的方式传递listp,目的是置listp 为NULL，防止指向链表头的指针成为野指针。当然也可以在不在freeall里置NULL，而在调用之后再置空。
2). 当一块存储区域被释放之后，程序里就不能再使用它了。因此，在释放listp指向元素之前，必须把listp->next 保存在一个局部变量里。
表特别适合那些需要在中间插入和删除的情况，也适用于管理一批规模经常变动的无顺序数据。如果同时还必须应付频繁的更新和随机访问，那么最好就是使用某些非线性的数据结构，例如树或散列表等。
链表其他常见操作如下（在特定项前或后插入新项，删除特定项，反转链表）
/* addnewbefore: add the new node before the element val if there is _disibledevent=>*/ Node * addnewbefore(Node * listp, int val, Node * newp) { Node * pre = NULL; Node * p = listp; while(p != NULL) { if(p->value == val) { if(pre == NULL) { newp->next = p; return newp; } else { pre->next = newp; newp->next = p; break; } } pre = p; p = p->next; } return listp; } /* addnewafter: add the new node after the element val if there is _disibledevent=>*/ Node * addnewafter(Node * listp, int val, Node * newp) { Node * head = listp; while(listp != NULL) { if(listp->value == val) { newp->next = listp->next; listp->next = newp; break; } listp = listp->next; } return head; } /* deletenode: delete the node val, for the first matching*/ Node * deletenode(Node * listp, int val) { Node * pre = NULL; Node * head = listp; while(listp != NULL) { if(listp->value == val) { if(pre == NULL) { head = listp->next; free(listp); } else { pre->next = listp->next; free(listp); } break; } pre = listp; listp = listp->next; } return head; } /* reverselist: reverse the list by recursion.*/ Node * reverselist(Node * listp) { if(listp == NULL || listp->next == NULL) { return listp; } else { Node * temp = reverselist(listp->next); listp->next = NULL; return addend(temp, listp); } } /*reverselist: reverse the list by loop */ Node * reverselistl(Node * listp) { if(listp == NULL || listp->next == NULL) { return listp; } Node * pre = listp; Node * cur = listp->next; Node * next = NULL; while(cur != NULL) { next = cur->next; cur->next = pre; pre = cur; cur = next; } listp->next = NULL; return pre; } int _tmain(int argc, _TCHAR* argv[]) { int i; Node * listp = NULL; listp = addend(listp, newnode(1)); listp = addend(listp, newnode(2)); listp = addend(listp, newnode(3)); listp = addend(listp, newnode(4)); listp = addend(listp, newnode(5)); listp = addend(listp, newnode(6)); listp = addend(listp, newnode(7)); listp = addend(listp, newnode(8)); cout << "add new node before" << endl; listp = addnewbefore(listp, 1, newnode(100)); apply(listp, printnv, "%d\n"); cout << "add new node after" << endl; listp = addnewafter(listp, 2, newnode(200)); apply(listp, printnv, "%d\n"); cout << "delete node 7" << endl; listp = deletenode(listp, 7); apply(listp, printnv, "%d\n"); cout << "reverse the list by recursion" << endl; listp = reverselist(listp); apply(listp, printnv, "%d\n"); cout << "reverse the list by loop" << endl; listp = reverselistl(listp); apply(listp, printnv, "%d\n"); }
8. 树
树是一种分层性数据结构。在一棵树立存储着一组项，每个项存储一个值，它可以有指针指向0个或多个元素，但是只能被另一个项所指。树根是其中唯一的例外，没有其他项的指针指向它。
用二分检索树说明树的原理，结点中存储的值定义了树结构：对于一个特定结点，其左子树中存储着较小的值，而右子树里存储着较大的值。
/* definition node for tree*/ typedef struct TreeNode TreeNode; struct TreeNode { int value; TreeNode * left; // lesser TreeNode * right; // greater };
由于树的很多结点包含多个指向其他元素的指针，所以，很多在表或者数组结构中需要O(n)时间的操作，在树中只需要O(logn)时间。
二分检索树的构造方式：在树里递归地向下，根据情况确定向左或向右，直接找到了链接新结点的正确位置。结点应该正确地初始化为TreeNode对象，它包括一直值和两个空指针。新结点总是作为叶子加进去，它没有子结点。
/* newtreenode: create a new tree node*/ TreeNode * newtreenode(int value) { TreeNode * newp; newp = (TreeNode *) emalloc(sizeof(TreeNode)); newp->value = value; newp->left = NULL; newp->right = NULL; return newp; } /* insert: insert newp in treep, return treep */ TreeNode * insert(TreeNode * treep, TreeNode * newp) { int cmp; if ( treep == NULL) { return newp; } if (treep->value == newp->value) { printf("insert: duplicate entry %s ignored",newp->value); } else if (newp->value < treep->value) { treep->left = insert(treep->left, newp); } else { treep->right = insert(treep->right, newp); } return treep; }
平衡二叉树严格定义：
一棵空树是平衡二叉树；
若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当 ①TL 、 TR 都是平衡二叉树；② ｜ hl － hr ｜≤ 1；时，则 T 是平衡二叉树。 二叉树检索，和二分检索思想相同，都是“分而治之”，这是产生对数时间性能的根源。
/* lookup: look up node(val) in tree treep */ TreeNode * lookup(TreeNode * treep, int value) { if (treep == NULL) { return NULL; } if (treep->value == value) { return treep; } else if (treep->value > value) { return lookup(treep->left, value); } else { return lookup(treep->right, value); } }
最新评论