数据结构课程简介课件

数据结构课程简介一、课程性质与教学目的二、基本要求三、教学内容四、学分及学时分配五、参考书目六、前期课程及后续课程第一章一、课程性质与教学目的 用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是数据结构要研究的内容。数据结构是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。二、基本要求1.了解数据结构及其分类、数据结构与算法的密切关系。2.熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3.掌握设计算法的步骤和算法分析方法。4.掌握数据结构在排序和查找等常用算法中的应用。5.初步掌握文件组织方法和索引技术。三、教学内容见书目录学时：课程讲授学时四、学分及学时分配五、参考书目v严蔚敏等著 数据结构 清华大学出版社 1997v范策等著 算法与数据结构 机械工业出版社 2004v李春保 数据结构与习题解析 清华大学出版社 1997v谢楚屏等编著 数据结构 人民邮电出版社六、前期课程及后续课程v前期：C语言，计算机基础，离散数学v后续：操作系统，数据库等目目目目 录录录录第一章第一章第一章第一章 绪绪绪绪 论论论论第二章第二章第二章第二章 线性表线性表线性表线性表第三章第三章第三章第三章 栈和队列栈和队列栈和队列栈和队列第四章第四章第四章第四章 串串串串第五章第五章第五章第五章 数组和广义表数组和广义表数组和广义表数组和广义表第六章第六章第六章第六章 树和二叉树树和二叉树树和二叉树树和二叉树第七章第七章第七章第七章 图图图图第八章第八章第八章第八章 查查查查 找找找找第九章第九章第九章第九章 内部排序内部排序内部排序内部排序第十章第十章第十章第十章 文文文文 件件件件q 本本 章章 说说 明明1.1 数据结构数据结构1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现1.4 算法和算法分析算法和算法分析本章说明q本章的主要内容基本概念和术语 抽象数据类型的表示与实现算法和算法分析（掌握时间复杂度和空间复杂度）q本章与后续各章的关系本章是后续各章的准备1.1 数据结构1什么是数据结构 我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。例1-1 书目检索自动化问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表 计算机处理的对象之间存在着线性关系，称为线性的数据结构。例1-2 人机对奕问题树.CEDABABACADBABCBDDADBDCEAEBECED图例1-3 多岔路口交通灯的管理问题v1968年美国克努特教授开创了数据结构的最初体系：v数据的逻辑结构和存储结构及其操作。v数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。2.数据结构课程数据结构定义v数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科主要研究和讨论以下三个方面的问题:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构.(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构.(3)对各种数据结构进行的运算.1.2 基本概念和术语1数据2数据对象、数据结构3数据的两种存储结构4.数据类型、抽象数据类型 v数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机加工的“原料”。v数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，也称节点或记录v数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。1.2 基本概念和术语1.数据q数据对象：是性质相同的数据元素的集合，是数据的一个子集。例：整数数据对象是集合N=0，1，2，字母字符数据对象是集合C=“A”，“B”，“Z”q数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。2.数据对象、数据结构1.2 基本概念和术语 根据数据元素间关系的基本特性，有四种基本数据结构：集 合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图数据结构的形式定义：数据结构是一个二元组 Data_Structure=(D,S)其中，D 是数据元素的有限集,S 是D上关系的有限集例1-4 复数 Complex=(C,R)例1-5 课题小组 Group=(P,R)P=T,G1,Gn,S11,Snm1n3，1m2，R=R1,R2R1=|1in,1n3,R2=|1in,1jm,1m2,1.2 基本概念和术语位：在计算机中表示信息的最小单位，二进制数的一位位串：由若干个位组合，表示一个数据元素。（以后称“元素”或“结点”）例：整数用一个字长（16位）表示，字符用8位表示子位串：表示一个数据项。（以后称“数据域”）q数据的逻辑结构只抽象反映数据元素的逻辑关系q数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现1.2 基本概念和术语数据的逻辑结构与存储结构密切相关 算法设计 取决于选定的逻辑结构 算法实现 依赖于采用的存储结构存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系3数据的两种存储结构1.2 基本概念和术语元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Loc+（i-1)*m顺序存储1536元素21400元素11346元素3 元素41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 1400 1400 13461346 元素元素4 4 .1400 1400 元素元素2 2 1536 1536 .15361536 元素元素3 3 13461346 链式存储 h 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表栈队树形结构图形结构数据结构的三个方面：数据类型：是一个值的集合和定义在这个值集上的所有 的操作。如，整型。数据类型可分为：非结构的原子类型和结构类型。v 原子类型的值是不可分解的v结构类型的值是由若干成分按某种结构组成的。4.数据类型 抽象数据类型 数据类型在高级语言中指数据的取值范围及其上可进行的操作的总称例 C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;数据类型可以看成是已经实现了的数据结构。抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。也就是说抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。按抽象数据类型值的不同特性，分为三种类型：原子类型:变量的值是不可分解的。固定聚合类型:变量的值由确定数目的成分按 某种结构组成。可变聚合类型:其值的成分数目不确定。抽象数据类型的形式定义 我们用一个三元组来表示一个抽象数据类型：（D，S，P）D是数据对象，S是D上的关系集，P是对D的基本操作。ADT 抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT 抽象数据类型名。数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述抽象数据类型格式：P8-9例1-6 抽象数据类型三元组的定义：ADT Triplet 数据对象：D=e1，e2,e3|e1,e2,e3Elemset (定义了关系运算的某个集合)数据关系：R1=e1,e2,基本操作：InitTriplet(&T,v1,v2,v3)/构造三元组T，e1,e2,e3分别被赋以参数v1,v2,v3的值DestroyTriplet（&T）/撤消三元组T Get Get（T,i,&eT,i,&e）/三元组三元组T T已存在，已存在，1=i=31=i=3 用用e e返回第返回第i i元的值元的值 Put(&T,i,e)/Put(&T,i,e)/三元组三元组T T已存在，已存在，1=i=31=i=3 将将T T的第的第i i元值变为元值变为e e IsAscending(TIsAscending(T)/)/三元组三元组T T已存在，已存在，1=i=31=i=3 三元素若升序排列返回三元素若升序排列返回1 1，否则返回，否则返回0 0 IsDescending(TIsDescending(T)Max(T,&e)Max(T,&e)Min(T,&e)Min(T,&e)ADT Triplet v多形数据类型：是其值的成分不确定的数据类型。如例1-6中定义的抽象数据类型Triplet，其元素e1,e2,e3可以是整数或字符串，也可以是由多种成分构成。1.3 抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。精选了C 的一个子集，扩充修改，增强了语言的描述功能。v预定义常量和类型v数据结构的表示：存储结构用类型（typedef）定义来 描述。v数据元素类型约定为ElemType.v基本操作的算法用函数描述：1类C语言P10-11v函数类型 函数名（函数参数表）/算法说明 语句序列 /函数名v增加了引用调用的参数传递方式。v赋值语句、选择语句(if else,switch)、循环语句(for,while,do while)、结束语句、输入输出语句(scanf,printf)、注释语句v基本函数v逻辑运算约定:&|例1-7 Triplet的表示和实现/-采用动态分配的顺序存储结构Typedef ElemType*Triplet;/由InitTriplet分配三个元素存储空间/-基本操作的函数原型说明Status InitTriplet(Triplet&T,ElemType v1,ElemType v2,ElemType v3)Status DestroyTriplet（&T）Status Get（T,i,&e）Status Put(&T,i,e)Status IsAscending(T)Status IsDescending(T)Status Max(T,&e)Status Min(T,&e)/-基本操作的实现 Status InitTriplet(Triplet&T,ElemType v1,ElemType v2,ElemType v3)/构造三元组T，依次置T的三个元素的处值为v1,v2和v3。T=(ElemType*)malloc(3*sizeof(ElemType);/分配三个元素的存储空间If(!T)exit(OVERFLOW);/分配存储空间失败T0=v1;T1=v2;T2=v3;return OK;/InitTripletStatus DestroyTriplet（Triplet&T）/销毁T free(T);T=NULL;return OK;/DestroyTripletStatus Get（Triplet T,int i,ElemType&e）/1=i=3,用e返回T的第i元的值 if(i3)return ERROR;e=Ti-1;return OK;/GetStatus Put（Triplet T,int i,ElemType&e）/1=i=3,用e返回T的第i元的值 if(i3)return ERROR;Ti-1=e;return OK;/PutStatus Max（Triplet T,ElemType&e）/用e返回指向T的最大元素值 e=(T0=T1)?(T0=T2)?T1:T2);return OK;/Max1.4 算法和算法分析1算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的重要特性：有穷性算法必须在执行有限步骤后结束确定性算法的每一步必须是确切定义的，不能产生二义性可行性算法是能实现的输 入一个算法有零个或多个输入输 出一个算法有一个或多个输出1.4 算法和算法分析2算法设计的要求衡量算法优劣的标准q 正确性q 可读性 q 健壮性q 效率与低存储量要求3算法效率的度量v算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量。（算法时间是由控制结构和原操作的决定的）v记号引用了“O”。“O”表示一个 数量级的概念。本书中根据算法中语句执行的最大次数（频度）来 估算一个算法执行时间的数量级。v时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），T（n）=O（f（n）它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。v语句的频度：是该语句重复执行的次数。1.4 算法和算法分析#define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn)int i,j,k for(i=1;i=n;+i)/n+1for(j=1;j=n;+j)/n*(n+1)Cij=0;/n2for(k=1;k=n,k+)n2(n+1)Cij=Cij+aik*bkj;/n3 T(n)=n+1+n*(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1量级：T(n)=O(n3)例：求两个n阶方阵的乘积C=AB例：（a）+x;s=0;（b）for(i=1;i=n;+i)+x;s+=x;（c）for(j=1;j=n;+j)for(k=1;karrsize 或对某个 k(1kn)使 k!2kmaxint 时，应按出错处理。注意选择你认为较好的出错处理方法。课后习题3.在程序设计中，可采用下列三种方法实现输出和输入：(1)通过 scanf 和 printf 语句；(2)通过函数的参数显式传递；(3)通过全局变量隐式传递。试讨论这三种方法的优缺点，并编写算法求一元多项式的值，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法，本题的输入为ai(i=0,1,n)，x0和n，输出为Pn(x0)。课后习题4.设 n 为正整数。试确定下列各程序段中前置以记号 的语句的频度：(1)i=1;k=0;while(i=n-1)k+=10*i;i+;(2)i=1;k=0;do k+=10*i;i+;while(i=n-1);课后习题 (3)i=1;k=0;while(i=n-1)i+;k+=10*i;(4)k=0;for(i=1;i=n;i+)for(j=i;j=n;j+)k+;(5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+=delta;课后习题 (6)i=1;j=0;while(i+jj)j+;else i+;(7)x=n;y=0;/n 是不小于1的常数while(x=(y+1)*(y+1)y+;(8)x=91;y=100;while(y0)if(x100)x-=10;y-;else x+;课后习题