数据结构课件(李春葆 第3版)第1章 绪论.ppt

1、第1章绪论、1.2算法及其记述、1.1数据结构是什么、1.3算法分析、本章的总结、1.4数据结构算法计程仪程序、1.1.1数据结构的定义、1.1.2逻辑结构类型、1.1.3存储结构类型、1.1.4数据结构和数据类型、1.1数据结构是什么这是计算机操作对象的总称，也是计算机处理信息的特定符号表示形式。 数据要素：数据(集合)的“个体”，是数据的基本单位。 1.1.1数据结构的定义，数据对象：具有相同性质的若干数据元素的集合。 例如，200402类是学生数据的对象，其中“张三”是数据元素。 数据结构：数据与数据元素的相互关系。 可以看作是相互之间存在某种特定关系的数据元素的集合。 因此，数据结构可

2、视为具有结构的数据元素的集合。 数据结构包括： (1)数据元素之间的逻辑关系，即数据的逻辑结构。 (2)数据要素及其关系在计算机存储器中的存储方式、即数据的存储结构，也被称为数据的物理结构。 (3)添加到该数据中的操作，即数据的运算。 例1.1有表1.1所示的学生表。 该表的数据要素是学生记录查询密码，各数据要素由4个数据项(学号、姓氏、性别、班级编号)构成。 表1.1学生表。 本表中的记录查询密码的顺序反映数据元素之间的逻辑关系，其中每个学生记录查询密码用数字来标识，所述逻辑关系可以表示为、 花括号“”表示元素ai和ai 1之间相邻，即ai在ai 1之前，ai 1在ai之后。 将数据存储在计

3、算机内存中的方法是存储结构。 在c /习语言中，通常以结构体排列和网络链接表这两种方式来实现其存储结构。 收纳学生表的结构体数组Stud为： struct int no； 存储学校编号*/char name8； 保存名称*/char sex2； /*存储性别*/char等级4； 存储班号*/Stud7=1、张斌、男人、9901、5、王佑、女人、9901； 可选地，结构阵列stu的各个元素被顺序存储在存储器中，即，与第i(1i6)个学生相对应的元素stui被存储在与第I-1个学生相对应的元素stui-1之前，其中stui-1紧跟在stui之后。存储学生表的网络链接表的节点类型StudType存储

4、定义为typedefstructstudentnodeintno的/*学校编号*/char name8； 保存名称*/char sex2； /*存储性别*/char等级4； /*存储类编号*/structstudentnode*next； /*保存指向下一个学生的指针*/StudType； 网络链接表的最初的节点地址head，1，张斌，男，9901，8，刘丽，女，9902，3.4，李英，女，9901，2.0，陈华，男，9902，1.2，王奇，男，9901，2.6，董强，男，9902，5， 其中head是指向第一个数据元素的指针。 由学生表构成的网络链接表可以对“学生表”这一数据结构进行一系列的

5、运算。 例如，增加一个学生记录查询密码、删除一个学生记录查询密码、查找性别为“女”的学生记录查询密码、查找班号为“9902”的学生记录查询密码等。 从前面的两个存储结构可以看出，相同的运算根据存储结构的不同而实现过程不同。 例如，在Stud阵列中，在Stud3.no与Stud1.no (与Stud0相比，Stud0.no不是2.0 )相比，在Stud3.no成为2.0之前，可以返回S。 对于以head为首的节点指针的网络链接表，从head指向的节点进行比较，head-no不是2.0，而是从其next得到下一个节点的地址，与下一个节点的no结构域进行比较，直到某个节点的no结构

6、域成为2.0为止，其name结构域为了更准确地说明数据结构，B=(K，r )是包括数据元素k和k上的二元关系的集合r的数据结构。 其中K=ki| 1in，n0 R=rj| 1jm，m0，逻辑结构的描述或表示：其中ki表示集合k中的第I个节点或数据元素。n是k中的节点的数量，特别是如果n=0，k为空集合，因此b也没有结构，有时也可以认为拥有什么结构。 rj表示集合r中的第j个二元关系(以下，全部简称为关系)。 m是空集合，r中的关系的个数，特别是m=0，表示r是相互独立的集合，而在该集合k中的元节点之间没有任何关系。 双位数(x，yK) x是第一节点，y是第二节点。 x是y的直接前驱节点(通常是

7、前驱节点) y是x的直接后续节点(通常是后续节点)。 在某节点没有前驱节点的情况下，如果该节点称为开始节点，在某节点没有后续节点，则将该节点称为终止节点。 说明：表示有方向关系，表示没有(x，y )方向关系。 采用离散数学的表达方法。 例如，例1.1的学生表用二项组表示。 学生表有七个节点，依次用k1k7表示，对应的二项组表示为B=(K，r )。 其中，K=k1，k2，k3，k4，k5，k6，k7 R=r /是r=、另外，例如，k=2，6，3，1，8，1.2，7，4，5，1.0 9，11 r=r1，r2其中，r 1表示行关系，r2表示列关系r1 例如，上述“学生表”的数据结构由下图的格拉夫表示

8、。 学生表数据结构图，(1)线性结构节点间的关系：一对一。 特征：开始节点和终止节点是唯一的，除了开始节点和终止节点以外，其馀节点都只有一个前驱节点，后续节点只有一个。 顺序表是典型的线性结构。 1.1.2逻辑结构类型，(2)树结构节点间的关系： 1对多。 特征：起始节点是唯一的，终止节点不是唯一的。 除了终端节点以外，除了各节点中有一个以上后续节点的开始节点以外，各节点只有一个前驱节点。 /多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多，多对多特征：没有起始节点和终止节点，所有节点可能有多个前驱节点和后续节点。

9、在(2)连锁存储方法、(3)目录索引存储方法、(4)哈希存储方法、1.1.3存储结构类型、(1)逐次存储方法、(1)数据型的高级程序语言中，对于一般在计程仪程序中出现的变量、常数或者式，必须明确地说明它们所属的数据型。 根据类型，可获得的值的范围会不同，可获得的操作也不同。 数据类型是值的集合和为此集合定义的一组操作的总称。 1.1.4数据结构和数据类型，例如C/C的int是整数数据类型。 这是所有整数的集合(在1.6二进制位计算机上是32767的整数)和相关的整数运算(例如、等)。 (2)所谓抽象数据类型抽象数据类型(Abstract Data Type简称ADT )，是指用户在进行软件系统

10、设计时从问题的数学模型中抽象出的逻辑数据结构和逻辑数据结构上的运算，不考虑计算机的具体存储结构和运算的具体实现算法。 抽象数据类型=数据元素集合抽象运算，例如抽象数据类型的多个定义： ADT Complex数据对象： D=e1，e2|e1，e2全部为实数数据关系： R1=| e1为多个实数部分，e2为多个虚数部分，e1e2i，基本运算： assign complex (whign 打印机(% dn，n )、华中科技高等院校试题、(2)描述二语音exam2() y=0的x=5/y； 打印机(“% d，%dn”，x，y； 试问这两种记述不能满足算法的特征，违反了哪个特征的解： (1)算法是死亡循环

11、，违反了算法的贫困特征。 (2)算法包含零除法错误，违反了算法的可行性特征。 1.2.2算法描述，本说明书采用c /习语言描述算法。 说明：参照运算符“tmp=x； x=y； y=tmp； 注意： a和b的值不交换。因此，为了利用指针返回波形残奥节计量器的值，需要将上面描述的函数映射到void swap2(int *x，int *y) int tmp； tmp=*x； 将/*x的值设为tmp */* x=* y； /*x表示的值变更为* y */* y=tmp/* y表示的值tmp */swap2(/* a是通常的整数变量*/int /*b是a的参照变量*/在这里说明b变量是变量a的参照，b也

12、等于4，然后这两个变量同步地a变化时b也同步变化，b变化时a也同步变化。 难点，难点，难点() int a=2； int /*输出： a=4，b=4*/，引用在函数形式残奥仪表中经常使用，如果采用引用形式残奥仪表，则在调用函数时将波形残奥仪表的更改还原为实际的残奥仪表。 例如，void swap (其中y=tmp是执行语句swap(a，b )时，a和b的值交换的函数。 作成例1.3算法，读入3个整数x、y、z的值，要求从大到小的输出。 解：依次输入x、y、z三个整数，通过比较进行交换后，变为xyz，输出x、y、z。 在算法中，需要考虑尽量减少这些个的3个要素的比较和移动，下面的算法在最坏的情况

13、下只进行3次比较和7次移动。 voidsdescending()printf(x (输入x，y，scanf(%d，%d，1.3算法分析，1.3.1算法时间复杂度分析，1.3.2算法空间复杂度分析，一个算法是控制结构(顺序、分支和循环三种)和原操作(固有数据类型的操作) 1.3.1算法时间复杂度分析、控制语句1原操作、控制语句n原操作、一个算法、相同的问题能够由多个算法实现。 如何比较算法的执行效率呢？ 由于算法描述的语言不同，算法执行的环境不同，所以绝对不能用执行时间进行比较，但是为了容易比较相同问题的不同算法，对于研究的问题一般从算法中选择基本运算的原操作(以下，仅将基本运算的原操作称为基本

14、运算)。 算法的执行时间是基本运算所需的时间与其运算次数(也称为频度)的积。 一般被视为算法的基本运算的是最深循环中的句子。 在一个算法中，进行基本运算的次数越少，其执行时间也相对少的基本运算次数越多，其执行时间也相对多。 因此，通常将算法中包含的基本运算次数的多寡进行算法的时间复杂度，即，一个算法的时间复杂度是其算法的基本运算次数。 算法中的基本运算次数T(n )是具有问题规模n的函数f(n )，t (n )=o (标记为f(n ) )，记号“o”读为“大o”，表示伴随问题规模n的增大的算法执行时间的增加率和f(n )的增加率相同。 关于“o”的形式，如果f(n )是正整数n的函数，则T(n)=O(f(n ) )在nn0时仅求|T(n)|M|f(n)|、即T(n )的最上位，忽略其下位项和常数系数，从而