C语言总结（二）

一、
递归函数和回调函数。
1、递归函数
递归函数 的定义就是，函数本身不断地在他的函数体内调用自己。直至到结束条件成立。
递归函数最重要的就是结束条件。你要是结束条件没有或者是结束条件永远不成立。那么就形成死递归，占用大量资源且最后一定会导致栈区满了。
递归主要用于一些重复操作要操作很多一遍且，知道那个条件成立的时候就不递归的操作。
比如：求N的阶乘！

#include 
int main(){
int n ;
extern jiecheng;
n = jiecheng(100);
printf("%dn",n);
}
int jiecheng(int n){
 n= n * n-1;
return n<=0 ? n :jiechegn(n-1);
}

不用递归的话估计你可以写一个循环然后循环100次n * n-1; n – ;这样也可以但是递归更简洁，而且看起来更牛逼。

2、回调函数
回调函数的定义为：我这个函数在另一个函数中作为参数。
经典用法是在内核中：request_irq里面的一个参数就是irq_handle的中断处理函数。
当中断触发的时候就会跳转到irq_handle进行中断处理。
————————————————————————————————————
二、经典排序算法

1、快速排序 qsort（时间复杂度）
快速排序的算法思想就是，找一个基准值，比我大的放右边，比我小的放左边，然后利用递归左右两边的数组再找一个基准值，把比它大的放右边，比它小的放左边。

手写qsort:

#include 
int * Qsort (int *arr,int n);
int main (){
int arr[10] = {1,2,3,5,6,,6,7,8,.3,3,2,1,,,34,5,,,6,3,,43};
Qsort(arr,10);
for(i=0；i<10;++i)
printf("%d"arr[i]);
pits("");
}
int * Qsort (int *arr,int n){
	int begin = arr[0];
	int end = arr[n];
    int tmp = arr[begin];   //基准值
    int i = begin; 
    int j = end; 
    while(i != j){ 			//判断比较完毕的标志  这还是有点巧妙的
        while(arr[j] >= tmp && j > i)  //从后面开始 如果后面有那个值比基准大，则循环 j --,z这也就是说，如果不成立才会转到后面去交换
            j--;
        while(arr[i] <= tmp && j > i) 	//一旦上面有一个值要交换，那么我也从前面找一个值比基准值大的去交换
            i++;
        if(j > i){			//交换
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;				
    Quick_Sort(arr, begin, i-1);		
    Quick_Sort(arr, i+1, end);			//循环比较
}

}

2、选择排序
遍历一个数组，找出它最小的值，放入另一个数组中。循环遍历n-1次就可以了：

#include 
int * select(char arr[10]);
int main(){
	int arr[10] = {1,2,3,5,6,,6,7,8,.3,3,2,1,,,34,5,,,6,3,,43};
	select(char arr[10]);
	for(i=0；i<10;++i)
	printf("%d"arr[i]);
	pits("");
}
int * select(char arr[10]){
int i=0, j= 1;
int arr1[10]
while(i <=10){
	if(arr[i] < arr[j]){
		swap(arr[i],arr[j]);
		j++;
	}  //找到最小值
	arr1[i] =arr[i];
	i++
	}
	int * p = arr1;
	return p;
}

3、插入排序
和选着排序相反，对于后面要插进来的数据，它先遍历一遍已经排好的，看它放哪里合适再把它放进去。

#include 
int * insert_sort(char arr[10]);
int main(){
	int arr[10] = {1,2,3,5,6,,6,7,8,.3,3,2,1,,,34,5,,,6,3,,43};
	select(char arr[10]);
	for(i=0；i<10;++i)
	printf("%d"arr[i]);
	pits("");
}
int * insert_sort(char arr[10]){
int i=0;
int j = 10;
int arr1[10];  //用于存放最终结果的
for(;i<10;i++){
int t =0;
for(;arr1[t]< arr[i];++t){
}
for(;t < i ;t++){
temp = arr1[t+1];
arr1[t+1] = arr1[t];
arr1[t+2] = temp;
}
return *p = arr1;
}

4、堆排序
1、利用树的数据结构比较左右孩子的值，让节点的值大于孩子的值获得大顶堆 ，
2、通过将大顶堆得堆顶元素和数组的最后一个元素交换。
3、再将剩余元素重新排成大顶堆。
好吧，我不懂，我不理解，怎么才能实现？？？

5、冒泡排序（太简单了，不讲）

——————————————————————————————————
三、数据结构
树、
typedf struct tree{
data_t data;
struct tree* lchild ,*rchild;
}

树的遍历。

遍历的话只要严格按照根左右 、左根右、左右根方法就没有问题。
eg:实例一遍中序。
左右根，从头节点开始看，左是B B作为下一个节点的根 也按照左根右 左边没有 ，那么第一个数就是B
左边没有的话，根也写了，那就写右 右是 C 但是C也作为一个根，左根右 那应该先写D 再写C 。。。按照这个逻辑。

#include
#include
#include"tree.h"

bitree * tree_create(){
	bitree *r;
	datatype ch;
	scanf("%c",&ch);
	if(ch=='#'){
		return NULL;}
	if((r=(bitree *)malloc(sizeof(bitree)))==NULL){
		return NULL;}
	r->data=ch;
	r->left=tree_create();
	r->right=tree_create();
	return r;
}

void preorder(bitree *r){
	if(r==NULL){
		return;}
	printf("%c",r->data);
	preorder(r->left);
	preorder(r->right);
	return;
}

void inorder(bitree *r){

	if(r==NULL){
		return;}
	preorder(r->left);
	printf("%c",r->data);
	preorder(r->right);
	return;
}

void postorder(bitree *r){

	if(r==NULL){
		return;}
	preorder(r->left);
	preorder(r->right);
	printf("%c",r->data);
	return;
}

————————————————————————————
查找
顺序查找：
折半查找：
哈希：hash
构造哈希函数的方法：映射的方法：平方取中，保留除数。。。。你甚至可以自己定义方法。
我们用最常见的保留除数法。
H(key) = key%p. p最好取质数
放在索引表的第H个位置。比如我有应该数 53 质数 p 为 7 这样就放在hash索引表的第7个位置。索引表可以看成应该数组。
索引表的大小：填充因子 a = n/m.0.7~0.8
处理冲突的方法：链地址法，把冲突的数拉成应该链表。

#include
#include
#include"hash.h"
#include


hash * hash_create(){
	hash *HT;
	if((HT=(hash *)malloc(sizeof(hash)))==NULL){
		printf("malloc hash failedn");
		return NULL;}
	memset(HT,0,sizeof(hash));
	
	return HT;}

int hash_insert(hash *HT,datatype key){
	linklist p,q;
	if(HT==NULL){
	return -1;}
//create a new node p deposit key
	if((p=(linklist )malloc(sizeof(linknode)))==NULL){
		printf("linklist malloc faliedn");
		return -1;}
	p->key=key;
	p->vaule=key%N;
	p->next=NULL;
//insert
	q=&(HT->data[key%N]);   //q指向 data[vaule}//当然不可以写成data[vaule]
	while(q->next&&q->next->key>p->key){
	q=q->next;
	p->next=q->next;
	q->next=p;}

	return 0;}


linklist  hash_search(hash *HT,datatype key){
	linklist p;
	if(HT==NULL){
	return NULL;}
	p=&(HT->data[key%N]);
	while(p->next&&p->next->key!=key){
	p=p->next;}//遍历
	if(p->next=NULL){
	return NULL;}
	else {
	printf("found:n");
	return p->next;}