数据结构第一章概论资料.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 a[5]={'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.算法----求解一个特定任务的指令的有限序列 例.求a[0n-1]中n个数的平均值(假定n0) float average(float a[ ],int n) { int i；float s=0.0； //累加器赋初值 for (i=0；in；i++) s=s+a[i]； //a[i]累加到s中 s=s/n； //计算平均值 printf(“ave=%f”,s)； //输出 return(s)； //返回 } 其中：a,n为输入量；s为输出量2.算法的5个特征,(1)有穷性：在有限步(或有限时间)之后算法终止。

例.{ i=0；s=0； while (i10) 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；i1000000000000；++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”, &x)； y=sqrt(x)； //当x0时,出错 return(y)； },4.算法的时间复杂度,衡量算法性能： a.算法正确性； b.执行算法所消耗的时间； c.执行算法所消耗的空间（主要考虑辅存空间）； d.算法易读易理解，易于编码，易于调试等。

主要讨论算法执行时间 算法所消耗的时间：算法中每条语句执行时间之和 每条语句执行时间=语句的执行次数×一次执行该语句的时间 语句的频度：设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n) 问题的规模n：指线性表的长度，多项式的项数，矩阵的阶数，树的结点数，图中的顶点或边数等 注：一次执行语句的时间是很难精确算出的：它与机器的执行速度，编译程序编译质量及运行环境等因素有关 算法所消耗的时间粗略地用算法中语句执行的最大次数来度量//求两个n阶方阵的乘积：C=A*B #define n 100 int Multiply(int a[n][n],int b[n][n],int c[n][n]) { int j,i,k； 语句的频度f(n) (1) for (i=0；in；i++) n+1 (2) for (j=0；jn；j++){ n(n+1) (3) c[i][j]=0； n2 (4) for (k=0；kn；k++) n2(n+1) (5) c[i][j]=c[i][j]+a[i][k]*b[k][j]； n3 } } 算法所消耗的时间就是所有语句频度之和T(n): T(n)=2n3+3n2+2n+1 T(n)是矩阵的阶数n的函数。

当n→∞， 2n3+3n2+2n+1与n3 同阶，即同一数量级记为： T(n)=O(f(n))=O(n3 ) 即与f(n)中最高的阶相同例1 { int s； 语句的频度f(n) scanf(“%d”,&s)； 1 s++； 1 printf(“%d”,s)； 1 } 其中：语句频度为：f(n)=f(1)=3 与问题规模n无关的常数 时间复杂度为：T(n)=O(f(n))=O(3)=O(1） O(1)称成为常量阶/常量数量级 只要算法的执行时间不随问题规模n增大而增长，即使算法中有上千条语句，其执行的时间只不过是一个较大的常数，算法的时间复杂度仍然是常数阶O(1)例2 分析下面的算法,void sum(int a[],int n) f(n） { int s=0,i； // 1次 for(i=0；in；i++) // n次 s=s+a[i]； // n次 printf(“%d”,s)； // 1次 } 其中：语句频度为：f(n)=1+n+n+1 时间复杂度为：T(n)=O(f(n))=O(2n+2)=O(n） O(n)称成为线性阶/线性数量级 一般情况下，对步进循环，只考虑循环体中的语句执行的次数，可忽略步长加1，终值判断，控制转移等成分。

例3 分析下面的算法,1. void sum(int m,int n) 2. { int i,j,s=0； // 1次 3. for(i=1；i=m；i++) // m次 4. { for(j=1；j=n；j++) // m*n次 5. s++； // m*n次 6. printf(“%d”,s)； // m次 7. } 8. } 其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1 当m=n时,f(n)=2n2+2n+1 T(n)=O(f(n))=O(2n2+2n+1)=O(n2) 平方阶 对嵌套层次的循环结构，时间的复杂度T(n)由最内层循环体语句的频度f(n)决定例4 分析下面的算法,1. void sum(int n) 2. { int i,j,s=0； // 1次 3. for(i=1；i=n；。