ds-1《数据结构C++版》及练习答案课件

1、数 据 结 构 徐 虹/Jxgl/HomePage/Default.asp说明总学时： 64(学时)= 50（课时）+ 14（实验）行课时间:第 1 13周周学时:平均每周 4 学时上机安排待定考试时间：课程结束上机安排13级计算机数媒专业1、2班指导老师:时间：5-11周 地点:计算机学院机房教材与参考书王红梅, 胡明, 王涛. 数据结构（C+版）第2版. 清华大学出版社万健，数据结构实用教程（C+版），电子工业出版社严蔚敏，数据结构，清华大学出版社Clifford A. Shaffer, 数据结构与算法分析，电子工业出版社Sartaj Sahni, 数据结构、算法与应用,机械工业出版社严蔚

2、敏，数据结构题集，清华大学出版社 3.课程的内容与组织 1.数据结构的研究对象课程简介数据是现实世界的数字化研究数据在计算机中的表示、关联、存储与处理方法 2.课程的性质与定位 数据组织与结构是计算机科学最基本内容，是人才信息素质的脊梁培养数据抽象能力，算法设计能力以及构造算法思维方法基本概念、基本结构、基本技术三层次用C+描述算法，突出算法实质例题、习题、典型题例、实习范例、课程设计全方位训练2. 数据结构课程的性质与地位 由于数据是计算机处理的对象，使用计算机的过程就是对数据进行加工处理的过程，因而数据的组织与结构被确立为计算机科学中最为基本内容。80年代初, 数据结构课程就已成为国内计算

3、机专业教学计划中的核心课程。 人类解决问题的思维方式可分为推理方式和算法方式两大类。推理方式凭借公理系统思维方法通过数学训练得到。算法方式则是凭借构造性思维，从具体操作规范入手，通过操作过程的构造实施来解决特定问题。 数据结构的学习过程，是算法构造性思维方法的训练过程，技能培养的重要程度不亚于知识传授。本门课程教学难点在于让学生理解、习惯算法构造思维方法。培养学生的数据抽象能力，算法设计能力以及创造性思维方法，才能够举一反三、触类旁通，从而达到应用知识解决复杂问题的目的。 数据结构是重要的专业基础课，是计算机科学的核心课程，是计算机理论与技术的重要基石。 该课程在大学二年级下学期开设，具有承上

4、启下的重要作用，既要对前一年学习的软件技术进行总结提高，又要为后续专业课程提供基础。它贯通始终，是计算机科学与技术人才素质培养框架中的中坚课程，对学生的软件开发能力培养有至关重要的作用，将为学生今后的专业生涯打下牢固基础。 2.数据结构课程的性质与地位 4. 成绩计算平时成绩:30% 考勤+作业+半期考试+上机+实验报告+课堂表现考试成绩:70%学生的考核资格按下述原则审查： 学生有以下情况之一者，不能参加课程成绩考核，该课程的考核成绩以零分处理。在确定学籍处理、授予学士学位时，该门课程以考核不及格门次参加统计。全期旷课累计达该课程教学时数五分之一（含五分之一）以上者；全期缺交该课程任课教师布

5、置作业三分之一（含三分之一）以上者；或全期所交该课程作业，虽达到任课教师布置作业三分之二以上，但所交作业的准确度、整洁度有二分之一不合格者；全期缺做该课程实习、实验或缺交实习、实验报告达三分之一（含三分之一）以上者；或全期参加该课程实习、实验，所交实习、实验报告都在三分之二以上，但有二分之一不合格者；未经批准或未办理选课手续，擅自修读该门课程者。目 录 第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串、数组和广义表 第五章：树 第六章：图 第七章：查找 第八章：内部排序程序设计的实质是什么?数据表示：将数据存储在计算机（内存）中数据处理：处理数据，设计方案（算法）数据结构问题起源于程

6、序设计 利用计算机求解问题的一般过程? 计算机不能分析问题并产生问题的解决方案，必须由人来分析问题，确定问题的解决方案，编写程序，然后让计算机执行程序最终获得问题的解。 高等数学理论力学线形代数001,003, 002, 004, LS002,001, 003特点：计算机按某个特定的要求进行查询.处理对象之间存在一种简单的线形关系,这类模型可以称为简单的线形数据结构.按书名排列樊映川华罗庚栾汝书001,003,004,按作者排列按索引号排列例2: 计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的

7、,从一个棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程. *(a) 棋盘格式示例(b)井字棋对弈树的局部*例3 七巧板涂色问题 如何表示区域之间的邻接关系？结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构.数据结构定义: 数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科.数据结构的地位 数据结构是计算机科学中一门综合性的专业基础课。可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心

8、课程。1. 2 基本概念数据（Data) 客观事物的符号表示，能输入到计算机中并被计算 机中程序处理的符号的总称。 数据元素 (Data element) 数据的基本单位，可由数据项组成。 数据类型 (Data Type) 是和数据结构密切相关的一个概念，在高级语言中，用以刻画（程序）操作对象的特性。是一个值的集合和定义在这个值集上的一组操作的总称。集合线性树图数据结构的二元组表示：Data_Structure = (D, S)其中：D是数据元素的有限集，S是D上关系的有限集数据结构类型数据的逻辑结构数据结构的形式定义：Data_Structure=D,S,P 其中： D是数据元素的有限集 S

9、是上下关系的有限集 P是对数据对象的基本操作数据的物理结构（存储结构），数据结构基本操作的实现；数据的存储结构：位、元素和数据域数据结构的存储形式有：顺序存储链式存储逻辑结构例三维实体造型问题左图的机械零件可以分解成三个基本的实体模型通过布尔运算+和-操作得到右图构成了一个树型的数据结构，每一个节点为一个基本实体模型或通过布尔运算得到的复合实体模型逻辑结构例地图表示问题左图的地图经抽象可以得到右图的结构右图构成了图状的数据结构数据的物理结构例分别用顺序结构和链式结构来存储数列“10,20,30,40”数列的顺序存储结构数列的链式存储结构逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，

10、是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。 本书讨论非数值问题的数据组织和处理，主要内容如下：（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；（2）数据的存储结构：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；（4）常用数据处理技术：查找技术、排序技

11、术、索引技术等。数据类型综述数据类型可以分为原子类型值不可以分解结构类型值由若干成分按某种结构组成。抽象数据类型（ADT） ADT是一个值的集合和定义在这个值集上的一组操作的总称。包括：原子类型、固定聚合类型和可变聚合类型。是与具体计算机内部表示和实现方式无关的数据类型是由一个逻辑上的数学模型以及定义在该模型上的一组操作构成可以用三元组定义 (D, S, P)D是数据对象S是D上的关系集P是对D的基本操作集1. 3 抽象数据类型的表示与实现基本概念抽象数据类型在软件系统开发的全过程中，对客观现实中存在的事物，存在三个观察层面应用层是用户通过物理观察得到的客观事物的视图，是可以用自然语言描述的，

12、或用图形、图像、音频、视频等物理量表达的在概念层次上的数据。逻辑层（抽象层）是从应用层次抽象出来的数据视图，利用抽象数据类型进行形式化描述。实现层明确地表示出了数据的组织与存储结构，并用某种具体的程序设计语言进行代码实现。抽象数据类型 在设计ADT时，把ADT的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合，一方面，ADT的使用者依据这些定义来使用ADT，即通过操作集合对该ADT进行操作；另一方面，ADT的实现者依据这些定义来完成该ADT各种操作的具体实现。 抽象数据类型例 ADT Set/ 集合的抽象数据类型 数据对象：D ai | aiElemType, i= 1,

13、 2, ., n, n 0 数据关系：R = aiaj | ai,ajD 基本操作：Init() 操作结果：构造一个空的集合。Destroy()操作结果：销毁集合。IsEmpty() 操作结果：判断集合是否为空，如为空，则返回TRUE；否则返回FALSE。 Insert(e) 操作结果：在集合中加入一个元素。如元素已存在，返回FALSE；否则返回TRUE。 Remove(e) 操作结果：在集合中移除一个元素。如元素存在，则返回TRUE；否则返回FALSE。 IsMember(e) 操作结果：判断在集合中是否存在元素。FindFirst(&e)操作结果：找到集合中的第一个元素。如成功，返回TRU

14、E；如果集合为空，返回FALSE抽象数据类型例 FindFirst(&e)操作结果：找到集合中的第一个元素。如成功，返回TRUE；如果集合为空，返回FALSEFindNext(&e) 初始条件：已经执行过FindFirst或FindNext操作 操作结果：在上一次查找的前提下，找到集合中的下一个元素；如成功，返回TRUE；如上次查找已到最后一个元素，返回FALSE。 Union(s) 操作结果：与另一个集合s做并运算，返回并集。Intersection(s) 操作结果：与另一个集合s做交运算，返回交集。Difference(s)操作结果：与另一个集合s做差运算，返回差集。数据操作描述数据的基本

15、操作： 插入：在数据结构的指定位置添加新的数据元素。 删除：去掉数据结构中某个指定的数据元素。更新：改变数据结构中某个数据元素的值。查找：在数据结构中寻找某个满足特定要求的数据元素。排序：重新安排数据元素的逻辑顺序关系，使之值按从小到大或从大到小的顺序排列。操作的分类加工型操作操作改变了（操作之前的）结构的值。引用型操作不改变值，只是查询或求得结构的值。操作的描述语言的描述预定义常量和类型 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 Status是函数的类型，其值是函数结果状态代码 typedef int St

16、atus;数据结构的表示用类型定义（typedef）描述，数据元素类型约定为ElemType，可以是C语言中任何数据类型。基本操作的算法用以下形式函数来描述函数类型函数名（函数参数表） / 算法说明 语句序列 /函数名 C+中操作的描述赋值语句循环语句选择语句注释结束语句输入和输出语句逻辑运算约定用C+描述算法函数形式函数类型 函数名(形参及类型说明) 函数语句部分 return(表达式值)； 函数中的形式参数有两种传值方式若为一般变量名，则为单向传值参数，若在变量前面增加“&”符号，则为双向传地址参数。例如有一个函数为void swap(&i, &j,k)，则i，j为双向传地址参数，k为单向

17、传值参数。函数的说明部分与函数的实现部分分离在C+中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说明部分与函数的实现部分分离开来。输入函数C+中的输入函数调用为: cin变量名。输出函数C+中的输出函数调用为:cout变量名。C+中的类C+对于面向对象程序设计的支持，核心部分就是类的定义。类的定义体现了抽象数据类型的思想，可以支持说明与实现的分离，将抽象数据类型的实现封装在类的内部，使之达到信息隐蔽的目的public 说明对于C+的类，类成员可以用public 声明，表示这些东西是公有的，可以在此类及其他类中使用。private 说明对于C+类，类成员可以用privat

18、e声明，表示这些东西是私有的，只能在本类中使用。protected说明对于C+类，类成员可以用protected声明，表示这部分是受保护的，只能在本类及它的所有派生类中使用。C+的作用域在C+中，每个变量都有一个作用域。在函数内声明的变量，仅能在该函数内部有效，在类中声明的变量，可以在该类内部有效。在整个程序中都能使用的变量，为全局变量，否则称为局部变量。若一个全局变量与一个局部变量同名，则该范围内全局变量不起作用。若要使之起作用，可以使用域操作符来实现。函数名重载C+中允件多个函数取相同的函数名，但形式参数或返回类型可以不同友元函数在C+的类声明中，可以使用保留字friend定义友元函数，使

19、用友元函数可以在一个类中访问另一个类中的私有成员（private）和被保护成员（protected）。内联（inline）函数在一个函数定义前加上inline前缀就成为内联函数。使用内联函数可以减少函数调用和参数传递的系统开销。数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构 数据的存储结构 顺序存储链式存储集合线性结构树结构图结构 非数值问题 数据表示1. 4 算法与算法分析算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 一个算法就是一个有穷规则的集合，规则规定了解决某特定问题的运算序列。算法的特性：有穷性、确定性、可行性、输入、输出。Algorithm + Data S

20、tructures = Programs算法 + 数据结构 = 程序 - Niklaus Wirth算法设计的两个目标易读、易编码和调试（软件工程）充分利用计算机资源（算法和数据结构）算法的设计要求正确性：程序不含语法错误；程序对于几组输入数据能够得出满足要求的结果；程序对于精心选择的典型、苛刻的输入数据能够得出满足要求的结果；程序对于一切合法的输入数据都能够得出满足要求的结果。可读性健壮性效率与低存储量要求最佳、最差、平均情况分析对于不同的输入情况，算法的时间代价不同例如:在一个数组中查找元素K分为最佳、最差、平均情况分析算法效率的度量算法效率需通过该算法编制的程序在计算机上运行所消耗的时间

21、多少以及所需辅助空间的大小来度量。频度：某语句重复执行的次数。时间复杂度：从算法中选取一个对于所研究的问题来说是基本操作的源操作，以该基本操作重复执行的次数作为算法的时间量度。 T（n）= O（f（n）。 它表示随着n的增大，算法执行时间的增长率和 f ( n ) 的增长率相同。程序段一： +x; s=0; 程序段二： for(i=1;i=n;+i) +x; s+=x; 程序段三： for(j=1;j=n;+j) for(k=1;k=n;+k) +x; s+=x; 例1：求下面程序的时间复杂度。 该程序中“+x”是基本操作语句，其频度为n2，其时间复杂度为O(n2)，为平方阶。 该程序中“+x

22、”是基本操作语句，其频度为1，其时间复杂度为O(1)，为常量阶。 该程序中“+x”是基本操作语句，其频度为n，其时间复杂度为O(n)，为线性阶。时间复杂度例 例: 两个矩阵相乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法操作时间复杂度: O(n3)时间复杂度例 例: 选择排序void select_sort(in

23、t& a, int n) / 将 a 中整数序列重新排列成自小至大有序的整数序列。for ( i = 0; i n-1; +i ) j = i ;/ 选择第 i 个最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( aj != ai ) aj ai / select_sort基本操作:比较(数据元素)操作时间复杂度: O(n2)课堂作业分析程序中各语句的频度Ex( ) int i , j , t ; (1) for( i=1 ; i10 ; i+) (2) cout i “ “; (3) for(i=1; i=2; i+) (4) cou

24、t “n”; (5) for(i=1; i=9; i+) (6) for(j=1; j = i ; j+) (7) t = i * j ; cout i “ “; (8) for(j=1; j3 ; j+) (9) cout “n”; Ex( ) int i , j , t ; (1) for( i=1 ; i10 ; i+) /n =10 (2) cout i “ “; /n =9 (3) for(i=1; i=2; i+) /n =3 (4) cout “n”; /n =2 (5) for(i=1; i=9; i+) /n =10 (6) for(j=1; j = i ; j+) /n =

25、54 (7) t = i * j ; cout i “ “; /n =45 (8) for(j=1; j3 ; j+) /n =27 (9) cout “n”; /n =18 Ex( ) int i , j , t ; (1) for( i=1 ; i10 ; i+) /n =10 (2) cout i “ “; /n =9 (3) for(i=1; i=2; i+) /n =3 (4) cout “n”; /n =2 (5) for(i=1; i=9; i+) /n =10 (6) for(j=1; j = i ; j+) /n =54 (7) t = i * j ; cout i “ “; /n =45 (8) for(j=1; j3 ; j+) /n =27 (9) cout 0) if (x 100) x -= 10 ; y - ; else x + ;问if语句执行了多少次?(1100)y-执行了多少次?(100)x +执行了多少次?(1000)大O 表示法的运算规则单位时间简单布尔或算术运算赋值简单I/O函数返回加法规则: f1(n)+f2(n)=(max(f1(n)