八、哈希表
哈希存储：
将要存储数据的关键字和春初位置之间建立对应映射关系，
存储数据时，按照映射关系寻找存储位置；
查找数据，根据关键字和映射关系，寻找原数据的存储位置
映射关系称为哈希函数（散列函数）
目的：提高查找效率
f(key)=key%10：求余法
f(key)=a*key+b：一次函数法
哈希冲突/哈希矛盾：
key1!=key2
f(key1)==f(key2)
解决哈希冲突的方法：
1.开放定址法
2.链地址法
API:
1.创建哈希表
Node_t *hash_table[HASH_SIZE]={NULL};2.设计哈希函数
int hash_function(char ch) { if(ch>='a' && ch<='z') { return ch-'a'; } if(ch>='A' && ch<='Z') { return ch-'A'; } else { return HASH_SIZE-1; } }3.哈希表数据插入
int insert_hash_table(Node_t **hash_table,Data_t data) { int addr=hash_function(data.name[0]); Node_t *pnode=malloc(sizeof(Node_t)); if(NULL==pnode) { printf("malloc error\n"); return -1; } pnode->data=data; pnode->pnext=NULL; pnode->pnext=hash_table[addr]; hash_table[addr]=pnode; return 0; }4.哈希表的查找
Node_t *find_hash(Node_t **hash_table,char *pname) { int addr=hash_function(pname[0]); Node_t *ptmp=hash_table[addr]; while(ptmp!=NULL) { if(strcmp(pname,ptmp->data.name)==0) { return ptmp; } ptmp=ptmp->pnext; } return NULL; }5.销毁哈希表
void destory_hash(Node_t **hash_table) { for(int i=0;i<HASH_SIZE;++i) { Node_t *ptmp=hash_table[i]; while(ptmp!=NULL) { hash_table[i]=ptmp->pnext; free(ptmp); ptmp=hash_table[i]; } } }6.遍历哈希表
void show_hash(Node_t **hash_table) { for(int i=0;i<HASH_SIZE;++i) { Node_t *ptmp=hash_table[i]; while(ptmp!=NULL) { printf("%s,%s\n",ptmp->data.name,ptmp->data.tel); ptmp=ptmp->pnext; } printf("\n"); } }
九、算法相关
程序设计=数据结构+算法
算法：解决特定问题的步骤
算法的设计，
1.正确性，
2.可读性，高内聚 低耦合
3.健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4.高效率（时间复杂度）
5.低存储（空间复杂度）
空间复杂度：算法执行过程中额外开辟的空间随数据量n的变化关系。
O(1)
O(n)
时间复杂度
执行这个算法所花时间的度量
将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。
一般用大o表示法：O(n) 时间复杂度是关于数据n的一个函数随着n的增加，时间复杂度增长较慢的算法时间复杂度低
时间复杂度的计算规则
1，用常数1 取代运行时间中的所有加法常数
2，在修改后的运行函数中，只保留最高阶项。
3，如果最高阶存在且系数不是1，则去除这个项相乘的常数。
排序算法：
1.选择排序
2 冒泡排序
3.插入排序(稳定算法)
时间复杂度O（n^2）
空间复杂度O（1）
int a[10]={0,1,2,3,-4,-5,6,-7,8,9}; int tmp,i,j; for(i=1;i<10;++i) { tmp=a[i]; j=i; while(j>0 && tmp<a[j-1]) { a[j]=a[j-1]; --j; } a[j]=tmp; }4.希尔排序（不稳定）
时间复杂度O（nlogn）~ O(n^2)
空间复杂度O（1）
int inc=0,i=0,j=0,tmp=0; for(inc=len/2;inc>0;inc/=2) { for(i=inc;i<len;++i) { tmp=a[i]; j=i; while(j>=inc && tmp<a[j-inc]) { a[j]=a[j-inc]; j-=inc; } a[j]=tmp; } }5.快速排序（不稳定）
时间复杂度O(nlogn)
空间复杂度O(logn)~O(n)
void quick_sort(int *a,int begin,int end) { if(begin>=end) { return ; } int i=begin; int j=end; int key=a[i]; while(i<j) { while(i<j && key<=a[j]) { --j; } a[i]=a[j]; while(i<j && key>=a[i]) { ++i; } a[j]=a[i]; } a[i]=key; quick_sort(a, i+1, end); quick_sort(a, begin, i-1); }6.二分查找
前提条件：序列有序
时间复杂度：O(logn)
