一、顺序查找 条件：无序或有序队列。

原理：按顺序比较每个元素，直到找到关键字为止。

时间复杂度：O(n)

二、二分查找（折半查找） 条件：有序数组

原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束； 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

时间复杂度：O(logn)

三、二叉排序树查找 条件：先创建二叉排序树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 它的左、右子树也分别为二叉排序树。

原理：

在二叉查找树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：

2. 若x等于b的根节点的数据域之值，则查找成功；否则：

3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：

4. 查找右子树。

时间复杂度：

四、哈希表法（散列表） 条件：先创建哈希表（散列表）

…… …… 余下全文

算法基础题

一、常见查找算方法总结

1. 基本概念

数据：数据即信息的载体，是对客观事物的符号表示，指能输入到计算机中并被计算机程序处理的符号的总称。

数据项：数据项是数据具有独立意义的不可分割的最小单位，是对数据元素属性的描述。 数据元素：数据元素是数据的基本单位，是对一个客观实体的数据描述。

查找表：进行查找的数据元素通常是同一类型的数据元素或记录，由它们构成的集合称查找表。

查找：查找也称检索，是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在一个这样的记录，则称查找成功，反之查找失败。

2. 查找分类

2.1 线查找

1). 顺序查找

a. 算法思想：

设查找表是由n(n>0)个元素组成的，从第一个元素开始，顺序查找给定元素，若找到查找成功，反之失败。

b. 算法实现：

int search(int array[], int n, int data)

{

int i;

if(array == NULL) return -1;//查找失败

for(i = 0; i < n; ++i) {

if(array[i] == data) return i;//查找成功

…… …… 余下全文

对分查找算法及程序实现

一、设计思想

对分查找是计算机科学中的一个基础算法。对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。

二、教材分析

本课的课程标准内容：

（一）计算机解决问题的基本过程（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。

（三）算法与问题解决例举 C 查找、排序与问题解决

（2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。 本课的《学科教学指导意见》内容：

基本要求：1.初步掌握对分查找算法。

2.初步掌握对分查找算法的程序实现。

教材内容：第二章 算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算

…… …… 余下全文

《操作系统原理》算法总结

一、进程(作业)调度算法

?         先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。

?         短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。

?         时间片轮转调度算法：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。

…… …… 余下全文

经典包分类算法总结

1 RFC算法

1.1 RFC算法介绍

RFC(Recursive Flow Classification)算法[1]是一种多维IP分类快速查找算法，通过对实际的过滤规则数据库的考察，发现数据库中的过滤规则都有内在的结构和冗余度，这个特点可以为分类算法所利用。 RFC算法的主要思想是将IP分类问题看成一个将包头中的S比特数据到T比特的classID的一个映射（T=logN且N<<S,N是过滤规则的总数）。如果预先计算出包头中的这S位共2s种不同情况中每种情况所对应的classID值。那么每一个包只需要一次查表，即一次内存访问就可以得到相应的classID,但是这样会消耗极大的空间。RFC的思想是映射不是通过一步来完成，而是通过多个阶段（phase）完成，如图1.1所示。每个阶段的结果是将一个较大的集合映射成一个较小的集合，称其为一次缩减（reduction）。RFC算法共分P个阶段，每个阶段由一些列的并行的查找组成。每个查找的结果值比用于查找的索引值要短（故称为一次缩减）。

图1 RFC的基本构思

图2 一个四阶段的RFC缩减树

图1.2中建立了一种4阶段的缩减树，对IP包查找过程如下：

…… …… 余下全文

8.1 实现顺序查找的算法

一，  实验目的

1.熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程；

2.学会分析各种查找算法的性能。

二，  实验内容

8.1 实现顺序查找的算法

编写一个程序，输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序查找法查找关键字5的结果。

8.2 实现折半查找算法

编写一个程序，输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找关键字9的结果。要求：（1）用非递归方法；（2）用递归方法。

8.3 实现二叉排序树的基本运算

编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：

（1）由{4,9,0,1,8，6,3,5,2,7}创建一个二叉排序树bt；

（2）判断bt是否为一棵二叉排序树（提示：在遍历过程中检查是否符合二叉排序树定义）；

（3）采用非递归方法查找关键字为6的结点，并输出其查找路径（提示：查找过程中保留经过的结点信息，找到后顺序输出之）。

8.4 实现哈希表的相关运算

编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能：

（1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函数为H(k)=key % 11，并采用线性探测法解决冲突。输出哈希表；

…… …… 余下全文

《数据结构与算法》课程学习总结报告

10040120xx 10计本（4）班 章兴春

本学期所学习的《数据结构与算法》课程已经告一段落，就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。以便在所学习知识有更深刻的认识。 一、《数据结构与算法》知识点：

学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。

第一章主要介绍了相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。

第二章具体地介绍了顺序表的定义、特点及其主要操作，如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度，插入与删除算法中的对象平均移动次数。

…… …… 余下全文

算法总结

1.穷举法

穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的是穷举法，即将密码进行逐个推算直到找到真正的密码为止。理论上讲，穷举法可以破解任何一种密码，但对于一个长度为n位的密码，其可能的密码有2^n种。可见，当n较大时穷举法将成为一个NP难度问题。

典型例题

【百钱买百鸡问题】公元5世纪末，中国古代数学家张丘建在他的《算经》中提到了著名的―百钱买百鸡‖问题:鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？

分析:设鸡翁、鸡母、鸡雏的个数各为x、y、z,百钱买

百鸡问题可以用如下方程式表示:

5x+3y+z/3=100

x+y+z=100

1<=x<20,1<=y<33,3<=z<100,z mod3=0

对于百钱买白鸡问题，很容易用穷举法对x、y、z的取值，判断

方程（1）、（2）及z mod3=0是否成立，若成立，则是问题的一个

解。

百钱买白鸡问题求解算法:

…… …… 余下全文