搜索
数据结构佛山科学技术学院环建学院佛山科学技术学院FoshanUniversity2课程简介内容简介数据结构+算法=程序数据结构：问题的数学模型线性结构：线性表、栈、队列、串、…非线性结构：树…算法：求解问题的策略学时：56其中理论课46实验课10佛山科学技术学院FoshanUniversity3计算机专业的内功：数据结构、算法、离散数学、操作系统、数据库原理、计算机原理、编译原理、…——打基础是苦功夫，不愿吃苦是不能修成正果的！计算机的外功：语言、技术、平台、标准和工具计算机专业=编程专业?佛山科学技术学院FoshanUniversity4第一章绪论重点：数据结构的基本概念难点：ADT、算法复杂度基础：C语言的基本知识佛山科学技术学院FoshanUniversity5第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求佛山科学技术学院FoshanUniversity61.1什么是数据结构【例1】学生成绩单要求：给定学生的学号或姓名，要求打印出其成绩；若学生不存在，则报告没有该学生的信息。学号姓名成绩PB01001张平80PB01002王晴85………佛山科学技术学院FoshanUniversity71.1什么是数据结构【例1】学生成绩单计算机处理该问题时，应考虑：1)数据及其存储：学生(学号,姓名,成绩)structstudent{charsNo[8];charsName[9];intnScore;}astStudent[200];2)基本运算的实现佛山科学技术学院FoshanUniversity81.1什么是数据结构【例】图书馆的书目检索系统自动化问题【例】计算机和人对弈问题【例】多叉路口交通灯的管理问题【例】计算机辅助设计（CAD）问题【例】计算机辅助制造（CAM）问题【例】产品质量在线检测与故障诊断问题【例】智能设备控制问题【例】企业资源规划（ERP）问题【例】客户关系信息管理（CRM）问题【例】企业发展规划决策与分析问题。。。。。。佛山科学技术学院FoshanUniversity91.1什么是数据结构1）描述这类非数值计算问题的数学模型不是数学方程，而是树、表等之类的数据结构2）数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现结论佛山科学技术学院FoshanUniversity10第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求佛山科学技术学院FoshanUniversity111.2基本概念和术语1）客观事物的符号表示2）能输入到计算机中被计算机程序处理的符号集数据(Data)佛山科学技术学院FoshanUniversity121.2基本概念和术语1）数据的基本单位2）在计算机程序中作为一个整体进行考虑和处理3）一个数据元素可以由若干数据项(DataItem)组成4）数据项是具有独立含义的最小标识单位数据元素(DataElement)佛山科学技术学院FoshanUniversity131.2基本概念和术语性质相同的数据元素的集合e.g.C={‘A’,‘B’,…,‘Z’}数据对象(DataObject)佛山科学技术学院FoshanUniversity14形式定义：Data_Structure=(D,S)其中：D—数据对象,数据元素的有限集S—是D上关系的有限集数据结构(DataStructure)1.2基本概念和术语佛山科学技术学院FoshanUniversity15关系集合是空集，顶点元素间无任何关系。四个基本数据结构－－集合1.2基本概念和术语佛山科学技术学院FoshanUniversity161)元素间的关系是1:12)一个结点（除头结点外）有且仅有一个直接前驱3)一个结点（除尾结点外）有且仅有一个直接后继四个基本数据结构－－线性结构1.2基本概念和术语佛山科学技术学院FoshanUniversity17一个结点可以有多个直接后继（除叶子结点外），但只有一个直接前驱（除根结点外）。四个基本数据结构－－树型结构1.2基本概念和术语佛山科学技术学院FoshanUniversity18元素间的关系是m:n，一个结点可以有多个直接后继，也可以有多个直接前驱四个基本数据结构－－图型结构1.2基本概念和术语佛山科学技术学院FoshanUniversity191.2基本概念和术语-逻辑结构数据的逻辑结构特征从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关与数据元素的相对位置无关分类线性结构：线性表非线性结构：树、图佛山科学技术学院FoshanUniversity201.2基本概念和术语-存储结构数据的存储结构(物理结构)数据结构在计算机中的表示(又称映像)数据元素之间的关系的表示顺序映像（顺序存储结构）向量或数组（表格存储结构）非顺序映像（链式存储结构）单链表、双链表、多重链表、循环链表索引存储结构散列(hash)存储结构借用程序语言中的“数据类型”描述存储结构算法的设计取决于选定的数据（逻辑）结构，算法的实现取决于采用的存储结构佛山科学技术学院FoshanUniversity211.2基本概念和术语-数据类型数据类型—最早出现在高级程序语言中一个值的集合和定义在该值集上的一组操作按“值”的不同特性，数据类型可分为：原子类型：值不可分解。如C语言中的基本类型(整型、实型、字符型和枚举型)、指针类型和空类型。结构类型：值由若干成分按某种结构组成。如C语言中的数组、结构体类型应用：计算机硬件系统、操作系统、高级语言、数据库等计算机硬件系统：位、字节、字…佛山科学技术学院FoshanUniversity221.2基本概念和术语-抽象数据类型抽象数据类型(AbstractDataType,ADT)一个数学模型及定义在该模型上的一组操作。【例如】矩阵+（求转置、加、乘、逆、特征值）其定义仅取决于一组逻辑特性，而与计算机内部如何表示和实现无关佛山科学技术学院FoshanUniversity231.2基本概念和术语-抽象数据类型抽象数据类型(AbstractDataType,ADT)“抽象”：数据类型的数学抽象特性按值的不同特性，分为原子类型：值不可分解固定聚合类型：值由确定数目的成分按某种结构组成。如：复数由两个实数按确定的次序构成可变聚合类型：值的成分的数目不确定。如：可定义一个“有序整数序列”的抽象数据类型。佛山科学技术学院FoshanUniversity24抽象数据类型定义为（D,S,P）D—数据对象S—D上的关系集P—对D的基本操作集抽象数据类型1.2基本概念和术语-抽象数据类型佛山科学技术学院FoshanUniversity251.2基本概念和术语-抽象数据类型ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉佛山科学技术学院FoshanUniversity261.2基本概念和术语-抽象数据类型抽象数据类型的特征：数据抽象对程序处理的实体的描述,强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节佛山科学技术学院FoshanUniversity271.2基本概念和术语-抽象数据类型【例1-4】抽象数据类型复数的定义ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{e1,e2|e1是复数的实数部分,e2是复数的虚数部分}基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1、z2的和值。}ADTComplex佛山科学技术学院FoshanUniversity281.2基本概念和术语-抽象数据类型【例1-6】抽象数据类型三元组的定义ADTTriplet{数据对象：D＝{e1,e2,e3｜e1,e2,e3∈ElemSet}数据关系：R1＝{e1,e2,e2,e3}基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造三元组T,元素e1,e2和e3分别被赋以参数v1,v2和v3的值。DestroyTriplet(&T)操作结果：三元组T被销毁。Get(T,i,&e)初始条件：三元组T已存在，1≤i≤3。操作结果：用e返回T的第i元的值。Put(&T,i,e)初始条件：三元组T已存在，1≤i≤3。操作结果：改变T的第i元的值为e。……}ADTTriplet可以是int,char,…或复杂的结构类型佛山科学技术学院FoshanUniversity29第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求佛山科学技术学院FoshanUniversity301.3抽象数据类型的表示与实现表示：伪语言借用程序设计语言的结构描述---简洁、严谨忽略程序设计语言的细节---简洁伪C语言与C语言的区别抽象数据类型：typedef赋值：成组赋值、交换赋值选择语句：switch的扩展输入/输出：可以忽略格式串头文件、辅助变量定义：忽略C的扩展：引入C++的引用参数表示变参佛山科学技术学院FoshanUniversity311.3抽象数据类型的表示与实现伪C中的引用参数——C的扩展C的虚实结合：单向的值传递函数定义函数调用swap(inta,intb)┆{inta=3,b=4;intt;swap(a,b);//a为3，b为4t=a;a=b;b=t;┆}3a4bab形参单元34t343返回佛山科学技术学院FoshanUniversity321.3抽象数据类型的表示与实现伪C中的引用参数——C的扩展问题：如何简单地表示返回多个值？C支持的全局变量策略：inta=3,b=4;swap()┆{swap();//a为4，b为3intt;swap();//a为3，b为4t=a;a=b;b=t;┆}将形参定义为指针类型swap(int*pa,int*pb)intt;t=*pa;*pa=*pb;*pb=t;}将返回值定义为指针类型佛山科学技术学院FoshanUniversity331.3抽象数据类型的表示与实现C语言中标识符的辨别规则各种数据类型的关键信息及标志简单类型：具体的值类型，如int,float…数组：规模--维数、每一维的长度[]元素类型指针：指向的单元所具有的类型*函数：函数值的类型()结构体：各成员的类型struct共用体：各成员的类型union算符的优先级与结合性(),[],.,-自左向右结合单目运算符：类型运算符,*自右向左结合佛山科学技术学院FoshanUniversity34第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求佛山科学技术学院FoshanUniversity3