《数据结构 C++ 版 教学课件 ppt 作者 叶核亚 主编 第01章 绪论》由会员分享，可在线阅读，更多相关《数据结构 C++ 版 教学课件 ppt 作者 叶核亚 主编 第01章 绪论（25页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C+版）,叶核亚,数据结构（C+版）,第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计,数据结构（C+版）叶核亚,第1章 绪论,软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。 “数据结构十算法=程序”。 1.1 数据结构的基本概念 1.2 算法与算法设计,数据结构（C+版）叶核亚,1.1 数据结构的基本概念,1.1.1 抽象数据类型与数据结构 1.1.2 数据的逻辑结构 1.1.3
2、 数据的存储结构 1.1.4 数据的操作,数据结构（C+版）叶核亚,1.1.1 抽象数据类型与数据结构,数据、数据元素、数据项 描述客观事物的数字、字符以及所有能输入到计算机中并能为计算机接受的各种符号集合统称为数据（data）。数据是计算机程序的处理对象。 表示一个事物的一组数据称作一个数据元素（data element），数据元素是数据的基本单位；构成数据元素的数据称作该数据元素的数据项（data item），数据项是数据元素的不可分割的最小单位。 数据类型 类型是一组值的集合。数据类型（data type）是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据元素的性质、取值范围以
3、及对数据元素所能进行的各种操作。,数据结构（C+版）叶核亚,表1-1 学生信息表,class Student char number8; char name20; char boy4; int age; ;,数据结构（C+版）叶核亚,抽象数据类型 抽象数据类型（Abstract Data Type，缩写为ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。没有定义具体数据类型的数据元素称作抽象数据元素。 数据结构 对一个数据元素集合来说，如果在数据元素之间存在一种或多种特定的关系，则称为数据结构（data structure）。因此，“结构”就是指数据元素之间存在的关系。,数据结构（C+版
4、）叶核亚,1.1.2 数据的逻辑结构,线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。 树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。 图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。,图1-1 三种基本的数据结构,数据结构（C+版）叶核亚,1.1.3 数据的存储结构,数据元素在计算机中的存储表示方式称为数据的存储结构，也称为物理结构。 顺序存储结构 顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。 链式存储结构 指针是指向物理存储
5、单元地址的变量。由数据元素域和指针域组成的一个整体称为一个结点（node）。链式存储结构是使用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来，其特点是逻辑上相邻的数据元素在物理上（即内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。,数据结构（C+版）叶核亚,图1-2 两种存储结构,数据结构（C+版）叶核亚,1.1.4 数据的操作,对一种数据类型的数据元素进行的某种处理称作数据的操作。 访问数据元素。 统计数据元素个数。 更新数据元素值。 插入数据元素，在数据结构中增加新的结点。 删除数据元素，将指定数据元素从数据结构中删除。 查找在数据结构中查找满足一定条
6、件的数据元素。插入、删除、更新操作都包括一个查找操作，以确定需要插入、删除、更新数据元素的确切位置。 排序在线性结构中数据元素数目不变的情况下，将数据元素按某种指定的顺序重新排列。,数据结构（C+版）叶核亚,1.2 算法与算法设计,1.2.1 算法 1.2.2 算法设计 1.2.3 算法分析,数据结构（C+版）叶核亚,1.2.1 算法,算法定义 有穷性算法必须在执行有穷步之后结束。 确定性算法的每一个步骤必须是确切地定义的。 输入算法有零个或多个输入。 输出算法有一个或多个输出，即与输入有某种特定关系的量。 可行性算法中有待执行的操作和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行
7、的，而且用笔和纸做有穷次就可以完成。 算法的描述 算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码描述。此时算法是由语义明确的操作步骤组成的有限序列，它精确地指出怎样从给定的输入信息得到要求的输出信息。,数据结构（C+版）叶核亚,例1-3 学生信息表的顺序查找算法,图1-5 学生信息表的顺序查找过程,数据结构（C+版）叶核亚,算法与数据结构 算法是建立在数据的逻辑结构与存储结构上的。 对于同样的逻辑结构和存储结构，根据问题的不同要求，采用不同的算法。 同样的数据结构，不同的存储结构，则采用的算法必然不同。例如，存储结构不同的线性表其排序算法必然不同。,数据结构（C+版）叶核亚,例1
8、-4 字典的分块查找算法。,图1-6 字典与其索引表示意图,数据结构（C+版）叶核亚,算法与程序 算法用抽象的语言描述解决特定问题的每一步的操作。程序是计算机能理解和执行的指令序列。 一个程序实现一个算法。算法和程序的区别是算法的执行是有穷的，而程序的执行可以是无限的。例如操作系统程序，只要系统不受破坏，操作系统的运行将不会停止。,数据结构（C+版）叶核亚,1.2.2 算法设计,算法设计目标 正确性 可读性 健壮性 高时间效率 高空间效率 算法设计实现,数据结构（C+版）叶核亚,例1-5 求最大值算法的设计与调用,从两个整数类型数据中得到较大数值的算法设计如下： int Max(int a,i
9、nt b) return (a=b)?a:b; 主函数中，调用Max(Max(a,b),c)将从三个整数中返回最大值，例如， cout“max=“Max(Max(1,2),3)endl;,数据结构（C+版）叶核亚,例1-6 求两个整数的最大公因数的算法实现。,数据结构（C+版）叶核亚,1.2.3 算法分析,算法的时间复杂度 算法的执行时间等于所有语句执行时间的总和，是算法所处理的数据个数n的函数，表示为O(f(n)，O(f(n)称为该算法的时间复杂度。O(1)表示时间是一个常数，不依赖于n；O(n)表示时间与n成正比，是线性关系，O(n2)、O(n3)、O(2n)分别称为平方阶、立方阶和指数阶
10、；O(log2n)为对数阶。 算法的空间复杂度,数据结构（C+版）叶核亚,例1-7 算法时间复杂度的分析。,一个简单语句的时间复杂度为O(1)。 int count=0; 时间复杂度为O(n)的循环语句。 int n=8,count=0,i; for(i=1;i=n;i+) count+; 时间复杂度为O(log2n)的循环语句。 int n=8,count=0,i; for(i=1;i=n;i*=2) count+; 时间复杂度为O(n2)的二重循环。 count=0; for(i=1;i=n;i+) for(j=1;j=n;j+) count+;,数据结构（C+版）叶核亚,时间复杂度为O(
11、nlog2n)的二重循环。 count=0; for(i=1;i=n;i*=2) for(j=1;j=n;j+) count+; 时间复杂度为O(n)的二重循环。 count=0; for(i=1;i=n;i*=2) for(j=1;j=i;j+) count+;,数据结构（C+版）叶核亚,表1-2 时间复杂度随n变化情况的比较,数据结构（C+版）叶核亚,实习1,实验目的 正确安装并熟练使用一种C环境进行编辑、编译、调试、运行程序。 理解C语言，掌握基本数据类型，熟练运用分支、循环等语句控制程序流程。 题意 输出下列方阵： n=4 1 2 6 7 3 5 8 13 4 9 12 14 10 11 15 16,
