湘潭大学-数据结构-课件-ppt-Ch01-Introduction

数据结构与算法分析DataStructuresandAlgorithmAnalysis朱江[e-mail]教材及参考文献教材数据结构与算法分析：C语言描述（原书第2版），MarkAllenWeiss著，冯舜玺译，机械工业出版社参考文献《数据结构》，陈越、何钦铭、徐镜春、魏宝刚、杨枨编著，高等教育出版社地位：是计算机及相关专业的一门专业基础课。研究内容：在计算机中如何有效地表示数据如何合理地组织数据和处理数据算法设计和算法性能分析技术要求：对计算机的组成有基本的了解程序设计方法C语言对涉及离散数学的知识，如表、树、图、集合等，有初步的了解。作用：为软件开发和程序设计提供了必要的技能训练为后续的专业课程，如数据库系统、操作系统、编译原理等，打下良好的知识基础【定义】“数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。”计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示——数据结构信息的处理——算法Algorithm+DataStructures=ProgramsAlgorithm:求解问题的策略DS:问题的数学模型Programs:为计算机处理问题编制的一组指令而信息的表示和组织（DS）又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是“数据结构”所要研究的问题。[例1.1]如何在书架上摆放图书？【分析】[方法1]随便放——任何时候有新书进来，哪里有空就把书插到哪里。[方法2]按照书名的拼音字母顺序排放。[方法3]把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放。查找效率极低！有时插入新书很困难！可能造成空间的浪费！[例1.2]写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。voidPrintN(intN){inti;for(i=1;i=N;i++)printf(“%d\n”,i);return;}voidPrintN(intN){if(!N)return;PrintN(N–1);printf(“%d\n”,N);return;}[例1.3]多项式的标准表达式可以写为：f(x)=a0+a1x+a2x2+…+anxn现给定一个多项式的阶数n，并将全体系数存放在数组a[]里。请写程序计算这个多项式在给定点x处的值。[方法1]计算多项式函数值的直接法doublef(intn,doublea[],doublex){/*计算阶数为n，系数为a[0]...a[n]的多项式在x点的值*/inti;doublep=a[0];for(i=1;i=n;i++)p+=a[i]*pow(x,i);returnp;}[方法2]秦九韶法f(x)=a0+x(a1+x(a2+…+x(an)…)doublef(intn,doublea[],doublex){/*计算阶数为n，系数为a[0]...a[n]的多项式在x点的值*/inti;doublep=a[n];for(i=n;i0;i--)p=a[i-1]+x*p;returnp;}#includestdio.h#includetime.hclock_tstart,stop;/*clock_t是clock()函数返回的变量类型*/doubleduration;/*记录被测函数运行时间，以秒为单位*/intmain(){/*不在测试范围内的准备工作写在clock()调用之前*/start=clock();/*开始计时*/function();/*把被测函数加在这里*/stop=clock();/*停止计时*/duration=((double)(stop-start))/CLK_TCK;/*计算运行时间*//*其他不在测试范围的处理写在后面，例如输出duration的值*/return0;}秦九韶算法的计算速度明显比直接法快了一个数量级！为什么会这样？5/25代码1.6测试函数function()的运行时间–即使解决一个非常简单的问题，往往也有多种方法，且不同方法之间的效率可能相差甚远–解决问题方法的效率•跟数据的组织方式有关（如例1.1）•跟空间的利用效率有关（如例1.2）•跟算法的巧妙程度有关（如例1.3）6/25数据对象：计算机要处理的事物，如例1.1中“图书”。术语定义操作：处理事物的动作集合，如例1.1中的“查找”和“插入”，例1.2的函数“求值”等。算法：操作的实现方法，如例1.1的按字母序排放的“查找”和“插入”、例1.2的“直接法”和例1.3的“秦九韶法”等。通常一个算法用一个函数来实现。逻辑结构：数据对象的逻辑组织关系。分为“线性”、“树”和“图”。例1.1中按方法1来处理，就是把图书集看成是线性的结构；按方法3来处理，就是把图书集看成是树形的结构。物理结构：数据对象信息在计算机内存中的存储组织关系。一般分为“顺序存储”和“链式存储”。数据类型：数据对象的类型确定了其“操作集”和“数据定义域”。抽象数据类型抽象数据类型：“抽象”的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象集和操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。[例1.4]“矩阵”的抽象数据类型定义类型名称：Matrix数据对象集：一个MN的矩阵A。操作集：对于任意矩阵A、B、CMatrix，以及正整数i、j、M、N，以下仅列出几项有代表性的操作。1）MatrixCreate(intM,intN)：返回一个MN的空矩阵；2）intGetMaxRow(MatrixA)：返回矩阵A的总行数；3）intGetMaxCol(MatrixA)：返回矩阵A的总列数；4）ElementTypeGetEntry(MatrixA,inti,intj)：返回矩阵A的第i行、第j列的元素；5）MatrixAdd(MatrixA,MatrixB)：如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志；6）MatrixMultiply(MatrixA,MatrixB)：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；7）……•数据结构课程的体系结构逻辑结构基本运算的定义（概念层/抽象层）存储结构（实现层）解决实际问题（应用层）基本运算的实现•典型应用排序：考察采用顺序存储时，不同实现方法的特点关键字的比较和移动次数（最好、最坏、平均）稳定性辅助空间查找：考察采用不同的存储结构查找的效率用平均查找长度ASL衡量表的可维护性examples：SelectionproblemSupposeyouhaveagroupofNnumbersandwouldliketodeterminethekthlargest.数学知识复习指数XAXB=XA+BXA/XB=XA-B(XA)B=XABXN+XN=2XN≠X2N2N+2N=2N+1对数定义1.1XA=B当且仅当logxB=A。定理：logAB=logCB/logCA;A,B,C0,A≠1logAB=logA+logB;A,B0logA/B=logA-logBLog(AB)=BlogAlogXX对所有X0成立Log1=0,log2=1,log1024=10,log1048576=20级数几何级数∑2i=2N+1-1∑Ai=(AN+1-1)/(A-1)算术级数∑i=N(N+1)/2≈N2/2∑i2=N(N+1)(2N+1)/6≈N3/3∑ik=Nk+1/|k+1|k≠1k=1时HN=∑1/i≈logeN欧拉常数(Euler’sconstant):上式中误差趋向于γ≈0.57721566，称为欧拉常数。一般的代数运算∑f(N)=Nf(N)NNn0-1∑f(i)=∑f(i)-∑f(i)i=n0i=1i=1模运算A≡B(modN)若A≡B(modN)，则A+C≡B+C(modN)，以及AD≡BD(modN)证明方法归纳法第一步：证明基准情形(basecases)接着进行归纳假设(inductivehypothesis)然后使用假设证明定理对下一个值也成立定理得证通过反例证明反证法证明递归的四条基本法则：基准情形(BaseCases):必须总有某些基准情形，它无须递归就能解出；不断推进(Makingprogress):对于那些需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进；设计法则(Designrule)：假设所有的递归调用都能运行；合成效益法则(compoundinterestrule)：在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性工作。关于递归(Recursion)递归的概念在程序设计方法学中的定义：一个程序直接和间接调用自己，则这个程序称为递归的，这种调用称为递归。需要使用到的递归方法通常有以下三种情况：1.定义是递归的如阶乘函数的递归程序：longFactorial(longn){if(n==0)return1;/*判断递归结束的条件*/elsereturnn*Factorial(n-1);/*递归，过程中调用自己*/}又如Fibonnacci序列的递归程序：longfib(longn){if(n=1)returnn;elsereturnfib(n-2)+fib(n-1);}这两个程序演示了最简单的递归调用。当执行fib(4)时，将会有如图所示的过程。主程序3fib(4)＝fib(3)+fib(2)21fib(3)=fib(2)+fib(1)11fib(2)=fib(1)+fib(0)10fib(1)fib(0)图6-1求解fib(4)的过程递归调用返回结果这两个程序虽然简单，却显示了使用递归过程的一般规则：（1）要解决的问题需要使用到解法相同的同类子问题的答案（2）问题应该能向简单的方向分解（3）问题最终能分解成能直接解决的子问题（4）递归过程与原问题递归的定义相一致。2.数据结构是递归的某些数据结构就是递归的。单链表的整个结构就是一个递归结构，如图单链表的递归结构可如下定义：（1）一个由数据项和指针项组成的数据结构。（2）其指针为NULL，或指向一个单链表。ListNodeListNodeListNode……headdatalinkdatalinkdata∧继续考虑单链表删除非空单链表中最后一个结点，可以利用递归形式：intdelLast(ListNode*f){if(f-link==NULL){/*判断是否末结点*/delete(f);return0;}/*末结点返回0*/elseif(delLest(f-link)==0)/*递归调用dele*/f-link=NULL;/*将末结点的前一结点指针设为NULL*/return1;/*非末结点返回1*/}递归在处理多种数据结构时都经常会运用，树也是一种递归的数据结构。关于树这种数据结构的许多算法，都将用到递归。3.问题的解法是递归的有的问题本身不是递归的，但使用递归的方法将有助于解决这种问题。考虑以下的这种情况：有一组人，他们的身高是已知的，目标是判断这组人之中是否有同样身高的人。算法如下：intif_same(intheight[],intn){inti=0;while(in-1)/*height[n-1]分别与height[0]～height[n-2]比较*/if(height[n-1]==height[i])return1;/*有相同值则停止比较，返回1*/returnif_same(he