数据结构和算法.ppt

重要性：,人类社会已步入信息时代；“计算”已成为理论研究、实验研究的基本手段；给我一个支点，我能撬动地球 给我一个接口，我能驱动地球,信息领域：,软件-核心问题是算法；算法+数据结构=程序设计 产品 软件,先修课程：,程序设计的经验、离散数学、概率分析,课程特点：,抽象、有难度,课程学习要求：,1、上课做好笔记；2、按时、独立、认真完成作业；3、独立完成实验：实验课前完成实验报告的前3个环节；进实验室完成程序的调试与测试；实验成绩综合给出。4、勤奋学习，积极思考，提出问题，解决问题。5、上课不迟到、不早退，班级考勤。,课程考核方法：,1、期末考试：50%；2、实验：30%；3、课堂笔记：5%；4、平时表现（作业、考勤）：5%；5、阶段测验：5%；6、课程总结：5%；,引言,一般来说,用计算机解决具体问题时,大致需要经过以下几个步骤:具体问题 抽象(数学)模型 分析 求解方法 程序设计 测试,数据结构是一门 讨论怎样合理地组织数据、建立合适的数据结构，从而提高计算机执行程序时的时间效率和空间效率问题的课程。,第1章 数据结构和算法,1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析,数据 在计算机科学中，数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称。例如：数值数据、字符、声音、图像、图形等,简单的说，数据是信息的载体，所有能够数字化的信息均可认为是数据,数据元素 数据元素是数据的基本单位，在程序设计时通常作为一个整体进行考虑和处理。同义词：元素、结点、顶点、记录、对象、元组等。,数据项 具有独立含义的最小标识单位 同义词：字段、域、属性等。,表中某一本书的相关数据(表中每一行)都是一个数据元素，每一个数据元素其具有独立意义。每一个数据元素由4个简单数据项(书号、书名、作者、价格)组成。,数据类型 是一个同类值的集合和定义在这个值集上的一组操作的总称。当我们在高级程序语言中定义每一种数据类型，在程序编译时计算机语言编译系统就知道了以下信息：(1)一组性质相同的值集合，(2)一个预定的存储体系，(3)定义在这个值集合上的一组操作。数据类型可分为两类：,数据类型,简单数据类型、结构数据类型,简单数据类型 简单类型的数据是不可分解的整体，如整数、实数、字符、指针、枚举量等。请解释整型数据类型。答：整型数据类型通常有short(2字节)、int(2字节)、long(4字节)等形式，其值集为某个区间上的整数。如果整型是两个字节表示的，其值集范围是：-3276832767，定义在整型数据上的操作为：单目正(+)操作、负(-)操作，双目加(+)操作、减(-)操作、乘(*)操作、除(/)操作和取模(MOD)操作等算术运算，双目关系(，=，等)操作运算以及赋值(=)操作等。,例,结构数据类型 结构类型由简单数据类型按照一定的规则构造而成。结构数据类型中还可包含结构数据类型，所以结构数据类型的数据可以分解成若干个简单数据类型的数据或子结构数据类型。也称作复合数据类型。,数据对象 数据对象是数据类型的实例，简称对象。数据对象举例。答：例如：25，是整型数据对象。A，是字符数据对象。char*p，定义p为一个字符指针对象。int a10，定义a为一个含有10个整型数的整型数组对象。Rectangle r，定义 r 为一个Rectangle类型的对象。RECtangle rec，定义 rec 为一个RECtangle 抽象数据类型的对象。,例,第1章 数据结构和算法,1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析,(1)数据的逻辑结构，即数据元素间的逻辑关系；(2)数据的存储结构，数据元素在计算机存储器中的存储方式；(3)数据的运算，对数据施加的操作。,数据结构 没有统一的定义，通常指数据元素之间的相互关系，即数据的组织形式；包括：,数据的逻辑结构定义：数据元素之间的相互联系称为数据的逻辑结构。,根据数据元素之间关系的不同特性，通常有下列四类基本结构。线性逻辑结构 树型逻辑结构 图型逻辑结构 集合逻辑结构,数据的逻辑结构可以用图形形象地表示。用图形中的每一个节点(或叫顶点)对应着一个数据元素，用两节点间的连线(称有向边或弧)对应着关系中的一个序偶，其中第一个元素为起始点，第二个元素为终止点，箭头指向终止点。,线性逻辑结构,节点之间是一个对一个的关系，呈线性关系，是线性逻辑结构。它的特征是：若结构为非空集，则该结构有且只有一个开始节点和一个终端节点，并且所有节点都最多只有一个直接前趋和一个直接后继。,树形逻辑结构,它的特征是：节点之间是一个对多个的关系，一个节点可能有一个直接前趋和多个直接后继。呈树形关系，是树形数据结构(非线性结构)。,图形逻辑结构它的特征是：节点之间是多个对多个的关系，一个节点可能有多个直接前趋和多个直接后继。呈图形关系(非线性结构)。,集合逻辑结构,集合中数据元素之间的关系是松散的，实际运算时可以用其它结构来表示它。,数据的存储结构 数据的存储结构是 用计算机处理具体问题时，必须考虑由这个具体问题抽象出的数据在计算机中的存储方式，以便于运算。通常情况下，数据在计算机中存储方式有以下四种：顺序存储 链接存储 索引存储 散列存储,指数据在计算机中的存储方式,顺序存储 将逻辑上相邻的结点存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现（3，5，6，8，23，12，54）=float an,例1.6,例1.7,链接存储 逻辑上相邻的结点不一定存储在物理位置相邻的存储单元中，结点间的逻辑关系由附加的指针字段来体现。一组数据元素的集合（3，5，6）,例1.8,例设有一组线性排列的数据元素(zhao，qian，sun，li，zhou，wu，zheng，wang)，其链接存储形式如图所示。,索引存储 该方法在存储结点信息的同时，建立附加的索引表。索引表中的每一个索引项由唯一标识某结点的关键字以及该结点的地址组成。例,散列存储 应用一个函数，将每一个结点的关键字作为该函数的自变量，得到相应的函数值作为该结点的存储地址。有函数 y=2x,集合（3，5，6）的存储：,例,数据的运算 正如整数和实数分别对应不同的运算一样，不同逻辑结构的数据有不同的运算。数据运算不仅仅是加、减、乘、除、矩阵、微分、积分、方程等等这些数值计算问题，还包括像在一张表格中，进行查找记录，增加记录，修改记录，删除记录等等操作运算，而怎样才能进行这样的运算呢?在数据结构中，这些运算常常涉及算法问题。,数据的运算例如：线性结构的数据数据可以非常方便地进行插入、删除数据元素，而对于树和图这样的非线性结构的数据可以有查询数据元素之间的关系、遍历数据元素等运算。通常情况下，逻辑关系不同的数据分别对应一组运算的集合；而数据的存储结构反映数据在计算机内部的存储安排，对具有相同逻辑关系的数据考虑其不同的物理存储，目的是为了提高算法的效率。,根据以上分析，我们可以看到数据结构的概念主要包括如图所示的三个方面的主要内容：,我们讨论两数据结构是否相同，主要看它们的逻辑结构、存储结构和运算集合是否相同，这三者中只要有一个不同，都不能称这两个数据结构相同。,设有两个呈线性排列的数据分别是1,3,5,7,9和0.1,0.2,0.4,0.6,0.8（其中的每个数是数据元素），现将它们分别存放在整型一维数组A5和实型一维数组B5中。现在，我们来分析这两个数据的数据结构是否相同。,例,首先，这两个数据都是呈线性排列，则它们的逻辑结构均为线性逻辑结构；其次，它们分别存储在一维数组中，这使得逻辑位置相邻的数据元素在物理存储位置上也相邻，这样它们都属于顺序存储结构；另外，根据C语言语法规定，一维数组A5中的数据元素间可以进行加、减、乘、除和模运算，而一维数组B5中的数据元素间只能进行加、减、乘、除运算；这样，数据1,3,5,7,9和数据0.1,0.2,0.4,0.6,0.8的运算集合不同。可以断定，这两个数据有着完全不同的数据结构。,数据类型 可看作是高级语言提供的数据结构数据结构3方面的联系 同一逻辑结构的不同存储结构，用不同的名字称谓 如：线性表 顺序表、链表、散列表 运算不同，称谓也不同 如：线性表 栈、队列,第1章 数据结构和算法,1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析,数据类型 简单类型 int float double char 构造类型 数组 int5 char25 结构体 struct 结构型名 数据类型名 成员;,例1.13 struct student long number;char name20;char sex;float score3;struct student A50;,指针型 int a,b,*p=q=&b；,已知定义：int x，*k=&x；试问：表达式*k，&x，*&x，&*k，&*x和*&k各表示什么？答：对于*k，表示变量x。对于&x，&是地址运算符，&x表示变示变量x的地址。对于*&x，表示*k，即变量x。对于&*k，*k表示变量x，&*k即表示变量x的地址(&x)。对于*&k，表示变量k。而&*x则存在语法错误。,用户自定义类型,typedef 类型名1 类型名2;(1)typedef int AB;(2)typedef struct long number；stutable;stutable A50;(3)typedef int*POINT;POINT p;,例1.15,运算符 指向结构体成员的指针引用 结构体成员的引用 struct student long number;float score;x,*p=,例1.16,函数 系统函数 内存分配函数（申请内存函数）void*malloc(int size)功能：申请大小为size个字节的内存。返回值：若申请成功，则返回所分配 的内存单元首地址。,内存释放函数 void free(void*blocd)功能：释放由malloc等内存分配函数申请到的内存，其首地址放在参数block中。返回值：无注：当程序中使用了上述两个函数时，应在程序的开头使用：include“alloc.h”,例1.18 char*p1;p1=malloc(80);scanf(“%s”,p1);printf(“%s”,p1);free(p1);,用户自定义函数 数据类型符 函数名（形参表）形参说明；函数体；return语句；,函数返回值的类型,return(值or变量)；无返回值：return;,函数调用 a.函数名（实参表）；b.变量函数名（实参表）；求三个整数的和、积、最大值、最小值。main()int a,b,c,x,y,v,w;scanf(“%d%d%d”,例1.19,int sum(int a,int b,int c)return(a+b+c);int mul(int a,int b,int c)return(a*b*c);int max(int a,int b,int c)int x;if(ab)x=a;else x=b;if(xc)x=c;return x;,程序测试 是指在计算机上利用输入数据(测试数据)来实际运行该程序，把程序的实际行为与所期望的行为进行比较。如果两种行为不同，就可判定程序中有问题存在。但是，对于大多数实际的程序，可能的用于测试数据的数量太大了，不可能进行穷尽测试。实际用来测试的输入数据空间的子集称之为,程序测试,测试集,第1章 数据结构和算法,1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析,什么是算法 算法是为解决一个特定问题而采取的确定的有限的步骤，是指令的有限序列。算法具有输入、输出、有穷性、确定性和可行性特性。,算法的特性 按照算法的定义，一个算法必须具备下列五个特性：有穷性：必须在执行有穷个操作之后结束，而且“有穷性”也应在合理的范围内。确定性：也称无二义性。算法中，对每一个操作的描述都必须是精确的、有确切的含义，而不是模棱两可的。可行性：一个算法必须由可执行的步骤组成，即算法中的每一个步骤都应当能有效地执行，并得到确定的结果。0n个输入：一般情况下，输入的是算法的操作对象，可以在算法执行前临时给出，也可以在编写算法时直接给出。1n个输出：算法对输入的操作对象执行操作后合乎逻辑的操作结果。,书写一个算法可以用多种算法描述工具。,算法的评价标准 对一个问题可以有很多的解决方法，用计算机处理问题也可以设计出不同的算法。那么，什么样的算法是“好”的呢？设计和评价一个算法的好坏往往要从各个方面考虑。算法的评价有以下几个标准：1、正确性：该算法必须是正确的，要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。这方面的内容在计算机软件学有详细介绍。另外，要证明算法正确性是一个比较困难的问题。,2、可读性：为提高算法的可读性，我们提倡模块化程序设计理念，并在程序的适当地方增添注释。这使得算法易于理解、易于调试、易于移植；算法应该具有良好的可读性。3、健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。4、时间与空间效率：算法的时间效率与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。,第1章 数据结构和算法,1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析,1.5 算法性能分析,1.5.1 算法的时间性能分析 1.5.2 算法的空间性能分析,一个算法所耗费的时间,用 各条语句执行的次数之和 来计量,又称：时间复杂度T(n),又称：频度,【例】语句的执行次数的计算 for(i=1;i=n;i+)printf(“%d”,i);,共3n2次 即：T(n)3n2,可以看出，算法的时间复杂度T(n)是问题规模n的函数，它表示执行该算法所需的时间随问题规模的增大而增加。其实，大多数算法的执行时间都与问题的规模成正比，在计算算法的时间性能时，我们通常考察时间复杂度T(n)随问题规模扩大的增长率,两个函数f(n)和g(n)的相对增长率可以这样计算：若变量n的函数f(n)和g(n)满足：则称f(n)和g(n)的相对增长率是同一数量级，并用f(n)=(g(n)的形式表示。,定义,对上例 T(n)3n2 有,【例】for(i=1;i=n;i+)for(j=1;j=i;j+)printf(“%d”,i);执行次数：,【例】i=1;while(in)i=i*2;次数：1 2 3 k i 2 22 23 2k 若 2kn 次数 klog2n 即：T(n)=O(log2n)常用数量级（时间复杂度）：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!),1.5 算法分析,1.5.1 算法的时间性能分析 1.5.2 算法的空间性能分析,定义 一个算法的空间复杂度S(n)定义为该算法所需的存储空间，它也是问题规模n的函数，记为 S(n)=(f(n)一个算法所需的存储空间除了存储算法本身所用的指令、常数、变量和输入数据外，还有一部分是对数据进行操作的工作单元，以及为实现计算所需信息的辅助空间。算法的空间性能包括运行算法所需的存储空间以及辅助存储空间的大小。,1、数据结构和数据类型两个概念之间有区别吗？2、简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。3、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。,习 题,4、计算下列各程序段的时间复杂度(1)for(i=0；in；i+)for(j=0；jm；j+)Aij=0；(3mn+4n+2)(2)s=0；for i=0；in；i+)for(j=0；jn；j+)s+=Bij；sum=s；(4n2+4n+3),(3)i=1；while(i=n)i=i*3；2/3*n+2(4)i=0；k=0；do k=k+10*i；i+；while(in)；3n+2,The end,