下一页计算机软件基础 The software basic of computer主讲：刘志强 西安交通大学 计算机教学实验中心第2单元 线性数据结构 （一）1下一页上一页停止放映第2单元 线性数据结构（一）教学目标： 了解数据结构的有关概念 什么是线性DS、线性表 了解线性DS的特点 了解线性DS的逻辑结构、物理结 构以及操作2下一页上一页停止放映学习要求通过本单元的学习，了解并掌握： 有关数据结构（DS）的基本概念 数据元素、DS、逻辑结构、物理结构、 DS的分类及特点、算法、时间复杂度等 线性DS的常用存储结构 顺序、链表、索引、散列存储结构 单向、双向、循环链表等 线性DS的有关算法 增、删、改3下一页上一页停止放映涉及的章节第1章的1.1 数据结构概述(P13P17)1.2 线性表(P17P32)4下一页上一页停止放映数据结构问题的由来计算机求解问题过程步骤：实际 问题 求解问题 模型 算法分析抽象模型求解命令编程调试程序编制 程序运行 程序求解 结果结果输出用户 需求数据类型、格式 、 逻辑结构数据 逻辑 运算数据的物理 操作5下一页上一页停止放映问题模型l结构分析 线性方程组l人口预报 微分方程l优化问题 线性规划、非线性规划l震动问题 矩阵分析；特征值、特征 向量l信息管理 二维数据表l下棋 人工智能(树型结构)l交通管理最佳道路选择(图型结构)6下一页上一页停止放映下棋问题11 1 1111111 11 1111117下一页上一页停止放映一、基本概念l数据（Data）能存于计算机、并被计算机处理的符号的集合 。它是客观事物的符号表示。l数据元素（Element）是数据的基本单位、数据集合中的个体。l数据结构（Data Structure）是带有结构特征的数据元素的集合；它有三个 要素：DS=数据的逻辑结构+存储结构+数据的运算数据结构是以数据为加工对象，研究数据组织 方式和相关操作方法的学问。也可以说：怎样 去组织一批特定的数据。8下一页上一页停止放映数据结构分类线性表 堆栈 队列 串 数组树 二叉树 图线性结构非线性结构数据结构DS9下一页上一页停止放映1. 数据的逻辑结构它是描述数据间的顺序（逻辑）关系 ，只是抽象地反映数据元素的结构， 而不管它们在计算机中如何存放。一 般用下列二元组来描述：DS=（D，R）其中：D：是数据元素的有限集合；R：是数据元素之间关系的集合。10下一页上一页停止放映举例l课题组由1名教师、13名研究生、16 名本科生组成；成员关系是：教师指导 研究生、研究生指导12名本科生。定义DS如下：Group=（D，R）其中：D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2R=R1,R2R1=|1 i n , 1 n 3R2=|1in ,1 j m , 1 n 3 , 1 m 2 11下一页上一页停止放映2. 数据的存储结构l又称物理结构l是指数据结构在计算机中 的表示(又称映象),即数据 在计算机中的存放。12下一页上一页停止放映逻辑结构和物理结构的关系 数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以 在理论上、形式上进行研究、推理、运算等 各种操作。 数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则 无法进行任何操作。 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的 存储结构。13下一页上一页停止放映数据存储结构分类l顺序存储结构l链式存储结构l索引存储结构l散列存储结构 14下一页上一页停止放映顺序存储结构把数据元素按某种顺序存放在一块连续的存储单 元中的存储形式。数据结点结构:特点: 连续存放;逻辑上相邻,物理上也相邻。 结构简单，易实现。 插入、删除操作不便（需大量移动元素）。d1 d2 dn数据域15下一页上一页停止放映链式存储结构以链表形式将数据元素存放于任意存储单元中 ，可连续存放，也可以不连续存放，以指针实 现链表间的联系。数据结点结构:特点: 非连续存放,借助指针来表示元素间的关系; 插入、删除操作简单，只要修改指针即可； 结构较复杂，需要额外存储空间。d1.d2dn 数据域 指针域16下一页上一页停止放映索引存储结构数据按索引形式存放。存储时分为：数据项和索引 号；通过索引表记录逻辑号（记录号）和物理号（ 存储序号）之间的对应关系。数据结点结构:序 号： 1 2 3 4 5 6 7 数据项：索引号：特点： 非连续存放； 检索速度快； 增、删操作简单。12 21 35 2 45 5 10 4 3 2 7 1 6 5数据域 索引顺序号17下一页上一页停止放映散列存储结构l在数据元素与存储位置之间建立一种存储 关系F，根据这种关系F，已知元素E，就 可以得到它的存储地址，即D=F（E）。l哈希查找中的哈希表就是这样一种存储结 构。特点： 数据元素间无内在联系； 存储形式不定。18下一页上一页停止放映3. 数据运算l 数据运算是指对存放在物理结构上 的数据,按定义的逻辑结构进行的各 种操作。常见操作有： 输入、检索、插入、删除、修改 、排序等。19下一页上一页停止放映4、算法与算法分析算法（Algorithm） 是对特定问题求解步骤的一种描述； 是一组指令的有限集合。 算法和数据结构的关系为了充分地利用系统资源；既要效率高 、速度快，又要存储空间少。显然，这 是矛盾的。 研究算法追求的目标是：时间和空间的适当和谐20下一页上一页停止放映算法的特性l有穷性 一个算法必须总是在执行有穷步后 结束，且每一步都可在有穷时间内完成；l确定性 算法中的每一个指令比须有明确的 含义，不能有二义性；l可行性 算法中描述的操作都是可通过已经 实现的基本运算、执行有限次实现的；l输入 一个算法应有0个或多个输入；l输出 一个算法应有1个或多个输出。21下一页上一页停止放映算法的设计要求l正确性（Correctness）l可读性（Readability）l健壮性（Robustness）l高效率与低存储量22下一页上一页停止放映正确性（Correctness）l有4个层次： A. 程序不含语法错误； B. 程序对几组输入数据能够得出满 足规格要求的结果； C. 程序对精心选择的、典型的、苛 刻的、带有刁难性的几组输入数据 能够得出满足规格要求的结果； D. 程序对一切合法的输入数据都能 产生满足规格要求的结果。23下一页上一页停止放映可读性（Readability） l算法的第一目的是为了阅读和交流；l可读性有助于对算法的理解；l可读性有助于对算法的调试和修改。24下一页上一页停止放映健壮性（Robustness）l当输入非法数据时，算法也能适 当地作出反应或进行处理；并且 ，处理出错的方法应该是返回一 个表示错误或错误性质的值并中 止程序的执行，以便在更高的抽 象层次上进行处理。25下一页上一页停止放映高效率与低存储量l处理速度快l存储容量小l时间和空间是矛盾的、实际问题 的求解往往是求得时间和空间的 统一、折中。26下一页上一页停止放映算法的描述算法的描述方式（常用的）：自然语言流程图 特定的表示算法的图形 符号 算法描述 伪语言 包括程序设计语言的三 大基本结构及自然语言的一种语言类语言 类似高级语言的语言，例如，类PASCAL、类C语言。27下一页上一页停止放映算法的评价算法评价的标准：时间复杂度和空间复杂度。 时间复杂度 指在计算机上运行该算法所花费的时间。用 “O（数量级）”来表示，称为“阶”。常见的 时间复杂度有：O（1） O（logn） O（n ） O（ n2 ）常数阶 对数阶 线性阶 平方阶 空间复杂度指算法在计算机上运行所占用的存储空间。 度量同时间复杂度。28下一页上一页停止放映时间复杂度举例（a） X：=X+1 ； O（1）（b） FOR I：=1 TO n DO X：= X+1； O（n）（c） FOR I：= 1 TO n DOFOR J：= 1 TO n DO O（ n2 ）X：= X+1；29下一页上一页停止放映二、线性表是指数据元素之间的关系为一一对应 的线性关系的数据结构。例如，一星 期七天的英文缩写表示：（Sun，Mon，The，wed，Thu，Fri，Sat ）是一个线性表，其中的元素是字符 串，表的长度为7。线性表虽然简单，但是应用范围非常 广泛。30下一页上一页停止放映（一）、线性表的逻辑结构定义： 线性表是n（n0）个元素a1,a2,an 的有 限序列;表中每个数据元素,除了第1个和最后1个外, 有且仅有一个前趋元素和后继元素。 形式定义：含有n个数据元素的线性表是一种数据结构，表示为 ： Linear_list=( D , R )其中: D=ai | aiD0,i=1,2,3,n,n 0R=N, N=|ai-1,ai D0 ,i=1,nD是数据元素的有限集合,R是D上逻辑关系的有限集 合。关系N是一个有序偶对的集合。31下一页上一页停止放映相互关系描述1）L的长度为n（n 0），当n为0时，表示是空表； 2）每个元素（除了第1个和最后一个元素外），有唯一的前趋和后继； 3）线性表中各元素间存在着线性关系； 4）均匀性；各元素数据类型必须相同； 5）有序性；各元素是有序的，不可交换次序。32下一页上一页停止放映线性表的基本操作Setnull（L） 置空表 Length（L） 求表长度；求表中元素个数 Get（L，i） 取表中第i个元素（1i n） Prior（L，i） 取i的前趋元素 Next（L，i） 取i的后继元素 Locate（L，x） 返回指定元素在表中的位置 Insert（L，i，x）插入元素 Delete（L，x） 删除元素 Empty（L） 判别表是否为空33下一页上一页停止放映（二）、线性表的顺序存储结构l将表中元素一个接一个的存入一组连续的 存储单元中，这种存储结构是顺序结构。l采用顺序存储结构的线性表简称为“顺序表 ”。顺序表的存储特点是：只要确定了起始 位置，表中任一元素的地址都通过下列公 式得到：LOC（ai）=LOC（a1）+（i-1）*L1i n其中，L是元素占用存储单元的长度。34下一页上一页停止放映线性表元素存储示意图a1a2 . ai .元素序号 内存状态 存储地址12 .i .LOC(a1) LOC(a1)+1.LOC(a1)+(i-1) .35下一页上一页停止放映算法1-1 插入算法算法步骤:step1 将第n至第i个元素后移一个存储位置; step2 将x插入到ai-1之后;step3 表的长度+1。线性表采