数据结构：哈希表 算法相关 排序算法

八、哈希表哈希存储将要存储数据的关键字和春初位置之间建立对应映射关系存储数据时按照映射关系寻找存储位置查找数据根据关键字和映射关系寻找原数据的存储位置映射关系称为哈希函数散列函数目的提高查找效率f(key)key%10求余法f(key)a*keyb一次函数法哈希冲突/哈希矛盾key1!key2f(key1)f(key2)解决哈希冲突的方法1.开放定址法2.链地址法API:1.创建哈希表Node_t *hash_table[HASH_SIZE]{NULL};2.设计哈希函数int hash_function(char ch) { if(cha chz) { return ch-a; } if(chA chZ) { return ch-A; } else { return HASH_SIZE-1; } }3.哈希表数据插入int insert_hash_table(Node_t **hash_table,Data_t data) { int addrhash_function(data.name[0]); Node_t *pnodemalloc(sizeof(Node_t)); if(NULLpnode) { printf(malloc error\n); return -1; } pnode-datadata; pnode-pnextNULL; pnode-pnexthash_table[addr]; hash_table[addr]pnode; return 0; }4.哈希表的查找Node_t *find_hash(Node_t **hash_table,char *pname) { int addrhash_function(pname[0]); Node_t *ptmphash_table[addr]; while(ptmp!NULL) { if(strcmp(pname,ptmp-data.name)0) { return ptmp; } ptmpptmp-pnext; } return NULL; }5.销毁哈希表void destory_hash(Node_t **hash_table) { for(int i0;iHASH_SIZE;i) { Node_t *ptmphash_table[i]; while(ptmp!NULL) { hash_table[i]ptmp-pnext; free(ptmp); ptmphash_table[i]; } } }6.遍历哈希表void show_hash(Node_t **hash_table) { for(int i0;iHASH_SIZE;i) { Node_t *ptmphash_table[i]; while(ptmp!NULL) { printf(%s,%s\n,ptmp-data.name,ptmp-data.tel); ptmpptmp-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.插入排序(稳定算法)时间复杂度On^2空间复杂度O1int a[10]{0,1,2,3,-4,-5,6,-7,8,9}; int tmp,i,j; for(i1;i10;i) { tmpa[i]; ji; while(j0 tmpa[j-1]) { a[j]a[j-1]; --j; } a[j]tmp; }4.希尔排序不稳定时间复杂度Onlogn~ O(n^2)空间复杂度O1int inc0,i0,j0,tmp0; for(inclen/2;inc0;inc/2) { for(iinc;ilen;i) { tmpa[i]; ji; while(jinc tmpa[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(beginend) { return ; } int ibegin; int jend; int keya[i]; while(ij) { while(ij keya[j]) { --j; } a[i]a[j]; while(ij keya[i]) { i; } a[j]a[i]; } a[i]key; quick_sort(a, i1, end); quick_sort(a, begin, i-1); }6.二分查找前提条件序列有序时间复杂度O(logn)