自考数据结构 串讲笔记.ppt

自考数据结构 串讲笔记自考乐园版 课程代号：02331,课程说明,串讲目的参考教材：数据结构黄刘生主编经济科学出版社,更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/,课程说明,知识点：线形表、栈、队列、数组、广义表、树、图、查找和排序。,第一章绪论,基本概念与术语数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。,（一）数据结构概念包括三个方面（三要素）数据之间的逻辑关系（逻辑结构）数据在计算机中的存储方式（存储结构）实现数据操作的算法（数据的运算）,（二）、相关术语,1、数据：能输入计算机并能计算机程序处理的符号的总称。2、数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。3、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。,4、（1）数据的逻辑结构：数据之间的关系。A.集合（无顺序）：B.线性结构（一对一）：C.树形结构（一对多）：D.网状、图结构（多对多）：,（）数据的存储结构（物理结构）数据结构在计算机中的表示。（种）A.顺序表示借助数据在连续的存储空间中的相对位置表示元素关系。B.链式表示借助数据元素的存储地址的指针表示元素关系。,2.算法和算法分析,一、算法定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：有穷性确定性可行性零个或多个输入一个或多个输出,大O表示法大O表示同级别例：f(n)=n2,f(n)=1/2(n(n-1),f(n)=(n-1)(n+2)均表示为：O(n2)加法规则：若T1(n)=O(f1(n),T2(n)=O(f2(n)则两段程序连在一起的时间代价为:T(n)=T1(n)+T2(n)=O(max(f1(n),f2(n),例:,语句段 频度f(n)时间复杂度T(n)x=x+11O(1)for(j=1;j=3n+5;j+)3n+5O(n)x=x+1;for(i=1;i=3n;i+)3n2O(n2)for(j=1;j=n;j+)x=x+1;i=0;n+1O(n)while(x!=ai,求时间复杂度的原则,当重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。,更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/,算法时间开销随时间规模变化趋势,n,T(n),随n增大,T(n)增加快,算法坏,随问题规模n增大,T(n)趋缓,算法好,T(n)的增大趋势:O(1)O(log2n)O(n)O(nlog2n)O(n2)O(nk)O(2n)O(en),算法的存储空间需求,算法空间开销与输入形式无关时，仅考虑辅加空间开销。空间量依赖特定输入，讨论最坏情况下的空间开销。,（本章结束）,1.线性表的逻辑结构,一、线性结构线性表是n个数据元素的有限序列当n=0时，称线性表为空表当n0时，线性表中各元素都有确定序号线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外，均具有唯一的前驱、后继元素（a1,a2,ai-1,ai,ai+1,an),无前驱,直接前驱,直接后继,无后继,第二章线性表,2.线性表的顺序存储结构,一、线性表的顺序存储在计算机内开辟一片连续空间（存储单元）依次存放表中所有元素。设线性表为A（a1,a2,ai,an），表中的一个元素占用L个存储单元，第一个元素a1的起始地址是Loc(a1)，则第i个元素的起始地址为：Loc(ai)=Loc(a1)+(i-1)*L,a1,a2,ai,an,连续空间,3.线性表的链式存储结构一、单链表,定义：存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。结点：,Data,Pointer,两个概念：,头指针：指示链表中第一个结点。头结点：在第一个结点之前附设的结点，其指针域指向链表中第一个结点。,在链表中第i个结点前插入新结点b（前插）算法分析：基本操作：查找第i-1个元素当1in 频度为：i-1当in(最坏，即i不合法)频度为：nT(n)=O(n),二、循环链表,特点尾结点的next指针指向头结点，可以设头结点和尾结点指针。优点可迅速找到头、尾结点。,a1,an,