网站做代码图像显示不出来,建设网站写需求分析报告,郑州设计工作室,担保交易网站开发1.哈希表1.哈希算法将数据通过哈希算法映射成一个关键值#xff0c;存放都在同一位置实现数据的高效存储和查找#xff0c;将时间复杂度尽可能降低至O#xff08;1#xff09;2.哈希碰撞多个数据通过哈希算法得到的键值相同#xff0c;称为产生哈希碰撞3.哈希表构建哈希表…1.哈希表1.哈希算法
将数据通过哈希算法映射成一个关键值存放都在同一位置实现数据的高效存储和查找将时间复杂度尽可能降低至O1
2.哈希碰撞
多个数据通过哈希算法得到的键值相同称为产生哈希碰撞
3.哈希表
构建哈希表存放0-100之间的数据哈希算法选择1.将0-100之间的数据的个位作为键值
4.哈希表的实现
1.元素插入
int insert_data_hashtable(int tmpdata)
{hashnode **pptmpnode NULL;hashnode *pnewnode NULL;int key 0;key tmpdata % INDEX;for(pptmpnode (phashtable[key]); *pptmpnode ! NULL (*pptmpnode)-data tmpdata; pptmpnode (*pptmpnode)-pnext){}pnewnode malloc(sizeof(hashnode));if(pnewnode NULL){perror(fail to malloc);return -1;}pnewnode-data tmpdata;pnewnode-pnext *pptmpnode;*pptmpnode pnewnode;return 0;
}2.遍历
int show_data_hashtable(void)
{int i 0;hashnode *ptmpnode NULL;for(i 0; i INDEX; i){printf(%d:, i);ptmpnode phashtable[i];while(ptmpnode ! NULL){printf(%-2d , ptmpnode-data);ptmpnode ptmpnode-pnext;}printf(\n);}return 0;
}3.元素查找
hashnode *find_data_hashtable(int tmpdata)
{int key 0;hashnode *ptmpnode NULL;key tmpdata % INDEX;ptmpnode phashtable[key];while(ptmpnode ! NULL ptmpnode-data tmpdata){if(ptmpnode-data tmpdata){return ptmpnode;}ptmpnode ptmpnode-pnext;}4.销毁
int destroy_hashtable(void)
{int i 0;hashnode *ptmpnode NULL;hashnode *pfreenode NULL;for(i 0; i INDEX; i){ptmpnode phashtable[i];pfreenode phashtable[i];while(ptmpnode ! NULL){ptmpnode ptmpnode-pnext;free(pfreenode);pfreenode ptmpnode;}phashtable[i] NULL;}return 0;
}
2.排序和查找算法1.冒泡排序
时间复杂度o(n^2)相邻两个元素比较大的向后走小的向前走
2.选择排序
时间复杂度o(n^2)从前到后找最小值与前面的元素交换找到 len-1个最小值最后一个最大值即排序完成
3.插入排序
时间复杂度o(n^2)如果数组有序时间复杂度降低至o(n)将数组中的每个元素插入到有序数列中先将要插入的元素取出依次和前面元素比较比元素大的向后走直到前一个元素比要插入的元素小或者到达有序数列开头为止
4.希尔排序
时间复杂度o(nlogn)通过选择不同的步长将数组拆分成若干个小的数组实现插入排序若干个小的数组成为有序数列后使得数组的数据大致有序最后再对整体完成一次插入排序
5.快速排序
时间复杂度o(nlogn)选择左边的作为键值从后面找一个比键值小的放前面从前面找一个比键值的放后面键值放中间左右两边有元素则递归调用
6.折半查找二分查找int mid_search(int *parray, int low, int high, int tmpdata)
{int mid 0;if (low high){return -1;}mid (low high) / 2;if (tmpdata parray[mid]){return mid;}else if (tmpdata parray[mid]){return mid_search(parray, mid1, high, tmpdata);}else if (tmpdata parray[mid]){return mid_search(parray, low, mid-1, tmpdata);}
}
