数据结构域算法设计-符号表的设计与实现 教案

《数据结构域算法设计-符号表的设计与实现 教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、符号表的设计与实现1.实验目的了解符号表的作用、组织和数据结构，设计和实现一个符号表。2.实验要求a)合理有效地设计符号表可存储程序语言中的各种标识符（变量、常量、数组、结构、指针、函数和过程）及其属性和作用域信息b)列出关键算法的具体实现的思路3.实验原理及内容（1）符号表的作用符号表用于登录名字（标识符）、相应对象的种类（常量、变量、数组、结构、文件、标号、指针、函数与过程等）、属性（整型、实型、字符型、布尔型与枚举型等）和作用域信息。由于在编译的各个阶段都要对符号表进行频繁操作（查表和填表），在整个编译时间中占了较大比例，因此如何有效合理地组织符号表并选择好的填表和查表方式，对于提高

2、编译器的工作效率有很大影响。（2）符号表的组织源程序中的每个标识符在符号表中都有1个条目，一般由两部分组成：名字栏和信息栏。如果一个语言对标识符的最大长度有限制，可设计名字栏的域大小为最大长度来容纳整个标识符；若该语言对标识符最大长度无限制或最大长度较大（如：32），为节省存储空间，可另用一个字符数组存储标识符，在名字栏域中存储其起始地址和长度（字符个数）。源程序中的标识符种类繁多，不同种类的标识符所需要存储的信息不同。如：变量需存储其类型、存储地址等，数组应存储其数组维数m、数组元素类型T、各维元素个数di、起始地址base等，指针应存储其指向对象类型的位置，函数应存储其参数及类型、返回

3、值类型等……源程序中的说明将标识符与具有某种类型属性的数据对象相关联。同一个标识符在不同程序位置被说明时代表不同的数据对象。当出现对一个标识符的引用时，需根据作用域规则查符号表获取正确的符号表条目。C语言采用静态作用域规则，按最近嵌套原则确定作用域。1.符号表的设计与实现的算法思想由于线性表的访问复杂度为O（n），效率较低，符号表常采用效率更高的哈希技术进行实现：当出现标识符id的定义时，计算哈希函数H(id)，获取其在哈希表的存储位置，如该位置为空，则直接存储，否则应用冲突消解方法来获取其存储位置；当出现对标识符id的引用时，计算哈希函数H(id)，获取其在哈希表的存储位置。（1）主程序

4、示意图如图4-1所示。置初值调用switch选择要进行的操作调用不同case中的方法结束图4-1符号表设计与实现主程序示意图（2）Insert分析程序示意图如图4-2所示。调用insert函数是否存在表否是调用read读入函数将表信息存入哈希表中出错处理图4-2insert分析函数示意图（1）Find分析程序示意图如图4-3所示。输入表名是否存在表否是调用find函数在哈希表中找到表信息结束返回表信息提示不存在图4-3find分析函数示意图（2）Remove分析程序示意图如图4-4所示。输入表名（key）是否存在表否是调用remove函数结束显示删除成功提示删除失败图4-4remove分析

5、函数示意图（3）Show分析程序示意图如图4-5所示。调用show结束显示哈希列表中表信息图4-5show分析函数示意图1.符号表设计与实现主要代码boolCHashTable::Insert(CRecord&record)//在哈希表中插入表{list&OldList=m_Array[MyHash(record.GetKey())];if(find(OldList.begin(),OldList.end(),record)!=OldList.end()){returnfalse;}OldList.push_back(record);m_nCurrentSize++;re

6、turntrue;}boolCHashTable::Find(char*key)//通过关键字在哈希表中找到表，显示表信息{list&OldList=m_Array[MyHash(key)];list::iteratorit;for(it=OldList.begin();it!=OldList.end();it++){if(strcmp(key,it->GetKey())==0){system("cls");cout<<"查找结果："<PrintHead();it->Show();returntrue;}}returnfalse;

7、}boolCHashTable::Remove(char*key)//输入关键字，删除哈希列表中的表及信息{list&OldList=m_Array[MyHash(key)];list::iteratorit;for(it=OldList.begin();it!=OldList.end();it++){if(strcmp(key,it->GetKey())==0){OldList.er