第十三章数据抽象.ppt

,第一章,C,语言的基本概念,关于:,Qiao Lin,6279.2961(Office),CIC,Tsinghua Univ,About Grade,Score,Homework and Experiments,Score,About Lessons,*,安徽大学计算机教学部,计算机程序设计基础,第十三章,数据抽象,学习目标,理解数据抽象原则，了解抽象数据类型的概念,理解栈，能使用多种方法实现栈,理解队列，能使用多种方法实现队列,熟悉符号表的概念，掌握抽象符号表的接口设计原则与基本实现策略,熟悉哈希表的概念，了解哈希表设计的关键问题，并能针对具体应用问题进行具体分析,13.1 抽象数据类型,抽象的表现形式,行为抽象：函数,数据结构抽象：抽象数据类型,抽象数据类型的基本概念,仅关心类型的行为，不关心数据的具体实现细节,C,语言中的基本数据类型：仅关心如何使用数据，而不关心如何表示这些数据,抽象数据类型的划分：依据数据之间的关系,线性数据结构与非线性数据结构,线性数据结构与非线性数据结构,线性数据结构,非线性数据结构,13.2 线性表类型,线性表定义,或为空表，或为数据类型相同的一组数据，且,各元素只有一个直接前驱和一个直接后继,表头元素只有后继没有前驱,表尾元素只有前驱没有后继,线性表抽象,逻辑抽象：不关心元素的具体数据类型,物理抽象：不关心元素的存储格式,线性表操作,创建新表；,在某节点前插入新节点；,在某节点后插入新节点；,获得某个指定节点值；,设置某个指定节点值；,删除某个指定节点；,删除线性表；,获得当前元素的下一个元素；,获得当前元素的上一个元素；,设置当前元素位置；,获得当前元素位置；,将非空线性表置为空；,判断线性表是否为空；,判断线性表是否为满；,获得线性表长度；,线性表操作,int,Create,(List*,pList,);,int,InsertBefore,(List*,pList,int,pos,int,value,);,int,InsertAfter,(List*,pList,int,pos,int,value,);,int,GetElement,(List,list,int,pos,int,*,element,);,int,SetElement,(List*,pList,int,pos,int,value,);,int,DeleteElement,(List*,pList,int,pos,);,void,DeleteAll,(List*,pList,);,int,Next,(List,list,int,*,next,);,int,Prior,(List,list,int,*,prior,);,int,GetCurPos,(List,list,int,*,pos,);,int,SetCurPos,(List*,pList,int,pos,);,void,Clear,(List*,pList,);,int,IsEmpty,(List,list,);,int,IsFull,(List,list,);,int,GetLength,(List,list,int,*,length,);,线性表应用示例,主函数,void,main,(),int,i,temp,;,List,list,;,if(!,Create,(&,list,),printf,(“Sorry!,n,“);return;,for(,i,=0;,i,10;,i,+),InsertBefore,(&,list,0,i,);,for(,i,=0;,i,element,=(,int,*),malloc,(,MAXSIZE,*,sizeof(,int,);,if(!,pList,element,),printf,(“Cant,malloc,memory for the list!,n,“);,return 0;,pList,length,=0;,pList,current,=0;,return 1;,获取下一元素,int,Next,(List*,pList,int,*,next,),assert,(,pList,!=,NULL,);,if(!,IsEmpty,(*,pList,),if(,GetElement,(*,pList,pList,current,+1,next,),pList,current,+;,return 1;,return 0;,return 0;,获取上一元素,int,Next,(List*,pList,int,*,next,),assert,(,pList,!=,NULL,);,if(!,IsEmpty,(*,pList,),if(,GetElement,(*,pList,pList,current,1,next,),pList,current,;,return 1;,return 0;,return 0;,前插入元素,int,InsertBefore,(List*,pList,int,pos,int,value,),int,i,;,assert,(,pList,!=,NULL,);,if(,IsFull,(*,pList,),printf,(“Full!,n,“);return 0;,if(!,IsEmpty,(*,pList,),if(,pos,pList,length,1),printf,(“Position,error!,n,“);return 0;,if(,pList,length,=,MAXSIZE,),printf,(“Overflow!,n,“);return 0;,for(,i,=,pList,length,;,i,pos,;,i,),pList,element,i,=,pList,element,i,1;,pList,element,pos,=,value,;,pList,length,+;,if(,pos,current,),pList,current,+;,return 1;,else,if(,pos,!=0),printf,(“Invalid,position!,n,“);return 0;,pList,element,0=,value,;,pList,length,+;,pList,current,=0;,return 1;,后插入元素,int,InsertAfter,(List*,pList,int,pos,int,value,),int,i,;,assert,(,pList,!=,NULL,);,if(,IsFull,(*,pList,),printf,(“Full!,n,“);return 0;,if(!,IsEmpty,(*,pList,),if(,pos,pList,length,1),printf,(“Position,error!,n,“);return 0;,if(,pList,length,=,MAXSIZE,),printf,(“Overflow!,n,“);return 0;,for(,i,=,pList,length,;,i,pos,+1;,i,),pList,element,i,=,pList,element,i,1;,pList,element,pos,+1=,value,;,pList,length,+;,if(,pos,current,),pList,current,+;,return 1;,else,if(,pos,!=0),printf,(“Invalid,position!,n,“);return 0;,pList,element,0=,value,;,pList,length,+;,pList,current,=0;,return 1;,删除线性表与元素,void,DeleteAll,(List*,pList,),if(!,pList,element,),free,(,pList,element,);,pList,element,=,NULL,;,int,DeleteElement,(List*,pList,int,pos,),int,i;,assert,(,pList,!=,NULL,);,if(!,IsEmpty,(*,pList,),if(,pos,pList,length,1),printf,(“Position,error!,n,“);return 0;,for(,i,=,pos,;,i,length,1;,i,+),pList,element,i,=,pList,element,i,+1;,if(,pos,current,),pList,current,;,if(,pos,=,pList,current,)&(,pList,current,=,pList,length,1),pList,current,;,pList,length,;,return 1;,return 0;,获取与设置元素,int,GetElement,(List,list,int,pos,int,*,element,),if(!,IsEmpty,(,list,),if(,pos,list,.,length,1),printf,(“Position,error!,n,“);return 0;,*,element,=,list,.,element,pos,;return 1;,return 0;,int,SetElement,(List,*,pList,int,pos,int,value,),assert,(,pList,!=,NULL,);,if(!,IsEmpty,(*,pList,),if(,pos,pList,length,1),printf,(“Position,error!,n,“);return 0;,pList,element,pos,=,value,;return 1;,return 0;,获取与设置当前位置,int,GetCurPos,(List,list,int,*,pos,),if(!,IsEmpty,(,list,)*,pos,=,list,.,current,;return 1;,printf,(“Empty!,n,“);return 0;,int,SetCurPos,(List*,pList,int,pos,),assert,(,pList,!=,NULL,);,if(!,IsEmpty,(*,pList,),if(,pos,pList,length,1),printf,(“Position,error!,n,“);return 0;,pList,current,=,pos,;return 1;,printf(Empty,!n);,return 0;,其他辅助线性表函数,void,Clear,(List*,pList,),if(!,IsEmpty,(*,pList,),pList,current,=0;,pList,length,=0;,int,IsEmpty,(List,list,)return(,list,.,length,=0);,int,IsFull,(List,list,)return(,list,.,length,=,MAXSIZE,);,int,GetLength,(List,list,int,*,length,),if(!,IsEmpty,(,list,)*,length,=,list,.,length,;return 1;,printf,(“Empty!,n,“);return 0;,通用线性表类型,typedef,int,ListElement,;,/*,定义通用数据类型*/,typedef,struct,taglistListElement,*,element,;,int,length,;,int,current,;List;,int,Create,(List*,pList,);,int,InsertBefore,(List*,pList,int,pos,ListElement,value,);,int,InsertAfter,(List*,pList,int,pos,ListElement,value,);,int,GetElement,(List,list,int,pos,int,*,element,);,int,SetElement,(List*,pList,int,pos,ListElement,value,);,int,DeleteElement,(List*,pList,int,pos,);,void,DeleteAll,(List*,pList,);,int,Next,(List,list,int,*,next,);,int,Prior,(List,list,int,*,prior,);,int,GetCurPos,(List,list,int,*,pos,);,int,SetCurPos,(List*,pList,int,pos,);,void,Clear,(List*,pList,);,int,IsEmpty,(List,list,);,int,IsFull,(List,list,);,int,GetLength,(List,list,int,*,length,);,13.3 栈,栈定义,满足先进后出访问规则的数据集,栈操作集,创建新栈,入栈；出栈,清空栈,判断栈是否为空；判断栈是否为满,求栈的深度,栈操作,int,NewStack,(,stackADT,stack,);,void,FreeStack,(,stackADT,stack,);,int,Push,(,stackADT,stack,stackElementT,element,);,int,Pop,(,stackADT,stack,stackElementT,*,element,);,int,StackIsEmpty,(,stackADT,stack,);,int,StackIsFull,(,stackADT,stack,);,int,StackDepth,(,stackADT,stack,int,depth,);,抽象栈的实现,对线性表的再抽象：使用线性表实现栈,元素的插入与删除操作只发生在表尾,可以发生在表头吗？,typedef,int,stackElementT,;,typedef,List*,stackADT,;,可以，但需要元素移动操作,栈的创生与释放,int,NewStack,(,stackADT,stack,),if(,Create,(,stack,)return 1;,return 0;,void,FreeStack,(,stackADT,stack,),DeleteAll,(,stack,);,入栈,int,Push,(,stackADT,stack,stackElementT,element,),if(!,StackIsEmpty,(,stack,),if(!,InsertAfter,(,stack,stack,length,1,element,),return 0;,return 1;,else,if(!,InsertAfter,(,stack,0,element,)return 0;,return 1;,出栈,int,Pop,(,stackADT,stack,stackElementT,*,element,),if(!,StackIsEmpty,(,stack,),if(!,GetElement,(*,stack,stack,length,1,element,),return 0;,if(!,DeleteElement,(,stack,stack,length,1),return 0;,return 1;,return 0;,其他辅助栈函数,int,StackIsEmpty,(,stackADT,stack,),return,IsEmpty,(*,stack,);,int,StackIsFull,(,stackADT,stack,),return,IsFull,(*,stack,);,int,StackDepth,(,stackADT,stack,int,*,depth,),return,GetLength,(*,stack,depth,);,后缀表达式,中缀表达式,定义：操作符位于操作数之间的算术表达式,示例：,1+2 3,后缀表达式,定义：操作符位于操作数之后的算术表达式,示例：,1 2+3,栈应用,使用栈编写一个简单的整数计算器，具有加减乘除和幂运算功能，输入“,q”,表示结束,int,GetTwoOperands,(,stackADT,stack,int,*,op1,int,*,op2,);,void,Compute,(,stackADT,stack,char,op,);,void,Run,();,void,main,(),clrscr,();,Run,();,算法要点：输入字符，若不是+、*、/、则进栈，否则从栈中依次弹出两个操作数，运算后再将结果压栈，重复上述过程，直到输入字符“,q”,Run,(),函数负责栈的创建与删除，并负责将操作数存入栈中，如果其为运算符，则启动计算函数,Compute,()，,该函数先调用,GetTwoOperands,(),从栈中获得相关操作数，然后根据,Run,(),函数传入的运算符计算，并将结果作为新操作数入栈,栈应用,void,Run,(),char,c,20;,stackADT,calc,;,if(,NewStack,(,calc,),while(,gets,(,c,),c,0!=q),switch(,c,0),case:,/*,如果是负数，压栈，否则计算*/,if(,strlen,(,c,)1),Push,(,calc,atoi,(,c,);else,Compute,(,calc,c,0);break;,case/:case+:case*:case:,Compute,(,calc,c,0);break;,default:,Push,(,calc,atoi,(,c,);break;,FreeStack,(,calc,);,栈应用,void,Compute,(,stackADT,stack,char,op,),int,result,operand1,operand2,;,if(,GetTwoOperands,(,stack,&,operand1,&,operand2,),switch(,op,),case+:,result,=,operand2,+,operand1,;break;,case:,result,=,operand2,operand1,;break;,case*:,result,=,operand2,*,operand1,;break;,case:,result,=,pow,(,operand2,operand1,);break;,case/:,if(,operand1,=0),printf,(“Divide,by zero!,n,“);break;,else,result,=,operand2,/,operand1,;,break;,if(,Push,(,stack,result,),printf,(“=%,d,n,“,result,);,栈应用,int,GetTwoOperands,(,stackADT,stack,int,*,op1,int,*,op2,),if(,StackIsEmpty,(,stack,),printf,(“Missing,operand!,n,“);return 0;,if(,Pop,(,stack,op1,),if(,StackIsEmpty,(,stack,),printf,(“Missing,operand!,n,“);return 0;,if(,Pop,(,stack,op2,)return 1;,return 0;,计算器运行时栈状态变化,输入,栈动作,栈状态,结果显示,初始状态,无,(),无,10,Push,(10),(10),无,20,Push,(20),(20,10),无,30,Push,(30),(30,20,10),无,+,Pop,(),(20,10),无,Pop,(),(10),无,Push,(20+30),(50,10),50,Pop,(),(10),无,Pop,(),(),无,Push,(1050),(,40),40,程序文件的组织,主函数文件,主函数与计算器辅助函数原型与实现：,main.c,抽象栈库,函数原型：,stack.h,函数实现：,stack.c,抽象线性表库,函数原型与数据类型定义：,list.h,函数实现：,list.c,13.4 队列,队列定义,满足先进先出访问规则的数据集,队列操作集,创建新队列,入队；出队,清空队列,判断队列是否为空；判断队列是否为满,求队列的长度,遍历队列,队列操作,int,NewQueue,(,queueADT,queue,);,void,FreeQueue,(,queueADT,queue,);,int,Enqueue,(,queueADT,queue,queueElementT,element,);,int,Dequeue,(,queueADT,queue,queueElementT,*,element,);,int,QueueIsEmpty,(,queueADT,queue,);,int,QueueIsFull,(,queueADT,queue,);,int,QueueLength,(,queueADT,queue,int,*,length,);,void,TraverseQueue,(,queueADT,queue,);,抽象队列的实现,对线性表的再抽象：使用线性表实现队列,元素的插入操作只发生在队尾,元素的删除操作只发生在队首,typedef,int,queueElementT,;,typedef,List*,queueADT,;,队列的创生与释放,int,NewQueue,(,queueADT,queue,),if(,Create,(,queue,)return 1;,return 0;,void,FreeQueue,(,queueADT,queue,),DeleteAll,(,queue,);,入队,int,Enqueue,(,queueADT,queue,queueElementT,element,),if(!,QueueIsEmpty,(,queue,),if(!,InsertAfter,(,queue,queue,length,1,element,),return 0;,return 1;,else,if(!,InsertAfter,(,queue,0,element,)return 0;,return 1;,出队,int,Dequeue,(,queueADT,queue,queueElementT,*,element,),if(!,QueueIsEmpty,(,queue,),if(!,GetElement,(*,queue,0,element,),return 0;,if(!,DeleteElement,(,queue,0),return 0;,return 1;,return 0;,遍历队列,void,TraverseQueue,(,queueADT,queue,),queueElementT,element,;,int,i,len,;,if(,QueueIsEmpty,(,queue,),printf,(“Empty!,n,“);return;,QueueLength,(,queue,&,len,);,for(,i,=0;,i,len,;,i,+),GetElement,(*,queue,i,&,element,);,printf,(“%,d,n,“,element,);,其他辅助队列函数,int,QueueIsEmpty,(,queueADT,queue,),return,IsEmpty,(*,queue,);,int,QueueIsFull,(,queueADT,queue,),return,IsFull,(*,queue,);,int,Queuelength,(,queueADT,queue,int,*,length,),return,GetLength,(*,queue,length,);,队列应用,实现一个简单进度表,用户可以为某个项目产生一个进度表，对于进度表中各个进度安排以字符串形式表达，已经执行完的进度在进度表中删除，新进度安排在进度表尾，当然可以浏览当前所有未执行的进度,实现策略,数据结构使用队列，队头的进度首先得到执行并从队列中删除，队尾是新加入的进度,进度信息为字符串，可以使用定长字符数组实现，不过这容易导致存储空间的浪费，也可能因数组越界而使系统运行出现异常,使用字符指针队列更好，字符串资源由系统运行时动态分配,队列应用,#include,#include,#include,#include,#include“queue.h“,void,Enter,(,queueADT,myqueue,);,void,Remove,(,queueADT,myqueue,);,void,Review,(,queueADT,myqueue,);,队列应用,void,main,(),char,s,81;,queueADT,myqueue,;,NewQueue,(,myqueue,);,clrscr,();,for(;),printf(“E-Enter,n,R-Remove,n,V-reView,n,Q-Quit,n,“);,gets(,s,);,switch(*,s,),case E:case e:,Enter,(,myqueue,);break;,case R:case r:,Remove,(,myqueue,);break;,case V:case v:,Review,(,myqueue,);break;,case Q:case q:,FreeQueue,(,myqueue,);return;,队列应用,void,Enter,(,queueADT,myqueue,),char,temp,81,*,pTemp,;,if(,QueueIsFull,(,myqueue,),printf,(“Full!,n,“);,return;,printf,(“Input,event:“);,gets(,temp,);,pTemp,=(char*),malloc,(,strlen,(,temp,)+1);,strcpy,(,pTemp,temp,);,Enqueue,(,myqueue,pTemp,);,队列应用,void,Remove,(,queueADT,myqueue,),char*,pTemp,;,if(,QueueIsEmpty,(,myqueue,),printf,(“No,event!,n,“);return;,Dequeue,(,myqueue,&,pTemp,);,printf,(“%,s,n,“,pTemp,);,free,(,pTemp,);,void,Review,(,queueADT,myqueue,),TraverseQueue,(,myqueue,);,程序文件的组织,主函数文件,主函数与队列应用函数原型与实现：,main.c,抽象队列库,函数原型：,queue.h,函数实现：,queue.c,抽象线性表库,函数原型与数据类型定义：,list.h,函数实现：,list.c,13.5 符号表,非线性数据结构,线性数据结构的四个基本条件至少有一个不满足,符号表定义,可以通过特定关键字查找其对应意义的数据结构,概念上与字典类似,实现上每个元素具有键（关键字）和对应值,符号表的目的,提高查找效率，在常数时间内完成数据查找任务,抽象符号表接口设计,/*,symtbl.h,:,抽象符号表头文件*/,/*,PSYMBOLTABLE,为抽象符号表指针类型*/,/*符号表类型,SYMBOLTABLE,的具体实现隐藏于源文件中*/,typedef,struct,SYMBOLTABLE*PSYMBOLTABLE;,/*,CreateSymTbl,：,符号表构造函数*/,/*返回值：指向所构造的匿名抽象符号表数据对象的指针,*/,PSYMBOLTABLE,CreateSymTbl,();,/*,DestroySymTbl,：,符号表析构函数*/,/*,p,：,指向抽象符号表数据对象的指针,*/,void,DestroySymTbl,(PSYMBOLTABLE,p,);,抽象符号表接口设计,/*,GetCountOfSymTbl,：,获取符号表中存储的元素个数*/,/*,p,：,指向抽象符号表数据对象的指针,*/,/*,返回值：元素个数，类型为,unsigned,int,*/,unsigned,int,GetCountOfSymTbl,(PSYMBOLTABLE,p,);,/*,InsertIntoSymTbl,：,将元素插入到符号表中*/,/*,p,：,指向抽象符号表数据对象的指针,*/,/*,key,：,待插入元素的键信息，类型未知*/,/*,value,：,待插入元素的值信息，类型未知*/,/*返回值：无*/,void,InsertIntoSymTbl,(PSYMBOLTABLE,p,?,key,?,value,);,抽象符号表接口设计,/*,DeleteFromSymTbl,：,从符号表中删除特定元素*/,/*,p,：,指向抽象符号表数据对象的指针,*/,/*,key,：,待删除元素的键信息，类型未知*/,/*返回值：无*/,void,DeleteFromSymTbl,(PSYMBOLTABLE,p,?,key,);,/*,SearchInSymTbl,：,在符号表中查找指定元素*/,/*,p,：,指向抽象符号表数据对象的指针,*/,/*,key,：,待查找元素的键信息，类型未知*/,/*返回值：待查找元素的值信息，类型未知*/,?,SearchInSymTbl,(PSYMBOLTABLE,p,?,key,);,抽象符号表接口设计,/*,ClearSymTbl,：,清空符号表*/,/*,p,：,指向抽象符号表数据对象的指针,*/,/*,返回值：无*/,void,ClearSymTbl,(PSYMBOLTABLE,p,);,/*,TraverseSymTbl,：,遍历符号表，依次访问其中全部元素*/,/*,p,：,指向抽象符号表数据对象的指针,*/,/*,返回值：无*/,void,TraverseSymTbl,(PSYMBOLTABLE,p,);,确定键与值的类型,键的类型：与问题域有关,字符串的存储、查找与匹配,整数的存储、查找与匹配,值的类型：如何保证通用？,使用无型指针类型,无定义值的处理,void*,UNDEFINEDVALUE,=(void*)(&,UNDEFINEDVALUE,);,为什么不使用,NULL,？,抽象符号表接口定义,/*,SymTbl.h,:,抽象符号表头文件*/,#,ifndef,_SYMTBL_H,#define,_SYMTBL_H,extern void*,UNDEFINEDVALUE,;,typedef,struct,SYMBOLTABLE*PSYMBOLTABLE;,PSYMBOLTABLE,CreateSymTbl,();,void,DestroySymTbl,(PSYMBOLTABLE,p,);,unsigned,int,GetCountOfSymTbl,(PSYMBOLTABLE,p,);,void,InsertIntoSymTbl,(PSYMBOLTABLE,p,int,key,void*,value,);,void,DeleteFromSymTbl,(PSYMBOLTABLE,p,int,key,);,void*,SearchInSymTbl,(PSYMBOLTABLE,p,int,key,);,void,ClearSymTbl,(PSYMBOLTABLE,p,);,void,TraverseSymTbl,(PSYMBOLTABLE,p,);,#,endif,13.6 哈希表,哈希造表,目的：获得常数时间复杂度的查找效率,关键技术：将关键字与存储地址对应起来,最好情况下，查找或插入只需要一次访问,哈希函数：元素的散列,定义：设计关系,f,，,使关键字,k,与地址,f,(,k,),对应,好处：若存在关键字,k,，,则必定位于,f,(,k,),处，无需比较即可获得该数据,哈希函数示例,整数集,A,：,包含,10,个元素,9099,使用数组,遍历数组,10次,5次,调用哈希函数计算其地址,0次，直接从该地址处取数,如何保存这,10,个元素？,如何查找元素,99,？,几次比较操作才能获得结果？,查找任意一个元素，平均需要几次比较操作？,使用哈希表存储整数集,哈希函数：,f,(,x,)=,x,%10,散列结果：每个元素位于不同地址处,如何查找元素,99,？,几次比较操作才能获得结果？,哈希函数示例,整数集,B,：,包含,12,个元素,8899,使用数组,遍历数组,12次,6次,调用哈希函数计算其地址,0次，直接从该地址处取数,如何保存这,12,个元素？,如何查找元素,99,？,几次比较操作才能获得结果？,查找任意一个元素，平均需要几次比较操作？,使用哈希表存储整数集,哈希函数：,f,(,x,)=,x,%10,散列结果：大部分元素位于不同地址处,如何查找元素,99,？,几次比较操作才能获得结果？,哈希地址冲突,哈希地址冲突现象,不同键经哈希函数映射后，得到同一哈希地址,数学描述：虽然,k,1,k,2,，,但,f,(,k,1,)=,f,(,k,2,),例：整数集,B,，,哈希函数,f,(,x,)=,x,%10,解决方法：每个元素位于不同地址处,更换哈希函数：,f,(,x,)=,x,88,效果：冲突只能尽可能减少，而不能完全避免,链地址法,桶+线性链表,抽象哈希表的内部数据结构,/*,symtbl.c,：,抽象符号表源文件，内部数据结构*/,/*在源文件内部实现这些数据结构，外部不可访问，保证数据结构与信息的封装性*/,/*抽象结点类型，,PNODE,为指向结点类型的指针类型*/,typedef,struct,NODE*PNODE;,/*,结点类型；包含了元素信息,key,、,value,以及构造链表所需要的链接信息,next,*/,struct,NODE,int,key,;void*,value,;PNODE,next,;,/*,符号表数据类型；,count,：,符号表当前所保存的元素数目；,prime,：,符号表当前的桶数，此值一般为质数；,buckets,：,符号表的桶数组，因为需要动态确定桶数，所以使用指针而不是数组*/,struct,SYMBOLTABLE unsigned,int,count,;unsigned,int,prime,;PNODE*,buckets,;,抽象哈希表实现,/*,symtbl.c,：,抽象符号表的源文件*/,#,ifndef,_SYMTBL_H_,#include.,SymTbl.h,#,endif,#include,#include,#include,typedef,struct,NODE*PNODE;,struct,NODE,int,key,;void*,value,;PNODE,next,;,struct,SYMBOLTABLE,unsigned,int,count;,unsigned,int,prime;,PNODE*buckets;,;,抽象哈希表实现,/*,内部函数；仅在当前源文件中使用，外部不可见*/,/*,Hash,：,杂凑函数，将特定的键散列到哈希表的某个桶中*/,/*,key,：,键*/,/*,prime,：,哈希表的桶数*/,/*返回值：桶号，即散列后的地址*/,static unsigned,int,Hash,(,int,key,unsigned,int,prime,