数据结构第一章概论.ppt
数 据 结 构 -,第一章 绪 论,1.1 数据结构研究什么？ 将现实世界中的数据描述及关系表示出来，并存储到计算机内，供用户程序操作。 现实世界中的数据描述及关系： 4种：离散型，线性结构，层次结构，网状结构。 离散数学：研究离散型。 数据结构：研究线性结构，层次结构和网状结构。 线性结构：线性表表示。 层次结构：树形结构表示。 网状结构：图结构表示。 数据结构研究：数据逻辑结构，存储结构及施加其上的运算。,例1 L=(20,-5,66,15,44)是一个线性表 例2 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)； (姓名，性别，年龄)是记录(record), C语言将记录(record)定义为”结构”(struct)； 登记表也是一个线性表。,例3 家族中父子关系是一种层次结构-树 T,张一,张三,张二一,张三一,张三小,张三大,张二,张四,层次结构： 部门之间的隶属关系： 学校-系-科-班 领导和被领导之间领导关系： 主席-部长-司长-处长-科长,例4 无向图G,A,B,D,C,E,F,G,其中：A、B、C 等是顶点(vertex), 图中任意两个顶点之间都可能有关系。,网络结构： 电网，电信网，计算机通信网等。,1.基本数据结构的定义、特性、运算与算法 1.1 线性结构：线性表；栈,队列,双队列；数组,串。 1.2 非线性结构：树,二叉树；图,网络。 2.数据结构的存储结构与实现 选择存储结构,设计算法 3.查找算法：顺序,折半,分块,哈希,二叉排序树等 4.排序算法：内部排序,外部排序 5.文件 6.基本应用与综合应用 要求具备的知识： c语言及程序设计，具有一定的程序设计能力。,本课程的内容和任务,1.2 基本概念和术语,1.数据（data) - 所有能输入到计算机中并被计算机程序加工、处理 的符号的总称。 如：整数、实数、字符、声音、图象、图形等。 2.数据元素(data element)- 数据的基本单位。（元素、记录、结点、顶点） 在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项(data item)- 是数据的不可分割的最小单位。如：姓名、年龄等 一个数据元素可由一个或多个数据项组成。 如: (姓名、年龄),4.数据对象(data object),由性质相同(类型相同)的数据元素组成的集合。 数据对象是数据的一个子集。 例1 由4个整数组成的数据对象 D1=20,-30,88,45 例2 由正整数组成的数据对象 D2=1,2,3,. 例3 由26个字母组成的数据对象 D3=A,B,C,.,Z 其中：D1，D3是有穷集，D2是无穷集。 5.抽象数据对象 ElemSet=某种同类型的数据元素,6.数据结构(data structure)- 数据之间的相互关系，即数据的组织形式。 内容包括：数据逻辑结构、数据存储结构和数据运算。,数据逻辑结构：数据元素之间的逻辑关系。 数据存储结构：数据元素及其关系在存储器中的存储表示。 数据运算：定义在数据逻辑结构上的操作。如：查询，插入， 删除和修改，排序等。 数据逻辑结构有两大类： 线性结构：特征：若结构是非空集，则仅有一个开始结点和一个终止结点；其他结点都只有一个前趋结点和一个后继结点。 非线性结构：特征：一个结点有多个前趋结点和后继结点。 数据存储结构有4种：顺序存储结构，链接存储结构，索引存储结构和散列存储结构。,数据逻辑结构和存储结构与运算三者之间有紧密的关系： 如：给定一种数据的逻辑结构，可采取顺序存储结构或 链接存储结构进行存储； 按定义的运算和运算性质的不同，施加于同一数据结构 上，则会导致有不同的种类的数据结构产生。 如：限制在线性表的一端做插入和删除操作，称该线 性表为栈； 若限制在线性表的一端插入，另一端删除操作，称该 线性表为队。 其栈和队都有顺序存储结构或链接存储结构，则它们存储结构称为：顺序栈，链式栈，顺序队，链式队。,1.线性表 2.栈 线性结构 3.队列,双队列 4.数组 数据结构 5.字符串 非 线 性 1.树,二叉树 结 构 2.图,数据逻辑结构分类,数据顺序存储结构和链式存储结构（物理结构，存储表示,物理表示）,数据结构在计算机存储器中的映象(mapping)。 (1)顺序存储结构(向量,一维数组) 例. char a5=A,B,C,D； A B C D E 0 1 2 3 4 a是一维数组 (2)非顺序存储结构(链接表：指针类型和结构类型定义） 例. 单链表 data next Head A B C D 4个结点的单链表,7.数据类型（data type)- 是一个值的集合和定义在这个值上的一组操作的总称。 用数据类型定义数据结构。 (1)原子类型(如：int,char,float等) (2)结构类型(如：数组,结构,联合体等） 8.抽象数据类型(Abstract Data Type)- 与计算机的实现无关的数据类型。 形式定义： ADT 抽象数据类型名 1.数据对象； 2.数据关系:一个或多个关系； 3.一组基本操作/运算 ADT 抽象数据类型名 注意：常用DataType表示抽象元素类型。,1.3 算法和算法分析 数据的运算是通过算法描述的。,1.算法-求解一个特定任务的指令的有限序列。 例.求a0.n-1中n个数的平均值(假定n0)。 float average(float a ,int n) int i；float s=0.0； /累加器赋初值 for (i=0；i<n；i+) s=s+ai； /ai累加到s中 s=s/n； /计算平均值 printf(“ave=%f”,s)； /输出 return(s)； /返回 其中：a,n为输入量；s为输出量。,2.算法的5个特征,(1)有穷性：在有限步(或有限时间)之后算法终止。 例. i=0；s=0； while (i<10) s+； i+； (2)确定性：无二义性。 例. x=5；y=10； z=x+y； printf(“%d,%d,%d”,x,y,z)； x+y 解释为：x + (+y)？ (x+)+ y？,(3)可行性：可以在计算机上实现。 for( i=1,s=0；i<1000000000000；+i)s+；？ (4)输入：有0或多个输入量。 (5)输出：至少有一个输出量。 3.算法设计要求 (1)正确性 a.无语法错误； b.对n组输入产生正确结果； c.对特殊输入产生正确结果； d.对所有输入产生正确结果。 (2)可读性：“算法主要是为了人的阅读与交流”。 (3)健壮性：有出错处理的提示。 (4)高效与低存储量,下列描述不符合算法的什么特征和要求？,例1 void suanfa1( ) int i,s=0； for (i=0；i=0；i+) /死循环 s+； /不能终止 例2 float suanfa2( ) int x,y； scanf(“%d”, (2) while(i=0 若a中最前一个元素是要找的k，则(3)语句的频度为常数0。在这种情况下，采用最坏的时间复杂度作为算法的时间复杂度：T(n)=0(n),常用时间复杂度递增依次为： 常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n2), 立方阶O(n3)K方阶O(nk)， 指数阶O(2n)。 O(1)算法效率最高，O(2n)算法效率最低。 5.算法的空间复杂度 执行算法所需存储空间的大小。也是问题规模n的函数。 6.算法的复杂度 包括：算法时间复杂度和算法空间复杂度。,低,高,例6 冒泡排序的C语言算法 / 对数组a中n个数按递增次序作冒泡排序 1. Void bubble1(int a,int n) 2. int i,j,temp； 3. for(i=0；iaj+1) / ？ 次 6. temp=aj； / ？ 次 7. aj=aj+1； / ？ 次 8. aj+1=temp； / ？ 次 9. 10. for(i=0；i<n；i+) / n 次 11. printf(“%d”,ai)； / n 次 12. 思考：在最好情况下，f(n)= ? T(n)=O(f(n)= ? 在最坏情况下，f(n)= ? T(n)=O(f(n)= ?,例7 冒泡排序的“类C语言”算法 / 对数组a中n个数按递增次序作冒泡排序 1. void bubble2(int a,int n) 2. for(i=n-1,change=TRUE；i1 && change；i-) 3. change=FALSE； / change为交换标志 4. for(j=0；jaj+1) 6. aj aj+1；/ 交换元素 7. change=TRUE； /修改交换标志 8. 9. 10. 思考：在最好情况下，f(n)= ? T(n)=O(f(n)= ? 在最坏情况下，f(n)= ? T(n)=O(f(n)= ?,
