• /  40
  • 下载费用: 14.90积分  

绪论信息技术算法和程序福建教师招考

'绪论信息技术算法和程序福建教师招考'
数 据 结 构 参考书目:Ø《数据结构》 ——高等教育出版社 刘大有、唐海鹰、孙舒杨、虞强源、杨鲲 编著Ø《数据结构C++语言描述》 ——清华大学出版社 William Ford 、 William Topp 著 刘卫东、沈官林 译 严蔚敏 审Ø《数据结构程序设计题典》 ——清华大学出版社 李春葆、曾惠、张植民 编著 力为运动商城www.leevy.cn整理 目 录 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表力为运动商城www.leevy.cn整理 第六章 树 第七章 图 第八章 查找 第九章 排序 期末复习 力为运动商城www.leevy.cn整理 第一章 绪 论Ø 知 识 点 数据结构中常用的基本概念和术语 算法描述和分析方法 Ø 难 点 算法复杂度的分析方法 Ø 要 求 了解数据的逻辑结构和存储结构, 算法的基本概念,它们对于程序设 计的重要性以及相互关系 掌握算法时间复杂度的概念及分析方法第 1 章 绪 论 数据结构 什么是数据结构例1:02080- 3350102198306077480595291832736200 002080-3 班号 0595-2918327 办公室电话号码362000 泉州邮编35010219830607748 身份证号码 结论1. 杂乱的数据不能表达和交流信息 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 6第 1 章 绪 论 数据结构 例2: 电话号码簿 (a1,b1) (a2,b2)…(an,bn) 其中: ai为某人姓名,bi为该人的电话号码。 要求:设计一个算法,给定一个姓名时, 能查出此人的电话号码。 ? 如果姓名和电话号码的排列次序无规律, 则只能逐一比较姓名进行查找 ? 如果姓名按字典顺序组织,则查找就快捷多了 结论2. 数据之间是有联系的   这些联系常常影响算法的选择和效率。   《DS》就是要研究数据之间的联系。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 7第 1 章 绪 论 数据结构 例3:大学学生管理机构 学校     一系  ...八系 ...        一年级 二年级 三年级 四年级         1班 ...8班         张三...李四 结论3. 数据之间是有结构的 例3中数据之间呈分层结构(树状结构) 《DS》就是要研究数据之间的各类结构。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 8第 1 章 绪 论 数据结构 例4:图书目录管理 设每个书目含:书名,作者,登录号,分类,出版 年月 对图书目录常有如下操作: ? 查找:某书在书库中是否存在? ? 插入:购进新书时的登录; ? 删除:报废或丢失的书,需从目录中去掉;结论4. 在某种数据结构上可定义一组运算《DS》就是要研究各类数据结构上的各种运算。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 9第 1 章 绪 论 数据结构 综上所述: 《DS》主要研究内容: ? 数据的组织形式(数据的各种逻辑结构和存 储结构,以及它们之间的相应关系); ? 定义相应的操作(算法); ? 实现操作(设计算法); ? 评估算法(分析算法的效率)。 数据结构讨论描述现实世界实体的数学模型 及其上的操作在计算机中的表示和实现。 常见的数据结构有: 数组、栈、队列、表、串、树、图和文件等。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 10第 1 章 绪 论 数据结构 常见数据结构示例 1. 线性表示例 学号 姓名 性别 籍贯 电 话 通 讯 地 址 01 张三 男 长沙 8639000 麓山南路327 号 02 李四 男 北京 23456789 学院路435 号 03 王五 女 广州 30472589 天河路478 号 04 赵六 男 上海 41237568 南京路1563 号 05 钱七 女 南京 5013472 南京大学 06 刘八 女 武汉 61543726 武汉大学 07 朱九 男 昆明 4089651 云南大学 08 孙十 女 杭州 6154372 西湖路635 号 图1-1 学生数据表 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 11第 1 章 绪 论 数据结构 2. 树形结构示例 一层 Tt a b c 二层 b1 b c a1 a2 2 1 c2 d 三层 d1 d2 d3 四层 图 1-2 树形结构示意图 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 12第 1 章 绪 论 数据结构 3. 图形结构示例 1 2 3 6 4 5 图 1-3 图形结构示意图 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 13第 1 章 绪 论 数据结构 基本概念和术语? 数据(Data):一切能够由计算机接受和处理的对 象。 ? 数据元素(Data element):数据的基本单位,是 组成数据的“事实”、“数值”或“符号” ,在 程序中作为一个整体加以考虑和处理 。? 数据项(Data item):数据的不可分割的最小单位, 在有些场合下,数据项又称为字段或域。? 数据对象(Data object):性质相同的数据元素 组成的集合,是数据的一个子集。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 14第 1 章 绪 论 数据结构 数据及数据元素 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 15第 1 章 绪 论 数据结构? 数据结构(Data structure): v是相互之间存在一种和多种特定关系的数据元 素的集合 v讨论计算机系统中数据的组织形式及其相互关 系? 数据结构的研究,主要指数据的逻辑结构 和物理结构的研究 Ø数据的逻辑 结构:数据元素之间的相互关系 Ø数据的物理 结构:数据结构在计算机的表示, 又称数据的存储结构,包括数据元素的表示和 关系的表示 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 16第 1 章 绪 论 数据结构 逻辑结构? 数据之间的相互关系称为逻辑结构。 通常分为4类基本结构: ? 集合:结构中的数据元素除了同属于一种类型 外,别无其它关系。 ? 线性结构:结构中的数据元素之间存在一对一 的关系。 ? 树型结构:结构中的数据元素之间存在一对多 的关系。 ? 图状结构或网状结构:结构中的数据元素之间 存在多对多的关系。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 17第 1 章 绪 论 数据结构数据(逻辑)结构的形式定义为: 一个二元组: Data-Structure=(D,S) 其中: D是数据元素的有限集; S是D上关系的有限集。例 复数的数据结构定义: Complex=(C,R) 其中:C是含两个实数的集合﹛C1,C2﹜,分别表 示复数的实部和虚部。R={P},P是定义在集合上 的一种关系{〈C1,C2〉}。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 18第 1 章 绪 论 数据结构 存储结构: ? 顺序存储结构 Ø 连续顺序地存放数据元素 Ø 若数据的逻辑结构也是顺序(线性)的,则逻辑结构和 物理结构就完全统一 Ø 连续存放的数据元素可以在内存中容易找到 ? 链式存储结构 ü 元素在内存中不一定连续存放 ü 在元素中附加指针项,通过指针可以找到关系元素 元素+指针 结点 元素 指针 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 19 第 1 章 绪 论 数据结构顺序存储结构 0300 K1 0301 K2 0302 K3 0303K1 K2 K3 K4 K4 0304 0305 0306 0307 0308 0309 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 20第 1 章 绪 论 数据结构 0300 K1 K1 0301 K2 0302 K3 0303 K2 K3 K4 0304 K5 0305K4 K5 K6 K6 0306 0307 0308 0309 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 21 第 1 章 绪 论 数据结构 链式存储结构 K1 0300 K1 0310 K2 0320 K2 K3 K3 0330 K4 0340 K5 0350 K4 K5 K6 K6 0370 0380通过指针,可以方便地找到关系结点 指向后继结点的指针 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 22 第 1 章 绪 论 数据结构? 索引存储方法 0300 – 为放在内存中 K1 的元素建立索 0301 0302 引表 1 K3 0303 – 元素可以离散 2 0304 存放 3 K4 0305 – 通过查索引表 4 K2 0306 找到需要的元 0307 素 0308 0309 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 23 第 1 章 绪 论 数据结构例:班级的逻辑关系与课堂上的座次 0300一个树形关系结构用索引方式存储 K1 0301 0302 1 1 K3 0303 2 K6 3 0304 2 3 K4 4 0305 K2 5 0306 K5 4 5 6 6 0307 0308 0309 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 24 第 1 章 绪 论 数据结构? 数据类型(data type):是一组性质相同的 值的集合以及定义于这个值集合上的一组操 作的总称。? 抽象数据类型(abstract data type)简 称ADT:是指一个数学模型以及定义在该模 型上的一组操作。 – 抽象数据类型实际上就是对该数据结构的定义。 – 用三元组描述如下: –  (D,S,P) D--数据对象 S--D上的关系集 P--对D的基本操作 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 25第 1 章 绪 论 数据结构 描述一种抽象数据类型可采用如下书写格式: ADT 抽象数据类型名 { 数据对象: < 数据对象的定义> //伪代码描述 数据关系: < 数据关系的定义>//伪代码描述 基本操作: < 基本操作的定义> }ADT 抽象数据类型名 基本操作名(参数表) 初始条件:<初始条件描述> 操作结果:<操作结果描述> 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 26第 1 章 绪 论 数据结构? 小结: – 数据结构包括数据的逻辑结构,数据在计算机 系统中的存储结构和数据操作的集合 – 把数据以一定的逻辑结构组织起来,以适当的 方式存储在计算机系统的存储器里,其最终目 的是为了有效处理数据,提高数据处理运算速 度 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 27第 1 章 绪 论 数据结构 算法(Algorithm):? 算法的概念及特点 –算法是为解决某一特定类型问题规定 的运算规则的有穷集合 ? 有穷性 非无限执行,必须在有限步骤内结束 ? 确定性 非二义,下一步必须是明确的 特 有效性 每一步是可执行的 点 ? ? 输入 外部输入零个或多个 ? 输出 至少一个 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 28 第 1 章 绪 论 数据结构 算法与程序? 相似:都是解决问题的方法和步骤,是指令 的集合? 区别: – 有穷性 程序使用程序设计语言 – 描述方法 算法可以使用框图及其他语言? 联系:程序用某种程序设计语言来实现算法 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 29第 1 章 绪 论 数据结构 算法的设计要求:? 正确性:算法应能正确地实现处理要求 。? 可读性:有助于对算法的理解,便于纠正 和扩充 。? 健壮性:使证明其正确性比较容易,对算 法进行修改也比较方便。? 效率与低存储:达到所需的时、空性能。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 30第 1 章 绪 论 数据结构 算法效率的度量:? 算法的复杂性包括时间复杂性(所需运算时间)和空间复 杂性(所占存储空间),重点是时间复杂性 。? 事后验证、事先估计:? 一个算法所需的运算时间通常与所解决问题的规模大小有 关。 – 用n 表示问题规模的量 ,把算法运行所需的时间T表示为n的函数, 记为T(n)。 –定义:如果存在两个正常数c和n0,对于所有的n≧n0,有︱f(n) ︳ ≦c|g(n) ︳ 则记作 f(n)=O(g(n)) –一般情况下,算法中基本操作重复执行的次数是问题规模n的某个 函数,算法的时间量记作 T(n)=O(f(n)) 称作算法的渐近时间复杂度。它描述了当n逐渐增大时T(n)的极限情况 频度:指该语句重复执行的次数。 (一个算法所需的执行时间就是该算法中所有语句执行次数之和。) 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 31第 1 章 绪 论 数据结构 例1、 {++x;s=0;} 将x自增看成是基本操作,则语句频度为1,即时间复杂度为 O(1) 如果将s=0也看成是基本操作,则语句频度为2,其时间复 杂度仍为O(1),即常量阶。 例2、for(I=1;I<=n;++I) {++x;s+=x;} 语句频度为:2n  其时间复杂度为:O(n) 即时间复杂度为线性阶。 例3、for(I=1;I<=n;++I)     for(j=1;j<=n;++j) {++x;s+=x;} 语句频度为:2n2 其时间复杂度为:O(n2) 即时间复杂度为平方阶。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 32第 1 章 绪 论 数据结构定理:若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一 个m次多项式, 则A(n)=O(n m)证略。例4for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i,j]=x;}语句频度为: 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2) 即此算法的时间复杂度为平方阶. 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 33第 1 章 绪 论 数据结构 一个算法时间为O(1)的算法,它的基本运算执行的次数是固 定的。因此,总的时间由一个常数(即零次多项式)来限界。 而一个时间为O(n2)的算法则由一个二次多项式来限界。 v 最常用的计算算法时间复杂度的多项式的关系为: O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3) 指数时间的关系为: O(2n)<O(n!)<O(nn) v ”O“的运算规则: 1、T1(n) = O(f(n)) T2(n) = O(g(n)) 则:T(n) = T1(n) + T2(n) = O( max(f(n) , g(n) ) 2、T1(m) = O(f(m)) T2(n) = O(g(n)) 则:T(m , n) = T1(m) + T2(n) = O( f(n) + g(n) ) 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 34第 1 章 绪 论 数据结构? 计算下面交换i和j内容程序段的时间复杂性。 temp=i; i=j; j=temp; ? 解:以上三条单个语句均执行1次,该程序 段的执行时间是一个与问题n无关的常数, 因此,算法的时间复杂度为常数阶,记作 T(n)=O(1). 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 35第 1 章 绪 论 数据结构? 计算下面求累加和程序段的时间复杂性 (1) sum=0; (1次) (2) for(i=1;i<=n;i++) (n次 ) (3) for(j=1;j<=n;j++) (n2次 ) (4) sum++; (n2次 )? 解:T(n)=2n2+n+1 =O(n2) 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 36第 1 章 绪 论 数据结构? 算法的运行时间往往还与具体输入的数据 有关,通常用以下两种方法来确定一个算 法的运算时间:? 1. 平均时间复杂性:研究同样的n值时各种 可能的输入,取它们运算时间的平均值。? 2. 最坏时间复杂性:研究各种输入中运算 最慢的一种情况下的运算时间。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 37第 1 章 绪 论 数据结构 Void bubble-sort(int a[],int n) for(I=n-1;change=TURE;I>1 && change;--I) { change=false; for(j=0;j<I;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=TURE} } 最好情况:0次 最坏情况:1+2+3+…+n-1 =n(n-1)/2 平均时间复杂度为:O(n2) 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 38第 1 章 绪 论 数据结构 算法的存储空间需求 算法的空间复杂度 S(n) = O(g(n)) 表示随着问题规模n的增大,算法运行所需存储量的增长率与 g(n)的增长率相同。 算法的存储量包括: 1.输入数据所占空间; 2.程序本身所占空间; 3.辅助变量所占空间。 v 若输入数据所占空间只取决与问题本身,和算法无关,则 只需要分析除输入和程序之外的额外空间。 v 若所需额外空间相对于输入数据量来说是常数,则称此算 法为原地工作。 v 若所需存储量依赖于特定的输入,则通常按最坏情况考虑。 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 39 第 1 章 绪 论 数据结构? 本章介绍了贯穿全书的基本概念和基本 思想。 – 数据 – 数据结构 ? 逻辑结构 ? 物理结构 – 算法 – 算法的时间复杂性 – 习题:P8 1.4 ,1.8 (1)、(6)、(7) 力力为为运运动动商商城城wwwwww..leeevvyy.c.cnn整整理理 40数 据 结 构 参考书目:Ø《数据结构》 ——高等教育出版社 刘大有、唐海鹰、孙舒杨、虞强源、杨鲲
关 键 词:
绪论信息技术算法和程序福建教师招考 ppt、pptx格式 免费阅读 下载 天天文库
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:绪论信息技术算法和程序福建教师招考
链接地址: https://www.wenku365.com/p-39814390.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开