《数据结构》课件-第1章 数据结构与算法概述

数据构C语言描述结数据结构C语言戚爽主讲课程信息课程名称：数据结构英文名称：DataStructure教材：数据结构

邹岚主编上课教师：戚爽学时：64学时（4学时/周*16周）3数据结构的研究内容《数据结构》课程是研究程序设计中非数值计算的数据以及它们之间的关系和操作等的一门学科。它以数学为基础、涉及计算机硬件与计算机软件的研究范围，是计算机相关专业的一门核心基础课程。数据结构软件数学硬件为什么要学习数据结构01计算机各相关专业重要的专业基础课，处于核心地位。02各高校计算机相关专业考研/专升本必考的专业课。03为从事有关计算机的教学、科研、开发、管理等奠定重要的专业基础。《数据结构》属于武术中的“练功”科目“练武不练功，到头一场空”前、后续课程关系C语言程序设计前导课程数据结构专业核心数据库原理操作系统软件工程后续课程计算机网络1课程目标能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术。学编程的境界学会写程序学会高效地写程序学会写高效的程序学会设计算法学会设计有用的算法写作：学字，词，文法，句法快速地写文章写简洁明快的好文章选择结构，流程，方法写人们喜欢看的文章学习要求123提前预习、认真听课、按时完成书面及上机作业注意先修课程的知识准备C语言程序设计注意循序渐进基本概念、基本思想、基本步骤、算法设计4注意培养算法设计的能力理解所讲算法、对此多做思考：若问题要求不同，应如何选择数据结构，设计有效的算法综合成绩构成期末考试60%平时成绩40%考核办法出勤率上机作业随堂测试课堂纪律无故迟到无故旷课玩游戏、手机第1章

绪论1.4算法及算法分析1.1

数据结构在程序设计中的作用1.2本课程讨论的主要内容1.3数据结构的基本概念1.5习题第一章绪论知识目标：了解数据结构的发展理解数据结构中的基本概念理解抽象数据类型的概念、记法和用法理解算法分析的目的掌握算法及其特性掌握算法时间复杂度的分析方法技能目标：能分析一般算法的时间复杂度1.4算法及算法分析1.1数据结构在程序设计中的作用1.2本课程讨论的主要内容1.3数据结构的基本概念1.5习题1938年出生，从31岁起，开始出版他的历史性经典巨著：TheArtofComputerProgramming《计算机程序设计艺术》，他计划共写7卷，出版三卷之后，已震惊世界。1974年，他获得计算机科学界的最高荣誉——图灵奖，年仅36岁；1995年他又获得了冯·诺依曼奖。获奖作品至今才出到第四卷。其中第一卷《基本算法》中较系统地阐述了数据结构的逻辑结构和存储结构及其操作，开创了数据结构的课程体系。数据结构的创始人——唐纳德·克努特（高纳德）DonaldKnuth数据表示：将数据存储在计算机（内存）中数据处理：处理数据，设计方案（算法）著名计算机科学家沃思提出：程序设计的实质是什么?1.1数据结构在程序设计中的作用数据结构问题起源于程序设计程序=数据结构+算法利用计算机求解问题的一般过程？数学模型解题思路数据结构算法数据类型程序问题抽象设计编码运行结果1.1数据结构在程序设计中的作用计算机不能分析问题并产生问题的解决方案，必须由人来分析问题，确定问题的解决方案，编写程序，然后让计算机执行程序最终获得问题的解。程序设计的实质：对具体问题选择一种适合的数据结构，设计一个优秀的算法。操作对象对象间关系举个栗子1.1数据结构在程序设计中的作用例1-1手机电话号码查询问题将电话号码集合组织成线性结构和树结构，查找操作的效率不同，当数据量较大时差别就更大。1.4算法及算法分析1.1数据结构在程序设计中的作用1.2本课程讨论的主要内容1.3数据结构的基本概念1.5习题例1-2学籍管理问题完成什么功能?各表项之间是什么关系？1.2本课程讨论的主要内容线性结构中数据元素存在着由依次排列的先后次序决定的关系例1-3人—机对弈问题如何实现对弈？各格局（棋盘状态）之间是什么关系？1.2本课程讨论的主要内容树型结构中，除树根外，每个元素都有唯一的前驱（后继个数不限）例1-4七巧板涂色问题如何表示区域之间的邻接关系？1.2本课程讨论的主要内容在图结构中，任一数据元素，均可有多个前趋和多个后继，也称网状结构使用至多4种不同颜色对七巧板进行涂色（每块涂一种颜色），要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。1.2本课程讨论的主要内容由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。数据结构是研究程序设计中非数值计算的数据以及它们之间的关系和操作等的一门学科。重点分析数据之间抽象的相互关系，不涉及数据的具体内容。1.2本课程讨论的主要内容存储结构逻辑结构数据处理（算法）顺序结构链式结构集合树型

结构图

结构查找技术排序技术索引技术图数据结构的知识架构线性

结构如何实现插入、

删除、查找等

基本操作，

有效地处理数据如何组织待处理的数据以及数据之间的关系如何有效地存储数据以及数据之间的逻辑关系索引结构散列结构1.4算法及算法分析1.1数据结构在程序设计中的作用1.2本课程讨论的主要内容1.3数据结构的基本概念1.5习题1.3数据结构的基本概念数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数值数据：整数、实数等非数值数据：图形、图像、声音、文字等数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的最小单位。学号姓名性别出生日期政治面貌0001陆宇男1996/09/02团员0002李明男1995/12/25党员0003汤晓影女1996/03/26团员数据项数据元素1.3数据结构的基本概念数据、数据元素、数据项之间的关系包含关系：数据由数据元素组成，数据元素由数据项组成。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。数据结构数据元素关系1.3数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？七巧板涂色问题中，板块之间的逻辑关系指的是什么？思维1.3数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。数据的逻辑结构在形式上可定义为一个二元组：Data_Structure=(D,R)其中D是数据元素的有限集合，R是D上关系的集合。1.3数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。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>}1.3数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。内存数据的运算:定义在数据的逻辑结构上，

实现在数据的存储结构上。面向问题面向计算机1.3数据结构的基本概念数据结构从逻辑上分为四类：集合：数据元素之间就是“属于同一个集合”；1.3数据结构的基本概念数据结构从逻辑上分为四类：集合：数据元素之间就是“属于同一个集合”；线性结构：数据元素之间存在着一对一的线性关系；数据结构从逻辑上分为四类：集合：数据元素之间就是“属于同一个集合”；线性结构：数据元素之间存在着一对一的线性关系；树结构：数据元素之间存在着一对多的层次关系；1.3数据结构的基本概念1.3数据结构的基本概念数据结构从逻辑上分为四类：集合：数据元素之间就是“属于同一个集合”；线性结构：数据元素之间存在着一对一的线性关系；树结构：数据元素之间存在着一对多的层次关系；图结构：数据元素之间存在着多对多的任意关系。1.3数据结构的基本概念通常有两种存储结构：顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。…batcateat…起始地址例：（bat,cat,eat）逻辑上相邻的数据元素的存储位置也相邻。例：（bat,cat,eat）0200020803000325…………bat0200cat0325eat∧1.3数据结构的基本概念通常有两种存储结构：顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。通常用高级程序语言中，用一维数组类型来表示顺序存储结构；用指针类型来描述链式存储结构。逻辑结构和存储结构之间的关系数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。为了区别于存储结构，常常将数据的逻辑结构称为数据结构。1.3数据结构的基本概念数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型指由系统定义的、用户可直接使用且可构造的类型。数据类型中定义了两个集合：类型的取值范围、可允许使用的一组运算集。1.3数据结构的基本概念C语言中的int型变量，是指由-32768到32767范围中的值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。长整型longC数据类型基本类型构造类型指针类型空类型void字符类型char整型实型单精度型float双精度型double数组结构体struct共用体union短整型short整型int枚举类型一般来说，高级语言中的数据类型可分为两类：非结构的原子类型原子类型的值是不可分解的。C语言中的标准类型（整型、实型、字符型、枚举型）及指针和空类型。结构类型结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是原子型或结构型。C语言中的数组、结构体、共用体。1.3数据结构的基本概念1.3数据结构的基本概念抽象数据类型（AbstractDataType，ADT）基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型描述的是一组逻辑特性，与计算机内部的表示和实现无关。抽象数据类型数据对象数据关系基本操作一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT通常由用户定义并且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。逻辑结构操作集合抽象数据类型定义ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>基本操作名(参数表)初始条件：<初始条件描述>操作结果：<操作结果描述>}ADT抽象数据类型名1.3数据结构的基本概念例：P5队列的抽象数据类型描述数据的操作：插入、删除、修改、检索、排序等数据的逻辑结构

数据的存储结构

顺序存储链式存储集合线性结构树结构图结构非数值问题数据表示加工型运算引用型运算1.3数据结构的基本概念（总结）1.4算法及算法分析1.1数据结构在程序设计中的作用1.2本课程讨论的主要内容1.3数据结构的基本概念1.5习题1.4算法及算法分析算法（Algorithm）：是对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.4算法及算法分析常用的描述方法有：用自然语言描述算法用流程图描述算法用N-S流程图描述算法用计算机语言描述算法用伪代码描述算法欧几里德算法——辗转相除法求两个自然数m和n的最大公约数1.4算法及算法分析mnr欧几里德算法（有穷性、确定性、可行性）1.4算法及算法分析例：欧几里德算法步骤1：将m除以n得到余数r；步骤2：若r等于0，则n为最大公约数，

算法结束；否则执行步骤3；步骤3：将n的值放在m中，将r的值放在n中，

重新执行步骤1；自然语言1.4算法及算法分析优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想

注意事项：避免写成自然段算法的描述方法——自然语言1.4算法及算法分析例：欧几里德算法N开始输入m和n

r=m%nr=0m=n；n=r输出n结束Y流程图1.4算法及算法分析优点：流程直观易懂缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次算法的描述方法——流程图1.4算法及算法分析例：欧几里德算法#include<stdio.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){printf(“%d\n”,CommonFactor(63,54));}程序设计语言1.4算法及算法分析优点：能由计算机执行缺点：抽象性差，拘泥于具体细节而忽略算法逻辑的重要性，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数算法的描述方法——程序设计语言1.4算法及算法分析例：欧几里德算法

1.r=m%n;

2.循环直到r等于0

2.1m=n;

2.2n=r;

2.3r=m%n;

3.输出n;上述伪代码再具体一些，用C语言的函数来描述。伪代码1.4算法及算法分析伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计，被称为“算法语言”或“第一语言”。优点：表达能力强，抽象性强，容易理解算法的描述方法——伪代码1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}对C语言进行了如下简化：局部变量可以不声明；写出子函数即可，子函数不用在主函数中调用，省略主函数；所有的包含函数（头函数.h）可以省略；交换两个变量的语句可以简写为a←→b。1.4算法及算法分析通常用以下几个标准来评价其优劣：正确性：算法必须能正确解决问题。易读性：算法应当便于阅读和理解，以利于修改和改写成程序。健壮性：当输入非法数据时，算法也能做出特殊处理，不会继续操作或死机。高效性：算法的效率主要从时间和空间两个方面考虑。解决一个问题的算法如果使用时间少和占用空间少，则是算法高效率的体现。1.4算法及算法分析算法分析度量算法效率的方法：事后统计：将算法实现，测算其时间和空间开销。缺点：编写程序实现算法将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素。事前分析：即渐进复杂度，对算法所消耗资源的一种估算方法。算法分析算法分析（AlgorithmAnalysis）：对算法所需要的计算机资源——时间和空间进行估算。时间复杂度（TimeComplexity）：一个算法所进行的计算次数的多少。T(n)空间复杂度（SpaceComplexity）：指在算法执行过程中，需要的辅助空间（临时开辟的存储空间）数量。S(n)1.4算法及算法分析算法的时间复杂度的事前分析一个高级语言程序在计算机上运行所

消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度1.4算法及算法分析同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，——使用绝对时间单位衡量算法效率不合适算法的时间复杂度事前分析算法的执行时间＝每条语句执行时间之和执行次数×执行一次的时间指令系统、编译的代码质量单位时间每条语句执行次数之和基本语句的执行次数1.4算法及算法分析for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;问题规模n基本语句1.4算法及算法分析一般情况下，算法中基本操作重复执行的次数称为语句频度或时间频度，它是问题规模n的某个函数，用T(n)表示。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度（TimeComplexity）。n越大算法的执行时间越长排序：n为记录数矩阵：n为矩阵的阶数多项式：n为多项式的项数集合：n为元素个数树：n为树的结点个数图：n为图的顶点数或边数1.4算法及算法分析时间复杂度可以估算出当问题规模变大时，算法运行时间增长的速度。估算算法运行时间的基本前提是：确定问题的“规模”和确定算法执行“基本语句”的次数的关系。问题规模：一般是指输入数据量的数目。基本语句：一般是指执行次数最多的语句，比如，最内层循环的循环体。1.4算法及算法分析求解算法时间复杂度的具体步骤是：找出算法中的基本语句算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。计算基本语句的执行次数的数量级保留基本语句执行次数的最高次幂，忽略所有低次幂和最高次幂的系数。用大O记号表示算法的时间复杂度称为算法的渐进时间复杂度（时间复杂度）：T(n)=O(f(n))例：求下面程序段的时间复杂度。intx=0;for(i=0;i<n;i++)for(j=0;j<n;j++) x++;1.4算法及算法分析基本语句是x++，其执行次数是n2，用大O记号表示为T(n)=O(n2)从好到坏表示时间复杂度的函数依次是：常量阶O(1)；//算法执行时间恒定，不随问题规模的扩大而扩大对数阶O(log2

n)；线性阶O(n)；平方阶O(n2)；多项式阶O(nk)；指数阶O(2n)

算法的时间复杂度越大，其执行效率就越低。1.4算法及算法分析算法复杂度，举例：①{x++;s=x+2;} ②for(k=1;k<=n;k++)s=k+2； ③for(k=1;k<=n;k++)for(j=1;j<=n;j++)s=k+j；1.4算法及算法分析时间复杂度为O(1)时间复杂度为O(n)时间复杂度为O(n2)1.4算法及算法分析最好情况、最坏情况、平均情况例：在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）。

intFind(intA[],intn){for(i=0;i<n;i++)if(A[i]==k)break;returni; }基本语句的执行次数是否只和问题规模有关？1.4算法及算法分析最好情况、最坏情况、平均情况结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布空间复杂度关于算法的存储空间需求，类似于算法的时间复杂度，我们采用空间复杂度作为算法所需存储空间的量度，记作：S(n)=O(f(n))

其中，n为问题的规模，O表示数量级。算法占据的空间：算法本身要占据的空间，输入/输出，指令，常数，变量等；算法要使用的辅助空间1.4算法及算法分析空间复杂度1.4算法及算法分析【算法1】

for(i=0;i<n/2;i++){t=a[i];a[i]=a[n-i-1];a[n-i-1]=t;}

【算法2】

for(i=0;i<n;i++)b[i]=a[n-i-1];for(i=0;i<n;i++)a[i]=b[i];

例：将一维数组a中的n个数逆序存放到原数组中。S(n)=O(n)S(n)=O(1)原地工作1.5习题(1)从数据结构S中找出满足条件的结点在S中位置的运算是_____________型运算。(2)从数据结构S中读出结构中指定位置上内容运算是_____________型运算。(3)从数据结构S中的某指定位置上增加一个新结点的运算是_____________型运算。(4)从数据结构S中撤消结构中指定位置上结点的运算是_____________型运算。(5)从数据结构S中修改结构中某指定结点内容的运算是_____________型运算。1.5.1习题——填空题(1)数据表示是指数据_____________。

A.书写在纸上 B.从机外转为机内

C.磁盘中的数据 D.光盘中的数据(2)数据元素是数据的基本单位，其内_____________数据项。

A.只能包括一个 B.不包含

C.可以包含多个

D.必须包含多个(3)逻辑关系是指数据元素间的_____________。

A.类型 B.存储方式

C.结构 D.数据项1.5.2习题——选择题(4)逻辑结构是_____________关系的整体。

A.数据元素之间逻辑 B.数据项之间逻辑

C.数据类型之间 D.存储结构之间(5)数据结构有_____________种基本逻辑结构。

A.1 B.2C.3 D.4(6)下列四种基本的逻辑结构中，数据元素之间关系最弱的是_______。

A.集合 B.线性结构

C.树形结构 D.图状结构1.5.2习题——选择题(7)一个存储结点存放一个_____________。

A.数据项 B.数据元素

C.数据结构 D.数据类型(8)用类C语言描写的算法_____________。

A.可以直接在计算机上运行

B.可以描述解题思想和基本框架

C.不能改写成C语言程序

D.与C语言无关(9)算法能正确地实现预定功能的特性称为___________。

A.正确性 B.易读性

C.健壮 D.高效率1.5.2习题——选择题(10)下列时间复杂度中最坏的是_____________。

A.O(1) B.O(n) C.O(log2n) D.O(n2)(11)下列时间复杂度中最好的是_____________。

A.O(1) B.O(n) C.O(log2n) D.O(n2)(12)下列算法的时间复杂度是_____________。

for(i=0;i<n;i++)for(j=0;j<n;