《第十三章数据抽象》由会员分享，可在线阅读，更多相关《第十三章数据抽象（79页珍藏版）》请在金锄头文库上搜索。
1、1安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础第十三章 数据抽象学习目标学习目标理解数据抽象原则，了解抽象数据类型的概念理解数据抽象原则，了解抽象数据类型的概念理解数据抽象原则，了解抽象数据类型的概念理解数据抽象原则，了解抽象数据类型的概念理解栈，能使用多种方法实现栈理解栈，能使用多种方法实现栈理解栈，能使用多种方法实现栈理解栈，能使用多种方法实现栈理解队列，能使用多种方法实现队列理解队列，能使用多种方法实现队列理解队列，能使用多种方法实现队列理解队列，能使用多种方法实现队列熟悉符号表的概念，掌握抽象符号表的接口设计熟悉符号表的概念，掌握抽象符号表的接口设计熟悉
2、符号表的概念，掌握抽象符号表的接口设计熟悉符号表的概念，掌握抽象符号表的接口设计原则与基本实现策略原则与基本实现策略原则与基本实现策略原则与基本实现策略熟悉哈希表的概念，了解哈希表设计的关键问题，熟悉哈希表的概念，了解哈希表设计的关键问题，熟悉哈希表的概念，了解哈希表设计的关键问题，熟悉哈希表的概念，了解哈希表设计的关键问题，并能针对具体应用问题进行具体分析并能针对具体应用问题进行具体分析并能针对具体应用问题进行具体分析并能针对具体应用问题进行具体分析2安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.1 抽象数据类型抽象的表现形式抽象的表现形式行为抽象：函数行
3、为抽象：函数行为抽象：函数行为抽象：函数数据结构抽象：抽象数据类型数据结构抽象：抽象数据类型数据结构抽象：抽象数据类型数据结构抽象：抽象数据类型抽象数据类型的基本概念抽象数据类型的基本概念仅关心类型的行为，不关心数据的具体实现细节仅关心类型的行为，不关心数据的具体实现细节仅关心类型的行为，不关心数据的具体实现细节仅关心类型的行为，不关心数据的具体实现细节C C C C 语言中的基本数据类型：仅关心如何使用数据，语言中的基本数据类型：仅关心如何使用数据，语言中的基本数据类型：仅关心如何使用数据，语言中的基本数据类型：仅关心如何使用数据，而不关心如何表示这些数据而不关心如何表示这些数据而不关心如何
4、表示这些数据而不关心如何表示这些数据抽象数据类型的划分：依据数据之间的关系抽象数据类型的划分：依据数据之间的关系线性数据结构与非线性数据结构线性数据结构与非线性数据结构线性数据结构与非线性数据结构线性数据结构与非线性数据结构3安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础线性数据结构与非线性数据结构线性数据结构线性数据结构非线性数据结构非线性数据结构4安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.2 线性表类型线性表定义线性表定义或为空表，或为数据类型相同的一组数据，且或为空表，或为数据类型相同的一组数据，且或为空表，或为数据类
5、型相同的一组数据，且或为空表，或为数据类型相同的一组数据，且各元素只有一个直接前驱和一个直接后继各元素只有一个直接前驱和一个直接后继各元素只有一个直接前驱和一个直接后继各元素只有一个直接前驱和一个直接后继表头元素只有后继没有前驱表头元素只有后继没有前驱表头元素只有后继没有前驱表头元素只有后继没有前驱表尾元素只有前驱没有后继表尾元素只有前驱没有后继表尾元素只有前驱没有后继表尾元素只有前驱没有后继线性表抽象线性表抽象逻辑抽象：不关心元素的具体数据类型逻辑抽象：不关心元素的具体数据类型逻辑抽象：不关心元素的具体数据类型逻辑抽象：不关心元素的具体数据类型物理抽象：不关心元素的存储格式物理抽象：不关心元
6、素的存储格式物理抽象：不关心元素的存储格式物理抽象：不关心元素的存储格式5安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础线性表操作创建新表；创建新表；创建新表；创建新表；在某节点前插入新节点；在某节点前插入新节点；在某节点前插入新节点；在某节点前插入新节点；在某节点后插入新节点；在某节点后插入新节点；在某节点后插入新节点；在某节点后插入新节点；获得某个指定节点值；获得某个指定节点值；获得某个指定节点值；获得某个指定节点值；设置某个指定节点值；设置某个指定节点值；设置某个指定节点值；设置某个指定节点值；删除某个指定节点；删除某个指定节点；删除某个指定节点；删除某个指
7、定节点；删除线性表；删除线性表；删除线性表；删除线性表；获得当前元素的下一个元素；获得当前元素的下一个元素；获得当前元素的下一个元素；获得当前元素的下一个元素；获得当前元素的上一个元素；获得当前元素的上一个元素；获得当前元素的上一个元素；获得当前元素的上一个元素；设置当前元素位置；设置当前元素位置；设置当前元素位置；设置当前元素位置；获得当前元素位置；获得当前元素位置；获得当前元素位置；获得当前元素位置；将非空线性表置为空；将非空线性表置为空；将非空线性表置为空；将非空线性表置为空；判断线性表是否为空；判断线性表是否为空；判断线性表是否为空；判断线性表是否为空；判断线性表是否为满；判断线性表是
8、否为满；判断线性表是否为满；判断线性表是否为满；获得线性表长度；获得线性表长度；获得线性表长度；获得线性表长度；6安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础线性表操作intint CreateCreate( List * ( List * pListpList ); );intint InsertBeforeInsertBefore( List * ( List * pListpList, , intint pospos, , intint value value ); );intint InsertAfterInsertAfter( List * ( Lis
9、t * pListpList, , intint pospos, , intint value value ); );intint GetElementGetElement( List ( List listlist, , intint pospos, , intint * *element element ); );intint SetElementSetElement( List *( List *pListpList, , intint pospos, , intint value value ); );intint DeleteElementDeleteElement( List *(
10、 List *pListpList, , intint pos pos ); );void void DeleteAllDeleteAll( List *( List *pListpList ); );intint NextNext( List ( List listlist, , intint * *next next ); );intint PriorPrior( List ( List listlist, , intint * *prior prior ); );intint GetCurPosGetCurPos( List ( List listlist, , intint * * p
11、os pos ); );intint SetCurPosSetCurPos( List *( List *pListpList, , intint pospos ); );void void ClearClear( List *( List *pListpList ); );intint IsEmptyIsEmpty( List ( List listlist ); );intint IsFullIsFull( List ( List listlist ); );intint GetLengthGetLength( List ( List listlist, , intint * *lengt
12、h length ); );7安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础线性表应用示例主函数主函数void void mainmain() () intint i i, , temptemp; ; List List listlist; ; if( ! if( !CreateCreate( &( &listlist ) ) ) ) printfprintf( “Sorry!( “Sorry!n n“ ); return; “ ); return; for( for( i i = 0; = 0; i i 10; 10; i i+ ) + ) InsertBefo
13、reInsertBefore( &( &listlist, 0, , 0, i i ); ); for( for( i i = 0; = 0; i i 10; elementelement = ( = ( intint * ) * )mallocmalloc( ( MAXSIZE MAXSIZE * * sizeof(sizeof(intint) ) ;) ) ; if( ! if( !pListpListelement element ) ) printfprintf(“Cant(“Cant mallocmalloc memory for the list! memory for the l
14、ist!n n“);“); return 0; return 0; pListpListlength length = 0;= 0; pListpListcurrentcurrent = 0; = 0; return 1; return 1; 10安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础获取下一元素intint NextNext( List *( List *pListpList, , intint * *next next ) ) assertassert( ( pListpList != != NULLNULL ); ); if( ! if( !IsEm
15、ptyIsEmpty(*(*pListpList) ) ) if( if( GetElementGetElement(*(*pListpList, , pListpListcurrent current + 1, + 1, nextnext) ) ) pListpListcurrentcurrent+;+; return 1; return 1; return 0; return 0; return 0; return 0; 11安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础获取上一元素intint NextNext( List *( List *pListpLi
16、st, , intint * *next next ) ) assertassert( ( pListpList != != NULLNULL ); ); if( ! if( !IsEmptyIsEmpty(*(*pListpList) ) ) if( if( GetElementGetElement(*(*pListpList, , pListpListcurrent current 1, 1, nextnext) ) ) pListpListcurrentcurrent ; ; return 1; return 1; return 0; return 0; return 0; return
17、 0; 12安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础前插入元素intint InsertBeforeInsertBefore( List *( List *pListpList, , intint pospos, , intint value value ) ) intint i i; ; assertassert( ( pListpList != != NULLNULL ); ); if( if( IsFullIsFull(*(*pListpList) ) ) ) printfprintf(“Full!(“Full!n n“); return 0; “);
18、 return 0; if( ! if( !IsEmptyIsEmpty(*(*pListpList) ) ) if( if( pospos0| pListpListlengthlength1 ) 1 ) printfprintf(“Position(“Position error! error!n n“); return 0; “); return 0; if( if( pListpListlength length = = MAXSIZE MAXSIZE ) ) printfprintf(“Overflow!(“Overflow!n n“); return 0; “); return 0;
19、 for( for(i i= =pListpListlengthlength; ;i i pospos; ;i i ) ) pListpListelementelement i i=pListpListelementelement i i 1; 1; pListpListelementelement pospos = = valuevalue; ; pListpListlengthlength+;+; if( if( pos pos = current current ) ) pListpListcurrentcurrent+;+; return 1; return 1; else else
20、if( if( pos pos != 0 ) != 0 ) printfprintf(“Invalid(“Invalid position! position!n n“); return 0; “); return 0; pListpListelementelement0 = 0 = valuevalue; ; pListpListlengthlength+; +; pListpListcurrent current = 0;= 0; return 1; return 1; 13安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础后插入元素intint InsertAf
21、terInsertAfter( List *( List *pListpList, , intint pospos, , intint value value ) ) intint i i; ; assertassert( ( pListpList != != NULLNULL ); ); if( if( IsFullIsFull(*(*pListpList) ) ) ) printfprintf(“Full!(“Full!n n“); return 0; “); return 0; if( ! if( !IsEmptyIsEmpty(*(*pListpList) ) ) if( if( po
22、spos0| pListpListlengthlength1 ) 1 ) printfprintf(“Position(“Position error! error!n n“); return 0; “); return 0; if( if( pListpListlength length = = MAXSIZE MAXSIZE ) ) printfprintf(“Overflow!(“Overflow!n n“); return 0; “); return 0; for( for(i i= =pListpListlengthlength; ;i i pospos+1;+1;i i)pList
23、pListelementelement i i=pListpListelementelement i i 1;1; pListpListelementelement pospos+1 = +1 = valuevalue; ; pListpListlengthlength+;+; if( if( pos pos current current ) ) pListpListcurrentcurrent+;+; return 1; return 1; else else if( if( pos pos != 0 ) != 0 ) printfprintf(“Invalid(“Invalid posi
24、tion! position!n n“); return 0; “); return 0; pListpListelementelement0 = 0 = valuevalue; ; pListpListlengthlength+; +; pListpListcurrent current = 0;= 0; return 1; return 1; 14安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础删除线性表与元素void void DeleteAllDeleteAll( List *( List *pListpList ) ) if( ! if( !pListpL
25、istelement element ) ) freefree( ( pListpListelement element ); ); pListpListelement element = = NULLNULL; ; intint DeleteElementDeleteElement( List *( List *pListpList, , intint pospos ) ) intint i; i; assertassert( ( pListpList != != NULLNULL ); ); if( ! if( !IsEmptyIsEmpty(*(*pListpList) ) ) if(
26、if( pospos0| pListpListlengthlength1 ) 1 ) printfprintf(“Position(“Position error! error!n n“); return 0; “); return 0; for( for(i i= =pospos; ; i i lengthlength1;1;i i+) +) pListpListelementelement i i=pListpList elementelement i i+1;+1; if( if( pos pos = current current ) ) pListpListcurrentcurren
27、t ; ; if( ( if( (pos pos = = pListpListcurrentcurrent) & () & (pListpListcurrent current = = pListpListlengthlength1) )1) ) pListpListcurrentcurrent ; ; pListpListlengthlength ; ; return 1; return 1; return 0; return 0; 15安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础获取与设置元素intint GetElementGetElement( List
28、 ( List listlist, , intint pospos, , intint * *element element ) ) if( ! if( !IsEmptyIsEmpty( (listlist) ) ) if( if( pospos0| listlist. .lengthlength1 ) 1 ) printfprintf(“Position(“Position error! error!n n“); return 0; “); return 0; * *element element = = listlist. .elementelement pospos; return 1;
29、 return 1; return 0; return 0; intint SetElementSetElement(List(List * *pListpList, , intint pospos, , intint valuevalue ) ) assertassert( ( pListpList != != NULLNULL ); ); if( ! if( !IsEmptyIsEmpty(*(*pListpList) ) ) if( if( pospos0| pListpListlengthlength1 ) 1 ) printfprintf(“Position(“Position er
30、ror! error!n n“); return 0; “); return 0; pListpListelementelement pospos = = valuevalue; return 1; return 1; return 0; return 0; 16安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础获取与设置当前位置intint GetCurPosGetCurPos( List ( List listlist, , intint * *pos pos ) ) if( ! if( !IsEmptyIsEmpty( (listlist) ) *) ) *po
31、s pos = = listlist. .currentcurrent; return 1; ; return 1; printfprintf(“Empty!(“Empty!n n“); return 0;“); return 0; intint SetCurPosSetCurPos( List *( List *pListpList, , intint pos pos ) ) assertassert( ( pListpList != != NULLNULL ); ); if( ! if( !IsEmptyIsEmpty(*(*pListpList) ) ) if( if( pos pos
32、0 | pListpListlengthlength1 )1 ) printfprintf(“Position(“Position error! error!n n“); return 0; “); return 0; pListpListcurrentcurrent = = pospos; return 1; return 1; printf(Emptyprintf(Empty !n); !n); return 0; return 0; 17安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础其他辅助线性表函数void void ClearClear( List *(
33、 List *pListpList) ) if(!if(!IsEmptyIsEmpty(*(*pListpList) ) pListpListcurrent current = 0; = 0; pListpListlength length = 0; = 0; intint IsEmptyIsEmpty( List ( List list list ) return () return (listlist. .length length = 0); = 0); intint IsFullIsFull( List ( List listlist) return () return (listli
34、st. .length length = = MAXSIZEMAXSIZE); ); intint GetLengthGetLength( List ( List listlist, , intint * *length length ) ) if( ! if( !IsEmptyIsEmpty( (listlist) ) *) ) *length length = = listlist. .lengthlength; return 1; ; return 1; printfprintf(“Empty!(“Empty!n n“); return 0;“); return 0; 18安徽大学计算机
35、教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础通用线性表类型typedeftypedef intint ListElementListElement; ; /* /* 定义通用数据类型定义通用数据类型定义通用数据类型定义通用数据类型 */ */typedeftypedef structstruct taglistListElementtaglistListElement * *elementelement; ; intint lengthlength; ; intint currentcurrent; List; List;intint CreateCreate( List *
36、 ( List * pListpList ); );intint InsertBeforeInsertBefore( List * ( List * pListpList, , intint pospos, , ListElementListElement value value ); );intint InsertAfterInsertAfter( List * ( List * pListpList, , intint pospos, , ListElementListElement value value ); );intint GetElementGetElement( List (
37、List listlist, , intint pospos, , intint * *element element ); );intint SetElementSetElement( List *( List *pListpList, , intint pospos, , ListElementListElement value value ); );intint DeleteElementDeleteElement( List *( List *pListpList, , intint pos pos ); );void void DeleteAllDeleteAll( List *(
38、List *pListpList ); );intint NextNext( List ( List listlist, , intint * *next next ); );intint PriorPrior( List ( List listlist, , intint * *prior prior ); );intint GetCurPosGetCurPos( List ( List listlist, , intint * * pos pos ); );intint SetCurPosSetCurPos( List *( List *pListpList, , intint pospo
39、s ); );void void ClearClear( List *( List *pListpList ); );intint IsEmptyIsEmpty( List ( List listlist ); );intint IsFullIsFull( List ( List listlist ); );intint GetLengthGetLength( List ( List listlist, , intint * *length length ); );19安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.3 栈栈定义栈定义满足先进后出访问规则的数据
40、集满足先进后出访问规则的数据集满足先进后出访问规则的数据集满足先进后出访问规则的数据集栈操作集栈操作集创建新栈创建新栈创建新栈创建新栈入栈；出栈入栈；出栈入栈；出栈入栈；出栈清空栈清空栈清空栈清空栈判断栈是否为空；判断栈是否为满判断栈是否为空；判断栈是否为满判断栈是否为空；判断栈是否为满判断栈是否为空；判断栈是否为满求栈的深度求栈的深度求栈的深度求栈的深度20安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础栈操作intint NewStackNewStack( ( stackADTstackADT stack stack ); );void void FreeSta
41、ckFreeStack( ( stackADTstackADT stackstack ); );intint PushPush( ( stackADTstackADT stackstack, , stackElementTstackElementT elementelement ); );intint PopPop( ( stackADTstackADT stackstack, , stackElementTstackElementT * *elementelement ); );intint StackIsEmptyStackIsEmpty( ( stackADTstackADT stack
42、 stack ) ;) ;intint StackIsFullStackIsFull( ( stackADTstackADT stackstack ); );intint StackDepthStackDepth( ( stackADTstackADT stackstack, , intint depthdepth ); );21安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象栈的实现对线性表的再抽象：使用线性表实现栈对线性表的再抽象：使用线性表实现栈元素的插入与删除操作只发生在表尾元素的插入与删除操作只发生在表尾元素的插入与删除操作只发生在表尾元素的插入与删除
43、操作只发生在表尾可以发生在表头吗？可以发生在表头吗？可以发生在表头吗？可以发生在表头吗？typedeftypedef intint stackElementTstackElementT; ;typedeftypedef List * List *stackADTstackADT; ;可以，但需要元素移动操作可以，但需要元素移动操作可以，但需要元素移动操作可以，但需要元素移动操作22安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础栈的创生与释放intint NewStackNewStack( ( stackADTstackADT stack stack ) ) if(
44、 if( CreateCreate( (stackstack) ) return 1;) ) return 1; return 0; return 0; void void FreeStackFreeStack( ( stackADTstackADT stackstack ) ) DeleteAllDeleteAll( ( stack stack ); ); 23安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础入栈intint PushPush( ( stackADTstackADT stackstack, , stackElementTstackElementT
45、element element ) ) if( ! if( !StackIsEmptyStackIsEmpty( (stackstack) ) ) if( ! if( !InsertAfterInsertAfter( (stackstack, , stackstack lengthlength 1, 1, elementelement) ) ) return 0; return 0; return 1; return 1; else else if( ! if( !InsertAfterInsertAfter( (stackstack, 0, , 0, elementelement) ) re
46、turn 0;) ) return 0; return 1; return 1; 24安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础出栈intint PopPop( ( stackADTstackADT stackstack, , stackElementTstackElementT * *element element ) ) if( ! if( !StackIsEmptyStackIsEmpty( (stackstack) ) ) if( ! if( !GetElementGetElement(*(*stackstack, , stackstack lengt
47、hlength 1, 1, elementelement) ) ) ) return 0; return 0; if( ! if( !DeleteElementDeleteElement( (stackstack, , stackstack lengthlength 1) )1) ) return 0; return 0; return 1; return 1; return 0; return 0; 25安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础其他辅助栈函数intint StackIsEmptyStackIsEmpty( ( stackADTstackAD
48、T stackstack ) ) return return IsEmptyIsEmpty( *( *stack stack ); ); intint StackIsFullStackIsFull( ( stackADTstackADT stackstack ) ) return return IsFullIsFull( *( *stack stack ); ); intint StackDepthStackDepth( ( stackADTstackADT stackstack, , intint * *depth depth ) ) return return GetLengthGetLe
49、ngth( *( *stackstack, , depthdepth ); ); 26安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础后缀表达式中缀表达式中缀表达式定义：操作符位于操作数之间的算术表达式定义：操作符位于操作数之间的算术表达式定义：操作符位于操作数之间的算术表达式定义：操作符位于操作数之间的算术表达式示例：示例：示例：示例：1 + 2 31 + 2 3后缀表达式后缀表达式定义：操作符位于操作数之后的算术表达式定义：操作符位于操作数之后的算术表达式定义：操作符位于操作数之后的算术表达式定义：操作符位于操作数之后的算术表达式示例：示例：示例：示例：1 2
50、+ 3 1 2 + 3 27安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础栈应用使用栈编写一个简单的整数计算器，具有加使用栈编写一个简单的整数计算器，具有加减乘除和幂运算功能减乘除和幂运算功能 ，输入，输入“ “q”q”表示结束表示结束intint GetTwoOperandsGetTwoOperands( ( stackADTstackADT stackstack, , intint * *op1op1, , intint * *op2 op2 ); );void void ComputeCompute( ( stackADTstackADT stackstac
51、k, char , char op op ); );void void RunRun();();void void mainmain() () clrscrclrscr();(); RunRun();(); 算法要点：输入字符，若不是算法要点：输入字符，若不是算法要点：输入字符，若不是算法要点：输入字符，若不是+ +、 、* *、/ /、 则则则则进栈，否则从栈中依次弹出两个操作数，运算后进栈，否则从栈中依次弹出两个操作数，运算后进栈，否则从栈中依次弹出两个操作数，运算后进栈，否则从栈中依次弹出两个操作数，运算后再将结果压栈，重复上述过程，直到输入字符再将结果压栈，重复上述过程，直到输入字符再
52、将结果压栈，重复上述过程，直到输入字符再将结果压栈，重复上述过程，直到输入字符“ “q”q” RunRun() ()函数负责栈的创建与删除，并负责将操作函数负责栈的创建与删除，并负责将操作函数负责栈的创建与删除，并负责将操作函数负责栈的创建与删除，并负责将操作数存入栈中，如果其为运算符，则启动计算函数数存入栈中，如果其为运算符，则启动计算函数数存入栈中，如果其为运算符，则启动计算函数数存入栈中，如果其为运算符，则启动计算函数ComputeCompute() ()，该函数先调用该函数先调用该函数先调用该函数先调用GetTwoOperandsGetTwoOperands() ()从栈中获得从栈中获
53、得从栈中获得从栈中获得相关操作数，然后根据相关操作数，然后根据相关操作数，然后根据相关操作数，然后根据RunRun() ()函数传入的运算符函数传入的运算符函数传入的运算符函数传入的运算符计算，并将结果作为新操作数入栈计算，并将结果作为新操作数入栈计算，并将结果作为新操作数入栈计算，并将结果作为新操作数入栈28安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础栈应用void void RunRun() () char char c c20; 20; stackADTstackADT calccalc; ; if( if( NewStackNewStack( (calc
54、calc) ) ) while( while( getsgets( (c c), ), c c0 != q )0 != q ) switch( switch( c c0 )0 ) case : case : /* /* 如果是负数，压栈，否则计算如果是负数，压栈，否则计算如果是负数，压栈，否则计算如果是负数，压栈，否则计算 */ */ if(if(strlenstrlen( (c c) 1) ) 1) PushPush( (calccalc, , atoiatoi( (c c); else ); else ComputeCompute( (calccalc, , c c0); break;0)
55、; break; case /: case +: case *: case : case /: case +: case *: case : ComputeCompute( ( calccalc, , c c0 ); break;0 ); break; default: default: PushPush( ( calccalc, , atoiatoi( (c c) ); break; ) ); break; FreeStackFreeStack( ( calccalc ); ); 29安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础栈应用void void Com
56、puteCompute( ( stackADTstackADT stackstack, char , char opop ) ) intint resultresult, , operand1operand1, , operand2operand2; ; if( if( GetTwoOperandsGetTwoOperands( (stackstack, &, &operand1operand1, &, &operand2operand2) ) ) switch( switch(opop) ) case +: case +: result result = = operand2 operand
57、2 + + operand1operand1; break; break; case : case : resultresult = = operand2operand2 operand1operand1; break; ; break; case *: case *: result result = = operand2 operand2 * * operand1operand1; break; break; case : case : resultresult = = powpow( ( operand2operand2, , operand1 operand1 ); break;); b
58、reak; case /:case /: if( if( operand1 operand1 = 0 ) = 0 ) printfprintf(“Divide(“Divide by zero! by zero!n n“); break; “); break; else else result result = = operand2 operand2 / / operand1operand1; ; break; break; if( if( PushPush( (stackstack, , resultresult) ) ) ) printfprintf(“=%(“=%d d n n“, “,
59、resultresult); ); 30安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础栈应用intint GetTwoOperandsGetTwoOperands( ( stackADTstackADT stackstack, , intint * *op1op1, , intint * *op2op2 ) ) if( if( StackIsEmptyStackIsEmpty( (stackstack) ) ) printfprintf(“Missing(“Missing operand! operand!n n“); return 0;“); return 0;
60、 if( if( PopPop( (stackstack, , op1op1) ) ) if( if( StackIsEmptyStackIsEmpty( (stackstack) ) ) printfprintf(“Missing(“Missing operand! operand!n n“); return 0;“); return 0; if( if( PopPop( (stackstack, , op2op2) ) return 1; ) ) return 1; return 0; return 0; 31安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础计算
61、器运行时栈状态变化输入输入输入输入栈动作栈动作栈动作栈动作栈状态栈状态栈状态栈状态结果显示结果显示结果显示结果显示初始状态初始状态初始状态初始状态无无无无() ()无无无无1010PushPush(10)(10)(10)(10)无无无无2020PushPush(20)(20)(20, 10)(20, 10)无无无无3030PushPush(30)(30)(30, 20, 10)(30, 20, 10)无无无无+ +PopPop() ()(20, 10)(20, 10)无无无无PopPop() ()(10)(10)无无无无PushPush(20+30)(20+30)(50, 10)(50, 10
62、)5050 PopPop() ()(10)(10)无无无无PopPop() ()() ()无无无无PushPush(1050)(1050)( ( 40)40) 404032安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础程序文件的组织主函数文件主函数文件主函数与计算器辅助函数原型与实现：主函数与计算器辅助函数原型与实现：主函数与计算器辅助函数原型与实现：主函数与计算器辅助函数原型与实现：main.cmain.cmain.cmain.c抽象栈库抽象栈库函数原型：函数原型：函数原型：函数原型：stack.hstack.hstack.hstack.h函数实现：函数实现：函
63、数实现：函数实现：stack.cstack.cstack.cstack.c抽象线性表库抽象线性表库函数原型与数据类型定义：函数原型与数据类型定义：函数原型与数据类型定义：函数原型与数据类型定义：list.hlist.hlist.hlist.h函数实现：函数实现：函数实现：函数实现：list.clist.clist.clist.c33安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.4 队列队列定义队列定义满足先进先出访问规则的数据集满足先进先出访问规则的数据集满足先进先出访问规则的数据集满足先进先出访问规则的数据集队列操作集队列操作集创建新队列创建新队列创建新队
64、列创建新队列入队；出队入队；出队入队；出队入队；出队清空队列清空队列清空队列清空队列判断队列是否为空；判断队列是否为满判断队列是否为空；判断队列是否为满判断队列是否为空；判断队列是否为满判断队列是否为空；判断队列是否为满求队列的长度求队列的长度求队列的长度求队列的长度遍历队列遍历队列遍历队列遍历队列34安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础队列操作intint NewQueueNewQueue( ( queueADTqueueADT queue queue ); );void void FreeQueueFreeQueue( ( queueADTqueue
65、ADT queuequeue ); );intint EnqueueEnqueue( ( queueADTqueueADT queuequeue, , queueElementTqueueElementT element element ); );intint DequeueDequeue( ( queueADTqueueADT queuequeue, , queueElementTqueueElementT * *elementelement ); );intint QueueIsEmptyQueueIsEmpty( ( queueADTqueueADT queuequeue ); );in
66、tint QueueIsFullQueueIsFull( ( queueADTqueueADT queuequeue ); );intint QueueLengthQueueLength( ( queueADTqueueADT queuequeue, , intint * *length length ); );void void TraverseQueueTraverseQueue( ( queueADTqueueADT queuequeue ); );35安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象队列的实现对线性表的再抽象：使用线性表实现队列对线性表的
67、再抽象：使用线性表实现队列元素的插入操作只发生在队尾元素的插入操作只发生在队尾元素的插入操作只发生在队尾元素的插入操作只发生在队尾元素的删除操作只发生在队首元素的删除操作只发生在队首元素的删除操作只发生在队首元素的删除操作只发生在队首typedeftypedef intint queueElementTqueueElementT; ;typedeftypedef List * List *queueADTqueueADT; ;36安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础队列的创生与释放intint NewQueueNewQueue( ( queueADTqu
68、eueADT queue queue ) ) if( if( CreateCreate( (queuequeue) ) return 1;) ) return 1; return 0; return 0; void void FreeQueueFreeQueue( ( queueADTqueueADT queuequeue ) ) DeleteAllDeleteAll( ( queue queue ); ); 37安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础入队intint EnqueueEnqueue( ( queueADTqueueADT queuequeu
69、e, , queueElementTqueueElementT element element ) ) if( ! if( !QueueIsEmptyQueueIsEmpty( (queuequeue) ) ) if( ! if( !InsertAfterInsertAfter( (queuequeue, , queuequeue lengthlength 1, 1, elementelement) ) ) ) return 0; return 0; return 1; return 1; else else if( ! if( !InsertAfterInsertAfter( (queueq
70、ueue, 0, , 0, elementelement) ) return 0;) ) return 0; return 1; return 1; 38安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础出队intint DequeueDequeue( ( queueADTqueueADT queuequeue, , queueElementTqueueElementT * *element element ) ) if( ! if( !QueueIsEmptyQueueIsEmpty( (queuequeue) ) ) if( ! if( !GetElementGe
71、tElement(*(*queuequeue, 0, , 0, elementelement) ) ) return 0; return 0; if( ! if( !DeleteElementDeleteElement( (queuequeue, 0) ), 0) ) return 0; return 0; return 1; return 1; return 0; return 0; 39安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础遍历队列void void TraverseQueueTraverseQueue( ( queueADTqueueADT queu
72、e queue ) ) queueElementTqueueElementT elementelement; ; intint i i, , lenlen; ; if( if( QueueIsEmptyQueueIsEmpty( (queuequeue) ) ) printfprintf(“Empty!(“Empty!n n“); return;“); return; QueueLengthQueueLength( ( queuequeue, &, &lenlen ); ); for( for( i i = 0; = 0; i i lenlen; ; i i+)+) GetElementGet
73、Element( *( *queuequeue, , i i, &, &element element ); ); printfprintf( “%( “%d d n n“, “, element element ); ); 40安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础其他辅助队列函数intint QueueIsEmptyQueueIsEmpty( ( queueADTqueueADT queuequeue ) ) return return IsEmptyIsEmpty( *( *queue queue ); ); intint QueueIsFullQu
74、eueIsFull( ( queueADTqueueADT queuequeue ) ) return return IsFullIsFull( *( *queue queue ); ); intint QueuelengthQueuelength( ( queueADTqueueADT queuequeue, , intint * *length length ) ) return return GetLengthGetLength( *( *queuequeue, , lengthlength ); ); 41安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础队列
75、应用实现一个简单进度表实现一个简单进度表实现一个简单进度表实现一个简单进度表 用户可以为某个项目产生一个进度表，对于进度表中各用户可以为某个项目产生一个进度表，对于进度表中各用户可以为某个项目产生一个进度表，对于进度表中各用户可以为某个项目产生一个进度表，对于进度表中各个进度安排以字符串形式表达，已经执行完的进度在进个进度安排以字符串形式表达，已经执行完的进度在进个进度安排以字符串形式表达，已经执行完的进度在进个进度安排以字符串形式表达，已经执行完的进度在进度表中删除，新进度安排在进度表尾，当然可以浏览当度表中删除，新进度安排在进度表尾，当然可以浏览当度表中删除，新进度安排在进度表尾，当然可以
76、浏览当度表中删除，新进度安排在进度表尾，当然可以浏览当前所有未执行的进度前所有未执行的进度前所有未执行的进度前所有未执行的进度实现策略实现策略实现策略实现策略 数据结构使用队列，队头的进度首先得到执行并从队列数据结构使用队列，队头的进度首先得到执行并从队列数据结构使用队列，队头的进度首先得到执行并从队列数据结构使用队列，队头的进度首先得到执行并从队列中删除，队尾是新加入的进度中删除，队尾是新加入的进度中删除，队尾是新加入的进度中删除，队尾是新加入的进度 进度信息为字符串，可以使用定长字符数组实现，不过进度信息为字符串，可以使用定长字符数组实现，不过进度信息为字符串，可以使用定长字符数组实现，不
77、过进度信息为字符串，可以使用定长字符数组实现，不过这容易导致存储空间的浪费，也可能因数组越界而使系这容易导致存储空间的浪费，也可能因数组越界而使系这容易导致存储空间的浪费，也可能因数组越界而使系这容易导致存储空间的浪费，也可能因数组越界而使系统运行出现异常统运行出现异常统运行出现异常统运行出现异常 使用字符指针队列更好，字符串资源由系统运行时动态使用字符指针队列更好，字符串资源由系统运行时动态使用字符指针队列更好，字符串资源由系统运行时动态使用字符指针队列更好，字符串资源由系统运行时动态分配分配分配分配42安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础队列应用#i
78、nclude #include #include #include #include #include #include #include #include “queue.h“#include “queue.h“void void EnterEnter( ( queueADTqueueADT myqueuemyqueue ); );void void RemoveRemove( ( queueADTqueueADT myqueuemyqueue ); );void void ReviewReview( ( queueADTqueueADT myqueuemyqueue ); );43安徽大学计
79、算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础队列应用void void mainmain()() char char s s81; 81; queueADTqueueADT myqueuemyqueue; ; NewQueueNewQueue( ( myqueuemyqueue ); ); clrscrclrscr();(); for(;) for(;) printf(“E-Enterprintf(“E-Entern nR-RemoveR-Removen nV-reViewV-reViewn nQ-Q-QuitQuitn n“);“); gets( gets(s s);
80、); switch(* switch(*s s) ) case E: case e: case E: case e: EnterEnter( ( myqueuemyqueue ); break;); break; case R: case r: case R: case r: RemoveRemove( ( myqueuemyqueue ); break;); break; case V: case v: case V: case v: ReviewReview( ( myqueuemyqueue ); break;); break; case Q: case q: case Q: case
81、q: FreeQueueFreeQueue( ( myqueuemyqueue ); return; ); return; 44安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础队列应用void void EnterEnter( ( queueADTqueueADT myqueuemyqueue ) ) char char temptemp81, *81, *pTemppTemp; ; if( if( QueueIsFullQueueIsFull( (myqueuemyqueue) ) ) printfprintf(“Full!(“Full!n n“);“); ret
82、urn; return; printfprintf(“Input(“Input event : “); event : “); gets( gets(temptemp); ); pTemppTemp = ( char * ) = ( char * )mallocmalloc( ( strlenstrlen( (temptemp) + 1 );) + 1 ); strcpystrcpy( ( pTemppTemp, , temp temp ); ); EnqueueEnqueue( ( myqueuemyqueue, , pTemppTemp ); ); 45安徽大学计算机教学部安徽大学计算机教
83、学部计计算算机机程程序序设设计计基基础础队列应用void void RemoveRemove( ( queueADTqueueADT myqueuemyqueue ) ) char * char *pTemppTemp; ; if( if( QueueIsEmptyQueueIsEmpty( (myqueuemyqueue) ) ) printfprintf(“No(“No event! event!n n“); return;“); return; DequeueDequeue( ( myqueuemyqueue, &, &pTemppTemp ); ); printfprintf(“%(“
84、%s s n n“, “, pTemppTemp ); ); freefree( ( pTemppTemp ); ); void void ReviewReview( ( queueADTqueueADT myqueuemyqueue ) ) TraverseQueueTraverseQueue( ( myqueuemyqueue ); ); 46安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础程序文件的组织主函数文件主函数文件主函数与队列应用函数原型与实现：主函数与队列应用函数原型与实现：主函数与队列应用函数原型与实现：主函数与队列应用函数原型与实现：main.c
85、main.cmain.cmain.c抽象队列库抽象队列库函数原型：函数原型：函数原型：函数原型：queue.hqueue.hqueue.hqueue.h函数实现：函数实现：函数实现：函数实现：queue.cqueue.cqueue.cqueue.c抽象线性表库抽象线性表库函数原型与数据类型定义：函数原型与数据类型定义：函数原型与数据类型定义：函数原型与数据类型定义：list.hlist.hlist.hlist.h函数实现：函数实现：函数实现：函数实现：list.clist.clist.clist.c47安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.5 符号表
86、非线性数据结构非线性数据结构线性数据结构的四个基本条件至少有一个不满足线性数据结构的四个基本条件至少有一个不满足线性数据结构的四个基本条件至少有一个不满足线性数据结构的四个基本条件至少有一个不满足符号表定义符号表定义可以通过特定关键字查找其对应意义的数据结构可以通过特定关键字查找其对应意义的数据结构可以通过特定关键字查找其对应意义的数据结构可以通过特定关键字查找其对应意义的数据结构概念上与字典类似概念上与字典类似概念上与字典类似概念上与字典类似实现上每个元素具有键（关键字）和对应值实现上每个元素具有键（关键字）和对应值实现上每个元素具有键（关键字）和对应值实现上每个元素具有键（关键字）和对应值
87、符号表的目的符号表的目的提高查找效率，在常数时间内完成数据查找任务提高查找效率，在常数时间内完成数据查找任务提高查找效率，在常数时间内完成数据查找任务提高查找效率，在常数时间内完成数据查找任务48安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象符号表接口设计/* /* symtbl.hsymtbl.h: : 抽象符号表头文件抽象符号表头文件抽象符号表头文件抽象符号表头文件 */ */* /* PSYMBOLTABLEPSYMBOLTABLE为抽象符号表指针类型为抽象符号表指针类型为抽象符号表指针类型为抽象符号表指针类型 */ */* /* 符号表类型符号表类型符
88、号表类型符号表类型SYMBOLTABLESYMBOLTABLE的具体实现隐藏于源文件中的具体实现隐藏于源文件中的具体实现隐藏于源文件中的具体实现隐藏于源文件中 */ */typedeftypedef structstruct SYMBOLTABLE* PSYMBOLTABLE; SYMBOLTABLE* PSYMBOLTABLE;/* /* CreateSymTblCreateSymTbl：符号表构造函数符号表构造函数符号表构造函数符号表构造函数 */ */* /* 返回值：指向所构造的匿名抽象符号表数据对象的指针返回值：指向所构造的匿名抽象符号表数据对象的指针返回值：指向所构造的匿名抽象符号
89、表数据对象的指针返回值：指向所构造的匿名抽象符号表数据对象的指针 */ */PSYMBOLTABLE PSYMBOLTABLE CreateSymTblCreateSymTbl();();/* /* DestroySymTblDestroySymTbl：符号表析构函数符号表析构函数符号表析构函数符号表析构函数 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针 */ */void void DestroySymTblDestroySymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p
90、p ); );49安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象符号表接口设计/* /* GetCountOfSymTblGetCountOfSymTbl：获取符号表中存储的元素个数获取符号表中存储的元素个数获取符号表中存储的元素个数获取符号表中存储的元素个数 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针 */ */* /* 返回值：元素个数，类型为返回值：元素个数，类型为返回值：元素个数，类型为返回值：元素个数，类型为unsigned unsigned intin
91、t */ */unsigned unsigned intint GetCountOfSymTblGetCountOfSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ); );/* /* InsertIntoSymTblInsertIntoSymTbl：将元素插入到符号表中将元素插入到符号表中将元素插入到符号表中将元素插入到符号表中 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针 */ */* /* keykey：待插入元素的键信息，类型未知待插入元素的键信息，类型未知待
92、插入元素的键信息，类型未知待插入元素的键信息，类型未知 */ */* /* valuevalue：待插入元素的值信息，类型未知待插入元素的值信息，类型未知待插入元素的值信息，类型未知待插入元素的值信息，类型未知 */ */* /* 返回值：无返回值：无返回值：无返回值：无 */ */void void InsertIntoSymTblInsertIntoSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, ? , ? keykey, ? , ? valuevalue ); );50安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象符号表
93、接口设计/* /* DeleteFromSymTblDeleteFromSymTbl：从符号表中删除特定元素从符号表中删除特定元素从符号表中删除特定元素从符号表中删除特定元素 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针 */ */* /* keykey：待删除元素的键信息，类型未知待删除元素的键信息，类型未知待删除元素的键信息，类型未知待删除元素的键信息，类型未知 */ */* /* 返回值：无返回值：无返回值：无返回值：无 */ */void void DeleteFromSymTblDelet
94、eFromSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, ? , ? keykey ); );/* /* SearchInSymTblSearchInSymTbl：在符号表中查找指定元素在符号表中查找指定元素在符号表中查找指定元素在符号表中查找指定元素 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针 */ */* /* keykey：待查找元素的键信息，类型未知待查找元素的键信息，类型未知待查找元素的键信息，类型未知待查找元素的键信息，类型未知 */ */* /* 返
95、回值：待查找元素的值信息，类型未知返回值：待查找元素的值信息，类型未知返回值：待查找元素的值信息，类型未知返回值：待查找元素的值信息，类型未知 */ */? ? SearchInSymTblSearchInSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, ? , ? keykey ); );51安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象符号表接口设计/* /* ClearSymTblClearSymTbl：清空符号表清空符号表清空符号表清空符号表 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象
96、的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针 */ */* /* 返回值：无返回值：无返回值：无返回值：无 */ */void void ClearSymTblClearSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ); );/* /* TraverseSymTblTraverseSymTbl：遍历符号表，依次访问其中全部元素遍历符号表，依次访问其中全部元素遍历符号表，依次访问其中全部元素遍历符号表，依次访问其中全部元素 */ */* /* p p：指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符号表数据对象的指针指向抽象符
97、号表数据对象的指针 */ */* /* 返回值：无返回值：无返回值：无返回值：无 */ */void void TraverseSymTblTraverseSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ); );52安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础确定键与值的类型键的类型：与问题域有关键的类型：与问题域有关字符串的存储、查找与匹配字符串的存储、查找与匹配字符串的存储、查找与匹配字符串的存储、查找与匹配整数的存储、查找与匹配整数的存储、查找与匹配整数的存储、查找与匹配整数的存储、查找与匹配值的类型：如何保证通用？值的类
98、型：如何保证通用？使用无型指针类型使用无型指针类型使用无型指针类型使用无型指针类型无定义值的处理无定义值的处理void*void* UNDEFINEDVALUE UNDEFINEDVALUE = (void*)(&= (void*)(& UNDEFINEDVALUEUNDEFINEDVALUE); );为什么不使用为什么不使用为什么不使用为什么不使用NULLNULL？53安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象符号表接口定义/* /* SymTbl.hSymTbl.h: : 抽象符号表头文件抽象符号表头文件抽象符号表头文件抽象符号表头文件 */ */#
99、#ifndefifndef _SYMTBL_H_SYMTBL_H#define #define _SYMTBL_H_SYMTBL_Hextern void* extern void* UNDEFINEDVALUEUNDEFINEDVALUE; ;typedeftypedef structstruct SYMBOLTABLE* PSYMBOLTABLE; SYMBOLTABLE* PSYMBOLTABLE;PSYMBOLTABLE PSYMBOLTABLE CreateSymTblCreateSymTbl();();void void DestroySymTblDestroySymTbl( PS
100、YMBOLTABLE ( PSYMBOLTABLE p p ); );unsigned unsigned intint GetCountOfSymTblGetCountOfSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ); );void void InsertIntoSymTblInsertIntoSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, , intint keykey, void* , void* valuevalue ); );void void DeleteFromSymTblDeleteFromSymTbl( P
101、SYMBOLTABLE ( PSYMBOLTABLE p p, , intint keykey ); );void* void* SearchInSymTblSearchInSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, , intint keykey ); );void void ClearSymTblClearSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ); );void void TraverseSymTblTraverseSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ); );# #
102、endifendif54安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.6 哈希表哈希造表哈希造表目的：获得常数时间复杂度的查找效率目的：获得常数时间复杂度的查找效率目的：获得常数时间复杂度的查找效率目的：获得常数时间复杂度的查找效率关键技术：将关键字与存储地址对应起来关键技术：将关键字与存储地址对应起来关键技术：将关键字与存储地址对应起来关键技术：将关键字与存储地址对应起来 最好情况下，查找或插入只需要一次访问最好情况下，查找或插入只需要一次访问最好情况下，查找或插入只需要一次访问最好情况下，查找或插入只需要一次访问哈希函数：元素的散列哈希函数：元素的散列定
103、义：设计关系定义：设计关系定义：设计关系定义：设计关系f f，使关键字使关键字使关键字使关键字k k与地址与地址与地址与地址f f( (k k) )对应对应对应对应好处：若存在关键字好处：若存在关键字好处：若存在关键字好处：若存在关键字k k，则必定位于则必定位于则必定位于则必定位于f f( (k k) )处，无需处，无需处，无需处，无需比较即可获得该数据比较即可获得该数据比较即可获得该数据比较即可获得该数据55安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础哈希函数示例整数集整数集整数集整数集A A：包含包含包含包含1010个元素个元素个元素个元素90999099
104、使用数组使用数组使用数组使用数组遍历数组遍历数组遍历数组遍历数组1010次次次次5 5次次次次调用哈希函数计算其地址调用哈希函数计算其地址调用哈希函数计算其地址调用哈希函数计算其地址0 0次，直接从该地址处取数次，直接从该地址处取数次，直接从该地址处取数次，直接从该地址处取数 如何保存这如何保存这如何保存这如何保存这1010个元素？个元素？个元素？个元素？ 如何查找元素如何查找元素如何查找元素如何查找元素9999？ 几次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？ 查找任意一个元素，平均需要几次比较操作？查找任意一个元素，平均需要几次比较
105、操作？查找任意一个元素，平均需要几次比较操作？查找任意一个元素，平均需要几次比较操作？使用哈希表存储整数集使用哈希表存储整数集使用哈希表存储整数集使用哈希表存储整数集 哈希函数：哈希函数：哈希函数：哈希函数：f f( (x x) = ) = x x % 10 % 10 散列结果：每个元素位于不同地址处散列结果：每个元素位于不同地址处散列结果：每个元素位于不同地址处散列结果：每个元素位于不同地址处 如何查找元素如何查找元素如何查找元素如何查找元素9999？ 几次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？56安徽大学计算机教学部安徽大学计算
106、机教学部计计算算机机程程序序设设计计基基础础哈希函数示例整数集整数集整数集整数集B B：包含包含包含包含1212个元素个元素个元素个元素88998899使用数组使用数组使用数组使用数组遍历数组遍历数组遍历数组遍历数组1212次次次次6 6次次次次调用哈希函数计算其地址调用哈希函数计算其地址调用哈希函数计算其地址调用哈希函数计算其地址0 0次，直接从该地址处取数次，直接从该地址处取数次，直接从该地址处取数次，直接从该地址处取数 如何保存这如何保存这如何保存这如何保存这1212个元素？个元素？个元素？个元素？ 如何查找元素如何查找元素如何查找元素如何查找元素9999？ 几次比较操作才能获得结果？几
107、次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？ 查找任意一个元素，平均需要几次比较操作？查找任意一个元素，平均需要几次比较操作？查找任意一个元素，平均需要几次比较操作？查找任意一个元素，平均需要几次比较操作？使用哈希表存储整数集使用哈希表存储整数集使用哈希表存储整数集使用哈希表存储整数集 哈希函数：哈希函数：哈希函数：哈希函数：f f( (x x) = ) = x x % 10 % 10 散列结果：大部分元素位于不同地址处散列结果：大部分元素位于不同地址处散列结果：大部分元素位于不同地址处散列结果：大部分元素位于不同地址处 如何查找元素如何查找元素如何查找元素如何
108、查找元素9999？ 几次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？几次比较操作才能获得结果？57安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础哈希地址冲突哈希地址冲突现象哈希地址冲突现象不同键经哈希函数映射后，得到同一哈希地址不同键经哈希函数映射后，得到同一哈希地址不同键经哈希函数映射后，得到同一哈希地址不同键经哈希函数映射后，得到同一哈希地址数学描述：虽然数学描述：虽然数学描述：虽然数学描述：虽然 k k1 1 k k2 2，但但但但 f f( (k k1 1) = ) = f f( (k k2 2) ) 例：整数集例：整数集例：
109、整数集例：整数集B B，哈希函数哈希函数哈希函数哈希函数 f f( (x x) = ) = x x % 10 % 10解决方法：每个元素位于不同地址处解决方法：每个元素位于不同地址处更换哈希函数：更换哈希函数：更换哈希函数：更换哈希函数： f f( (x x) = ) = x x 88 88效果：冲突只能尽可能减少，而不能完全避免效果：冲突只能尽可能减少，而不能完全避免效果：冲突只能尽可能减少，而不能完全避免效果：冲突只能尽可能减少，而不能完全避免58安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础链地址法桶桶 + + 线性链表线性链表59安徽大学计算机教学部安徽大
110、学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表的内部数据结构/* /* symtbl.csymtbl.c：抽象符号表源文件，内部数据结构抽象符号表源文件，内部数据结构抽象符号表源文件，内部数据结构抽象符号表源文件，内部数据结构 */ */* /* 在源文件内部实现这些数据结构，外部不可访问，保证数据在源文件内部实现这些数据结构，外部不可访问，保证数据在源文件内部实现这些数据结构，外部不可访问，保证数据在源文件内部实现这些数据结构，外部不可访问，保证数据结构与信息的封装性结构与信息的封装性结构与信息的封装性结构与信息的封装性 */ */* /* 抽象结点类型，抽象结点类型，抽象结点
111、类型，抽象结点类型，PNODEPNODE为指向结点类型的指针类型为指向结点类型的指针类型为指向结点类型的指针类型为指向结点类型的指针类型 */ */typedeftypedef structstruct NODE* PNODE; NODE* PNODE;/* /* 结点类型；包含了元素信息结点类型；包含了元素信息结点类型；包含了元素信息结点类型；包含了元素信息keykey、valuevalue以及构造链表所需要以及构造链表所需要以及构造链表所需要以及构造链表所需要的链接信息的链接信息的链接信息的链接信息nextnext */ */structstruct NODE NODE intint ke
112、ykey; void* ; void* valuevalue; PNODE ; PNODE nextnext; ; ;/* /* 符号表数据类型；符号表数据类型；符号表数据类型；符号表数据类型；countcount：符号表当前所保存的元素数目；符号表当前所保存的元素数目；符号表当前所保存的元素数目；符号表当前所保存的元素数目；primeprime：符号表当前的桶数，此值一般为质数；符号表当前的桶数，此值一般为质数；符号表当前的桶数，此值一般为质数；符号表当前的桶数，此值一般为质数；bucketsbuckets：符符符符号表的桶数组，因为需要动态确定桶数，所以使用指针而不号表的桶数组，因为需要动
113、态确定桶数，所以使用指针而不号表的桶数组，因为需要动态确定桶数，所以使用指针而不号表的桶数组，因为需要动态确定桶数，所以使用指针而不是数组是数组是数组是数组 */ */structstruct SYMBOLTABLE unsigned SYMBOLTABLE unsigned intint countcount; unsigned ; unsigned intint primeprime; PNODE* ; PNODE* bucketsbuckets; ; ;60安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* symtbl.csymtbl.
114、c：抽象符号表的源文件抽象符号表的源文件抽象符号表的源文件抽象符号表的源文件 */ */# #ifndefifndef _SYMTBL_H_SYMTBL_H_#include .#include .SymTbl.hSymTbl.h # #endifendif#include #include #include #include #include #include typedeftypedef structstruct NODE* PNODE; NODE* PNODE;structstruct NODE NODE intint keykey; void* ; void* valuevalue;
115、PNODE ; PNODE nextnext; ; ;structstruct SYMBOLTABLE SYMBOLTABLE unsigned unsigned intint count; count; unsigned unsigned intint prime; prime; PNODE* buckets; PNODE* buckets; ;61安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* 内部函数；仅在当前源文件中使用，外部不可见内部函数；仅在当前源文件中使用，外部不可见内部函数；仅在当前源文件中使用，外部不可见内部函数；仅在当前
116、源文件中使用，外部不可见 */ */* /* HashHash：杂凑函数，将特定的键散列到哈希表的某个桶中杂凑函数，将特定的键散列到哈希表的某个桶中杂凑函数，将特定的键散列到哈希表的某个桶中杂凑函数，将特定的键散列到哈希表的某个桶中 */ */* /* keykey：键键键键 */ */* /* primeprime：哈希表的桶数哈希表的桶数哈希表的桶数哈希表的桶数 */ */* /* 返回值：桶号，即散列后的地址返回值：桶号，即散列后的地址返回值：桶号，即散列后的地址返回值：桶号，即散列后的地址 */ */static unsigned static unsigned intint Hash
117、Hash( ( intint keykey, unsigned , unsigned intint primeprime ) ) return (unsigned return (unsigned int)int)keykey % % primeprime; ; 62安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* FreeBucketFreeBucket：释放桶中的所有元素释放桶中的所有元素释放桶中的所有元素释放桶中的所有元素 */ */* /* u u：指向指定桶第一个结点的指针指向指定桶第一个结点的指针指向指定桶第一个结点的指针指向指定
118、桶第一个结点的指针 */ */* /* 返回值：被删除的结点数目返回值：被删除的结点数目返回值：被删除的结点数目返回值：被删除的结点数目 */ */static unsigned static unsigned intint FreeBucketFreeBucket( PNODE ( PNODE u u ) ) unsigned unsigned intint n n = 0; = 0; PNODE PNODE t t; ; while( while( u u != != NULLNULL ) ) t t = = u u; ; u u = = u u nextnext; ; freefree(
119、 ( t t ); ); + +n n; ; return return n n; ; 63安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* FindNodeFindNode：在特定的桶中查找指定元素在特定的桶中查找指定元素在特定的桶中查找指定元素在特定的桶中查找指定元素 */ */* /* u u：指向某个桶第一个结点的指针指向某个桶第一个结点的指针指向某个桶第一个结点的指针指向某个桶第一个结点的指针 */ */* /* keykey：待查找的键待查找的键待查找的键待查找的键 */ */* /* 返回值：与待查找键匹配的结点指针；若不存在，
120、则返回返回值：与待查找键匹配的结点指针；若不存在，则返回返回值：与待查找键匹配的结点指针；若不存在，则返回返回值：与待查找键匹配的结点指针；若不存在，则返回NULLNULL */ */static PNODE static PNODE FindNodeFindNode( PNODE ( PNODE u u, , intint keykey ) ) if( if( u u = = NULLNULL ) return ) return NULLNULL; ; while( while( u u != != NULLNULL & & u u keykey != != keykey ) ) u u =
121、 = u u nextnext; ; return return u u; ; 64安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* 接口函数的实现接口函数的实现接口函数的实现接口函数的实现 */ */* /* CreateSymTblCreateSymTbl：符号表构造函数符号表构造函数符号表构造函数符号表构造函数 */ */PSYMBOLTABLE PSYMBOLTABLE CreateSymTblCreateSymTbl( unsigned ( unsigned intint primeprime ) ) unsigned unsign
122、ed intint i i; ; PSYMBOLTABLE PSYMBOLTABLE p p; ; /* /* 为匿名符号表数据对象分配存储空间，为匿名符号表数据对象分配存储空间，为匿名符号表数据对象分配存储空间，为匿名符号表数据对象分配存储空间，p p指向该对象指向该对象指向该对象指向该对象 */ */ p p = ( PSYMBOLTABLE ) = ( PSYMBOLTABLE )mallocmalloc( ( sizeof(structsizeof(struct SYMBOLTABLE) );SYMBOLTABLE) ); p p countcount = 0; = 0; p p pr
123、imeprime = = primeprime; ; /* /* 为各个桶指针分配空间，为各个桶指针分配空间，为各个桶指针分配空间，为各个桶指针分配空间，p p bucketsbuckets指向第一个桶指向第一个桶指向第一个桶指向第一个桶 */ */ p p bucketsbuckets = ( PNODE* ) = ( PNODE* )mallocmalloc( ( sizeof(PNODEsizeof(PNODE) * ) * primeprime ); ); for( for( i i = 0; = 0; i i bucketsbuckets i i = = NULLNULL; ; re
124、turn return p p; ; 65安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* DestroySymTblDestroySymTbl：符号表析构函数符号表析构函数符号表析构函数符号表析构函数 */ */void void DestroySymTblDestroySymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ) ) unsigned unsigned intint i i; ; /* /* 断言断言断言断言p p非空，非空，非空，非空，p p正常应为符号表指针正常应为符号表指针正常应为符号表指针正常
125、应为符号表指针 */ */ assertassert( ( p p != != NULLNULL ); ); /* /* 清空符号表中所有元素清空符号表中所有元素清空符号表中所有元素清空符号表中所有元素 */ */ ClearSymTblClearSymTbl( ( p p ); ); /* /* 释放全部桶对象释放全部桶对象释放全部桶对象释放全部桶对象 */ */ for( for( i i = 0; = 0; i i primeprime; +; +i i ) ) freefree( ( p p bucketsbuckets i i ); ); /* /* 释放匿名符号表对象并设为空，以确
126、保它不会指向已释放释放匿名符号表对象并设为空，以确保它不会指向已释放释放匿名符号表对象并设为空，以确保它不会指向已释放释放匿名符号表对象并设为空，以确保它不会指向已释放的内存区域的内存区域的内存区域的内存区域 */ */ freefree( ( p p ); ); p p = = NULLNULL; ; 66安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* InsertIntoSymTblInsertIntoSymTbl：将元素插入到符号表中将元素插入到符号表中将元素插入到符号表中将元素插入到符号表中 */ */void void Inser
127、tIntoSymTblInsertIntoSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, , intint keykey, void* , void* valuevalue ) ) unsigned unsigned intint n n; PNODE ; PNODE t t; ; assertassert( ( p p != != NULLNULL ); ); n n = = HashHash( ( keykey, , p p primeprime ); ); /* /* 杂凑，即将杂凑，即将杂凑，即将杂凑，即将keykey散列到桶散列到桶散列到桶散列到桶n
128、 n中中中中 */ */ t t = = FindNodeFindNode( ( p p bucketsbuckets n n, , keykey ); ); /* /* 在桶在桶在桶在桶n n中查找中查找中查找中查找keykey */ */ if( if( t t = = NULLNULL ) ) /* /* t t为空表示为空表示为空表示为空表示keykey不存在不存在不存在不存在 */ */ /* /* 构造新结点，插入到桶构造新结点，插入到桶构造新结点，插入到桶构造新结点，插入到桶n n链表的开头链表的开头链表的开头链表的开头 */ */ t t = ( PNODE ) = ( PNO
129、DE )mallocmalloc( ( sizeof(structsizeof(struct NODE) ); NODE) ); t t keykey = = keykey; ; t t nextnext = = p p bucketsbuckets n n; ; p p bucketsbuckets n n = = t t; ; + +p p countcount; ; t t valuevalue = = valuevalue; ; /* /* 设置设置设置设置t t的的的的valuevalue值值值值 */ */ 67安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基
130、基础础抽象哈希表实现/* /* DeleteFromSymTblDeleteFromSymTbl：从符号表中删除元素从符号表中删除元素从符号表中删除元素从符号表中删除元素 */ */void void DeleteFromSymTblDeleteFromSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p, , intint keykey ) ) unsigned unsigned intint n n; PNODE ; PNODE t t, , u u; ; assertassert( ( p p != != NULLNULL ); ); n n = = HashH
131、ash( ( keykey, , p p primeprime ); ); /* /* 杂凑，即将杂凑，即将杂凑，即将杂凑，即将keykey散列到桶散列到桶散列到桶散列到桶n n中中中中 */ */ t t = = FindNodeFindNode( ( p p bucketsbuckets n n, , keykey ); ); /* /* 在桶在桶在桶在桶n n中查找中查找中查找中查找keykey */ */ if( if( t t = = NULLNULL ) return; ) return; /* /* 查找查找查找查找t t之前的结点之前的结点之前的结点之前的结点u u，u u n
132、extnext与与与与t t指向同一个数据对象指向同一个数据对象指向同一个数据对象指向同一个数据对象 */ */ u u = = p p bucketsbuckets n n; ; if( if( u u = = t t ) ) p p bucketsbuckets n n = = t t nextnext; ; else while( else while( u u nextnext != != t t ) ) u u = = u u nextnext; ; u u nextnext = = t t nextnext; ; freefree( ( t t ); ); /* /* 删除删除删除
133、删除t t，之前应维持链表其他元素间关系不变之前应维持链表其他元素间关系不变之前应维持链表其他元素间关系不变之前应维持链表其他元素间关系不变 */ */ p p countcount; ; /* /* 递减元素个数值递减元素个数值递减元素个数值递减元素个数值 */ */ 68安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* ClearSymTblClearSymTbl：清空符号表清空符号表清空符号表清空符号表 */ */void void ClearSymTblClearSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE
134、p p ) ) unsigned unsigned intint i i; ; assertassert( ( p p != != NULLNULL ); ); /* /* 清除全部桶中的全部元素清除全部桶中的全部元素清除全部桶中的全部元素清除全部桶中的全部元素 */ */ for( for( i i = 0; = 0; i i primeprime; +; +i i ) ) /* /* 清除当前桶中的全部元素，并递减符号表中的元素个数清除当前桶中的全部元素，并递减符号表中的元素个数清除当前桶中的全部元素，并递减符号表中的元素个数清除当前桶中的全部元素，并递减符号表中的元素个数 */ */ p
135、 p countcount = = FreeBucketFreeBucket( ( p p bucketsbuckets i i ); ); p p bucketsbuckets i i = = NULLNULL; ; 69安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* SearchInSymTblSearchInSymTbl：在符号表中查找特定键在符号表中查找特定键在符号表中查找特定键在符号表中查找特定键 */ */void* void* SearchInSymTblSearchInSymTbl( PSYMBOLTABLE ( PSYMB
136、OLTABLE p p, , intint keykey ) ) unsigned unsigned intint n n; ; PNODE PNODE u u; ; assertassert( ( p p != != NULLNULL ); ); n n = = HashHash( ( keykey, , p p primeprime ); ); /* /* 杂凑，即将杂凑，即将杂凑，即将杂凑，即将keykey散列到桶散列到桶散列到桶散列到桶n n中中中中 */ */ u u = = FindNodeFindNode( ( p p bucketsbuckets n n, , keykey )
137、; ); /* /* 在桶在桶在桶在桶n n中查找中查找中查找中查找keykey */ */ /* /* 若若若若u u不为空，返回不为空，返回不为空，返回不为空，返回valuevalue域，否则域，否则域，否则域，否则UNDEFINEDVALUEUNDEFINEDVALUE */ */ if( if( u u != != NULLNULL ) ) return return u u valuevalue; ; else else return return UNDEFINEDVALUEUNDEFINEDVALUE; ; 70安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计
138、基基础础抽象哈希表实现/* /* TraverseSymTblTraverseSymTbl：遍历符号表遍历符号表遍历符号表遍历符号表 */ */void void TraverseSymTblTraverseSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ) ) unsigned unsigned intint i i; PNODE ; PNODE u u; ; assertassert( ( p p != != NULLNULL ); ); /* /* 对全部桶进行下述处理对全部桶进行下述处理对全部桶进行下述处理对全部桶进行下述处理 */ */ for( fo
139、r( i i = 0; = 0; i i primeprime; +; +i i ) ) u u = = p p bucketsbuckets i i; ; /* /* 对当前桶的所有结点进行下述处理对当前桶的所有结点进行下述处理对当前桶的所有结点进行下述处理对当前桶的所有结点进行下述处理 */ */ while( while( u u != != NULLNULL ) ) /* /* 输出当前结点的输出当前结点的输出当前结点的输出当前结点的keykey域与域与域与域与valuevalue域域域域 */ */ printfprintf( “%( “%d d, %, %d d n n“, “,
140、u u keykey, (, (int)int)u u valuevalue ); ); u u = = u u nextnext; ; 71安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表实现/* /* GetCountOfSymTblGetCountOfSymTbl：获取符号表的元素数目获取符号表的元素数目获取符号表的元素数目获取符号表的元素数目 */ */unsigned unsigned intint GetCountOfSymTblGetCountOfSymTbl( PSYMBOLTABLE ( PSYMBOLTABLE p p ) ) asse
141、rtassert( ( p p != != NULLNULL ); ); return return p p countcount; ; 72安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础哈希函数的设计设计原则：保证键尽可能均匀地散列设计原则：保证键尽可能均匀地散列设计原则：保证键尽可能均匀地散列设计原则：保证键尽可能均匀地散列static unsigned static unsigned intint HashHash( ( intint keykey, unsigned , unsigned intint primeprime ) ) return (unsi
142、gned return (unsigned int)int)keykey % % primeprime; ; 注意事项：哈希函数的设计非常困难，正确的哈希注意事项：哈希函数的设计非常困难，正确的哈希注意事项：哈希函数的设计非常困难，正确的哈希注意事项：哈希函数的设计非常困难，正确的哈希函数并一定有效函数并一定有效函数并一定有效函数并一定有效static unsigned static unsigned intint HashHash( ( intint keykey, unsigned , unsigned intint primeprime ) ) return 0; return 0; 7
143、3安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础负载因子与桶的数目负载因子负载因子链的平均长度链的平均长度链的平均长度链的平均长度 = = NN / / n n，NN为项数，为项数，为项数，为项数，n n为桶数为桶数为桶数为桶数与哈希表的查找效率有关，应使其尽可能小与哈希表的查找效率有关，应使其尽可能小与哈希表的查找效率有关，应使其尽可能小与哈希表的查找效率有关，应使其尽可能小合理选择桶的数目合理选择桶的数目与问题域的大小有关与问题域的大小有关与问题域的大小有关与问题域的大小有关一般为质数一般为质数一般为质数一般为质数桶数可以变化的哈希表桶数可以变化的哈希表桶数可
144、以变化的哈希表桶数可以变化的哈希表 增加桶数，降低负载因子（改变桶数时需要再散列）增加桶数，降低负载因子（改变桶数时需要再散列）增加桶数，降低负载因子（改变桶数时需要再散列）增加桶数，降低负载因子（改变桶数时需要再散列）74安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础13.7 哈希表的应用重重 集集定义：允许元素重复的集合定义：允许元素重复的集合定义：允许元素重复的集合定义：允许元素重复的集合应用场合：网络线路问题、单词频率统计问题应用场合：网络线路问题、单词频率统计问题应用场合：网络线路问题、单词频率统计问题应用场合：网络线路问题、单词频率统计问题重集元素的计
145、数重集元素的计数初始条件：原始数据序列保存在文件中初始条件：原始数据序列保存在文件中初始条件：原始数据序列保存在文件中初始条件：原始数据序列保存在文件中关键技术：在获取数据的同时将其插入哈希表关键技术：在获取数据的同时将其插入哈希表关键技术：在获取数据的同时将其插入哈希表关键技术：在获取数据的同时将其插入哈希表75安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表应用示例/* global.h/* global.h：头文件头文件头文件头文件 */ */# #ifndefifndef _GLOBAL_H_GLOBAL_H_#define #define _GL
146、OBAL_H_GLOBAL_H_/* /* 原始元素数目原始元素数目原始元素数目原始元素数目 */ */# #define define SIZESIZE 28 28/* /* 原始数据序列文件名原始数据序列文件名原始数据序列文件名原始数据序列文件名 */ */# #define define RAWFILERAWFILE “ “raw.datraw.dat“ “/* /* 由文件数据构造原始数据序列由文件数据构造原始数据序列由文件数据构造原始数据序列由文件数据构造原始数据序列 */ */void void CreateSeriesCreateSeries( char* ( char* fil
147、enamefilename, , intint seriesseries, , intint sizesize ); );# #endifendif76安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表应用示例/* main.c/* main.c：主文件主文件主文件主文件 */ */# #include include # #ifndefifndef _GLOBAL_H_GLOBAL_H_#include “Global.h“#include “Global.h“# #endifendif# #ifndefifndef _SYMTBL_H_SYMTBL_H_
148、#include “#include “SymTbl.hSymTbl.h“ “# #endifendifvoid void CreateSeriesCreateSeries( char* ( char* filenamefilename, , intint seriesseries, , intint sizesize ) ) FILE* FILE* f f; ; intint i i; ; f f = = fopenfopen( ( filenamefilename, “r“ );, “r“ ); for( for( i i = 0; = 0; i i sizesize; +; +i i )
149、 ) fscanffscanf( ( f f, “%, “%d d “, & “, &seriesseries i i ); ); fclosefclose( ( f f ); ); 77安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象哈希表应用示例intint mainmain(int(int argcargc, char* , char* argvargv) intint seriesseries SIZESIZE; ; intint i i; ; void* void* valuevalue; ; PSYMBOLTABLE PSYMBOLTABLE p p
150、; ; CreateSeriesCreateSeries( ( RAWFILERAWFILE, , seriesseries, , SIZESIZE ); ); /* /* 构造数据序列构造数据序列构造数据序列构造数据序列 */ */ p p = = CreateSymTblCreateSymTbl( 17 );( 17 ); /* /* 构造符号表构造符号表构造符号表构造符号表 */ */ for( for( i i = 0; = 0; i i SIZESIZE; +; +i i ) ) /* /* 将元素插入到符号表中将元素插入到符号表中将元素插入到符号表中将元素插入到符号表中 */ */
151、 /* /* 在插入前判断该元素是否已存在在插入前判断该元素是否已存在在插入前判断该元素是否已存在在插入前判断该元素是否已存在 */ */ valuevalue = = SearchInSymTblSearchInSymTbl( ( p p, , seriesseries i i ); ); /* /* 若该元素无定义，将若该元素无定义，将若该元素无定义，将若该元素无定义，将valuevalue设设设设1 1，否则递增，否则递增，否则递增，否则递增valuevalue */ */ if( if( valuevalue = = UNDEFINEDVALUEUNDEFINEDVALUE ) ) I
152、nsertIntoSymTblInsertIntoSymTbl( ( p p, , seriesseries i i, (void*)1 );, (void*)1 ); else else InsertIntoSymTblInsertIntoSymTbl( ( p p, , seriesseries i i, (void*)(, (void*)(int)int)valuevalue + 1) ); + 1) ); TraverseSymTblTraverseSymTbl( ( p p ); ); DestroySymTblDestroySymTbl( ( p p ); return 0; );
153、 return 0; 78安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础抽象符号表的局限性数据类型数据类型typedeftypedef intint/char* KEY;/char* KEY;typedeftypedef void*/ void*/structstruct VALUE* PVALUE; VALUE* PVALUE;元素遍历元素遍历缺点：需要知道缺点：需要知道缺点：需要知道缺点：需要知道valuevalue的确切类型的确切类型的确切类型的确切类型值的删除值的删除valuevalue一定是指针吗？是否需要释放？如何释放一定是指针吗？是否需要释放？如何释放一定是指针吗？是否需要释放？如何释放一定是指针吗？是否需要释放？如何释放？79安徽大学计算机教学部安徽大学计算机教学部计计算算机机程程序序设设计计基基础础作 业第第410410页：第三题（编程题）页：第三题（编程题）第第第第4 4 4 4、7 7 7 7、15151515小题小题小题小题第第411411页：第三题（编程题）页：第三题（编程题）第第第第20202020小题小题小题小题
