数据结构起步new

《数据结构起步new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构唐文斌twb@net9.org初级数据结构线性表(插入、删除、查找)数组链表(ext.块状链表)队列(ext.环形队列)BFS栈括号匹配初级数据结构树树的表示法•完全二叉树的数组实现•儿子列表•左儿子右兄弟树的遍历Trie结构(字母树)Trie结构的动机利用串的公共前缀来节约内存,加快检索速度.例如‘computer’和‘command’前3个字母是一样的,所以我们希望它们共享前3个字母.Trie的特点根节点不含字母,其他节点仅包含一个字母从根节点到某一个节点,路径上所有字母依次连起

2、来所构成的字符串,称为该节点对应的单词.每个节点的儿子包含的字母各不相同.Trie的实现存储方式:一般使用儿子数组的方法,开26个(52个)指针.如果空间较紧张,可使用左儿子右兄弟方法.插入/查找:只需要一重循环,从根节点开始,根据相应的字母不断往下走即可Trie示例P={her,iris,he,is}hiheirisheririirisTrie建立示例P’={than,the,then,this}than,thanthe,thethen,thentthisththathethithanthenthisT

3、rie应用举例并查集原理-树结构每个集合用一棵树表示,根为集合代表并查集实现与应用实现应用Kruskal例1.亲戚或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们像个好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推

4、出Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。分析本质:是否在图的同一个连通块问题:图太庞大,每次还需要遍历解决:用并查集例2.矩形在平面上画了N个长方形，每个长方形的边平行于坐标轴并且顶点坐标为整数。我们用以下方式定义印版：每个长方形是一个印版；如果两个印版有公共的边或内部，那么它们组成新的印版，否则这些印版是分离的数出印版的个数.左图有两个，右图只有一个分析把矩形看作点，有公共边的矩形连边，问题转化为求连通分量的个数判断方法：Y(X2,Y2)(X,

5、Y)22(X,Y)11(X,Y)11X例3.团伙如果两个认识,那么他们要么是朋友要么是敌人,规则如下朋友的朋友是朋友敌人的敌人是朋友给出一些人的关系(朋友、敌人),判断一共最多可能有多少个团伙并查集的其他应用线段染色,next法哈希表哈希表(Hashtable)经常被用来做字典(dictionary),或称符号表(symbol-table)直接存取表直接存取表(Direct-accesstable)的基本思想是:如果key的范围为0~m-1而且所有key都不相同,那么可以设计一个数组T[0..m-1],

6、让T[k]存放key为k的元素,否则为空(NIL)显然,所有操作都是O(1)的问题:key的范围可能很大!64位整数有18,446,744,073,709,551,616种可能,而字符串的种类将会更多!解决方案:哈希函数哈希函数的选取严格均匀分布的哈希函数很难寻找,但一般说来有三种方法在实际使用中效果不错取余法:取h(k)=kmodm乘积法:取h(k)=(A*kmod2w)rsh(w-r)点积法:随机向量a和k的m进制向量做点积实践中经常采用取余法取余法r一般来说不要取m=2,因为它只取决于k的后r位一

7、般取m为不太接近2或10的幂乘积法r取m=2,计算机字长为w,则H(k)=(A*kmod2w)rsh(w-r)w-1w其中rsh表示右移位,A是满足2

8、址法(openaddressing):自己的位置被占了,就去占别人的链地址法Key相同的元素形成一个链表链地址法的查找效率链地址法的时间效率取决于hash函数的分布.我们假设每个k将等可能的被映射到任意一个slot,不管其他key被映射到什么地方设n为key的数目,m为不同的slot数,装载因子α=n/m,即每