如何做学校的网站,怀仁建设局网站,电商网站平台有哪些功能模块,在网站上保存网址怎么做哈希表#xff1a;
哈希表#xff08;Hash table#xff09;#xff0c;也被称为散列表#xff0c;是一种根据关键码值#xff08;Key value#xff09;而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录#xff0c;以加快查找的速度。这个映射…哈希表
哈希表Hash table也被称为散列表是一种根据关键码值Key value而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数被称为散列函数或哈希函数而存放记录的数组则被称为散列表或哈希表。
哈希表的优点
查找速度快哈希表通过哈希函数直接定位到数组中的位置因此查找速度非常快时间复杂度接近O(1)。插入和删除操作方便由于哈希表是基于数组实现的因此插入和删除操作也相对简单。空间利用率高哈希表通过哈希函数将关键码值映射到有限的数组空间中可以高效地利用存储空间。
哈希表的缺点
冲突问题不同的关键码值可能通过哈希函数得到相同的哈希值即产生冲突。解决冲突的方法有多种如开放寻址法、链地址法等。哈希函数的选择哈希函数的选择对哈希表的性能有很大影响。一个好的哈希函数应该能够均匀地分布哈希值减少冲突的发生。动态扩容问题当哈希表中的元素数量增加到一定程度时可能需要进行动态扩容以维持性能。扩容操作会涉及到数据的重新哈希和存储可能会带来一定的性能开销。
#include hash.h
#include stdio.h
#include stdlib.h
#include string.hHSNode_t *hashtable[HASH_SIZE] {NULL};int hash_function(char key) //哈希表函数
{if (key akeyz){return key - a;}else if(key Akey Z){return key - A;}else{return HASH_SIZE-1;}
}int intsert_hashtable(HSDataType data)//向哈希表添加元素
{int addr hash_function(data.name[0]);HSNode_t *pnode (HSNode_t*)malloc(sizeof(HSNode_t));if(pnode NULL){perror(malloc fail);return 0;}pnode-data data;pnode - pnext NULL;if(hashtable[addr] NULL){hashtable[addr] pnode;return 0;}pnode -pnext hashtable[addr]-pnext;hashtable[addr]-pnext pnode;return 0;
}HSNode_t *find_hashtable(char *name)//查找
{int addr hash_function(name[0]);HSNode_t *p hashtable[addr];while(p ! NULL){if(!strncmp(p-data.name,name,strlen(name))){break;}p p-pnext;}return p;
}void print_hashtable()//打印哈希表
{int i 0;for( i 0 ; iHASH_SIZE;i){HSNode_t *p hashtable[i];while( p! NULL){printf(%s,%s\n,p-data.name,p-data.tel);p p-pnext;}}return ;
}void destroy_hashtable()//销毁哈希表
{for (int i 0;i HASH_SIZE;i){while(hashtable[i] ! NULL){HSNode_t *p hashtable[i];hashtable[i] p-pnext;free (p);}}
}算法
排序
选择排序法 基本思想 第1次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后 再从剩余的元素中选择最小或最大的元素然后放到已排序的序列的末尾。以此类推 直到全部待排序的数据元素排完。 时间复杂度O(n^2) 稳定性不稳定 代码
int main(void)
{int a[] {1,2,4,3,6,7,8,5,9,0};int len sizeof(a) / sizeof(a[0]);int i,j;for(i 0;i len -1;i){for(j i 1;j len;j){if(a[i] a[j]){int t;t a[i];a[i] a[j];a[j] t;}}}
} 插入排序法 基本思想 是将一个记录插入到已经排好序的有序表中从而得到一个新的、记录数增加1的有序表。在 整个排序过程中我们反复地将一个记录插入到前面已排好序的序列中直到全部记录插入 完成排序也就结束了。 时间复杂度O(n^2) 稳定性不稳定 代码
int main(void)
{int a[] {1,4,5,6,2,8,3,7,9,0};int len sizeof(a) / sizeof(a[0]);int i;for(i 1; i len;i){int j;int t a[i];j i;while(j 0 a[j - 1]t){a[j] a[j - 1];--j;}a[j] t;}return 0;
}
冒泡排序法 基本思想 通过重复地遍历要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过 来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。 时间复杂度O(n^2) 稳定性稳定 代码
int main(void)
{int a[] {1,4,5,6,2,8,3,7,9,0};int len sizeof(a) / sizeof(a[0]);int i,j;for(j len - 1;j 0;--j){for(i 0;i j;i){if(a[i] a[i 1]){int t;t a[i];a[i] a[i 1];a[i 1] t;}}}return 0;
} 快速排序法 基本思想 通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分 的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以 递归进行以此达到整个数据变成有序序列。 时间复杂度O(n log n) 稳定性不稳定 代码
#include stdio.hvoid print_array(int *a,int len)
{for(int i 0;i len ;i){printf(%d,,a[i]);}printf(\n);
}void quick_sort(int *a,int begin ,int end)
{int i begin;int j end;int key a[i];if(i j){return ;}while(i j){while(ij a[j] key){--j;}a[i] a[j];while(i j a[i] key){i;}a[j] a[i];}a[i] key;quick_sort(a,begin,i-1);quick_sort(a,i1,end);
}int main(int argc, char *argv[])
{int a[] {1,-1,3,2,4,-5,6,-7,8,9}; int len sizeof(a)/sizeof(a[0]);quick_sort(a,0,len-1);print_array(a,len);return 0;
}
