数据结构课程设计C语言课程设计报告文件统计.doc

数据结构课程设计之C源文件关键字统计李华溢 06050514课程设计报告C源文件关键字统计专 业： 计算机科学与技术(非师范)班 级： 2005级(5)班 姓 名： 李华溢 指导教师： 吉根林 二00七 年 九 月 三 日一、问题描述-3二、算法思想-32.1 Hash技术介绍-32.2 C语言关键字-42.3 Hash表的建立-52.4 算法描述- 5三、算法实现-63.1 数据结构 3.2 程序模块3.3 各模块之间的调用关系四、测试与分析-7五、总结-8一、问题描述利用Hash技术统计某个C源程序中的关键字出现的频度扫描一个C程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度，用线性探测法解决Hash冲突。设Hash函数为Hash(Key)=(Key第一个字符在1-26个字母中的序号)*100+(Key最后一个字符在1-26个字母中的序号)%41实现模型C源文件课程设计程序显示器输出关键字个数二、算法思想21 Hash技术介绍2.1.1 定义：哈希表是为了便于快速搜索而组织的键/值组合的集合。Hash Table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。键/值对的集合。 2.1.2 优点：哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 2.1.3 基本原理：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一个元素“分类”。 2.1.4哈希表的不可避免冲突(collision)现象：对不同的关键字可能得到同一个哈希地址 即key1key2，而f(key1)=f(key2)。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。 2.1.5处理冲突的方法方法1:线性探测法基本思想：将散列看成是一个环形表，探测序列是(假设表长为m)：H(k),H(k)+1,H(k)+2,m-1,0,1,H(k)-1用线性探法解决冲突时，求下一个开放地址的公式为：Hi = (H(k)+i) MOD m 方法2:拉链法 基本做法：将所有关键字为同义词的结点链接在同一个单链表中。若选定的哈希函数所产生的哈希地址为0m-1,则可将哈希表定义成一个由m个链表头指针组成的指针数组。这种方法的优点是： 不产生堆集。 由于结点空间是动态申请的，故更适合于造表前无法确定表长的情况。 从表中删除结点容易。22 C语言关键字2.2.1什么是C语言关键字 C语言关键字是C语言的保留的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。其特点是都有小写字母构成。2.2.2 C语言关键字有哪些double ：声明双精度变量或函数 int： 声明整型变量或函数 struct：声明结构体变量或函数 break：跳出当前循环 else ：条件语句否定分支（与 if 连用） long ：声明长整型变量或函数 switch :用于开关语句 case：开关语句分支 enum ：声明枚举类型 register：声明积存器变量 char ：声明字符型变量或函数 extern：声明变量是在其他文件正声明（也可以看做是引用变量） return ：子程序返回语句（可以带参数，也看不带参数） union：声明联合数据类型 const ：声明只读变量 float：声明浮点型变量或函数 short ：声明短整型变量或函数 unsigned：声明无符号类型变量或函数 continue：结束当前循环，开始下一轮循环 for：一种循环语句(可意会不可言传） signed：生命有符号类型变量或函数 void ：声明函数无返回值或无参数，声明无类型指针（基本上就这三个作用） default：开关语句中的“其他”分支 goto：无条件跳转语句 sizeof：计算数据类型长度 volatile：说明变量在程序执行中可被隐含地改变 do ：循环语句的循环体 while ：循环语句的循环条件 static ：声明静态变量 if：条件语句23 Hash表的建立为了避免冲突分布集中，采用Hash函数Hash(Key)=(Key第一个字符在1-26个字母中的序号)*100+(Key最后一个字符在1-26个字母中的序号)%41首先申请数组结构体41个。结构体数组里面有数据域和指针域。数据域存放关键字指针域存放冲突以后新建的结点的地址。 初始化的时候将字符串算出对应的地址(s0-dlta)*100+(send-dlta)%size; s是字符串。如果这个地址上暂时没有关键字，在当前位置存放这个关键字。如果已有，寻找其指针指向的位置，直到找到空位置，建立关键字。24 算法描述2.4.1 读入C源程序（按字符读入）建立fstream对象in然后用函数getline(in,s)按行读入字符串到string s中 再建立 istringstream对象sin，s赋值给sin。然后sin输出给char ch;2.4.2识别单词因为关键字都是小写字母组成不含有其他字符。所以在对源文件进行扫描的时候申请一个字符串名为TestStr 将从第一个是小写字母的字符开始到最后一个是小写字母的字符TestStr 然后对TestStr进行Hash查找 找到对应关键字 关键字次数+1 找不到 返回。 2.4.3 Hash查找1)用外部文件key.txt中已有的关键字建立hash表。然后将识别单词中获取的TestStr字符串进行Hash查找。如果找到对应记录说明是关键字，关键字个数+1，不是则退出。2)对于Hash冲突,在这个程序中采取的冲突解决方式是拉链法。如果在关键字在Hash表对应的位置已经被占用了那么开辟一个新的数据域并用占用位置的一个指针指向新数据域。 2.4.4 特殊情况的处理以下三种特殊情况 (“ ”之间 /* */注释块之间 / 注释行) 的字符串不需要参与统计在进行C源文件扫描的时候 是按字符一个一个读入的 定义2个char型变量 ch prech (prech初始化为 ;)ch记录当前字符 prech记录当前字符之前的一个字符1) 对于” ”处理的办法定义一个int型变量 enable_yh 初始化为1每次用ch读入字符的时候做以下判断 若enable_yh=1&ch= ” 的时候 将enable_yh改成0若 enable_yh=0&ch= ” 的时候 将enable_yh改成1enable_yh=1时候才进行 Hash查找2) 对/* */注释块处理的办法定义一个int型变量 enable_xh 初始化为1每次用ch读入字符的时候做以下判断prech=/&ch=* enable_xh=0;prech=*&ch=/ enable_xh=1;enable_yh=1时候才进行 Hash查找3) 对/注释行处理的办法定义一个int型变量 enable_xg 在对C源文件进行按行读写的时候 读每行之前 e nable_xg初始化为1 prech初始化为; 如果在读一行的过程中prech=/&ch=/ 就让enable_xg改为0 .enable_xg=1时候才进行 Hash查找 三、算法实现 3.1数据结构 全局变量 search_chances 记录进入Hash查找的函数的次数 search_times 记录Hash查找的次数 两者相除就是平均查找次数 (包括成功失败2种情况)typedef struct Lnode char str20;/关键字名称int frequency;/出现的次数struct Lnode *next;/冲突产生后的下个关键字 拉练法Lnode,*LinkList;3.2程序模块void CreateHash(Lnode Hash); / 通过文件”key.txt”建立hash表 拉练法int HashFun(char s); /构建的哈希函数 void InsertKey(char TestStr); /对可能为关键字的字符串 进行hash查找 并统计查找次数void Countkey(); /对待查的c源文件遍历 在适当条件下找出可能为关键字的字符串并调用InsertKey函数进行hash查找int IsSmallLetter(char ch); /判断某一个字符是否是小写字母void PrintHashList(); /打印给用户看hash表中关键字的次数main 3.3各模块之间的调用关系CountkeyCreateHashPrintHashListIsSmallLetterInsertKeyHashFun函数说明: main():主函数 CreateHash() 建立Hash表HashFun() Hash函数 CountKey() 读取C源文件并获取单词进行hash查找 IsSmalLetter() 判别是否是小写字母 InsertKey() 进行hash查找并计数 PrintHashList() 打印关键字个数四、测试与分析将自己做的课程设计的代码作为源文件进行测试。一共测试8次,实验表明程序是正确的。其中一次结果如下: 另分别对 “ “ / /* */进行测试都满足条件五、总结 1。C程序设计是面向过程的。函数是构成程序的基本单元，函数选择与设计很重要，有利于程序的编写 2。程序=数据结构+算法 其中数据结构的地位也是很重要的。 如果数据结构建立不够好，会影响算法的设计与实现。 当然算法的正确性，健壮性，可读性，高效低存储也是很重要的。3。对Hash查找的认识 有三个问题值得关注1如何定义一个好的hash函数 使元素在Hash表内分散均匀，使冲突降到最低。2如何建立Hash表以及避免Hash冲突 对拉链法和线性探测法的理解3Hash查找的性