智能仪器讲稿-第五章

《智能仪器讲稿-第五章》由会员分享，可在线阅读，更多相关《智能仪器讲稿-第五章（188页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章智能仪器的运算程序及数据处理智能仪器的运算程序及数据处理 常用数值计算：常用数值计算： 四则运算。四则运算。 常用函数常用函数 指数函数；对数函数；三角函数；乘方；开 方等。指数函数；对数函数；三角函数；乘方；开 方等。三角函数的计算三角函数的计算 如果连续函数如果连续函数f(x)在在X=a的邻域具有任意 阶有限导数，则能展开为的邻域具有任意 阶有限导数，则能展开为台劳级数：台劳级数：2(1)1()( )( ) ()( )( )2! ()()( )()!(1)!nnnnx af xf ax a f afax ax afafax ann=+?01 x设设!1 ! 2111, 1nex

2、+=+=?取取.)!1(3 +0？x2？x？x-2x ，符号标志增1x/2？()()2522211sin19 !7 !5 !3 !xxxxxxx=+ 结果0？是是否否是 - x x否切线法切线法( (牛顿法牛顿法) )求方程根求方程根( ) , ( )( )0( )( ) , ( )( , ) , f xa bf af bfxfxa bf xa ba b 是一个隔离区间0,1如图，在上，( )62.20,fxx=+2( )32.20.90,fxxx=+( )( )fxf x与同号，代入代入(1),得得1(1)10.738;(1)fxf= 2(0.738)0.7380.674;(0.738)fx

3、f=3(0.674)0.6740.671;(0.674)fxf=4(0.671)0.6710.671;(0.671)fxf=计算停止计算停止.30.671,10 .得根的近似值为其误差都小于01.x=曲线为凹的，令平方根的计算平方根的计算0xxh=+设x表示f(x)=0的根的真值，x0表示根的近似值，h为校正 量，则有因此方程f(x)=0可以表示为f(x0+h)=0 ，应用台劳公式展开得20000()()()()02hf xhf xhfxfxh+=+= 假设h充分小，可略去含有h的高次项，则得00()()0f xhfx+=001()()hf xfxh =或牛顿迭代法牛顿迭代法(1)0 010

4、0() ()f xxxhxfx=+=并且它是比x0要精确的根估计值。重复这个过程可得到更精确 的近似值，即(1) (2)(1) (1)() ()f xxxfx=(1) ( )(1) (1)() ()n nn nf xxxfx =用牛顿迭代法求平方根用牛顿迭代法求平方根( )2fxx=求一个数的平方根等价于求方程x2=k或x2-k=0的正根， 由此取因此2( )f xxk=2 (1)0 00 001()22xkkxxxxx=所以( )(1) (1)1()2nn nkxxx =N次迭代式为数据结构分类数据结构分类线性表 堆栈 队列 串 数组树 二叉树 图线性结构非线性结构数据结构线性表 堆栈 队列

5、 串 数组树 二叉树 图线性结构非线性结构数据结构 DS基本概念基本概念 线性结构线性结构 结构中有且仅有一个始结点和一个终 结点，每个内结点有且仅有一个前趋结 点和一个后继结点。结构中有且仅有一个始结点和一个终 结点，每个内结点有且仅有一个前趋结 点和一个后继结点。 非线性结构非线性结构 结构中的结点可能有多个前趋结点和 多个后继结点。结构中的结点可能有多个前趋结点和 多个后继结点。数据的逻辑结构数据的逻辑结构 线性结构 树形结构 图状结构 集合结构基本概念基本概念 数据结构数据结构 相互之间存在着某种关系的数据元素的集合。相互之间存在着某种关系的数据元素的集合。 逻辑结构逻辑结构 数据元素

6、之间的逻辑关系。数据元素之间的逻辑关系。 存储结构存储结构 逻辑结构在存储器中的映象。逻辑结构在存储器中的映象。数据结构数据结构表表 一行表示一个结点（元素），每个结点由学号、姓名、 性别等九个域（数据项）组成。一行表示一个结点（元素），每个结点由学号、姓名、 性别等九个域（数据项）组成。 表的第一行是始结点；最后一行是终结点；中间的行 都是内结点。表的第一行是始结点；最后一行是终结点；中间的行 都是内结点。 表的逻辑结构是线性结构。表的逻辑结构是线性结构。测量数据的非数值处理测量数据的非数值处理线性表定义：线性表定义： 线性表是线性表是n（n0）个元素）个元素 a1,a2,an 的有限序列；

7、表中每个数据 元素，除了第的有限序列；表中每个数据 元素，除了第1个和最后个和最后1个外，有且仅 有一个前趋元素和后继元素。个外，有且仅 有一个前趋元素和后继元素。 线性表的表示：线性表的表示： a0, a1,ai, ai+1,an-1 表头 栅栏（当前位置）表尾表头 栅栏（当前位置）表尾线性表的逻辑结构示意图线性表的逻辑结构示意图 线性表是具有相同属性的数据元素的有 限序列。线性表是具有相同属性的数据元素的有 限序列。表头元素表尾元素a1aia2ai+1an线性表的实现线性表的实现 顺序存储顺序存储 顺序映象顺序映象 以存储位置先后表示元素间的前趋和后继关系。以存储位置先后表示元素间的前趋和

8、后继关系。 用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据 元素。a0a1ai-1aian-1线性表的起始地址线性表的起始地址 称作线性表的基地址基地址线性表的实现线性表的实现 顺序存储顺序存储 若每个元素占用 l 个存储单元，用其中第一个 单元的地址作为元素的存储位置。则元素 ai 的 存储位置可以表示为LOC(ai)。 线性表中第 i+1 个元素和第 i 个元素的存储位 置间满足下列关系: LOC(ai+1) = LOC(ai) + l 线性表中第 i个元素的存储位置为： LOC(ai) = LOC(a0) + i * l 其中LOC(a0)是线性表的基地址。线性表的顺序存

9、储结构示意图线性表的顺序存储结构示意图MaxSize-1ann-1ai+1i aii-1a21a10数组存储空间下标位置数组存储空间下标位置 ElemType类型的数组类型的数组 listMaxSize存储线性表：存储线性表： A= (a1 ,a2 ,ai,ai+1 ,an)元素地址计算方法： 第元素地址计算方法： 第i个元素的存储位置为：个元素的存储位置为： list +(i-1)*sizeof(ElemType)顺序表的典型操作顺序表的典型操作 对顺序表的典型操作包括：计算表长度， 寻找变量或对象对顺序表的典型操作包括：计算表长度， 寻找变量或对象x（其类型与表元素相同） 在表中的位置（下

10、标值），判断（其类型与表元素相同） 在表中的位置（下标值），判断x是否在 表中，删除是否在 表中，删除x ，将，将x插入列表中第插入列表中第i个位置， 寻找个位置， 寻找x的后继，寻找的后继，寻找x的前驱，判断表是 否空，判断表是否满（表满不能再插入 数据，否则会溢出，产生不可预知的错 误），取第的前驱，判断表是 否空，判断表是否满（表满不能再插入 数据，否则会溢出，产生不可预知的错 误），取第i个元素的值。个元素的值。线性表的删除线性表的删除1431341096587241621892771185112110131234i图图a下标下标1431341096587241621897118511

11、211013图图b下标下标向表中插入一个数据向表中插入一个数据1431341096587241621892771185112110135432i 图图a下标下标11431341096587241621897118511211x013图图b下标下标线性表的实现线性表的实现 顺序存储顺序存储 元素插入操作的时间复杂度分析 假设在第 i 个位置插入元素的概率为pi，则在长度为n的线性表中插入一个元素所需移动元素次数的期望值插入一个元素所需移动元素次数的期望值 为：假定假定在线性表中任何一个位置上进行插入的概率插入的概率都是 相等相等的，则移动元素的期望值移动元素的期望值为：在线性表中插入一个元素平均

12、需要移动一半元素，时 间复杂度是线性阶，即O(n)。0()nisi iEp ni=01()12nis inEnin=+线性表的实现线性表的实现 顺序存储顺序存储 在顺序实现中： insert 和 remove 的时间复杂度是O(n)。 List、clear、empty、full、size、replace和retrieve的 时间复杂度是O(c)。(c为常数) 优点： 随机存取（ retrieve ） 缺点 插入（ insert ）、删除（ remove ）需移动大量元素 需要预先估计所需最大空间 表的容量不能动态扩充 思考：如何实现容量可动态增长的顺序存储的线性表？线性表举例线性表举例 L1=

13、（a,b,c,4,7,+,-,*,/） L2=（25,35,28,49,51,87,46,32,88） L3=（“BASIC”,“PASCAL”,“JAVA”,“OK”） L4=（a,b,c,d,e,f,g,h,i,j,k,x,y,z）堆栈堆栈 1. 栈的特点栈的特点 插入和刪除在同一端进行的线性表，符合插入和刪除在同一端进行的线性表，符合 LIFO规则。规则。 2. 栈的基本运算及时间复杂度栈的基本运算及时间复杂度 初始化栈（置空栈）、进栈、退栈、取栈顶 元素、判栈空。初始化栈（置空栈）、进栈、退栈、取栈顶 元素、判栈空。 3. 顺序栈（栈的顺序存储）顺序栈（栈的顺序存储） 4. 链栈（栈的

14、链式存储）链栈（栈的链式存储）栈有关概念栈有关概念栈上溢栈上溢 栈空间是有限的，若栈已满，在进行入栈操作时，就要产生上溢。栈空间是有限的，若栈已满，在进行入栈操作时，就要产生上溢。 栈下溢栈下溢 若栈空，再要执行出栈操作，则会发生下溢。若栈空，再要执行出栈操作，则会发生下溢。 栈顶指针栈顶指针 在栈操作过程中，有一个专门的栈指针（习惯上称它为在栈操作过程中，有一个专门的栈指针（习惯上称它为TOPTOP），指 出栈顶元素所在的位置。），指 出栈顶元素所在的位置。 栈空的条件：栈空的条件： top = 0top = 0 栈满的条件：栈满的条件： top = MAXSIZEtop = MAXSIZE

15、栈操作举例栈操作举例a1a2an栈底栈底栈顶栈顶MAXSIZETOP1.top=0A B C2.(空栈空栈)top=3A B3.top=2(C出栈）出栈）4.A B C D E Ftop=MAXSIZE队列队列 1. 队列的特点队列的特点 插入在一端，删除在另一端进行的线性表， 符合插入在一端，删除在另一端进行的线性表， 符合FIFO规则。规则。 2. 队列的基本运算及时间复杂度队列的基本运算及时间复杂度 初始化队列（置空队列）、进队、出队、取 队头元素、判队空。初始化队列（置空队列）、进队、出队、取 队头元素、判队空。 3. 队列的两种存储结构（循环队列、链 队列）队列的两种存储结构（循环队列、链 队列）线性表的实现线性表的实现 单单链表链表 用一组地址任意地址任意的存储单元存放存放线性表中的数据元素。 用附加的指针指示元素的前趋和后继关系。 为了表示数据元素ai 与其直接后继元素ai+1之间的逻辑 关系，对数据元素ai 而言，除存储其本身的信息外， 还需要存储指示其后继的指针（地址）信息。这两部 分合起来通常称为结点结点。 结点 元素 指针 n个结点通过指针链接形成一