考试点专业课:北京大学信息科学技术学院考研复习资料—— 数据结构讲义.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《考试点专业课:北京大学信息科学技术学院考研复习资料—— 数据结构讲义.pdf》由会员分享,可在线阅读,更多相关《考试点专业课:北京大学信息科学技术学院考研复习资料—— 数据结构讲义.pdf(208页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、张铭北京大学计算机系数据结构数据结构张铭张铭http:/ 数据库与信息系统张铭北京大学计算机系教学目的教学目的 掌握常用的基本数据结构的掌握常用的基本数据结构的ADT及其应用及其应用 学会合理地组织数据学会合理地组织数据,有效地表示数据有效地表示数据,有效地处理数据有效地处理数据 基本掌握算法的设计分析技术基本掌握算法的设计分析技术 提高程序设计的质量提高程序设计的质量张铭北京大学计算机系教学要求教学要求 平时平时(考勤考勤+作业作业)20 上机上机(+报告报告)30 期中期中20 期末期末30张铭北京大学计算机系诚信诚信 端正学习态度、调动学习兴趣端正学习态度、调动学习兴趣 提倡讨论,但严禁
2、抄袭提倡讨论,但严禁抄袭 可以讨论思路,请同学看算法的逻辑问题和效率问题。可以讨论思路,请同学看算法的逻辑问题和效率问题。但要亲自动手实现。但要亲自动手实现。发现抄袭,则抄袭者和被抄袭者本次作业或上机题计双倍倒扣分,即得发现抄袭,则抄袭者和被抄袭者本次作业或上机题计双倍倒扣分,即得-20分。以后的作业题会得到重点检查。严重的期评将给予不及格处理分。以后的作业题会得到重点检查。严重的期评将给予不及格处理 数据结构教学计划和要求数据结构教学计划和要求 http:/ 1.教学大纲教学大纲 2.课程基本要求课程基本要求 3.作业基本要求作业基本要求 4.上机实习和报告的基本要求上机实习和报告的基本要求
3、 5.程序设计风格和注释要求程序设计风格和注释要求张铭北京大学计算机系按时提交作业,严禁抄袭按时提交作业,严禁抄袭 所有书面作业和上机作业都必须在指定的期限内完成并提交所有书面作业和上机作业都必须在指定的期限内完成并提交 一般周一交书面作业。除非不可抗拒的客观原因,请严格按提交时间完成书面作业和上机作业。例如,一个满分为一般周一交书面作业。除非不可抗拒的客观原因,请严格按提交时间完成书面作业和上机作业。例如,一个满分为10分的作业题,记分标准为:分的作业题,记分标准为:(1)准时提交,满分可达)准时提交,满分可达10分;分;(2)延迟)延迟3天之内提交,满分可达天之内提交,满分可达7分;分;(
4、3)延迟)延迟7天之内提交,满分可达天之内提交,满分可达3分;分;(4)7天之后提交或不交,得分天之后提交或不交,得分-5分。分。(5)抄袭得)抄袭得 20分。分。张铭北京大学计算机系书面作业提交要求书面作业提交要求1)写学号、名字写学号、名字2)每次作业,都在作业本或电子稿的每次作业,都在作业本或电子稿的word文档中写上文档中写上“我保证没有抄袭他人作业我保证没有抄袭他人作业”的诚实保证。否则,计零分或根据抄袭情况倒扣分。的诚实保证。否则,计零分或根据抄袭情况倒扣分。3)写算法分析、注释写算法分析、注释 4)算法中直接使用的函数、过程先写算法中直接使用的函数、过程先写ADT,并说明函数功能
5、、入口参数、出口参数,并说明函数功能、入口参数、出口参数 5)注意算法格式注意算法格式(层次嵌套、不同功能块之间留空层次嵌套、不同功能块之间留空)张铭北京大学计算机系上机题提交要求上机题提交要求上机作业提交时打一个上机作业提交时打一个zip包,包中含有:包,包中含有:1.readme.txt文件,把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。1.readme.txt文件,把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。2.附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。例如,VC+中的.dsw,.dsp文件,rc目录中的图像资源文件;Jbuilder中的
6、.jpr或.jpx文件,特殊的Java包等等。2.附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。例如,VC+中的.dsw,.dsp文件,rc目录中的图像资源文件;Jbuilder中的.jpr或.jpx文件,特殊的Java包等等。3.上机实习总结报告上机实习总结报告张铭北京大学计算机系上机题编程风格要求上机题编程风格要求 1诚实代码保证诚实代码保证 2.内部文档要求内部文档要求 3.过程代码要求过程代码要求 4.面向对象的代码要求面向对象的代码要求张铭北京大学计算机系教材教材 张铭、刘晓丹译张铭、刘晓丹译,数据结构与算法分析数据结构与算法分析(C+第二版第二版),电子工业出版社,
7、电子工业出版社,2002年。(用年。(用1998年的第一版也可以)年的第一版也可以)张铭、刘晓丹译张铭、刘晓丹译,数据结构与算法分析数据结构与算法分析Java版,电子工业出版社,版,电子工业出版社,2001年。年。许卓群,数据结构,高等教育出版社,许卓群,数据结构,高等教育出版社,1988。严蔚敏,数据结构题集,清华大学出版社严蔚敏,数据结构题集,清华大学出版社张铭北京大学计算机系教学参考书教学参考书 Sartaj Sahni,Data Structures,Algorithms,and Applications in C+,机械工业出版社机械工业出版社 William Ford,Data S
8、tructure with C+,清华大学出版社,清华大学出版社 Rorbert L.Kruse,Alexander J.Ryba,Data Strutures and Program Design in C+,高等教育出版社,高等教育出版社,2001张铭北京大学计算机系教学参考书教学参考书(续续)殷人昆,数据结构殷人昆,数据结构用面向对象方法与用面向对象方法与C+描述,清华大学出版社,描述,清华大学出版社,1999。张乃孝,裘宗燕,数据结构张乃孝,裘宗燕,数据结构C+与面向对象的途径,高等教育出版社,与面向对象的途径,高等教育出版社,2001。张乃孝,数据结构基础,北京大学出版社。张乃孝,数
9、据结构基础,北京大学出版社。严蔚敏,数据结构 第二版严蔚敏,数据结构 第二版(Pascal和语言版都可以和语言版都可以),清华大学出版社。,清华大学出版社。张铭北京大学计算机系第一章 概论第一章 概论 1.1 什么是数据结构什么是数据结构 1.2 抽象数据类型抽象数据类型 1.3 算法的特性及分类算法的特性及分类 1.4 算法的度量算法的度量 1.5 数据结构和算法的选择数据结构和算法的选择张铭北京大学计算机系1.1 什么是数据结构什么是数据结构 数据结构数据结构的的地位地位:数学数学,硬件硬件,软件之间软件之间.核心专业基础课核心专业基础课.结构结构:关系关系+实体实体 数据结构数据结构:按
10、按照逻辑关系照逻辑关系组织起来的一批数据组织起来的一批数据,按一定的按一定的存储方法存储方法把它存储在计算机中把它存储在计算机中,并在这些数据上定义了一个并在这些数据上定义了一个运算运算的集合的集合.张铭北京大学计算机系1.1.1 数据的逻辑结构数据的逻辑结构(1)二元组B=(K,R)K-结点结点(初等或组合类型初等或组合类型)的集合的集合 R-K上的有穷关系的集合上的有穷关系的集合.一般一般R=r表示 一元关系表示 一元关系 例如例如,r=|KiK,1 i n (2)常见逻辑关系有常见逻辑关系有:线性(线性表,栈,队列,向量,字符串,多维数组,广义表线性表,栈,队列,向量,字符串,多维数组,
11、广义表),树,图,文件(本质上是线性结构,而其索引则往往用树型)(本质上是线性结构,而其索引则往往用树型)张铭北京大学计算机系线性结构线性结构 线性结构:仅有一个开始结点,仅有一个终端结点;其它都是内部结点,且都有且仅有一个前驱、一个后继。线性结构:仅有一个开始结点,仅有一个终端结点;其它都是内部结点,且都有且仅有一个前驱、一个后继。线性表的逻辑结构线性表的逻辑结构B=(K,R),其中,其中 K k k0 0,k,k1 1,k,kn-1n-1 R=r,r=|KiK,1 i n 图示法(注意与链表的图示区分开来)图示法(注意与链表的图示区分开来)k0Kn-2k1Kn-1张铭北京大学计算机系树型结
12、构树型结构B=K,R,R=r,r满足下列条件:有且仅有一个称为根的结点没有前驱;其它结点有且仅有一个前驱;对于非根结点都存在一条从根到该结点的路径(不需要画箭头了)。满足下列条件:有且仅有一个称为根的结点没有前驱;其它结点有且仅有一个前驱;对于非根结点都存在一条从根到该结点的路径(不需要画箭头了)。张铭北京大学计算机系有向图无向图图:图:B=K,R,R=r,K中结点相对于中结点相对于r前驱和后继个数都没有限制。前驱和后继个数都没有限制。左图逻辑结构左图逻辑结构B=(K,R),其中,其中K A,B,C,D,E,F A,B,C,D,E,FR=r,r=,R=r,r=(A,C),(A,E),(B,C)
13、,(B,F),(C,D),(C,F),(D,F),(E,F)张铭北京大学计算机系1.1.2 数据的存储结构数据的存储结构 顺序顺序方法方法 链接链接方法方法存储密度存储密度(1)=数据本身存储量数据本身存储量/整个结构占用存储量整个结构占用存储量n表示线性表中当前元素的数目,链表:表示线性表中当前元素的数目,链表:=n E/n(P+E)=E/(P+E)索引索引方法方法 散列散列方法方法head指针head指针 fruit张铭北京大学计算机系索引存储索引存储张铭北京大学计算机系索引存储(续)索引存储(续)张铭北京大学计算机系散列存储散列存储张铭北京大学计算机系倒排文件倒排文件WordPostin
14、gs Document Locationabacus4 394197192122256actor3 266192132945aspen1 543atoll3 11311703440张铭北京大学计算机系倒排文件与线性索引倒排文件与线性索引TermPointer tolist of postingsant bee cat dog elk fox gnu hog Inverted lists张铭北京大学计算机系1.1.3 数据的运算数据的运算 逻辑结构和存储结构都相同逻辑结构和存储结构都相同,但运算不同但运算不同,则数据结构不同则数据结构不同.例如例如,栈与队列栈与队列 对于一种数据结构对于一种数据
15、结构,常见的运算常见的运算 建立数据结构建立数据结构 清除数据结构清除数据结构 插入一个新数据元素插入一个新数据元素 删除某个数据元素删除某个数据元素 修改某个数据元素修改某个数据元素 排序排序 检索检索张铭北京大学计算机系1.2 抽象数据类型抽象数据类型 数据抽象与过程抽象数据抽象与过程抽象,实现信息隐蔽和局部化实现信息隐蔽和局部化以一个严格定义的过程接口的方式以一个严格定义的过程接口的方式,在数据结构上提供 一个抽象在数据结构上提供 一个抽象.数据的实现和处理细节被隐蔽了数据的实现和处理细节被隐蔽了.抽象数据类型抽象数据类型,定义了一组运算的数学模型定义了一组运算的数学模型.与物理存储结构
16、无关与物理存储结构无关,使软件系统建立在数据之上使软件系统建立在数据之上(面向对象面向对象)张铭北京大学计算机系ADT 逻辑定义逻辑定义:线性表:线性表(list)是由叫做元素是由叫做元素(element)的数据项组成的一种有限并且有序的序列。该序列中仅有一个开始结点,仅有一个终端结点;其它都是内部结点,且都有且仅有一个前驱、一个后继。的数据项组成的一种有限并且有序的序列。该序列中仅有一个开始结点,仅有一个终端结点;其它都是内部结点,且都有且仅有一个前驱、一个后继。线性表的逻辑结构线性表的逻辑结构B=(K,R),其中,其中 K k0,k1,k0,k1,kn-1,kn-1 R=r,r=|KiK,
17、1 i n 运算运算张铭北京大学计算机系template class List /List abstract classpublic:/Reinitialize the list.The client is responsible for/reclaiming the storage used by the list elements.virtual void clear()=0;/Insert an element at the front of the right partition./Return true if successful,false if the list is full.
18、virtual bool insert(const Elem&)=0;/Append an element at the end of the right partition./Return true if successful,false if the list is full.virtual bool append(const Elem&)=0;/Remove the first element of right partition.Return/true if successful,false if right partition is empty./The element remove
19、d is returned in the parameter.virtual bool remove(Elem&)=0;/Place fence at list start,making left partition emptyvirtual void setStart()=0;张铭北京大学计算机系/Place fence at list end,making right partition emptyvirtual void setEnd()=0;/Move fence one step left;no change if already at startvirtual void prev(
20、)=0;/Move fence one step right;no change if already at endvirtual void next()=0;/Return length of left partitionvirtual int leftLength()const=0;/Return length of right partitionvirtual int rightLength()const=0;/If pos or more elements are in the list,set the size/of left partition to pos and return
21、true.Otherwise,/do nothing and return false.virtual bool setPos(int pos)=0;/Return in first parameter the first element of the/right partition.Return true if successful,false/if the right partition is empty.virtual bool getValue(Elem&)const=0;/Print the contents of the listvirtual void print()const=
22、0;张铭北京大学计算机系1.3 算法的特性及分类算法的特性及分类 算法特性算法特性(1)有穷性有穷性(2)确定性确定性(3)0至多个输入至多个输入(4)1至多个输出至多个输出(5)有效性有效性(可行性可行性)张铭北京大学计算机系非数值基础算法(1)穷举法穷举法(百钱买百鸡百钱买百鸡)(2)贪心法贪心法(Huffman树树)(3)递归法递归法,分治法分治法(二分法检索二分法检索)(4)回溯法回溯法(八皇后八皇后)(5)动态规划法动态规划法(最佳二叉排序树最佳二叉排序树)(6)宽度优先和深度优先搜索宽度优先和深度优先搜索(7)-裁剪和分枝界限法裁剪和分枝界限法(8)并行算法并行算法张铭北京大学计算
23、机系顺序检索顺序检索用给定检索值与线性表中各结点的关键码逐个比较。用给定检索值与线性表中各结点的关键码逐个比较。若找到相当的结点,则检索成功;若找到相当的结点,则检索成功;否则检索失败(找遍了仍找不到)。否则检索失败(找遍了仍找不到)。存储:可以顺序、链接存储:可以顺序、链接排序要求:无排序要求:无张铭北京大学计算机系顺序检索算法顺序检索算法typedef struct elem int key;datatype info;ELEM;#define UNSUCCESSFUL-1/在线性表array中顺序检索,查找关键码K/返回i为关键码K在表中的下标,i值为-1表示检索失败int seqsrc
24、h(int K,ELEM*array,int n)int i=n-1;while(i=0&arrayi.key!=K)i-;return i;typedef struct elem int key;datatype info;ELEM;#define UNSUCCESSFUL-1/在线性表array中顺序检索,查找关键码K/返回i为关键码K在表中的下标,i值为-1表示检索失败int seqsrch(int K,ELEM*array,int n)int i=n-1;while(i=0&arrayi.key!=K)i-;return i;张铭北京大学计算机系顺序检索性能分析顺序检索性能分析1)检索
25、成功假设检索每个关键码是等概率的,Pi=1/n1)检索成功假设检索每个关键码是等概率的,Pi=1/n2)检索失败假设检索失败时都需要比较n+1次(设置了一个监视哨)2)检索失败假设检索失败时都需要比较n+1次(设置了一个监视哨)Piniinnniininin()()=+=01101121张铭北京大学计算机系二分法检索二分法检索对于已排序顺序线性表对于已排序顺序线性表设数组中间位置为mid,相应的元素值记为kmid。设数组中间位置为mid,相应的元素值记为kmid。如果kmid=k,那么检索工作就完成了。如果kmid=k,那么检索工作就完成了。当kmid k时,检索继续在前半部分进行。当kmid
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考试点专业课:北京大学信息科学技术学院考研复习资料 数据结构讲义 考试 专业课 北京大学 信息科学 技术学院 考研 复习资料 数据结构 讲义
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内