自考数据结构 串讲笔记

《自考数据结构 串讲笔记》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自考数据结构串讲笔记自考乐园版课程代号：02331课程说明串讲目的参考教材：《数据结构》黄刘生主编经济科学出版社更多优质自考资料尽在百度贴吧自考乐园俱乐部（http://tieba.baidu.com/club/5346389）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........课程说明知识点：线形表、栈、队列、数组、广义表、树、图、查找和排序。第一章　绪论§１．基本概念与术语数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象及他们之间关系和操作等的学科。（一）数据结构概念包括三个方面（三要素）数据之间的逻辑关系（逻辑结构）数据在计算机中的存储方式（存储结构

2、）实现数据操作的算法（数据的运算）（二）、相关术语1、数据：能输入计算机并能计算机程序处理的符号的总称。2、数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。3、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。4、（1）数据的逻辑结构：数据之间的关系。A.集合（无顺序）：B.线性结构（一对一）：C.树形结构（一对多）：D.网状、图结构（多对多）：（２）数据的存储结构（物理结构）数据结构在计算机中的表示。（２种）A.顺序表示借助数据在连续的存储空间中的相对位置表示元素关系。B.链式表示借助数据元素的存储地址的指针表示元素关系。§2.算法和算法分

3、析一、算法定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：有穷性确定性可行性零个或多个输入一个或多个输出大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(

4、n2)for(j=1;j<=n;j++)x=x+1;i=0;n+1O(n)while(x!=a[i]&&i<=n)i=i+1;求时间复杂度的原则当重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http://tieba.baidu.com/club/5346389）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........算法时间开销随时间规模变化趋势nT(n)随n增大,T(n)增加快,算法坏随问题规模n增大,T(n)趋缓,算法好T(n)的增大趋势:O(1)

5、g2n)0时，线性表中各元素都有确定序号线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外，均具有唯一的前驱、后继元素（a1,a2,…,ai-1,ai,ai+1,…,an)无前驱直接前驱直接后继无后继第二章　线性表§2.线性表的顺序存储结构一、线性表的顺序存储在计算机内开辟一片连续空间（存储单元）

6、依次存放表中所有元素。设线性表为A（a1,a2,…,ai,…,an），表中的一个元素占用L个存储单元，第一个元素a1的起始地址是Loc(a1)，则第i个元素的起始地址为：Loc(ai)=Loc(a1)+(i-1)*La1a2…ai…an……连续空间§3.线性表的链式存储结构一、单链表定义：存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。结点：DataPointer两个概念：头指针：指示链表中第一个结点。头结点：在第一个结点之前附设的结点，其指针域指向链表中第一个结点。在链表中第i个结点前插入新结点b（前

7、插）算法分析：基本操作：查找第i-1个元素当1≤i≤n频度为：i-1当i>n(最坏，即i不合法)频度为：nT(n)=O(n)二、循环链表特点尾结点的next指针指向头结点，可以设头结点和尾结点指针。优点可迅速找到头、尾结点。a1an…HeadHead空表三、双向链表和双向循环链表特点：在结点中增加一个指向前趋的指针域。优点：可迅速找到结点前趋。缺点：增加存储空间。（每个结点增加了一个指针域）双向链表a1a2双向循环链表a2a12、基本操作（1）