考试点专业课：北京大学信息科学技术学院考研复习资料—— 数据结构讲义.pdf

张铭北京大学计算机系数据结构数据结构张铭张铭http:/ 数据库与信息系统张铭北京大学计算机系教学目的教学目的 掌握常用的基本数据结构的掌握常用的基本数据结构的ADT及其应用及其应用 学会合理地组织数据学会合理地组织数据,有效地表示数据有效地表示数据,有效地处理数据有效地处理数据 基本掌握算法的设计分析技术基本掌握算法的设计分析技术 提高程序设计的质量提高程序设计的质量张铭北京大学计算机系教学要求教学要求 平时平时(考勤考勤+作业作业)20 上机上机(+报告报告)30 期中期中20 期末期末30张铭北京大学计算机系诚信诚信 端正学习态度、调动学习兴趣端正学习态度、调动学习兴趣 提倡讨论，但严禁抄袭提倡讨论，但严禁抄袭 可以讨论思路，请同学看算法的逻辑问题和效率问题。可以讨论思路，请同学看算法的逻辑问题和效率问题。但要亲自动手实现。但要亲自动手实现。发现抄袭，则抄袭者和被抄袭者本次作业或上机题计双倍倒扣分，即得发现抄袭，则抄袭者和被抄袭者本次作业或上机题计双倍倒扣分，即得-20分。以后的作业题会得到重点检查。严重的期评将给予不及格处理分。以后的作业题会得到重点检查。严重的期评将给予不及格处理 数据结构教学计划和要求数据结构教学计划和要求 http:/ 1.教学大纲教学大纲 2.课程基本要求课程基本要求 3.作业基本要求作业基本要求 4.上机实习和报告的基本要求上机实习和报告的基本要求 5.程序设计风格和注释要求程序设计风格和注释要求张铭北京大学计算机系按时提交作业，严禁抄袭按时提交作业，严禁抄袭 所有书面作业和上机作业都必须在指定的期限内完成并提交所有书面作业和上机作业都必须在指定的期限内完成并提交 一般周一交书面作业。除非不可抗拒的客观原因，请严格按提交时间完成书面作业和上机作业。例如，一个满分为一般周一交书面作业。除非不可抗拒的客观原因，请严格按提交时间完成书面作业和上机作业。例如，一个满分为10分的作业题，记分标准为：分的作业题，记分标准为：（1）准时提交，满分可达）准时提交，满分可达10分；分；（2）延迟）延迟3天之内提交，满分可达天之内提交，满分可达7分；分；（3）延迟）延迟7天之内提交，满分可达天之内提交，满分可达3分；分；（4）7天之后提交或不交，得分天之后提交或不交，得分-5分。分。（5）抄袭得）抄袭得 20分。分。张铭北京大学计算机系书面作业提交要求书面作业提交要求1)写学号、名字写学号、名字2)每次作业，都在作业本或电子稿的每次作业，都在作业本或电子稿的word文档中写上文档中写上“我保证没有抄袭他人作业我保证没有抄袭他人作业”的诚实保证。否则，计零分或根据抄袭情况倒扣分。的诚实保证。否则，计零分或根据抄袭情况倒扣分。3)写算法分析、注释写算法分析、注释 4)算法中直接使用的函数、过程先写算法中直接使用的函数、过程先写ADT，并说明函数功能、入口参数、出口参数，并说明函数功能、入口参数、出口参数 5)注意算法格式注意算法格式(层次嵌套、不同功能块之间留空层次嵌套、不同功能块之间留空)张铭北京大学计算机系上机题提交要求上机题提交要求上机作业提交时打一个上机作业提交时打一个zip包，包中含有：包，包中含有：1.readme.txt文件，把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。1.readme.txt文件，把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。2.附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。例如，VC+中的.dsw,.dsp文件，rc目录中的图像资源文件；Jbuilder中的.jpr或.jpx文件，特殊的Java包等等。2.附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。例如，VC+中的.dsw,.dsp文件，rc目录中的图像资源文件；Jbuilder中的.jpr或.jpx文件，特殊的Java包等等。3.上机实习总结报告上机实习总结报告张铭北京大学计算机系上机题编程风格要求上机题编程风格要求 1诚实代码保证诚实代码保证 2.内部文档要求内部文档要求 3.过程代码要求过程代码要求 4.面向对象的代码要求面向对象的代码要求张铭北京大学计算机系教材教材 张铭、刘晓丹译张铭、刘晓丹译,数据结构与算法分析数据结构与算法分析(C+第二版第二版)，电子工业出版社，电子工业出版社，2002年。（用年。（用1998年的第一版也可以）年的第一版也可以）张铭、刘晓丹译张铭、刘晓丹译,数据结构与算法分析数据结构与算法分析Java版，电子工业出版社，版，电子工业出版社，2001年。年。许卓群，数据结构，高等教育出版社，许卓群，数据结构，高等教育出版社，1988。严蔚敏，数据结构题集，清华大学出版社严蔚敏，数据结构题集，清华大学出版社张铭北京大学计算机系教学参考书教学参考书 Sartaj Sahni,Data Structures,Algorithms,and Applications in C+,机械工业出版社机械工业出版社 William Ford，Data Structure with C+，清华大学出版社，清华大学出版社 Rorbert L.Kruse,Alexander J.Ryba,Data Strutures and Program Design in C+，高等教育出版社，高等教育出版社，2001张铭北京大学计算机系教学参考书教学参考书(续续)殷人昆，数据结构殷人昆，数据结构用面向对象方法与用面向对象方法与C+描述，清华大学出版社，描述，清华大学出版社，1999。张乃孝，裘宗燕，数据结构张乃孝，裘宗燕，数据结构C+与面向对象的途径，高等教育出版社，与面向对象的途径，高等教育出版社，2001。张乃孝，数据结构基础，北京大学出版社。张乃孝，数据结构基础，北京大学出版社。严蔚敏，数据结构 第二版严蔚敏，数据结构 第二版(Pascal和语言版都可以和语言版都可以)，清华大学出版社。，清华大学出版社。张铭北京大学计算机系第一章 概论第一章 概论 1.1 什么是数据结构什么是数据结构 1.2 抽象数据类型抽象数据类型 1.3 算法的特性及分类算法的特性及分类 1.4 算法的度量算法的度量 1.5 数据结构和算法的选择数据结构和算法的选择张铭北京大学计算机系1.1 什么是数据结构什么是数据结构 数据结构数据结构的的地位地位:数学数学,硬件硬件,软件之间软件之间.核心专业基础课核心专业基础课.结构结构:关系关系+实体实体 数据结构数据结构:按按照逻辑关系照逻辑关系组织起来的一批数据组织起来的一批数据,按一定的按一定的存储方法存储方法把它存储在计算机中把它存储在计算机中,并在这些数据上定义了一个并在这些数据上定义了一个运算运算的集合的集合.张铭北京大学计算机系1.1.1 数据的逻辑结构数据的逻辑结构(1)二元组B=(K,R)K-结点结点(初等或组合类型初等或组合类型)的集合的集合 R-K上的有穷关系的集合上的有穷关系的集合.一般一般R=r表示 一元关系表示 一元关系 例如例如,r=|KiK,1 i n (2)常见逻辑关系有常见逻辑关系有:线性(线性表，栈，队列，向量，字符串，多维数组，广义表线性表，栈，队列，向量，字符串，多维数组，广义表)，树，图，文件（本质上是线性结构，而其索引则往往用树型）（本质上是线性结构，而其索引则往往用树型）张铭北京大学计算机系线性结构线性结构 线性结构：仅有一个开始结点，仅有一个终端结点；其它都是内部结点，且都有且仅有一个前驱、一个后继。线性结构：仅有一个开始结点，仅有一个终端结点；其它都是内部结点，且都有且仅有一个前驱、一个后继。线性表的逻辑结构线性表的逻辑结构B=(K,R)，其中，其中 K k k0 0,k,k1 1,k,kn-1n-1 R=r，r=|KiK,1 i n 图示法（注意与链表的图示区分开来）图示法（注意与链表的图示区分开来）k0Kn-2k1Kn-1张铭北京大学计算机系树型结构树型结构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),(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张铭北京大学计算机系索引存储索引存储张铭北京大学计算机系索引存储（续）索引存储（续）张铭北京大学计算机系散列存储散列存储张铭北京大学计算机系倒排文件倒排文件WordPostings Document Locationabacus4 394197192122256actor3 266192132945aspen1 543atoll3 11311703440张铭北京大学计算机系倒排文件与线性索引倒排文件与线性索引TermPointer tolist of postingsant bee cat dog elk fox gnu hog Inverted lists张铭北京大学计算机系1.1.3 数据的运算数据的运算 逻辑结构和存储结构都相同逻辑结构和存储结构都相同,但运算不同但运算不同,则数据结构不同则数据结构不同.例如例如,栈与队列栈与队列 对于一种数据结构对于一种数据结构,常见的运算常见的运算 建立数据结构建立数据结构 清除数据结构清除数据结构 插入一个新数据元素插入一个新数据元素 删除某个数据元素删除某个数据元素 修改某个数据元素修改某个数据元素 排序排序 检索检索张铭北京大学计算机系1.2 抽象数据类型抽象数据类型 数据抽象与过程抽象数据抽象与过程抽象,实现信息隐蔽和局部化实现信息隐蔽和局部化以一个严格定义的过程接口的方式以一个严格定义的过程接口的方式,在数据结构上提供 一个抽象在数据结构上提供 一个抽象.数据的实现和处理细节被隐蔽了数据的实现和处理细节被隐蔽了.抽象数据类型抽象数据类型,定义了一组运算的数学模型定义了一组运算的数学模型.与物理存储结构无关与物理存储结构无关,使软件系统建立在数据之上使软件系统建立在数据之上(面向对象面向对象)张铭北京大学计算机系ADT 逻辑定义逻辑定义：线性表：线性表(list)是由叫做元素是由叫做元素(element)的数据项组成的一种有限并且有序的序列。该序列中仅有一个开始结点，仅有一个终端结点；其它都是内部结点，且都有且仅有一个前驱、一个后继。的数据项组成的一种有限并且有序的序列。该序列中仅有一个开始结点，仅有一个终端结点；其它都是内部结点，且都有且仅有一个前驱、一个后继。线性表的逻辑结构线性表的逻辑结构B=(K,R)，其中，其中 K k0,k1,k0,k1,kn-1,kn-1 R=r，r=|KiK,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.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 removed 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()=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 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=0;张铭北京大学计算机系1.3 算法的特性及分类算法的特性及分类 算法特性算法特性(1)有穷性有穷性(2)确定性确定性(3)0至多个输入至多个输入(4)1至多个输出至多个输出(5)有效性有效性(可行性可行性)张铭北京大学计算机系非数值基础算法(1)穷举法穷举法(百钱买百鸡百钱买百鸡)(2)贪心法贪心法(Huffman树树)(3)递归法递归法,分治法分治法(二分法检索二分法检索)(4)回溯法回溯法(八皇后八皇后)(5)动态规划法动态规划法(最佳二叉排序树最佳二叉排序树)(6)宽度优先和深度优先搜索宽度优先和深度优先搜索(7)-裁剪和分枝界限法裁剪和分枝界限法(8)并行算法并行算法张铭北京大学计算机系顺序检索顺序检索用给定检索值与线性表中各结点的关键码逐个比较。用给定检索值与线性表中各结点的关键码逐个比较。若找到相当的结点，则检索成功；若找到相当的结点，则检索成功；否则检索失败(找遍了仍找不到)。否则检索失败(找遍了仍找不到)。存储：可以顺序、链接存储：可以顺序、链接排序要求：无排序要求：无张铭北京大学计算机系顺序检索算法顺序检索算法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;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)检索成功假设检索每个关键码是等概率的，Pi=1/n1)检索成功假设检索每个关键码是等概率的，Pi=1/n2)检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）2)检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）Piniinnniininin()()=+=01101121张铭北京大学计算机系二分法检索二分法检索对于已排序顺序线性表对于已排序顺序线性表设数组中间位置为mid，相应的元素值记为kmid。设数组中间位置为mid，相应的元素值记为kmid。如果kmid=k，那么检索工作就完成了。如果kmid=k，那么检索工作就完成了。当kmid k时，检索继续在前半部分进行。当kmid k时，检索继续在前半部分进行。相反地，若kmid k，就可以忽略mid以前的那部分，检索继续在后半部分进行。相反地，若kmid k，就可以忽略mid以前的那部分，检索继续在后半部分进行。KmidKmid k的两种情况，都缩小了一半的检索范围。k的两种情况，都缩小了一半的检索范围。张铭北京大学计算机系二分法的下一步工作是检查k可能存在的那部分元素中的中间位置。该位置上的元素值使我们又能缩小一半的检索范围。二分法的下一步工作是检查k可能存在的那部分元素中的中间位置。该位置上的元素值使我们又能缩小一半的检索范围。重复这个过程，就能找到指定的元素(或确定它不在数组中)。重复这个过程，就能找到指定的元素(或确定它不在数组中)。该过程至多需要重复次。该过程至多需要重复次。）（1log2+n张铭北京大学计算机系二分法检索算法二分法检索算法/Return the position of an element in a sorted array of/size n with value K.If none exist,return n.int binary(int array,int n,int K)int l=-1;int r=n;/l and r are beyond array boundswhile(l+1!=r)/Stop when l and r meetint i=(l+r)/2;/Check middle of remaining subarrayif(K arrayi)l=i;/In right halfreturn n;/Search value not in array张铭北京大学计算机系0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15(1)(4)(3)(2)检索关键码45。l=-1;r=16;K=45第一次：mid=7;array7=4145r=11;(l=7)第三次：mid=9;array9=5145r=9;(l=7)第四次：mid=8;array8=45=45；return 80 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15(1)(4)(3)(2)检索关键码45。l=-1;r=16;K=45第一次：mid=7;array7=4145r=11;(l=7)第三次：mid=9;array9=5145r=9;(l=7)第四次：mid=8;array8=45=45；return 8二分法检索图示二分法检索图示40414551545665727783362926211311张铭北京大学计算机系二分法检索性能分析二分法检索性能分析1)最大检索长度为1)最大检索长度为2)失败的检索长度是或2)失败的检索长度是或7315473154 6 62 2119131211913128 814141001001515）（1log2+n）（1log2+n）（1log2+n张铭北京大学计算机系二分法检索性能分析（续）二分法检索性能分析（续）3)成功的平均检索长度为：(n 50)3)成功的平均检索长度为：(n 50)4)优缺点4)优缺点优点：平均检索长度与最大检索长度相近，检索速度快优点：平均检索长度与最大检索长度相近，检索速度快缺点：要排序、顺序存储，不易更新(插/删)缺点：要排序、顺序存储，不易更新(插/删)E nniiijnnnn()()log()log()=+12111211211张铭北京大学计算机系1.4 算法的度量算法的度量 算法设计的两个目标算法设计的两个目标：易读、易编码和调试（软件工程）易读、易编码和调试（软件工程）充分利用计算机资源（算法和数据结构）充分利用计算机资源（算法和数据结构）评估方法评估方法 实验（运行程序）实验（运行程序）渐进分析渐进分析 关键资源关键资源 影响运行时间的因素影响运行时间的因素 往往与问题的输入规模往往与问题的输入规模n有关有关张铭北京大学计算机系最佳、最差、平均情况分析最佳、最差、平均情况分析 对于不同的输入情况，算法的时间代价不一样对于不同的输入情况，算法的时间代价不一样 例如，在一个数组中查找元素例如，在一个数组中查找元素K 往往分为最佳、最差、平均情况分析往往分为最佳、最差、平均情况分析张铭北京大学计算机系时间代价空间代价时间代价空间代价 算法的时间代价算法的时间代价:当问题的规模，由当问题的规模，由 1增至增至 n时时,解决该问题所占用的时间解决该问题所占用的时间,也以某单位由也以某单位由 1增至增至f(n),则称该算法的时间代价为则称该算法的时间代价为f(n)。算法的空间代价算法的空间代价:当问题的规模，由当问题的规模，由 1增至增至 n时时,解决该问题所占用的空间解决该问题所占用的空间,也以某单位由也以某单位由 1增至增至f(n),则称该算法的空间代价为则称该算法的空间代价为f(n)。时间时间/空间的权衡空间的权衡张铭北京大学计算机系大大O表示法及其运算规则表示法及其运算规则 大O表示法:称某程序的时间称某程序的时间(或空间或空间)代价为代价为 O(f(n),若存在正常数若存在正常数c 和和n0,当问题的规模当问题的规模n n0后后,该算法的时间该算法的时间(或空间或空间)代价代价T(n)cf(n),也称该算法的时间也称该算法的时间(或空间或空间)增长率为增长率为f(n)。对于所有足够大的输入数据集（对于所有足够大的输入数据集（n n0），算法在最佳或平均或最差情况下的运行步骤数为），算法在最佳或平均或最差情况下的运行步骤数为f(n)量级。量级。张铭北京大学计算机系大大O表示法的运算规则表示法的运算规则 单位时间单位时间 简单布尔或算术运算简单布尔或算术运算 赋值赋值 简单简单I/O 函数返回函数返回 加法规则加法规则:f1(n)+f2(n)=(max(f1(n),f2(n)If结构，结构，switch结构结构 乘法规则乘法规则:f1(n)f2(n)=(f1(n)f2(n)for,while,do-while结构结构张铭北京大学计算机系时间复杂性时间复杂性sum=0;for(i=1;i=n;i+)for(j=1;j=n;j+)sum+;T(n)=cc2n2 O(n2)张铭北京大学计算机系各增长率函数值的比较各增长率函数值的比较张铭北京大学计算机系增长率函数曲线张铭北京大学计算机系运行时间估计运行时间估计 例：假设例：假设CPU每秒处理每秒处理106个指令，对于输入规模为个指令，对于输入规模为=108的问题，时间代价为的问题，时间代价为T(n)=2n2的算法要运行多长时间？的算法要运行多长时间？操作次数为操作次数为 T(n)=T(108)=2(108)2=2 1016 运行时间为运行时间为 2 1016/106=2 1010秒秒 每天有每天有86,400秒，因此需要秒，因此需要231,480 天天(634 年年)张铭北京大学计算机系运行时间估计（续）运行时间估计（续）例：假设例：假设CPU每秒处理每秒处理106个指令，对于输入规模为个指令，对于输入规模为n=108的问题，时间代价为的问题，时间代价为T(n)=nlogn的算法要运行多长时间？的算法要运行多长时间？操作次数为操作次数为T(n)=T(108)=108 log108=2.66 109 运行时间为运行时间为 2.66 109/106=2.66 103秒，即秒，即44.33分钟分钟张铭北京大学计算机系规定时间内能解决的问题规模规定时间内能解决的问题规模 假设假设CPU每秒处理每秒处理106个指令，则每小时能够解决的最大问题规模个指令，则每小时能够解决的最大问题规模 T(n)/106 3600 对对T(n)=2n2，即即 2n2 3600 106 n 42,426 T(n)=nlogn 即即 nlogn 3600 106 n 133,000,000张铭北京大学计算机系 设设CPU每秒处理每秒处理108个指令（快个指令（快100倍倍）处理时间都降为原来的处理时间都降为原来的1/100 解决问题的规模解决问题的规模 对对T(n)=2n2，规模增加，规模增加10倍倍 T(n)=nlogn，规模增加，规模增加75倍倍加快硬件速度？加快硬件速度？2n2T(n)0.4433秒秒6.34年年nlogn100亿亿424,2641小时内解决的问题规模小时内解决的问题规模106指令指令/秒秒108指令指令/秒秒44.33秒秒634年年106指令指令/秒秒108指令指令/秒秒42,4261.33 亿亿处理输入规模为处理输入规模为n=108张铭北京大学计算机系快快10倍的计算机所能解决的问题规模倍的计算机所能解决的问题规模?-n=n+316132n3.16n=10n223702n27.37 10 n n 10n1,8422505n log n10n=10n5,00050020n10n=10n10,0001,00010nn/nChangennT(n)张铭北京大学计算机系1.5 数据结构和算法的选择数据结构和算法的选择 1.分析问题以确定资源限制分析问题以确定资源限制 2.确定基本运算，并度量每种运算所受的资源限制确定基本运算，并度量每种运算所受的资源限制 向数据结构中插入一个数据项向数据结构中插入一个数据项 从数据结构中删除一个数据项从数据结构中删除一个数据项 查找指定的数据项查找指定的数据项.3.选择最接近这些开销的数据结构选择最接近这些开销的数据结构张铭北京大学计算机系仔细考虑运算问题仔细考虑运算问题 开始时将所有数据项都插入数据结构，还是与其它操作混合在一起插入开始时将所有数据项都插入数据结构，还是与其它操作混合在一起插入?数据项可以被删除吗数据项可以被删除吗?所有数据项是安排在某一个已经定义好的序列中，还是允许随机进入所有数据项是安排在某一个已经定义好的序列中，还是允许随机进入?张铭北京大学计算机系时间时间/空间权衡空间权衡 数据结构数据结构 一定的空间来存储它的每一个数据项一定的空间来存储它的每一个数据项 一定的时间来执行单个基本操作一定的时间来执行单个基本操作 代价和效益代价和效益 空间和时间的限制空间和时间的限制 程序设计工作量程序设计工作量张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院第二章线性表2.1 线性表2.2 顺序表2.3 链表2.4 栈2.5 队列第二章线性表2.1 线性表2.2 顺序表2.3 链表2.4 栈2.5 队列张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院2.1 线性表2.1 线性表?线性结构：仅有一个开始结点，仅有一个终端结点；其它都是内部结点，且都有且仅有一个前驱、一个后继。线性结构：仅有一个开始结点，仅有一个终端结点；其它都是内部结点，且都有且仅有一个前驱、一个后继。线性表线性表 广义表广义表 文件文件?线性序列：线性结构中的所有结点按其关系可以排成一个序列。线性序列：线性结构中的所有结点按其关系可以排成一个序列。如(a0,a1,如(a0,a1,an-1),an-1)张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院线性表ADT线性表ADT?线性表ADT:线性表(lists)是由叫做元素(element)的数据项组成的一种有限并且有序的线性序列。可以为空表。主要属性有：线性表ADT:线性表(lists)是由叫做元素(element)的数据项组成的一种有限并且有序的线性序列。可以为空表。主要属性有：线性表的长度(msize,numinlist)线性表的长度(msize,numinlist)表头(head)表头(head)表尾(tail)表尾(tail)当前位置(curr)当前位置(curr)张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院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.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 removed 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()=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 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=0;张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院1.存储结构1.存储结构?顺序表顺序表 一维数组一维数组?链表链表 单链表单链表 双链表双链表 循环链表(单、双)循环链表(单、双)head指针head指针head指针head指针head指针head指针 fruit张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院2.运算2.运算?建立数据结构建立数据结构?清除数据结构清除数据结构?插入一个新数据元素插入一个新数据元素?删除某个数据元素删除某个数据元素?修改某个数据元素修改某个数据元素?排序排序?检索检索张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院3.根据运算分类(都有顺序和链式)3.根据运算分类(都有顺序和链式)?向量(一维数组,链式顺序表)向量(一维数组,链式顺序表)串串 所有表目都是同一类型结点的线性表所有表目都是同一类型结点的线性表 不限制操作形式不限制操作形式 根据存储的不同分为：顺序表,链表根据存储的不同分为：顺序表,链表?栈(LIFO,Last In First Out)栈(LIFO,Last In First Out)插入和删除操作都限制在表的同一端进行插入和删除操作都限制在表的同一端进行?队列(FIFO,First In First Out)队列(FIFO,First In First Out)插入操作在表的一端,删除操作在另一端插入操作在表的一端,删除操作在另一端张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院2.2 顺序表2.2 顺序表?1.顺序表顺序表 存储：固定长度的数组存储：固定长度的数组 运算：运算：插入、删除运算插入、删除运算 O(n)注意检查边界条件（程序设计的功底，鲁棒性）注意检查边界条件（程序设计的功底，鲁棒性）张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院顺序表类顺序表类template /Array-based list implementationclass AList:public List private:int maxSize;/Maximum size of listint listSize;/Actual number of elements in listint fence;/Position of fenceElem*listArray;/Array holding list elements张 铭 版权所有数据库与信息系统实验室北京大学信息科学与技术学院public:AList(int size=DefaultListSize)/Constructo