利用哈希技术统计C源程序关键字出现的频度

1 引言Hash技术是一种利用Hash函数进行查找的技术，在计算机软件应用中起着重要的作用。

利用Hash技术统计C源程序中关键字出现的频度的方法可以引申到统计任何文本文件中任何字符串个数的方法，在很多领域都有应用的可能。

2 问题分析 2.1 Hash函数Hash函数就是把任意长度的输入通过散列算法，变换成固定长度的输出的一种转换。

该输出就是散列值。

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一地确定输入值。

Hash函数主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的编码里。

因此也可以说，Hash函数就是一种数据内容和数据存放地址之间的映射关系。

2.2 关键技术统计C源程序中关键字出现的频度，主要分为这样几个关键技术：一是选择合适的Hash函数。

常用的Hash函数有直接定址法、除留余数法、数字分析法、平方取余法等众多种类，分别适合不同的问题要求。

Hash函数选择的好坏对发生冲突的概率有着很大影响，因而在很大程度上影响程序运行的效率。

二是如何将所有关键字使用Hash 函数存入比较数组中。

三是字符串模式匹配技术。

即如何在众多程序代码中选择出C 语言的关键字。

四是文件输入输出技术。

这是整个方法的前提，即需要统计关键字个数的C源程序必须从文件中读入，才能进行处理。

处理后的结果还需要写入文件中进行保存。

3 利用Hash函数统计C源程序中关键字出现频度的设计思想使用Hash技术必须首先选择Hash函数。

基于对问题的分析，在此我们选用除留取余法建立Hash函数。

因为直接投稿+我用户名定址法虽然简单但会造成内存单元的大量浪费，而数字分析法、平方取中法等方法过于复杂，本身对时间资源的消耗过大，在本问题中使用并不值得。

我们建立的Hash函数为： Hash（key）=[(key的第一个字母序号)*100+(key的最后一个字母序号)]%41 其中key为关键字，在本问题中为C源程序的关键字。

c语言中哈希表用法
在C语言中，哈希表是一种常用的数据结构，它能够提供快速的查找和插入操作。

哈希表利用哈希函数将关键字映射到数组索引上，并通过解决哈希冲突的方法来保证数据的唯一性。

要使用哈希表，首先需要定义一个合适的数组作为存储空间。

通常情况下，数组大小应该根据实际需求进行合理的设置。

一般来说，哈希表的大小应该是预计存入元素数量的两倍左右，以避免过多的哈希冲突。

定义哈希表数组之后，需要实现一个哈希函数。

哈希函数是将关键字映射到数组索引的算法，它应该能够将不同的关键字均匀地映射到数组中。

一个好的哈希函数应该具有高效性和低冲突性。

常用的哈希函数有除留余数法、乘法哈希法和平方取中法等。

需要解决哈希冲突的问题。

哈希冲突指的是不同的关键字映射到了相同的数组索引上。

有几种常用的解决方法，例如开放定址法和链地址法。

开放定址法是将冲突的元素放置到数组中的下一个可用位置，而链地址法是将冲突的元素放置到一个链表中。

在使用哈希表时，可以通过哈希函数将关键字映射到数组索引上，并使用相应的操作来进行查找、插入和删除操作。

例如，要查找一个元素，可以通过哈希函数得到数组索引，然后在该位置上查找关键字对应的元素。

如果哈希表中存在多个元素，那么可以通过解决冲突的方法进行进一步的查找。

哈希表是C语言中一种高效的数据结构，它能够提供快速的查找和插入操作。

通过合适的定义和实现，可以很好地利用哈希表来解决各种实际问题。

使用哈希表需要注意合理设置数组大小、选择合适的哈希函数和解决冲突的方法，以充分发挥哈希表的优势。

c语言和哈希表C语言和哈希表引言：C语言是一种通用的高级编程语言，被广泛应用于软件开发中。

而哈希表则是一种常用的数据结构，用于快速存储和查找数据。

本文将介绍C语言中如何使用哈希表以及哈希表的原理和应用。

一、哈希表的原理哈希表是一种基于哈希函数的数据结构，它能够将数据快速地映射到一个固定长度的数组中。

哈希表的核心思想是通过哈希函数将数据的关键字映射为数组的下标，从而实现快速的数据存取。

哈希函数是哈希表的关键，它能够将任意长度的数据映射为一个固定长度的哈希值。

好的哈希函数应该能够将数据均匀地映射到不同的哈希值，以避免冲突。

常见的哈希函数有除留余数法、平方取中法等。

二、C语言中的哈希表实现在C语言中，可以使用数组和链表结合的方式来实现哈希表。

首先需要定义一个固定长度的数组，然后使用哈希函数将数据的关键字映射为数组的下标。

如果发生冲突，即多个数据映射到同一个下标，可以使用链表将这些数据串联起来。

以下是一个简单的C语言哈希表的实现示例：```c#include <stdio.h>#include <stdlib.h>#define SIZE 10typedef struct Node {int key;int value;struct Node* next;} Node;Node* hashTable[SIZE];int hashFunction(int key) {return key % SIZE;}void insert(int key, int value) {int index = hashFunction(key);Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = key;newNode->value = value;newNode->next = NULL;if (hashT able[index] == NULL) {hashT able[index] = newNode;} else {Node* current = hashTable[index]; while (current->next != NULL) { current = current->next;}current->next = newNode;}}int search(int key) {int index = hashFunction(key);Node* current = hashTable[index]; while (current != NULL) {if (current->key == key) {return current->value;}current = current->next;}return -1;}int main() {insert(1, 10);insert(2, 20);insert(3, 30);printf("%d\n", search(2));return 0;}```三、哈希表的应用哈希表在实际开发中有广泛的应用，以下是一些常见的应用场景：1. 数据存储和查找：哈希表能够以常数时间复杂度进行数据的存储和查找操作，因此被广泛用于缓存系统、数据库索引等领域。

#include <windows.h>#include <stdio.h>#define MAX_LINELEN 512#define MAX_WORDLEN 64//关键字统计信息结构typedef struct tagKeyInfo{char chKey[MAX_WORDLEN];int nSum;struct tagKeyInfo *pNext;}KeyInfo;//处理输入文件int ProcessInputFile(char* pFileNameIn,KeyInfo* pHeader);//创建关键字链表KeyInfo* InitList(char* keyFileNameIn);//统计关键字信息void ComputKeyInfo(KeyInfo* pHeader,char* pWords);//输出关键字统计信息int PrintKeyInfo(char* pOutFileName,KeyInfo* pHeader);//删除关键字信息链表void DeleteKeyInfo(KeyInfo* pHeader);int main(int argc,char* argv[]){char keyFileNameIn[MAX_PATH]="";char chFileNameIn[MAX_PA TH]="";char chFileNameOut[MAX_PATH]="";KeyInfo* pHeader;//命令行中是否包含文件if(argc!=4){printf("Please input key file name(include full path:)\n");gets(keyFileNameIn);printf("Please input source file name(include full path:)\n");gets(chFileNameIn);printf("Please output target file name(include full path:)\n");gets(chFileNameOut);}else{strcpy(keyFileNameIn,argv[1]);strcpy(chFileNameIn,argv[2]);strcpy(chFileNameOut,argv[3]);}//创建关键字列表pHeader=InitList(keyFileNameIn);//处理输入文件ProcessInputFile(chFileNameIn,pHeader);// 输出关键字统计信息PrintKeyInfo(chFileNameOut,pHeader);// 删除关键字信息链表DeleteKeyInfo(pHeader);return 0;}//创建关键字链表KeyInfo* InitList(char* keyFileNameIn){int nPrePos;int i,j,k;char chBuff[MAX_LINELEN];char chWords[MAX_WORDLEN];KeyInfo* pHeader,*pCurrent,*pNew;FILE* pFileIn;pFileIn = fopen(keyFileNameIn,"rt");if (pFileIn == NULL){printf("Can not open file:%s\n",keyFileNameIn);return 0;}pNew=(KeyInfo*)malloc(sizeof(KeyInfo));if(pNew==NULL){printf("Can not allocate memory!");return NULL;}else{strcpy(pNew->chKey,"auto");pNew->nSum=0;pNew->pNext=NULL;pHeader=pNew;pCurrent=pHeader;}while(!feof(pFileIn))//没有结束标志{memset(chBuff,'\0',MAX_LINELEN);fgets(chBuff,MAX_LINELEN,pFileIn);nPrePos = -1;i = 0;while (chBuff[i] != '\0'){if (isspace(chBuff[i])||chBuff[i]==';'){if (nPrePos == -1){i++;continue;}else{memset(chWords,'\0',MAX_WORDLEN);for(j=nPrePos,k=0;j<i;j++,k++)chWords[k] = chBuff[j];chWords[k] = '\0';pNew = (KeyInfo*)malloc(sizeof(KeyInfo));if (pNew == NULL){printf("Can not allocate memory!");return NULL;}else{strcpy(pNew->chKey,chWords);pNew->nSum = 0;pNew->pNext = NULL;pCurrent->pNext=pNew;pCurrent=pNew;}nPrePos = i;}}else{if (nPrePos == -1 || isspace(chBuff[i-1]))nPrePos = i;}i++;}}fclose(pFileIn);return pHeader;}// 处理输入文件int ProcessInputFile(char* pFileNameIn,KeyInfo *pHeader) {int nPrePos;int i,j,k;char chBuff[MAX_LINELEN];char chWords[MAX_WORDLEN];FILE* pFileIn;pFileIn = fopen(pFileNameIn,"rt");if (pFileIn == NULL){printf("Can not open file:%s\n",pFileNameIn);return 0;}while(!feof(pFileIn))//没有结束标志{memset(chBuff,'\0',MAX_LINELEN);fgets(chBuff,MAX_LINELEN,pFileIn);nPrePos = -1;i = 0;while (chBuff[i] != '\0'){if (isspace(chBuff[i])||chBuff[i]==';'){if (nPrePos == -1){i++;continue;}else{memset(chWords,'\0',MAX_WORDLEN);for(j=nPrePos,k=0;j<i;j++,k++)chWords[k] = chBuff[j];chWords[k] = '\0';ComputKeyInfo(pHeader, chWords);nPrePos = i;}}else{if (nPrePos == -1 || isspace(chBuff[i-1]))nPrePos = i;}i++;}// 文件最后一个单词if (i-1 > nPrePos){memset(chWords,'\0',MAX_WORDLEN);for(j=nPrePos,k=0;j<i;j++,k++)chWords[k] = chBuff[j];chWords[k] = '\0';ComputKeyInfo(pHeader, chWords);}}fclose(pFileIn);return 1;}// 统计关键字信息void ComputKeyInfo(KeyInfo *pHeader, char* pWords){KeyInfo *pCurrent;pCurrent = pHeader;while(pCurrent != NULL){if (strcmp(pCurrent->chKey,pWords)==0){pCurrent->nSum++;break;}pCurrent = pCurrent->pNext;}//pHeader->nSum=pHeader->nSum+pCurrent->nSum会出错}// 输出关键字统计信息int PrintKeyInfo(char *pOutFileName,KeyInfo *pHeader){FILE* fileOut;KeyInfo *pCurrent;fileOut = fopen(pOutFileName,"wt");if (fileOut == NULL){printf("Can not create file:%s\n",pOutFileName);return 0;}printf("文件中关键字信息统计如下：\n");pCurrent = pHeader;while(pCurrent != NULL){printf("%s\t %d\n",pCurrent->chKey,pCurrent->nSum);fprintf(fileOut,"%s\t%d\n",pCurrent->chKey,pCurrent->nSum);pCurrent = pCurrent->pNext;}fclose(fileOut);return 1;}// 删除冠词信息链表void DeleteKeyInfo(KeyInfo *pHeader){KeyInfo *pCurrent;pCurrent = pHeader;while(pCurrent != NULL){pHeader = pCurrent->pNext;free(pCurrent);pCurrent = pHeader;}}。

东华理工大学课程设计实验报告姓名：学号：班级：实验题目：数据结构课程设计之利用哈希技术统计C源程序关键字出现的频度实验时间： 12月31日实验地点：软件楼一、实验目的加深对数据结构的了解二、实验内容三、实验步骤#include<iostream>#include<string>#include<iomanip>using namespace std;const int TOTAL=39; //39个关键字const int MAXLEN=10; //关键字长度const int HASHLEN=41; //哈希表长度int cont=0; //统计哈希表中的关键字个数char KeyWords[TOTAL][MAXLEN]= //构造二维数组存储39个关键字{"asm","auto","break","case","cdecl","char","const","continue","default","do","double","else","enum","extern","far","float","for","goto","huge","if","int","interrupt","long","near","pascal","register","return","short","signed","sizeof","static","struct","switch","typedef","union","unsigned","void","volatile","while",};int GetKey(char *keyword);void menu();void Select(int choice);int Input();int Read(char *filename);void Show(int key);int isLetter(char ch);int FindHX(char *keyword);int CreatHX(char *keyword);int GetFreePos(int key);int isKeyWords(char *word);class HASH//哈希表类{public:char keyword[MAXLEN];int count; //出现次数（频度）};HASH HS[HASHLEN];int main(){cout<<endl;cout<<" --数据结构课程设计之利用哈希技术统计C源程序关键字出现的频度--"<<endl;menu();Select(Input());return(0);}int GetKey(char *keyword) //哈西函数{return ( keyword[0]*100+keyword[strlen(keyword)-1] ) % 41; //Hash函数为：Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)] Mod 41 }void menu()//主菜单函数{cout<<endl;cout<<"\t1.读取一个文件"<<endl;cout<<"\t2.输出Hash表(关键字总数，冲突次数)"<<endl;cout<<"\t3.回主菜单"<<endl;cout<<"\t4.退出"<<endl;}int Input(){cout<<endl;cout<<"请输入你的选择(1-4): ";while(true) //确保输入的为数字{int choice=0;if((cin>>choice)){if((choice<=0)||(choice>4))cout<<"输入范围不正确，请重新输入"<<endl;}else{cout<<"输入错误，请重新输入"<<endl;cin.clear();}while(!isspace(cin.get())) //判断字符是否为空白符当字符为空白符时，返回非零值，否则返回零。

哈希表统计次数哈希表是一种常用的数据结构，它通过将数据与唯一的索引值关联起来，可以快速地查找、插入和删除数据。

在计算机科学中，哈希表被广泛应用于各种领域，如数据库管理系统、编译器、搜索引擎等。

本文将从不同的角度来探讨哈希表的统计次数。

一、哈希表的基本原理哈希表是由哈希函数和数组组成的。

哈希函数将数据映射到数组的特定位置，这个位置被称为索引值。

当需要查找、插入或删除数据时，只需要通过哈希函数计算出对应的索引值，就可以直接访问数组中的相应位置，从而实现高效的操作。

二、哈希表的统计次数在哈希表中，统计次数是指记录某个数据在哈希表中出现的次数。

通常，我们可以通过遍历哈希表来统计每个数据的出现次数。

具体的统计方法如下：1. 遍历哈希表，对每个数据进行计数。

2. 对于每个数据，如果它已经在哈希表中出现过，则将其对应的计数值加1；否则，将其加入哈希表，并将计数值初始化为1。

3. 最终，可以得到每个数据在哈希表中出现的次数。

三、哈希表的应用场景1. 字符串统计：哈希表可以用来统计字符串中每个字符出现的次数。

通过将每个字符映射到哈希表的索引值，然后计数，就可以得到字符串中每个字符的出现次数。

2. 单词统计：哈希表可以用来统计文本中每个单词出现的次数。

将文本分割成单词，然后将每个单词映射到哈希表的索引值，再计数，就可以得到文本中每个单词的出现次数。

3. 网络流量统计：哈希表可以用来统计网络流量中每个IP地址的出现次数。

将每个IP地址映射到哈希表的索引值，再计数，就可以得到每个IP地址的访问次数。

四、哈希表的优势和局限性哈希表具有以下优势：1. 高效的查找、插入和删除：通过哈希函数计算索引值，可以快速地定位数据。

2. 空间利用率高：哈希表可以根据实际数据量来动态调整数组的大小，从而节省内存空间。

3. 适用于大规模数据处理：哈希表可以处理大规模的数据，而不会因为数据量增加而导致性能下降。

然而，哈希表也存在一些局限性：1. 哈希冲突：不同的数据可能会映射到相同的索引值，从而导致冲突。

数据结构与算法课程设计报告题目：利用哈希技术统计C源程序关键字出现频度学生姓名：学号： ______班级： ____指导教师： _2012年 6 月18 日利用哈希技术统计C源程序关键字出现频度(1)题目内容：利用Hash技术统计某个C源程序中的关键字出现的频度(2)基本要求：扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。

用线性探测法解决Hash冲突。

设Hash函数为：Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41一、对题目的分析哈希表是为了便于快速搜索而组织的值组合的集合。

Hash Table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。

值对的集合。

理想的情况下是希望不经过任何比较，一次存储就能得到所查到的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

基本要求：使用一个下标范围比较大的数组来存储元素。

可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。

使用hash表存储关键字时难免会有不同的关键字对应同一关键码的情况，因此必须有个处理冲突的办法。

Hash函数：Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41二、处理冲突的方法处理冲突的办法—线性探测法用线性探法解决冲突时，把有冲突的关键字往后推移直到有空位置的关键码时再插入到hash表中。

C语言关键字:C语言关键字是C语言的保留的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。

其特点是都有小写字母构成。

C语言关键字有哪些：double int struct break else long switch case enum register char extern return union const float shortunsigned continue for signed void default goto sizeof volatile do while static if auto case定义一个多维数组，数组第一行存放关键字，数组第二行存储hash函数处理后关键字结点地址，用hash函数存储关键字Hash(Key)=[(Key第一个字符在1-26个字母中的序号)*100+(Key最后一个字符在1-26个字母中的序号)%41如此得到如for对应地址3，if对应于地址4，int对应地址18等等。

c语言哈希值计算哈希值计算是计算机科学中一个重要的概念，用于将任意长度的数据映射成固定长度的值。

在C语言中，我们可以通过使用哈希函数来进行哈希值的计算。

哈希函数是一种将输入数据映射成哈希值的算法。

它具有如下特点：对于相同的输入，哈希函数总是产生相同的输出；对于不同的输入，哈希函数尽可能地产生不同的输出。

这样的特点使得哈希函数在数据存储和查找等领域具有广泛的应用。

在C语言中，我们可以使用多种哈希函数来计算哈希值，其中一种常用的方法是使用除法取余法。

该方法的基本思想是将输入数据除以一个固定的数，然后取余数作为哈希值。

具体的实现代码如下所示：```cunsigned int hash(char* data) {unsigned int hashValue = 0;unsigned int prime = 31;for (int i = 0; data[i] != '\0'; i++) {hashValue = hashValue * prime + data[i];}return hashValue;}```上述代码中，我们使用了一个循环来遍历输入数据的每个字符，并将字符的ASCII码值乘以一个素数（本例中取31），然后加到哈希值上。

最后返回得到的哈希值作为结果。

除了除法取余法，还有其他一些常用的哈希函数，例如乘法散列法、平方取中法等。

这些方法各有特点，适用于不同的应用场景。

在实际应用中，我们需要根据具体的需求选择合适的哈希函数。

哈希值的计算不仅可以用于数据存储和查找，还可以用于数据校验和加密等领域。

在数据存储中，哈希值可以作为索引来快速定位数据，提高数据的查找效率。

在数据校验中，哈希值可以用于验证数据的完整性，防止数据被篡改。

在数据加密中，哈希值可以用于生成密钥或验证用户身份。

哈希值计算是一项重要的计算机科学技术，它可以通过哈希函数将任意长度的数据映射成固定长度的值。

在C语言中，我们可以使用不同的哈希函数来计算哈希值，以满足不同的应用需求。

C语言中的哈希计算哈希计算是计算机科学中一种常见的算法，用于将数据快速映射为固定长度的数字或哈希值。

在C语言中，哈希计算广泛应用于数据结构、密码学以及其他许多领域。

本文将介绍C语言中的哈希计算原理和常见应用。

一、哈希计算原理哈希计算的核心思想是将任意长度的输入数据映射为固定长度的哈希值。

哈希值在计算过程中不可逆，即无法通过哈希值还原出原始的输入数据。

C语言中常用的哈希计算算法包括MD5、SHA-1、SHA-256等。

在哈希计算过程中，需要选择合适的哈希函数。

哈希函数负责将输入数据分割成固定大小的块，并对每个块进行处理，最后生成哈希值。

常见的哈希函数采用位运算、位移操作和加法操作等，以确保生成的哈希值具有较好的随机性和均匀性。

二、C语言中的哈希计算函数在C语言中，可以使用各种哈希计算函数来进行哈希操作。

以下是一些常见的C语言哈希计算函数的示例：1. MD5哈希计算函数示例：```c#include <openssl/md5.h>void calculate_md5(const char* input, char* output) {unsigned char digest[MD5_DIGEST_LENGTH];MD5((unsigned char*)input, strlen(input), digest);for (int i = 0; i < MD5_DIGEST_LENGTH; i++) {sprintf(&output[i*2], "%02x", (unsigned int)digest[i]); }}```2. SHA-1哈希计算函数示例：```c#include <openssl/sha.h>void calculate_sha1(const char* input, char* output) {unsigned char digest[SHA_DIGEST_LENGTH];SHA1((unsigned char*)input, strlen(input), digest);for (int i = 0; i < SHA_DIGEST_LENGTH; i++) {sprintf(&output[i*2], "%02x", (unsigned int)digest[i]); }}```3. SHA-256哈希计算函数示例：```c#include <openssl/sha.h>void calculate_sha256(const char* input, char* output) {unsigned char digest[SHA256_DIGEST_LENGTH];SHA256((unsigned char*)input, strlen(input), digest);for (int i = 0; i < SHA256_DIGEST_LENGTH; i++) {sprintf(&output[i*2], "%02x", (unsigned int)digest[i]);}}```以上示例中，分别使用了openssl库中的MD5、SHA1和SHA256哈希函数。

数据结构课程设计报告——利用Hash技术和二分查找技术统计某个c 程序中关键字出现的频度班级：06级5班目录1．题目------------------------------------------- -3 2．算法思想----------------------------------------3 3．程序结构----------------------------------------3 4．测试结果----------------------------------------6 5．收获与体会--------------------------------------7一、题目扫描c源程序，利用hash技术和二分查找技术统计该源程序中的关键字出现的频度，并比较各自查找的次数。

（1）、先用Hash表存储c语言中32个关键字，再扫描c源程序取出每个单词，利用Hash查找技术统计该程序中的关键字出现的频度。

发生Hash冲突用线性探测法解决。

设Hash函数为：Hash（key）=[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41。

（2）、用顺序表存储c语言中的关键字，把c源程序取出每个单词利用二分查找技术统计该程序中的关键字的出现频度。

二、算法思想1、Hash表的建立首先按照c语言中关键字（共32个），根据Hash函数：Hash（key）=[(key 的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41，申请一个类数组，长度为41，类中有一个string型用来存储关键字和int类型用来存储出现的频率，并初始化为0。

2、Hash冲突解决用线性探测法解决。

把整个数组看成一个循环的数组，当发生冲突时，从发生冲突的位置的下一个位置起，依次寻找空的散列地址,再把关键字存入。

3、顺序表的建立二分查找要求所查的关键字必须有序，所以按照关键字的大小从小到大排列（用string类型直接比较）。