北大数据结构与算法课件01概论

数据结构与算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2教学目的…„“数据结构＋算法＝程序”„基本数据结构的ADT及其应用„合理组织数据,有效表示数据,有效处理数据„算法的设计分析技术„抽象能力„问题——数据——算法„提高程序设计的质量北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3课程的主要内容„理论„算法的数学基础„算法的时间和空间度量„抽象„排序、检索等重要问题类的有效算法„重要数据结构技术„设计„算法的选择、实现和测试北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4实习课目的配合“数据结构与算法”主课，提高实际动手能力和程序设计的质量„基本数据结构„线性表(向量、串、栈和队列)、二叉树、树、图等„ADT、STL„综合应用程序„排序、检索、文件、索引等技术„程序设计实践和技巧北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5实习课程内容(1/2)„C++编程技术补充„标准模板库STL的基本概念„C++流处理„程序设计实践和技巧„风格、设计和实现„界面、排错„测试、性能和可扩展性北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6实习课程内容(2/2)„基本算法„枚举法、贪心法„递归、回溯、搜索与分支限界„分治法、动态规划„问题建模„数学建模、软件模型„数据结构的应用北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30第一章概论„为什么要学习数据结构„什么是数据结构„抽象数据类型„算法的特性及分类„算法的效率度量„数据结构的选择和评价„总结北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31为什么要学习数据结构„计算机软件与理论学科的专业基础课程„后续专业课程学习的必要知识与技能准备„编译技术要使用栈、散列表及语法树„操作系统中用队列、存储管理表及目录树„数据库系统运用线性表、多链表、及索引树„……„增强求解复杂问题的能力北京大学信息学院张铭编写©版权所有，转载或翻印必究Page32什么是数据结构(datastructure)„数据逻辑结构„数据的存储结构„数据的运算存储数据结构逻辑运算北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33数据的逻辑结构„二元组：(K，R)„K是由有限个结点组成的集合„R是定义在集合K上的一组关系，其中每个关系(relation)r（r∈R）都是K×K上的二元关系„数据结构中，只讨论R={r}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34常见的逻辑关系„线性结构„树形结构„图结构„文件结构图⊇树⊇二叉树⊇线性表北京大学信息学院张铭编写©版权所有，转载或翻印必究Page35结点的类型„基本数据类型„整数类型(integer)„实数类型(real)„布尔类型(boolean)„在C++语言中一般使用整数0表示false，用非0表示true北京大学信息学院张铭编写©版权所有，转载或翻印必究Page36结点的类型„基本数据类型„字符类型(char)：用单个字节（8bit，最高位bit为0）表示ASCII字符集中的字符。„汉字符号需要使用2个字节（每个字节的最高位bit为1）的编码„Unicode，GB，Big5，HZ北京大学信息学院张铭编写©版权所有，转载或翻印必究Page37结点的类型„基本数据类型„指针类型(pointer)：指向某一内存单元的地址„32bit机器，4个字节表示一个指针„64bit的机器，8指针„指针操作„分配地址„赋值（另一个指针的地址值，NULL空值）„比较两个指针地址„指针增减一个整数量北京大学信息学院张铭编写©版权所有，转载或翻印必究Page38结点的类型„复合数据类型„基本数据类型/复合类型„数组intA[100];„结构typedefstruct{}B;classC{};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page39结点和结构„数据结构的设计一层一层地进行„先明确数据结点，及其主要关系r„对于复杂情况，再分析下一层次的逻辑结构„自顶向下的分析设计方法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page40结构的分类„对（K,R）的分类，用R的性质来刻划„线性结构（linearstructure）„树型结构（treestructure）„图结构（graphstructure）北京大学信息学院张铭编写©版权所有，转载或翻印必究Page41线性结构„应用最广泛，关系r是一种线性关系„‘前后关系’„‘大小关系’„关系r有向，全序性和单索性等约束条件„全序性：全部结点两两皆可以比较前后（关系r）„单索性：每一个结点y都存在唯一的直接后继结点z„y-z„x-…-z„则x-…y-z„x=y？北京大学信息学院张铭编写©版权所有，转载或翻印必究Page42线性结构„图示法（注意与链表的图示区别开来）k0Kn-2k1Kn-1k…北京大学信息学院张铭编写©版权所有，转载或翻印必究Page43树型结构„其关系r为层次关系，或称‘父子关系’、‘上下级关系’„每一个结点可以有多于一个的‘直接下级’，但是它只能有唯一的‘直接上级’。„根（root）结点没有父结点北京大学信息学院张铭编写©版权所有，转载或翻印必究Page44图结构有向图图：B={K,R},R={r},K中结点相对于r前驱和后继个数都没有限制。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page45图结构无向图左图逻辑结构B=(K,R)，其中K＝｛A,B,C,D,E,F}R={r}，r={A,C,C,A,A,E,E,A,B,C,C,B,B,F,F,B,C,D,D,C,C,F,F,C,D,F,F,D,E,F,FE}可以简写为:r={(A,C),(A,E),(B,C),(B,F),(C,D),(C,F),(D,F),(E,F)}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page46数据的存储结构„映射：逻辑→存储„对于数据逻辑结构（K,r）,其中r∈R„从K到存储器M的单元的映射：K→M„每一个结点k∈K都对应于唯一的区域c∈M。„关系元组（k1,k2）∈r（k1,k2∈K映射为存储单元的地址指向关系„四种存储结构：顺序、链接、索引、散列„空间时间权衡„尽量少的空间，尽量快的运算速度北京大学信息学院张铭编写©版权所有，转载或翻印必究Page47„把一组结点存储在按地址相邻的顺序存储单元里„结点间的逻辑后继关系用存储单元的自然顺序关系来表达„紧凑存储结构„紧凑性可以用‘存储密度’来度量：„存储密度(≤1)=数据本身存储量/整个结构占用存储量顺序存储——数组01234567S:北京大学信息学院张铭编写©版权所有，转载或翻印必究Page48链接（linked）的方法„指针的指向：结点间逻辑后继关系„两部分:数据字段、指针字段„链索：多个相关结点的依次链接就会形成„存储密度：ρ=n×E/n(P+E)=E/(P+E)a1anFirstLast单链表北京大学信息学院张铭编写©版权所有，转载或翻印必究Page49索引（indexing）的方法„索引法是顺序存储法的一种推广，它也使用整数编码来访问数据结点位置01234567数据节点的存储区域索引表北京大学信息学院张铭编写©版权所有，转载或翻印必究Page50back92733755数据库记录线形索引文件„索引函数Y：ZÆD„结点的整数索引值z∈Z„结点的存储地址d∈D北京大学信息学院张铭编写©版权所有，转载或翻印必究Page51倒排文件WordPostingsDocumentLocationabacus4394197192122256actor3266192132945aspen1543atoll311311703440北京大学信息学院张铭编写©版权所有，转载或翻印必究Page52倒排文件与线性索引TermPointertolistofpostingsantbeecatdogelkfoxgnuhogInvertedlists北京大学信息学院张铭编写©版权所有，转载或翻印必究Page53散列（hashing）的方法„散列是索引方法的一种延伸和扩展„更快的检索速度„受数组元素地址计算启发„Loc(A[i])=Loc(A[0])+i*sizeof(Element);„散列函数是将字符串s映射到非负整数z的一类函数h:SÆZ，对任意的s∈S，散列函数h(s)=z，z∈Z北京大学信息学院张铭编写©版权所有，转载或翻印必究Page54散列（hashing）的方法„散列函数h(s)除了它取非负整数值外，关键的问题：„恰当地选择散列函数„如何建造散列表„在构建散列表的中间解决‘碰撞’的办法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page55散列（hashing）的方法H(k)=k%1101234567891077147751106295北京大学信息学院张铭编写©版权所有，转载或翻印必究Page56数据的运算„逻辑结构和存储结构都相同,但运算不同,则数据结构不同„例如,栈与队列„对于一种数据结构,常见的运算„建立、清除数据结构„插入、删除、修改某个数据元素„排序、检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page57排序问题„Google等搜索引擎返回结果排级„图书馆员书目编号、上架„各种排名„《泰晤士报》大学排名„《福布斯》富豪榜„保研成绩排名„……„Windows资源管理器，文件查看„……北京大学信息学院张铭编写©版权所有，转载或翻印必究Page58抽象数据类型ADT„抽象数据类型是定义了一组运算的数学模型„剥离存储与实现细节„在适当的抽象层次上考虑程序的结构和算法„封装和信息隐蔽北京大学信息学院张铭编写©版权所有，转载或翻印必究Page59„逻辑、存储、运算三者不同，都可以看作不同数据结构„忽略存储，强调逻辑、运算则为ADT„不特别指明，允许使用STL北京大学信息学院张铭编写©版权所有，转载或翻印必究Page60栈的不同存储实现„插入、删除、检索都只能被限制在同一端的线性表先进后出LIFO„顺序实现„链表实现栈顶54871[0][1][2][3][4]elementmax_size-1N1234栈顶北京大学信息学院张铭编写©版权所有，转载或翻印必究Page61栈(stack)栈：限制访问端口的线性表：LIFO表„Push：元素插入称为栈的‘压入’„Pop：删除称为栈的‘弹出’„Top：表首被称为‘栈顶’1234栈底栈顶栈最大长度北京大学信息学院张铭编写©版权所有，转载或翻印必究Page62队列（queue）„插入在一端，删除、检索在另一端的线性表„先进先出FIFOABCEfrontBCDfrontrear北京大学信息学院张铭编写©版权所有，转载或翻印必究Page63栈的抽象数据类型enumBoolean{True,False}templateclassELEMclassStack{//栈的元素类型为ELEM//栈的存储：可以用顺序表或单链表存储，长//度为定长//栈的运算集为：Stack(ints);//创建栈的实例~Stack();//该实例消亡北京大学信息学院张铭编写©版权所有，转载或翻印必究Page64voidPush(ELEMitem);//item压入栈顶ELEMPop();//返回栈顶内容，并从栈顶弹出ELEMGetTop();//返回栈顶内容，但不弹出voidClearStack();//变为空栈BooleanIsEmpty();//返回真，若栈已空BooleanIsFull();//返回真，若栈已满};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page65算法及其特性„算法(algorithms)是为了求解问题而给出的指令序列„程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解北京大学信息学院张铭编写©版权所有，转载或翻印必究Page66算法及其特性„通用性„有效性„确定性„有穷性北京大学信息学院张铭编写©版权所有，转载