[数据结构教程第二十九课静态查找表]教学目的： 掌握查找的基本概念，顺序表查找的性能分析 教学重点： 查找的基本概念 教学难点： 顺序表查找的性能分析 授课内容： 一、查找的基本概念 查找表： 是由同一类型的数据元素（...+阅读
考点1 数据结构的基本概念
1、数据
在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息。
数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值能够确定一个数据元素的数据项。
2、数据结构
数据结构包括3个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。
(1)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。
(2)数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。
(3)数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算的集合。数据运算主要包括查找（检索）、排序、插人、更新及删除等。
考点2 主要的数据存储方式
实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最主要的存储方式。
1、顺序存储结构
顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特点如下。
(1)由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间利用率高。
(2)数据结构中第i个节点的存储地址乙可由下述公式计算求得：
Li＝L0＋（i－1）×K
L0为第一个节点存储地址，左为每个节点所占的存储单元数。
(3)插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人、删除运算会引起相应节点物理地址的重新排列。
2、链式存储结构
链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间逻辑上的联系。
链式存储结构的主要特点包括以下几个方面。
(1) 节点中除自身信自、外，还有表示链接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。
(2) 罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。
(3) 插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。考点3 算法设计与分析
在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时间代价和空间代价两个方面时间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法运行时所耗费的时间也以某种单位由f( 1)增至f(n)，则称该算法的时间代价为f(n)。
空间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现时所占用的空间也以某种单位由到g（1）增至g（n），则称该算法的空间代价为g（n）。
2. 线性表
线性表的逻辑结构是由n个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度．它是可变的．可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。
线性表的基本运算有：置表空、求表长、读表元素、插人、删除及检索等操作。
考点4 顺序表和一维数组
线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元中，其他元素依次类推。一般情况下，若长度为n的顺序表，在任何位置土插入或删除的概率相等，元素移动的平均次数均为n/2。
考点5 链表
链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。
1、线性链表
线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。
（1）在指针一P后插人指针9的关键运算步骤：
q ↑. link：＝P↑．link：
p ↑. link：＝q；
（2）删除指针P后继节点q的关键运算步骤：
q：＝p↑ . link；
p↑. link：＝q↑．link；
（3）在第一个节点（或称头节点）前插人一个指针P的关键运算步骤：
p↑. link：＝head；
head：二P；
（4）删除表中头节点的关键运算步骤：
head：＝head↑ . link：
2、双链表
在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。rlink指向节点的后继，llink指向节点的前驱，这样的结构方便向后和向前查找。
（l）若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink字段，步骤如下：
p↑ . llink↑. rlink：＝p↑. rlink；
P↑T．rlink↑. llink：＝P↑．llink；
(2)如果要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段和原来后继均Ilink字段，并重新设置q所指节点的Mink和rlink值，步骤如下：
q ↑. Mink：＝P：
q↑．rlink：＝P↑．rlink;
P↑．rlink r. Rink：＝q；
p↑．rlink：＝q;
3、可利用空间表
可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。
考点6 栈
栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶( top)，另一端为栈底( bottom)。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”（LIFO）表。
栈的基本操作有：
（1）push(S,X)。往栈S中插人（或称推人）一个新的栈顶元素x，即进栈。
（2）pop（S）。从栈S中删除（或称弹出）栈顶元素，即出栈。
（3）lop(S，X)：把栈S的栈顶元素读到变量x中，栈保持不变。
（4）empty（S）。判断栈S是否为空栈，是则返回值为真。
（5）makempty。（S）将栈S设置为空。
栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。
考点7 队列
队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾.
队列的基本操作有：
（1) enq（Q, X)。往队列口中插人一个新的队尾元素x，即人队。
（2）deq（口）从队列Q中删除队头元素，即出队。
（3）front口,x)将队列口的队头元素值读到变量x中，队列保持不变。
（4）empty ( Q )．判断队歹，l口是否为空，是则返回值为真。
（5）makempty（口）将队列口置为空队列。
和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。
考点8 串
串（或字符串）是由零个或多个字符组成的有限序列。零个字符的串是空串。串中字符的个数就是串的长度串中的字符可以是字母、数字或其他字符。
串的存储同样也有顺序存储和链式存储两种。顺序存储时，既可以采用非紧缩方式，也可以采用紧缩方式。
串的基本运算有连接、赋值、求长度、全等比较、求子串、找子串位置及替换等，其中找子串位置（或称模式匹配）比较重要。
3. 多维数组、稀疏矩阵和广义表
考点9 多维数组的顺序存储
多维数组是一维数组的推广。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的元素排在一个线性序列里。常用的排列次序有行优先顺序和列优先顺序两种。
考点10 稀疏矩阵的存储
稀疏矩阵是指矩阵中含有大量的0元素。对稀疏矩阵可进行压缩存储，即只存储其中的非0元素。若非0元素分布是有规律的，可用顺序方法存储非0元素。对于一般的稀疏矩阵，常见的存储方法还有不元组法和十字链表法，这里就不再介绍了。
考点11 广义表的定义和存储
广义表（又称列表）是线性表的另一种推广，是由零个或多个单元素或子表所组成的有限序列。它与线性表的区别在于：线性表中的元素都是结构上不可分的单元素，而广义表中的元素既可以是单元素，又可以是有结构的表广义表与线性表相比，具有如下3个方面的特征。
（１）广义表的元素可以是子表，而子表的元素还可以是子表。
（２）广义表可被其他广义表引用二
（３）广义表可以是递归的表，即广义表也可以是自身的一个子表。
以下为关联文档：
二维类间方差阈值分割的快速迭代算法【摘要】 传统的二维Otsu阈值分割算法采用穷举搜索法搜寻阈值向量。与此不同，本文提出了一种二维类间方差阈值分割的快速迭代算法，用迭代的思想解决原始二维Otsu方法计算复杂...
数据结构教程第二十六课图的定义与术语教学目的： 掌握图的定义及常用术语 教学重点： 图的常用术语 教学难点： 图的常用术语 授课内容： 一、图的定义 图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的...
MethodTable内存空间分配中加法运算算法在分析MethodTable具体分配内存实现的时候，看到了计算MethodTable的大小，然后分配空间的算法。其中有个加法运算实现的非常赞，特地截取出来。 所有的MethodTable的分配，都是通过...
数据结构教程第二十五课单元测验教学目的： 复习前面所学的内容,检验学习效果,拾遗补缺 教学重点： 教学难点： 授课内容： 测验题: 一，填空： 基本数据结构有＿＿＿＿，＿＿＿＿，＿＿＿＿，＿＿＿＿四种。 存储结构可根据数据元素在机器中的位置是否连续分...
Crtpto++的RSA签名算法将常见的一些加密库都测试一下，再根据情况选择一个应用到项目中去.crypto++国内用得蛮多的，资料还算比较齐全，但是让我讨厌的是源文件太乱，把所有的算法都包括进去了，我目前不能...
数据结构教程第二十八课图的存储结构教学目的： 掌握图的二种存储表示方法 教学重点： 图的数组表示及邻接表表示法 教学难点： 邻接表表示法 授课内容： 一、数组表示法 用两个数组分别存储数据元素（顶点）的信息和数据元...
数据结构教程第二十三课二叉树的存储结构教学目的： 掌握二叉树的两种存储结构 教学重点： 链式存储结构 教学难点： 链式存储二叉树的基本操作 授课内容： 一、复习二叉树的定义 二叉树的基本特征：每个结点的度不大于２。 二...
FDK算法中一种新的插值方法【摘要】 针对在FDK算法的反投影过程中，各个体素在探测器上投影分布的特点，本文提出一种新的插值方法。该方法根据体素投影的特点，采用在重建过程中，根据其在不同扫描角度下在各...
算理、算法比翼齐飞、有效融合—评《两、三位数除以一武进区奔牛实验小学 卢晶晶, 一、竖式计算教学与算理有效融合。算理与算法既有联系，又有区别，算理主要回答 为什么这样算 的问题，算法主要是解决 怎么算的问题 两者在计算教学...
