课程简介

课程简介数据结构深圳大学计算机系蔡茂国《数据结构》课程简介本课程教材为：《数据结构》(C语言版)严蔚敏，吴伟民清华大学出版社2004年11月（第28次印刷）2主要参考教材《数据结构》课程简介所有课件、作业及实验，均上传至：深圳大学首页－－课程中心－－输入学生姓名及密码，实现登录－－从《数据结构》课程下下载3课件下载第一章数据结构绪论数据结构深圳大学计算机系蔡茂国一、数据5第一节数据结构是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据非数值性数据第１章数据结构绪论二、数据元素（DataElement）6第一节数据结构数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成（此时数据元素被称为记录）数据元素又称为元素、结点、记录第１章数据结构绪论三、数据项（DataItem）7第一节数据结构具有独立含义的最小标识单位。第１章数据结构绪论学号姓名学院专业四、数据对象（DataObject）8第一节数据结构具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象C={‘A’,‘B’,‘C’,…‘F’}。第１章数据结构绪论五、结构（Structure）9第一节数据结构结构是元素之间的：空间位置关系相互作用和依赖关系第１章数据结构绪论五、结构10第一节数据结构四种基本结构集合结构线性结构树形结构图形结构第１章数据结构绪论456231125436123456123456六、数据结构（DataStructure）11第一节数据结构1.形式定义：某一数据对象的所有数据成员之间的关系。记为：Data_Structure={D,S}其中，D是某一数据对象，S是该对象中所有数据成员之间的关系的有限集合。第１章数据结构绪论六、数据结构12第一节数据结构2.线性数据结构举例L={K,R}K={1,2,3,4,5,6}R={1,2,2,3,3,4,4,5,5,6}第１章数据结构绪论123456六、数据结构13第一节数据结构3.树形数据结构举例T={K,R}K={1,2,3,4,5,6}R={1,2,1,3,2,4,2,5,3,6}第１章数据结构绪论456231六、数据结构14第一节数据结构4.图形数据结构举例G={K,R}K={1,2,3,4,5,6}R={(1,2),(1,5),(1,6),(2,3),(2,4),(2,6),(3,4),(4,5),(4,6),(5,6)}第１章数据结构绪论123456七、应用举例15第一节数据结构1.线性数据结构举例数据结构学生选课名单（部分）第１章数据结构绪论学号姓名学院专业2004131221黄磊信息工程学院信息工程学院2004131209熊玲玲信息工程学院信息工程学院2004131135彭智俊信息工程学院信息工程学院2004131252徐元庆信息工程学院信息工程学院2004131099吴小池信息工程学院信息工程学院2004131031陈明亮信息工程学院信息工程学院七、应用举例16第一节数据结构2.树形数据结构举例UNIX文件系统结构图（部分）第１章数据结构绪论/rootbinlibuseretcmathdsswhangxiongpan七、应用举例17第一节数据结构3.图形数据结构举例深圳城市交通示意图（部分）第１章数据结构绪论南山福田罗湖盐田宝安西丽梅林布吉龙华龙岗八、数据结构要解决的问题18第一节数据结构如何为应用程序中涉及到各种各样的数据，建立相应的数据结构（表、树或图），并依此实现软件功能从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现第１章数据结构绪论一、逻辑结构19第二节数据的结构逻辑结构描述数据元素之间的关系线性结构线性表（表，栈，队列，串等）非线性结构树（二叉树，Huffman树，二叉排序树等）图（有向图，无向图等）第１章数据结构绪论456231123456123456二、物理结构（存储结构）20第二节数据的结构物理结构是数据结构在计算机中的表示（或映象）顺序存储表示（可以用C语言中一维数组表示）链接存储表示（可以用C语言中的指针表示）索引存储表示散列存储表示第１章数据结构绪论二、物理结构（存储结构）21第二节数据的结构复数存储结构举例第１章数据结构绪论z1=3.0-2.3i指针或链(地址)…041506110613……-2.33.00415z1=3.0-2.3iz2=-0.7+4.8i…0300030206320634……3.0-2.3-0.74.8顺序存储结构链式存储结构一、数据类型22第三节数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称如C语言中的整型变量(int)，其值集为某个区间上的整数，定义在其上的操作为+,-,x,/等第１章数据结构绪论二、原子数据类型和结构数据类型23第三节数据类型1.原子数据类型是不可分解的数据类型如C语言中的整型(int)，实型(float)，字符型(char)，指针类型(*)和空类型(void)等第１章数据结构绪论二、原子数据类型和结构数据类型24第三节数据类型2.结构数据类型由若干成分（原子类型或结构类型）按某种结构组成的数据类型结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体如数组，由若干分量组成，每个分量可以是整数，也可以是数组（如intA[10]）第１章数据结构绪论三、抽象数据类型（AbstractDataType）25第三节数据类型由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离第１章数据结构绪论三、抽象数据类型（ADT）26第三节数据类型抽象数据类型（ADT）是一个数学模型以及定义在该模型上的一组操作抽象数据类型=数据结构+定义在此数据结构上的一组操作第１章数据结构绪论三、抽象数据类型（ADT表示）27第三节数据类型抽象数据类型可用（D，S，P）三元组表示D是数据对象S是D上的关系集P是对D的基本操作集。第１章数据结构绪论三、抽象数据类型（ADT定义）28第三节数据类型ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作(函数)的定义〉}ADT抽象数据类型名第１章数据结构绪论三、抽象数据类型（ADT定义举例）29第三节数据类型ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3∈ElemSet}数据关系：R={e1,e2,e2,e3}基本操作：Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最小值。}ADTTriplet第１章数据结构绪论三、抽象数据类型（ADT定义实现）30第三节数据类型抽象数据类型可以通过固有数据类型(C语言中已实现的数据类型)来实现抽象数据类型类class数据对象数据成员基本操作成员函数(方法)第１章数据结构绪论一、算法（Algorithm）31第四节算法分析算法是对特定问题求解步骤的一种描述是一有限长的操作序列第１章数据结构绪论一、算法（特性）32第四节算法分析有穷性：算法在执行有穷步后能结束确定性：每步定义都是确切、无歧义可行性：每一条运算应足够基本(已验算正确)输入：有0个或多个输入输出：有一个或多个输出第１章数据结构绪论一、算法（举例）33第四节算法分析例子：选择排序问题：递增排序解决方案：逐个选择最小数据算法框架：for(inti=0;in-1;i++){//n-1趟从a[i]检查到a[n-1]，找到最小数;若最小整数在a[k],交换a[i]与a[k];}第１章数据结构绪论二、算法设计的要求34第四节算法分析正确性：满足具体问题的需求可读性：便于理解和修改健壮性：当输入数据非法时，也能适当反应效率高：执行时间少空间省：执行中需要的最大存储空间第１章数据结构绪论三、时间复杂度35第四节算法分析衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度事后统计法：计算算法开始时间与完成时间差值事前统计法：依据算法选用何种策略及问题的规模n，是常用的方法第１章数据结构绪论三、时间复杂度36第四节算法分析时间复杂度是问题规模n的函数f(n)，即：T(n)=O(f(n))一般地，时间复杂度用算法中最深层循环内的语句中的原操作的重复执行次数表示第１章数据结构绪论三、时间复杂度37第四节算法分析a.{y*=x;}b.for(i=1;i=n;i++}{y*=x;}c.for(j=1;j=n;j++}for(i=1;i=n;i++}{y*=x;}a,b,c三个算法中，“y*=x;”程序段的时间复杂度分别为O(1),O(n),O(n2)，分别称为常量阶，线性阶，平方阶第１章数据结构绪论三、时间复杂度38第四节算法分析时间复杂度除常量阶[O(1)],线性阶[O(n)],平方阶[O(n2)]外，还有对数阶[O(logn)]，排列阶[O(n!)]，指数阶[O(2n)]等，是相对于问题规模n的增长率的表示方法指数阶随问题规模增长过快，一般不宜使用第１章数据结构绪论三、时间复杂度39第四节算法分析如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度如果无法求取平均时间复杂度，则采用最坏情况下的时间复杂度时间复杂度是衡量算法好坏的一个最重要的标准第１章数据结构绪论四、空间复杂度40第四节算法分析空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：S(n)=O(f(n))第１章数据结构绪论第二章线性表数据结构深圳大学计算机系蔡茂国一、线性数据结构的特点42第一节线性表在数据元素的非空有限集中１、存在惟一的一个被称作“第一个”的数据元素(如“１”)２、存在惟一的一个被称作“最后一个”的数据元素(如“６”)３、除第一个元素外，每个数据元素均只有一个前驱４、除最后一个元素外，每个数据元素均只有一个后继(next)(如“1”的next是“2”,“2”的next是“3”)第２章线性表123456二、线性表43第一节线性表线性表是最简单的一类线性数据结构线性表是由n个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系，可以写为：(a1,a2,…ai-1,ai,ai+1,…an-1,an)其中,ai是表中元素,i表示元素ai的位置,n是表的长度第２章线性表二、线性表44第一节线性表线性表中的元素具有相同的特性，属于同一数据对象，如：1.26个字母的字母表:(A,B,C,D,…,Z)2.近期每天的平均温度:(30℃,28℃,29℃,…)第２章线性表一、顺序表45第二节顺序表顺序表是线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素第２章线性表ABCDE…YZbb+1b+2b+3b+4…b+24b+25一、顺序表（元素位置）46第二节顺序表顺序表数据元素的位置：LOC(ai)=LOC(ai-1)+lLOC(ai)=LOC(a1)+(i-1)*ll表示元素占用的内存单元数第２章线性表a1a2…ai………an12…i………nbb+l…b+(i-1)*l………b+(n-1)*lidle二、顺序表的定义47第二节顺序表采用C语言中动态分配的一维数组表示顺序表第２章线性表#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量Typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(元素数)}Sqlist;三、顺序表的