数据基础结构概念

n个元素的数组向左循环移动

i个位置有许多应用会调用这个问题的算法，因此，要求有较高的时间性能和空间性能解法1：先将数组中的前

i

个元素存放在一个临时数组中，再将余下的

n–i

个元素左移

i个位置，最后将前

i

个元素从临时数组复制回原数组中后面的

i

个位置。共需要移动

i+(n–i)+i=i+n

次数组元素，但使用了

i

个额外的存储单元【数组循环左移问题】将一个具有

n个元素的数组向左循环移动

i个位置有许多应用会调用这个问题的算法，因此，要求有较高的时间性能和空间性能解法2：先设计一个函数将数组向左循环移动1个位置，然后再调用该算法

i次。只使用了1个额外的存储单元，但共需要移动

i×n

次数组元素算法的作用【数组循环左移问题】将一个具有

n个元素的数组向左循环移动

i个位置有许多应用会调用这个问题的算法，因此，要求有较高的时间性能和空间性能解法3：将这个问题看作是把数组AB转换成数组BA（A代表数组的前

i个元素，B代表数组中余下的

n–i

个元素），先将A置逆得到A-1B，再将B置逆得到A-1B-1，最后将整个A-1B-1置逆得到(A-1B-1)-1=BAabcdefgcbagfeddefgabc共交换

次数组元素，只使用了1个用来交换的临时单元算法的作用【排序问题】对整型数组r[n]进行非降序排列。【算法】有很多排序算法可以解决这个问题，不同排序算法的运行时间有很大差别，起泡排序和快速排序算法在不同数据规模的运行时间如下表所示，随着数据规模的增长，起泡排序和快速排序运行时间的差别越来越大。算法的作用1-2-4本课程讨论的主要内容v第一章绪论数据模型数据模型数值问题：数学方程非数值问题：表、树、图等数据结构问

题想法抽象模型基本思路算

法数据表示数据处理程

序程序语言编程环境例1-6

为百元买百鸡问题抽象数据模型（《算经》）【问题】鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？x+y+z=1005×x+3×y+z/3=1000≤x≤200≤y≤330≤z≤100【想法——数据模型】设

x、y

和

z

分别表示公鸡、母鸡和小鸡的个数，则有如下方程组成立：数据模型例1-7为学籍管理问题抽象数据模型如何实现增、删、改、查等功能？各表项之间是什么关系？数据表示——存储学籍表表结构学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………199701021998032819971116……抽象数据模型例1-8为人机对弈问题抽象数据模型如何实现对弈？计算机的操作对象？各格局之间是什么关系？数据表示——存储对弈树树结构抽象数据模型例1-9为七巧板涂色问题抽象数据模型如何实现涂色？如何表示区域之间的邻接关系？数据表示——存储七巧板图结构BDAFECG抽象ABEDCFG数据模型讨论什么（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；（4）常用数据处理技术：查找技术、排序技术等。（2）数据的存储结构：如何将表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；本课程主要讨论非数值问题的数据组织和处理数据结构和算法的作用对于许多实际的问题，写出一个正确的算法还不够，如果这个算法在规模较大的数据集上运行，运行效率就成为一个重要的问题对问题抽象出不同的数据模型问

题想法抽象模型基本思路算

法数据表示数据处理程

序程序语言编程环境对不同求解方法的抽象描述不同的算法效率不同对数据模型的不同表示（存储）1-3数据结构的基本概念v第一章绪论数据结构数据元素关系数据结构什么是数据？什么是数据元素？什么是结构？关系指的是什么？学什么？数据结构抽象数据类型如何描述与实现数据结构？1-3-1数据结构v第一章绪论理解数据数据：所有能输入到计算机中并能被程序识别和处理的符号集合数据数值数据：整数、实数等非数值数据：图形、图象、声音、文字等数据是程序的处理对象，严格来说，计算机=数据处理机学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………200601022006032820051116……数据是程序的处理对象理解数据数据：所有能输入到计算机中并能被程序识别和处理的符号集合数据元素：数据的基本单位，在程序中作为一个整体进行考虑和处理数据项：构成数据元素的最小单位学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………199701021998032819971116……数据元素数据项通常情况下，数据元素具有相同个数和类型的数据项理解数据元素一般来说，能独立、完整地描述问题世界的一切实体都是数据元素数据结构数据元素关系数据元素是讨论数据结构时的着眼点学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………199701021998032819971116……学籍管理问题，数据元素是什么？表项抽象理解数据元素数据结构数据元素关系人机对弈问题，数据元素是什么？格局抽象理解数据元素数据元素是讨论数据结构时的着眼点一般来说，能独立、完整地描述问题世界的一切实体都是数据元素数据结构数据元素关系七巧板涂色问题，数据元素是什么？区域DAFECGB抽象ABEDCFG理解数据元素数据元素是讨论数据结构时的着眼点一般来说，能独立、完整地描述问题世界的一切实体都是数据元素数据结构：相互之间存在一定关系的数据元素的集合按照视点的不同，分为逻辑结构和存储结构数据的逻辑结构：数据元素之间逻辑关系的整体是否基于内存关联方式或邻接关系取决于实际问题理解逻辑结构如何理解逻辑关系？数据结构：相互之间存在一定关系的数据元素的集合数据的逻辑结构：数据元素之间逻辑关系的整体数据的逻辑结构在形式上可定义为一个二元组：

Data_Structure=(D,R)其中D是数据元素的有限集合，R是D上关系的集合Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={(A,B),(A,E),(A,F),(B,C),(B,D),

(C,D),(D,E),(D,G),(E,F),(E,G)}ABEDCFG理解逻辑结构数据结构从逻辑上分为四类：（2）线性结构：数据元素之间是一对一的线性关系（3）树结构：数据元素之间是一对多的层次关系（4）图结构：数据元素之间是多对多的任意关系（1）集合：数据元素之间没有关系线性关系：线性结构非线性关系：树结构和图结构

理解逻辑结构数据结构：相互之间存在一定关系的数据元素的集合数据的存储（物理）结构：数据及其逻辑结构在计算机中的表示存储结构实质上是内存分配，具体实现时依赖于计算机语言计算机语言如何进行内存分配？在变量定义时进行内存分配内存数据元素逻辑关系算

法想

法数据表示数据处理理解存储结构通常有两种存储结构：（1）顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示redgreenblue……起始地址例：(red,green,blue)下标理解存储结构（2）链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示020002080300redgreenblue02000300∧………起始地址地址通常有两种存储结构：（1）顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示例：(red,green,blue)理解存储结构下标逻辑结构和存储结构的关系数据的逻辑结构是用户视图，面向问题数据的存储结构是实现视图，面向计算机

问

题想法抽象模型基本思路算

法数据表示数据处理程

序程序语言编程环境逻辑结构存储结构存储结构一种数据的逻辑结构可以采用多种存储结构来实现，采用不同的存储结构，其数据处理的效率往往是不同的数据本身的构成方式数据在内存的存储表示1-3-2抽象数据类型v第一章绪论理解数据类型什么是数据类型呢？数据类型：一组值的集合以及定义于这个值集上的一组操作inta,b;floatx,y;x=1234567.123;x=x%y;a=10000000000000;a=a%b;数据类型是数据的一种属性，包含三层含义：分配存储空间—存储格式，值的集合—取值范围，运算集合—进行运算。理解抽象水果地图抽象：抽出问题本质的特征而忽略非本质的细节1+1=22+3=5x+y=z抽象的好处是什么？算术运算代数运算在一个更高的层次上思考问题抽象数据类型把什么抽象掉了呢？抽象数据类型：一个数据模型以及定义在该模型上的一组操作

抽象数据类型问

题想法抽象模型基本思路逻辑结构数据模型=数据的逻辑结构强调有哪些数据元素，数据元素之间满足什么逻辑关系，基于数据模型有哪些基本操作抽象数据类型不考虑数据项，把具体的数据类型抽象掉了学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………199701021998032819971116……抽象抽象数据类型只考虑数据的逻辑结构和基本操作抽象数据类型抽象数据类型把什么抽象掉了呢？抽象数据类型：一个数据模型以及定义在该模型上的一组操作

如何实现抽象数据类型（abstract

data

type，简称ADT）呢？实现层（C、…）●自定义数据类型●自定义函数实现层（C++、Java、…）●成员变量●成员函数类抽象层●数据模型（逻辑结构）●操作集合（a）定义——ADT定义设计层●数据表示（存储结构）●算法（b）设计——数据结构设计（c）实现——程序语言实现抽象数据类型如何定义抽象数据类型呢？ADT

抽象数据类型名

数据元素之间逻辑关系的定义

输入：执行此操作所需要的输入功能：该操作将完成的功能输出：执行该操作后产生的输出

……

……endADT

DataModelOperation操作1操作2操作n操作接口（函数原型）抽象数据类型1-4算法的基本概念v第一章绪论见识算法图灵奖与算法Hoare在26岁发明了闻名于世的快速排序算法；Ronald、Shamir和Adleman发明了国际上最具影响力的公钥密码算法RSA；Knuth编著的《程序设计的艺术》奠定了数据结构与算法领域的主要内容；Floyd发明了求解多源点最短路径的Floyd算法以及堆结构；Karp在网络流和组合优化问题领域都发明了许多高效算法；

Hopcroft和他的学生Tarjan在数据结构和算法方面有众多创造性贡献；姚期智（Chi-ChihYao）发明了伪随机数的生成算法以及加密/解密算法；Sutherland发明的图形图像算法改善了屏幕刷新的文件显示；Dijkstra发明了单源点的最短路径算法Dijkstra算法；Wilkinson在数值线性代数方面发现很多有意义的算法；Blum发现了著名的算法设计技术——分支限界法……算法是计算机科学的基石三大学报文章概览见识算法算法及算法的特性学什么？算法的描述方法1-4-1算法及算法的特性v第一章绪论算法的起源算法的中文名称出自《周髀算经》（西周~秦汉）张仓《九章算术》创立的机械化算法体系今有三分之一，五分之二。问合之得几何？答曰：十五分之十一。又有三分之二，七分之四，九分之五。问合之得几何？答曰：得一、六十三分之五十。又有二分之一，三分之二，四分之三，五分之四。问合之得几何？答曰：得二、六十分之四十三。合分（分数相加）术（算法）曰：母（分母）互乘子（分子），并以为实（被除数），母相乘为法（除数），实如（除以）法而一。不满法者，以法命之，其母同者，直相从（加）之。欧几里得《几何原本》创立的逻辑演绎体系世界数学的两大体系算法的英文名称来自于波斯数学家阿勒·霍瓦里松《代数对话录》

（公元825年）Algorithm在Webster'sNewWorldDictionary（1957版）中尚未出现Algorithm——算法；Logarithm——对数；Algorism——算术欧几里得算法被人们认为是史上第一个算法算法的起源张仓《九章算术》创立的机械化算法体系欧几里得《几何原本》创立的逻辑演绎体系世界数学的两大体系算法的定义输入操作步骤：

1.………2.………3.………算法

:是对特定问题求解步骤的一种描述，是指令的有限序列算法不是问题的答案，而是解决问题的操作步骤1.柿子切块，鸡蛋加适量盐搅拌2.锅里放油3.把鸡蛋倒进去炒熟4.加入葱花5.把柿子放进去放少许盐和味精6.翻炒几下出锅装盘木须柿子的做法：输出算法的操作步骤应该满足什么要求？（1）有穷性：总是在执行有穷步之后结束，且每一步都在有穷时间内完成每一条指令都不是无限循环！有穷不是数学意义上的概念！算法的特性输入操作步骤：

1.………2.………3.………输出（1）有穷性：总是在执行有穷步之后结束，且每一步都在有穷时间内完成（2）确定性：每一条指令必须有确切的含义，相同的输入得到相同的输出上下文无关算法的操作步骤应该满足什么要求？算法的特性输入操作步骤：

1.………2.………3.………输出（3）可行性：操作步骤可以通过已经实现的基本操作执行有限次来实现（1）有穷性：总是在执行有穷步之后结束，且每一步都在有穷时间内完成（2）确定性：每一条指令必须有确切的含义，相同的输入得到相同的输出机器可执行算法的操作步骤应该满足什么要求？算法的特性输入操作步骤：

1.………2.………3.………输出步骤1：找出

m的所有质因子步骤2：找出

n的所有质因子步骤3：从第1步和第2步得到的质因子中找出所有公因子步骤4：将找到的所有公因子相乘，结果即为

m和

n的最大公约数【想法】将这两个自然数分别进行质因数分解，然后找出所有公因子并将这些公因子相乘。例如，48=2×2×2×2×3，36=2×2×3×3，公因子有2、2、3，因此，48和36的最大公约数为2×2×3=12。例1-12设计算法求两个自然数的最大公约数。【算法】设两个自然数是m和n，算法如下：满足算法的特性吗？如何找出所有质因子？如何找出所有公因子？质因数分解尚未找到多项式时间算法不满足确定性、有穷性！算法的特性好算法的特性（1）正确性：算法能满足具体问题的需求，即对于任何合法的输入，算法都会得出正确的结果。一个算法满足什么特性才能称之为好算法呢？（4）抽象分级：用合适的抽象分级组织表达算法的思想，

启发式规则7±2。（2）健壮性：算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。（3）可理解性：算法容易理解和实现。（5）高效性：具有较短的执行时间并占用较少的辅助空间。米勒原则：人类的短期记忆能力一般限于一次记忆

5～9

个对象1-4-2算法的描述方法v第一章绪论欧几里得算法辗转相除求两个自然数的最大公约数（古希腊（公元前300年））m

n

r35252510105【想法——基本思路】设两个自然数为m和

n，欧几里得算法的基本思想是将

m和

n辗转相除直到余数为01050自然语言描述算法【算法——自然语言描述】设两个自然数为m和

n，欧几里得算法如下：步骤1：将m除以n得到余数r；步骤2：若r等于0，则n为最大公约数，算法结束；否则执行步骤3；步骤3：将n的值放在m中，将r的值放在n中，重新执行步骤1；优点：容易理解；缺点：冗长、二义性使用方法：粗线条描述算法思想；注意事项：避免写成自然段辗转相除求两个自然数的最大公约数（古希腊（公元前300年））流程图描述算法优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次【算法——流程图描述】设两个自然数为m和

n，算法为开始结束r=m%nr=0m=nn=r输出nY辗转相除求两个自然数的最大公约数（古希腊（公元前300年））程序语言描述算法【算法——程序语言描述】设两个自然数为m和

n，算法为优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数辗转相除求两个自然数的最大公约数（古希腊（公元前300年））伪代码描述算法什么是伪代码呢？伪代码：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。伪代码有标准吗？伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化了描述算法的不必要的技术细节伪代码被称为“算法语言”或“第一语言”【算法——伪代码描述】设两个自然数为m和

n，算法为优点：表达能力强，抽象性强，

容易理解，容易实现使用方法：7±2伪代码描述算法辗转相除求两个自然数的最大公约数（古希腊（公元前300年））米勒原则：人类的短期记忆能力一般限于一次记忆

5～9

个对象输入：两个自然数m和n输出：m和n的最大公约数1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}只描述子函数；省略主函数和头函数伪代码描述算法辗转相除求两个自然数的最大公约数（古希腊（公元前300年））【算法——伪代码描述】设两个自然数为m和

n，算法为输入：两个自然数m和n输出：m和n的最大公约数1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;1-5算法分析v第一章绪论算法分析算法设计：面对一个问题，如何设计一个高效的算法算法分析：对已设计的算法，如何评价或判断其优劣检验评估指导改进如何评价算法？易读性健壮（容错）性可维护性可扩展性……效率（速度）——算法的核心和灵魂算法分析算法的时间复杂度学什么？算法的空间复杂度算法分析实例1-5-1算法的时间复杂度v第一章绪论度量算法效率如何度量算法的效率呢？缺点：（1）编写程序实现算法将花费较多的时间和精力

（2）所得实验结果依赖于计算机的软硬件等环境因素

事后统计（定量分析）：将算法实现，测算其时间和空间开销事前分析（定性分析）：对算法所消耗资源的一种估算方法时间空间对估算方法有什么要求呢？能够刻画效率；与语言环境无关；具有一般性……时间复杂度算法的执行时间＝每条语句执行时间之和执行次数×执行一次的时间指令系统、编译的代码质量单位时间每条语句执行次数之和=for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本语句的执行次数问题规模：输入量的大小基本语句：执行次数与整个算法的执行次数成正比的操作指令注意到，几乎所有算法，对于规模更大的输入需要运行更长的时间运行算法所需要的时间

T

是问题规模

n

的函数，记作

T(n)如何表示算法的运行时间函数呢？算法的运行时间=基本语句的执行次数如何计算算法中基本语句的执行次数呢？时间复杂度：当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶——关注的是增长趋势问题规模可以是多个变量

多元函数时间复杂度大O记号定义1-1若存在两个正的常数

c和

n0，对于任意

n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))。n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)T(n)和f(n)具有相同的增长趋势，T(n)的增长至多趋同于函数f(n)的增长定理1-1：若T(n)=amnm+am-1nm-1+

+a1n+a0是一个m次多项式，则T(n)=O(nm)关注增长率——忽略所有低次幂和最高次幂的系数大O记号时间复杂度是一种估算技术（信封背面的技术）Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)常见的时间复杂度：多项式时间，易解问题指数时间，难解问题时间复杂度是在不同数量级的层面上比较算法大O记号估算的局限冰雹猜想（HailstoneSequence，角谷猜想，3n+1问题）1.输入一个正整数n；2.如果n

等于1，结束算法；3.如果n

是奇数，则n

变为3n+1，否则n

变为n/2；4.重新执行步骤2；所有测试的正整数都可以终止，但是至今没有人证明对所有的正整数该过程都能够终止，而且至今没有人能够分析这个简单算法的时间复杂度例如：n=9，有{9,

28,

14,

7,

22,

11,

34,

17,

52,

26,

13,

40,

20,

10,

5,

16,

8,

4,

2,

1}例如：n=27，经过77步变换到达顶峰值9232，又经过32步变换到达谷底值11-5-2算法的空间复杂度v第一章绪论空间分析算法在运行过程中需要哪些存储空间？（1）输入/输出数据占用的空间取决于问题，与算法无关intCommonFactor(intm,intn){}voidBubbleSort(intr[],intn){ }voidEquation(doublea,doubleb,doublec,double*p,double*q){}（2）算法本身占用的空间与算法相关，大小固定intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}（1）输入/输出数据占用的空间取决于问题，与算法无关空间分析算法在运行过程中需要哪些存储空间？（3）执行算法需要的辅助空间与算法相关，体现效率除算法本身和输入输出数据所占用的空间外，算法临时开辟的存储空间空间复杂度：算法在执行过程中需要的辅助空间数量空间复杂度也是问题规模的函数，通常记作：S(n)=O(f(n))（2）算法本身占用的空间与算法相关，大小固定（1）输入/输出数据占用的空间取决于问题，与算法无关空间分析算法在运行过程中需要哪些存储空间？空间复杂度voidBubbleSort(intr[],intn){ intj,temp,bound,exchange=n; while(exchange!=0){

bound=exchange;exchange=0;for(j=1;j<bound;j++)if(r[j]>r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}}}voidMerge(intr[],ints,intm,intt){intr1[n];inti=s,j=m+1,k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i<=m)r1[k++]=r[i++];while(j<=t)r1[k++]=r[j++];for(i=s;i<t;i++)r[i]=r1[i];}O(1)O(n)就地（原地）算法：空间复杂度为O(1)，辅助空间是常数1-5-3算法分析实例v第一章绪论非递归算法例1++x;例2for(i=1;i<=n;++i)++x;O(1)常数阶O(n)线性阶例3for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;O(n2)平方阶例4for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}O(n3)立方阶例5for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;分析的策略是从内部（或最深层部分）向外展开例6for(i=1;i<=n;i=2*i) ++x;O(log2n)对数阶分析的策略是设其执行次数为T(n)，则有2T(n)≤n，即T(n)≤log2nO(n2)T(n)=O(log2n)=O(logn)非递归算法递归算法分析的策略是根据递归过程建立递推关系式并求解（求和表达式）例7分析递推式

的时间复杂度假定

n=2k各种情况基本语句的执行次数是否只和问题规模有关？例8在一维整型数组A[n]中顺序查找与给定值k相等的元素

intFind(intA[],intn,intk)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }如果算法的时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况最好情况：1次，O(1)最坏情况：n

次，O(n)平均情况：n/2次，O(n)基本语句？最好情况：不能代表算法的效率，当出现概率较大时分析最坏情况：最坏能坏到什么程度，实时系统需要分析平均情况：已知输入数据分布情况，通常假设等概率分布如果算法的时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况各种情况如何定义平均？2-1引言v第二章线性表学籍管理问题学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………200201022003032820031116……抽象学籍管理问题，数据元素是什么？元素之间的关系？完成什么功能？二维表线性结构Page01工资管理问题工资管理问题，数据元素是什么？元素之间的关系？完成什么功能？职工号000826000235000973…姓名王一梅李明郑浩…性别女男男…基本工资348038602850…岗位津贴190024001600…业绩津贴138016001050…抽象所有二维表抽象的数据模型都是线性结构吗？研究如何存储线性结构，并实现增、删、改、查等基本操作。二维表线性结构约瑟夫环问题【问题】约瑟夫环问题由古罗马史学家约瑟夫（Josephus）提出，他参加并记录了公元66—70年犹太人反抗罗马的起义。在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。这些起义者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。【想法——数据模型】设

n(n>0)个人围成一个环，n个人的编号分别为1，2，…，n，从第1个人开始报数，报到

m时停止报数，报

m的人出环，再从他的下一个人起重新报数，报到

m时停止报数，报m的人出环，……，如此下去，直到所有人全部出环为止。对于任意给定

n和

m，求

n个人出环的次序。如何存储这种环状线性结构，并求解约瑟夫环的出环次序呢？12354出环的顺序是：31524例如，n=5,m=3，则约瑟夫环问题随处可见的线性结构关于线性结构什么是线性结构？在逻辑上有什么特点？如何存储线性结构？在不同的存储结构上，如何实现插入、删除、查找等基本操作？在不同的存储结构上，基本操作的时空性能如何？2-2线性表的逻辑结构v第二章线性表线性表的定义线性表的逻辑特征线性表的抽象数据类型定义学什么？2-2-1线性表的定义v第二章线性表线性表的定义线性表（表）：n（n≥0）个具有相同类型的数据元素的有限序列（a1,a2,…,ai,…,an）线性表的长度：线性表中数据元素的个数空表：长度等于零的线性表ai（1≤i≤n）称为数据元素下角标

i表示该元素在线性表中的位置或序号线性表的逻辑特征1.数据元素个数的有限性a1ai-1aiana22.数据元素类型的相同性3.数据元素类型的抽象性4.相邻数据元素的序偶性，且a1无前驱，an无后继序偶：两个具有固定次序的元素组成的序列，记作(a，b)，且称a是b

的前驱，b是a

的后继L1=(1,3,5,7,9)L2=('a','e','i','o','u')L3=((Li,8,3),(Wang,7,4),(Zhang,5,5))不确定、任意2-2-2线性表的抽象数据类型定义v第二章线性表线性表的抽象数据类型定义ADTListDataModelOperationendADT线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系InitList：表的初始化，建一个空表CreateList：建立具有n个元素的线性表DestroyList：销毁表，释放表所占用的存储空间Length：求表的长度Get：在表中取序号为i

的数据元素Locate：在线性表中查找值等于x

的元素Insert：在表的第i

个位置处插入一个新元素xDelete：删除表中的第i

个元素Empty：判断表是否为空InitList

输入：无功能：表的初始化，建一个空表输出：无CreateList

输入：n个数据元素

功能：建立一个线性表

输出：具有n个元素的线性表DestroyList输入：无功能：销毁表，释放表所占用的存储空间输出：无Locate输入：数据元素x

功能：在线性表中查找值等于x

的元素输出：查找成功返回x

在表中的序号，否则返回0线性表的抽象数据类型定义（a1,a2,…,ai,…,an）Get输入：元素的序号i

功能：在表中取序号为i

的数据元素输出：若i合法，返回序号为i的元素值Length

输入：无功能：求表的长度输出：表中数据元素的个数Insert输入：插入位置i，待插x功能：在表的第i

个位置处插入一个新元素x输出：若插入成功，表中增加一个新元素；否则给出失败信息Delete

输入：删除位置i功能：删除表中的第i

个元素输出：若删除成功，表中减少一个元素；否则给出失败信息Empty输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0线性表的抽象数据类型定义（a1,a2,…,ai,…,an）（1）线性表的基本操作根据实际应用而定（2）复杂的操作可以通过基本操作的组合来实现（3）对不同的应用，操作的接口可能不同2-3线性表的顺序存储结构及实现v第二章线性表顺序表的存储结构顺序表的实现学什么？顺序表的类定义、构造函数、析构函数顺序表的判空、取长度操作：Empty、Length顺序表的查找操作：Get、Locate顺序表的插入、删除操作：Insert、Delete2-3-1顺序表的存储结构v第二章线性表顺序表的存储方法顺序表（向量）：线性表的顺序存储结构某些内存单元可能是空吗？例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素用什么属性来描述顺序表？342367434存储空间的起始位置顺序表的容量（最大长度）顺序表的当前长度例：（34,23,67,43）Page03顺序表的存储方法顺序表（向量）：线性表的顺序存储结构0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

长度数组的长度MaxSize线性表的长度lengthMaxSize≥length（a1,

…,ai-1

,ai,…,an）Page04顺序表的存储方法顺序表（向量）：线性表的顺序存储结构存取访问0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

长度（a1,

…,ai-1

,ai,…,an）如何求得任意元素的存储地址？cLoc(ai)Loc(a1)Loc(ai)=Loc(a1)+(i-1)×cPage07存取时间是O(1)随机存取2-3-2顺序表的实现v第二章线性表顺序表的实现——类定义InitList：表的初始化，建一个空表CreateList：建立具有n个元素的线性表DestroyList：销毁表，释放表所占用的存储空间Length：求表的长度Get：在表中取序号为i

的数据元素Locate：在线性表中查找值等于x

的元素In