第一章 数据结构与算法
(P1—P38)
(P1—P38)
1.1 算法
1.1.1 算法的基本概念 (P1—P4)
所谓算法是指解题方案的准确完整的描述。
1. 算法的基本特征
(1)可行性(2)确定性(3)有穷性(4)拥有够的情报
2. 算法的基本要素
一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
(1) 算法中对数据的运算和操作 (插入、删除)
(2) 算法的控制结构
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
1.1.2 算法复杂度(P4—P6)
算法的复杂度主要包括时间复杂度和空间复杂度。
1． 算法的时间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
2. 算法的空间复杂度
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
1.2数据结构的基本概念
数据结构，主要研究和讨论以下三个方面的问题：
① 数据的逻辑结构；
② 数据的存储结构；
③ 对各种数据结构进行的运算。(插入、删除)
主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，(时间复杂度)二是尽量节省在数据处理过程中所占用的计算机存储空间。(空间复杂度)
1.2.1什么是数据结构 (P6—P11)
1. 数据的逻辑结构
所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。
2. 数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称为数据的物理结构)
一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。
1.2.3线性结构与非线性结构 (P12)
一般将数据分为两大类型：线性结构与非线性结构。
线性结构又称线性表
如果一个数据结构不是线性结构，则称之为非线性结构。
1.3线性表及其顺序存储结构
1.3.1线性表的基本概念 (P12—P13)
线性表是由n (n≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为。
(a1,a2,…,ai,…,an)
非空线性表有如下一些结构特征：
① 有且只有一个根结点a1，它无前件；
② 有且只有一个终结点an，它无后件；
③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
1.3.2线性表的顺序存储结构 (P13—P14)
在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。
线性表的顺序存储结构具有以下两个基本特点：
① 线性表中所有元素据所占的存储空间是连续的；
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
假设线性表中的第一个数据元素的存储地址为ADR(a1)，每一个数据元素占K个字节，则线性表中第i 个元素ai在计算机存储空间中的存储地址为
ADR(a1)=ADR(a1)+(i-1)K
1.3.3顺序表的插入运算 (P14—P15)
在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。
1.3.4顺序表的删除运算 (P15—P16)
在平均情况下，要在线性表中删除一个元素，需要移动表中表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的。
由线性表在存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入删除的效率比较低。
1.4栈和队列
1.4.1栈及其基本运算 (P16—P18)
1.什么是栈
栈是限定在一端进行插入与删除的另一端称为栈底。即栈是按照“先进后出”(FILO)或“后进先出”(LIFO)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。
2.栈的顺序存储及其运算(采用顺序存储结构的栈称为顺序栈)
栈的基本运算有三种：入栈、退栈与读栈顶元素。
(1) 入栈运算(2)退栈运算(3)读栈顶元素
1.4.2队列及其基本运算 (P18—P20)
1.什么是队列
队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，一端称为排头(也称为队头)通常也用一个排头指针(front)指向排头元素的前一个位置。
队列双称为“先进先出”或“后进后出”的线性表。
3. 循环队列及其运算
在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
(1) 入队运算
(2) 退队运算
1.5线性链表
1.5.1线性链表的基本概念 (P20—P23)
由于线性表的顺序存储结构存在以上这些缺点，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。
在链式存储结构中，存储数据结构的存储空间可以下连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可以用于表示非线性结构。
1. 线性链表
线性表的链式存储结构称为线性链表。
2. 带链的栈
栈也是线性表，也可以采用链式存储结构。
3. 带链的队列
与栈类似，队列也是线性表，也可以采用链式存储结构。
1.5.2线性链表的基本运算 (P23—P25)
线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。
从线性链表的删除过程可以看出，在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。
1.5.3循环链表及其基本运算 (P25—P26)
循环链表具有以下两个特点：
(1) 在循环链表中增加了一个表头结点，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
(2) 循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
1. 6树与二叉树
1.6.1树的基本概念 (P26—P28)
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。
在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件个数称为该结点的度
在树中，所有结点中的最大的度称为树的度。
根结点在第1层。
树的最大层次称为树的深度。
1.6.2二叉树及其基本性质 (P28—P31)
1. 什么是二叉树
二叉树具有以下两个特点：
① 非空二叉树只有一个根结点；
② 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
2. 二叉树的基本性质
性质1在二叉树的第K层上，最多有2K-1(K≥1)个结点。
性质2深度为m的二叉树最多有2m-1个结点。
性质3在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。
3. 满二叉树与完全二叉树
(1)满二叉树
所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结
点，这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2K-1个结点，且深度为m的满二叉树有2m-1个结点。
(2)完全二叉树
所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边若干结点。
满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
性质6设完全二叉树共有n个结点。从根结点开始，按层序用自然数1,2，…，n给结点进行编号，则对于编号为k(k=1,2,…,n)的结点有以下结论：
① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。
② 若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点。
③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
1.6.3二叉树的存储结构 (P31—P32)
在计算机中，二叉树通常采用链式存储结构。
1.6.4二叉树的遍历 (P32—P33)
二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。
1. 前序遍历(DLR)
2. 中序遍历(LDR)
3. 后序遍历(LRD)
1.7查技术
1.7.1顺序查 (P33)
顺序查又称顺序搜索。
vb编程基础知识计算机 对于大的线性表来说，顺序查的效率是很低的。虽然顺序查的效率不高，但在下列两种情况下也只能采用顺序查：
(1) 线性表无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查。
(2) 即使是有序线性表，如果采用链式存储结构，也只能用顺序查。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论