《2022年数据结构课程设计C语言课程设计报告文件统计 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计C语言课程设计报告文件统计 .pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计之C 源文件关键字统计李华溢06050514-1-课程设计报告C源文件关键字统计专业：计算机科学与技术(非师范)班级：2005级(5)班姓名：李华溢指导教师：吉根林二 00 七 年九 月三 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-2-一、问题描述-3 二、算法思想-3 2.1 Hash技术介绍-32.2 C 语言关键字-4 2.3 Hash表的建立-5 2.4 算法描述-5 三、算法实现-6 3.1 数据结构3.2 程序模块3.3 各模块之间的调用关系四、测试与分析-7 五、总结-8
2、 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-3-一、问题描述利用 Hash 技术统计某个C源程序中的关键字出现的频度扫描一个C 程序，用 Hash 表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度，用线性探测法解决Hash 冲突。设Hash函数为Hash(Key)=(Key第一个字符在1-26 个字母中的序号)*100+(Key 最后一个字符在1-26 个字母中的序号)%41 实现模型二、算法思想21 Hash 技术介绍2.1.1 定义：哈希表是为了便于快速搜索而组织的键/值组合的集合。Ha
3、sh Table 是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。键/值对的集合。2.1.2 优点：哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。2.1.3 基本原理：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash 值）存在一一对应的关系，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字
4、为每一个元素“分类”。2.1.4哈希表的不可避免冲突(collision)现象：对 不 同 的 关 键 字 可 能 得 到 同 一 个 哈 希 地 址即key1 key2，而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:拉链法课程设计程序显示器输出关键字个数C 源文件名
5、师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-4-基本做法：将所有关键字为同义词的结点链接在同一个单链表中。若选定的哈希函数所产生的哈希地址为0m-1,则可将哈希表定义成一个由m 个链表头指针组成的指针数组。这种方法的优点是：不产生 堆集。由于结点空间是动态申请的，故更适合于造表前无法确定表长的情况。从表中删除结点容易。22 C 语言关键字2.2.1什么是 C 语言关键字C 语言关键字是C 语言的保留的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。其特点是都有小写字母构成
6、。2.2.2 C语言关键字有哪些double：声明双精度变量或函数int：声明整型变量或函数struct：声明结构体变量或函数break：跳出当前循环else：条件语句否定分支（与if 连用）long：声明长整型变量或函数switch:用于开关语句case：开关语句分支enum：声明枚举类型register：声明积存器变量char：声明字符型变量或函数extern：声明变量是在其他文件正声明（也可以看做是引用变量）return：子程序返回语句（可以带参数，也看不带参数）union：声明联合数据类型const：声明只读变量float：声明浮点型变量或函数short：声明短整型变量或函数unsig
7、ned：声明无符号类型变量或函数continue：结束当前循环，开始下一轮循环for：一种循环语句(可意会不可言传）signed：生命有符号类型变量或函数void：声明函数无返回值或无参数，声明无类型指针（基本上就这三个作用）default：开关语句中的“其他”分支goto：无条件跳转语句sizeof：计算数据类型长度volatile：说明变量在程序执行中可被隐含地改变do：循环语句的循环体while：循环语句的循环条件static：声明静态变量if：条件语句名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-5
8、-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 源程序（按字符读入）建立 fst
9、ream 对象 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 表。然后将识别单词中获取的TestS
10、tr 字符串进行 Hash 查找。如果找到对应记录说明是关键字，关键字个数+1，不是则退出。2)对于 Hash 冲突,在这个程序中采取的冲突解决方式是拉链法。如果在关键字在Hash 表对应的位置已经被占用了那么开辟一个新的数据域并用占用位置的一个指针指向新数据域。2.4.4 特殊情况的处理以下三种特殊情况(“”之间/*/注释块之间/注释行)的字符串不需要参与统计在进行 C 源文件扫描的时候是按字符一个一个读入的定义 2 个 char 型变量ch prech(prech初始化为,;?)ch 记录当前字符prech 记录当前字符之前的一个字符1)对于”处理的办法定义一个 int 型变量enable
11、_yh 初始化为 1 每次用 ch 读入字符的时候做以下判断若 enable_yh=1&ch=?”?的时候将 enable_yh 改成 0 若 enable_yh=0&ch=?”?的时候将 enable_yh改成 1 enable_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 在
12、对 C 源文件进行按行读写的时候读每行之前e nable_xg初始化为 1 prech 初始化为?;?如果在读一行的过程中prech=?/?&ch=?/?就让 enable_xg改为 0.enable_xg=1时候才进行Hash 查找名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-6-三、算法实现3.1 数据结构全局变量search_chances 记录进入 Hash 查找的函数的次数search_times 记录 Hash 查找的次数两者相除就是平均查找次数(包括成功失败2 种情况)typedef stru
13、ct 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 源文件遍历在适当条件下找出可能为关键字的字符串并调用 Insert
14、Key函数进行 hash 查找int IsSmallLetter(char ch);/判断某一个字符是否是小写字母void PrintHashList();/打印给用户看hash 表中关键字的次数 3.3各模块之间的调用关系函数说明:main():主函数CreateHash()建立 Hash 表HashFun()Hash 函数CountKey()读取 C 源文件并获取单词进行hash 查找IsSmalLetter()判别是否是小写字母InsertKey()进行 hash 查找并计数PrintHashList()打印关键字个数Countkey CreateHash PrintHashList I
15、sSmallLetterInsertKeyHashFunmain 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-7-四、测试与分析将自己做的课程设计的代码作为源文件进行测试。一共测试 8 次,实验表明程序是正确的。其中一次结果如下:另分别对“/*/进行测试都满足条件名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -数据结构课程设计之C 源文件关键字统计李华溢06050514-8-五、总结1。C 程序设计是面向过程的。函数是构成程序的基本单元，函数选择与设计很重要，有利于程序的编写2。程
16、序=数据结构+算法其中数据结构的地位也是很重要的。如果数据结构建立不够好，会影响算法的设计与实现。当然算法的正确性，健壮性，可读性，高效低存储也是很重要的。3。对 Hash 查找的认识有三个问题值得关注1如何定义一个好的hash 函数使元素在 Hash 表内分散均匀，使冲突降到最低。2如何建立Hash 表以及避免 Hash 冲突对拉链法和线性探测法的理解3Hash 查找的性能分析平均查找次数在(1-2)之间 可见 Hash 查找效率很高4。对程序设计水平又有了新的提高。程序越写越大,函数越写越多。5。合理的注释可以方便日后参考和改进6。写科技论文的格式规范1。注意排版，树形结构的段落分层2。概念的介绍要详尽3。尽量写出逻辑框图7。程序调错的提高Vc+6.0 在一些功能上不及Vs2005 方面并且代码不可以折叠，从 Vc+6.0 的 debug 过渡到VS2005 debug的使用也算是个不小的进步。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -