1算法1.1 算法的基本概念1．算法的概念(必记)：算法是指解题方案的准确而完整的描述。

分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。

整套的指导方案称之为算法，而具体的实现称之为程序。

并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。

结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。

2．算法的基本特征(必记)：a.可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。

b.确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

c.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

d.拥有足够的情报：算法有相应的初始数据。

3．算法的基本要素：一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。

基本运算和操作分为四类：a. 算术运算: (加、减、乘、除等运算)b. 逻辑运算: (与、或、非等运算)c. 关系运算: (大于、小于、等于、不等于等运算)d. 数据传输: (赋值、输入、输出等操作)算法的控制结构：算法中各操作之间的执行顺序称之为算法的控制结构。

一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。

注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。

4．算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。

1.2 算法的复杂度 (必记)算法的复杂度主要包括时间复杂度和空间复杂度。

1．算法的时间复杂度：是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。

可用平均性态和最坏情况两种分析方法。

其中平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。

2．算法的空间复杂度：一个算法的空间复杂度，是指执行这个算法所需要的内存空间。

包含有三部分所组成：算法程序所占的空间+输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。

历届的考题：1、算法具有五个特性，以下选项中不属于算法特性的是(______) [2005.4]A)有穷性B)简洁性C)可行性D)确定性2、问题处理方案的正确而完整的描述称为______。

[2005.4]3、下列叙述中正确的是________。

[2006.9]A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小第1页，共26 页4、算法复杂度主要包括时间复杂度和[_____]复杂度。

[2006.9]1.2 数据结构与算法数据结构作为计算机的一门学科，主要研究以下三个方面的问题：a ．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b ．在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c ．对各种数据结构进行的运算。

注意：讨论以上问题主要目的是为了提高数据处理的效率。

提高效率包括两个方面：一是提高数据处理的速 度，二是节省在数据处理过程中所占用的计算机存储空间。

2.1 什么是数据结构简单地说，数据结构是指相互有关联的数据元素的集合。

而数据元素之间的关联通常是指其前后件关系(即 先后顺序关系)，如春、夏、秋、冬之间的先后顺序关系。

因此，一个数据结构应包含以下两方面的信息：a.表示数据元素的信息； b.表示各数据元素之间的前后件关系。

1．数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。

注意：这种逻辑关系仅指元素之间的固有的一个先后顺序关系，而与它们在计算机中的存储顺序无关。

2．数据的存储结构数据的存储结构的概念：数据的逻辑结构在计算机存储空间中的存放形式 (也称数据的物理结构)。

注意：a 、数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同，也可以不相同。

b 、数据的存储结构有顺序、链接、索引等。

c 、数据元素采用不同的存储结构，其数据处理的效率是不同的。

2.2 数据结构的图形表示在数据结构中，没有前件的结点成为根结点( (也称为 叶子结点，如上图中的冬与儿子和女儿)。

注意：在进行处理时， 一个数据结构中的元素结点可能是在动态变化的。

这种变化可能是元素结点的个数发生变化，也可以是元素结点的先后顺序发生变化。

2.3 线性结构与非线性结构空的数据结构是：一个数据元素都没有的数据结构。

根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分为二大类：线性结构和非线性结构。

一个非空的数据结构满足下列两个条件，则为线性结构，线性结构又称为线性表。

a. 有且只有一个根结点； b.每一个结点最多有一个前件，也最多有一个后件。

在上图中，左边的是线性结构，而右边的是非线性结构。

注意：线性结构与非线性结构都可以是空的数据结构。

一个空的数据结构究竟属于线性结构还是属于非线性 结构， 要根据具体情况来确定。

如果对该数据结构的运算是按线性结构的规则来处理的， 则属于线性结构；否则属于非线性结构。

历届的考题：1、数据的存储结构是指(_____)[2005.4]A)存储在外存中的数据C)数据在计算机中的顺序存储方式B)数据所占的存储空间量D)数据的逻辑结构中计算机中的表示第2页，共26 页B)数据的逻辑结构属于线性结构，存储结构属于非线性结构C)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率1.3 线性表及其顺序存储结构3.1 线性表的基本概念非空线性表的结构特征如下：a.有且只有一个根结点，它无前件；b.有且只有一个终端结点，它无后 他所有结点有且只有一个前件，也有且只有一个后件。

线性表中结点的个数 n 称为线性表的长度。

当 n=0 时，称为空表。

3.2 线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点： a.线性表中所有元素所占的存储空间是连续的；b.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

注意： 在线性表的顺序存储结构中， 其前后件两个元素在存储空间中是紧邻的， 且前件元素一定在后件元素 的前面。

在线性表的顺序存储结构中，如第一个元素的地址为ADR(a1)，每个元素占用的存储空间大小为k 个字节， 则线性表中第 i 个元素的存储地址为：ADR(a1)+(i-1)*k3.3 顺序表的插入运算1003 1004冬秋冬在线性表的顺序存储结构中，当插入元素时，插入点后的元素都要向后移动一位，以让出一个存储空间。

在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。

因此，在线性表顺序存储的情况 下，要插入一个新元素，其效率是很低的。

3.4 顺序表的删除运算在线性表的顺序存储结构中，当删除元素时，删除点后的元素都要向前移动一位，以保证元素都是相邻存储的。

在平均情况下， 要在线性表中删除一个元素， 需要移动表中一半的元素。

因此， 在线性表顺序存储的情况下，要删除一个元素，其效率是很低的。

1.4 栈和队列4.1 栈及其基本运算 1．什么是栈栈是一种特殊的线性表。

栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允表示栈底。

第3页，共26 页2．栈的顺序存储及其运算栈的基本运算有三种：.入栈运算、退栈运算和.读栈顶元素。

4.2 队列及其基本运算1．什么是队列队列是允许在一端进行插入、而在另一端进行删除的特殊的线性表。

允许插入的一端称为队尾，允许删除的一端称为排头(或队头)。

队列又称为"先进先出"(FIFO)或"后进后出"(LILO)的线性表，它体现了"先来先服务"的原则。

往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。

2．循环队列及其运算所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

队列空和队列满的条件如下：队列空的条件为 s=0 ;队列满的条件为 s=1 且front=rear.循环队列主要有两种基本运算：入队运算和退队运算。

a.入队运算：在循环队列的队尾加入一个新元素，首先将队尾指针进一(即rear=rear+1)，并当rear=m+1 时置rear=1；然后将新元素插入到队尾指针指向的位置。

注意：当循环队列非空(s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为"上溢"。

( 即b. 退队运算：指在循环队列的排头位置退出一个元素并赋给指定的变量。

首先将排头指针进一front=front+1)，并当front=m+1 时置front=1;然后将排头指针指向的元素赋给指定的变量。

注意：当循环队列为空(s=0)时，不能进行退队运算，这种情况称为"下溢" 。

历届的考题：1、下列关于栈的描述中错误的是(_______)[2005.4]A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针2、按照"后进先出"原则组织数据的数据结构是(______)[2006.4]A)队列B)栈C)双向链表D)二叉树3、列关于栈的描述正确的是(______)[2005.9]A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素4、数据结构分为逻辑结构和存储结构，循环队列属于____结构。

[2005.9]5、按“先进后出”原则组织数据的数据结构是_____。

[2006.9]1.5线性链表5.1 线性链表的基本概念1.链式存储在顺序存储方式中所有的数据元素在内存中是相邻存放的，从而造成了在插入与删除数据元素时，需要大量移动相应的数据元素。

为了解决这种问题，可以将每个数据元素存储在内存中不相邻的不同位置，并利用上一个数据元素在存有数据的同时，也存放下一个数据元素所在的位置地址(称为一个存储单元，即结点)，以便查找。

这就是链式存储方式。

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放地址，称为指针域。

其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

注意：ahead 头结点开始结点a1 a2 …终端结点a n∧逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。