电子商务网站有哪些功能/软文写作的三个要素

今天我们主要的是用线性探测的方法处理哈希冲突的问题。
线性探测方法的具体实现如下：

test.h

#pragma once
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>//我们在这里的hash表期望存储的数据是键值对这样的结构#define HashMaxSize 1000typedef enum Stat{empty,//空状态valid,//有效状态deleted,//删除状态
}Stat;typedef int Hashtype;
typedef  int keytype;
typedef int valtype;typedef size_t (*HashFunc)(keytype key);  //这个结构表示的是哈希表中的一个元素
//这个元素同时包含了键值对
typedef struct Hashelme{keytype key;valtype value;Stat  stat;
}Hashelme;typedef struct Hashtable{Hashelme  data[HashMaxSize];size_t size;//哈希表当中元素的个数（【0，size）不能表示哈希表有效元素的区间HashFunc func;//这是一个函数指针，指向的是hash函数
}Hashtable;void HashInit(Hashtable* ht);void HashDestroy(Hashtable* ht);void HashInsert(Hashtable* ht,keytype key,valtype value);//此时我们根据key找到value就可以了
int HashFind(Hashtable* ht,keytype key,valtype* value);void HashRemove(Hashtable* ht,keytype key);

test.c的实现如下：

#include "hash1.h"size_t  HashDefault(keytype key){return key % HashMaxSize;
}void HashInit(Hashtable* ht)
{if(ht==NULL){return ;}ht->size=0;ht->func=HashDefault;size_t i=0;//将哈希表每一个位置初始化为空状态//表示从来没有被使用过for(i=0;i<HashMaxSize;i++){ht->data[i].stat=empty;}return;
}void HashDestroy(Hashtable* ht)
{if(ht==NULL){return;}//将哈希表中的每一个位置都为无效状态size_t i=0;for(i=0;i<HashMaxSize;i++){ht->data[i].stat=empty;}ht->size=0;ht->func=NULL;return;
}//插入数据void HashInsert(Hashtable* ht,keytype key,valtype value)
{if(ht==NULL){return;}//  1、判定当前hash表能否继续插入元素，假设负载因子为0.8if(ht->size>=0.8*HashMaxSize){return;//当前的hash表已经达到了负载因子的上限不能再继续进行插入了}//2、根据key计算出offset(由hash函数计算出有效位置的下标；size_t  offset=ht->func(key);//但是该位置可能之前已经被别的数据占据了，所以我们就要先判断出//该位置是否能够进行插入当前的数据，要是不能的话我们就进行offset进行往后查找while(1){//先判断当前计算出的位置能否放入当前的数据if(ht->data[offset].stat!=valid){//一旦我们计算出的位置不是有效位置，那么我们就可以把数据进行插入了//这个就是我们处理哈希冲突的线性探测的方法；ht->data[offset].key=key;ht->data[offset].value=value;//插入完成之后将该位置设置成有效状态ht->data[offset].stat=valid;//然后将哈希表的有效元素+1ht->size++;return;}//走到这里就说明当前我们计算出的当前位置不能放置当前的数据//判断当前位置上的元素是否和我们要插入的元素相等else if(ht->data[offset].stat==valid && ht->data[offset].key==key){//走到这里就说明存在相同的元素，//在这里我们约定这个哈希表中不存在重复的元素//所以我们就认为失败返回return;}//则更新offset的值进行往后查找else{offset++;if(offset>=HashMaxSize){//如果查找到hash的末尾还没有找到一个可插入的位置//那么我们就重置从头开始继续查找offset=0;}}//else结束}//while循环结束
}void HashPrint(Hashtable* ht,const char* msg)
{printf("[%s]\n",msg);int i=0;for(;i<HashMaxSize;i++){if(ht->data[i].stat==valid){printf("(%d:%d,%d) ",i,ht->data[i].key,ht->data[i].value);}}printf("\n");
}//此时我们根据key找到value就可以
int HashFind(Hashtable* ht,keytype key,valtype* value)
{if(ht==NULL){return 0;//非法输入}//判断当前哈希表中是否有效元素if(ht->size==0){return 0;//空哈希表}//根据当前元素计算出key值size_t offset=ht->func(key);//然后根据offset向后进行查找while(1){//在当前元素的状态为有效元素if(ht->data[offset].stat==valid){if(ht->data[offset].key==key){//找到了*value=ht->data[offset].value;return 1;}//当前位置存放的不是待查找的元素，//更新offset继续进行查找else{offset++;if(offset>=HashMaxSize){//重新进行二次查找offset=0;}}}else if(ht->data[offset].stat==empty){//说明待查找的元素不在hash表中，查找失败return 0;}}//while循环结束return 0;
}void HashRemove(Hashtable* ht,keytype key)
{if(ht==NULL){return;}if(ht->size==0){return;//空哈希表}int offset=ht->func(key);while(1){if(ht->data[offset].stat==valid && ht->data[offset].key==key){//找到了要删除的元素//将其状态置为可删除状态ht->data[offset].stat=deleted;ht->size--;return;}else if(ht->data[offset].stat==empty){//没有找到要删除的元素return;}else{offset++;if(offset>=HashMaxSize)offset=0;}}//while循环结束return;
}//////////////////////////////////////////////////////////
//////////////////test///////////////////////////////////
//////////////////////////////////////////////////////////#define TEST_HEADER printf("\n==============%s===========\n",__FUNCTION__);void test1(){TEST_HEADER;Hashtable ht;HashInit(&ht);printf("expext size is 0,actual size is %d\n",ht.size);//在这里用的“."//因为ht在这里是一个常量而不是一个指针类型的；printf("expect func is %p,actual func is %p\n",HashDefault,ht.func);}void test2()
{TEST_HEADER;Hashtable ht;HashInit(&ht);HashInsert(&ht,1,1);HashInsert(&ht,1,10);HashInsert(&ht,2,20);HashInsert(&ht,1000,100);HashInsert(&ht,2000,200);HashPrint(&ht,"插入5个元素");
}void test3()
{TEST_HEADER;Hashtable ht;HashInit(&ht);HashInsert(&ht,1,1);HashInsert(&ht,1,10);HashInsert(&ht,2,20);HashInsert(&ht,1000,100);HashInsert(&ht,2000,200);HashPrint(&ht,"插入5个元素");printf("\n");valtype value;int ret=HashFind(&ht,1000,&value);printf("expct return is 1,actual return is %d\n",ret);printf("expect value is 100,actual value is %d\n",value);printf("\n");ret=HashFind(&ht,2000,&value);printf("expct return is 1,actual return is %d\n",ret);printf("expect value is 200,actual value is %d\n",value);}void test4()
{TEST_HEADER;Hashtable ht;HashInit(&ht);HashInsert(&ht,1,1);HashInsert(&ht,1,10);HashInsert(&ht,2,20);HashInsert(&ht,1000,100);HashInsert(&ht,2000,200);HashPrint(&ht,"插入5个元素");printf("\n");HashRemove(&ht,2);HashPrint(&ht,"删除元素2: ");HashRemove(&ht,1000);HashPrint(&ht,"删除元素1000： ");}int main(){test1();test2();test3();test4();return;}

最后执行的结果为：

第二种方法具体见下一篇博客！！