《第1章 数据结构与算法》由会员分享，可在线阅读，更多相关《第1章 数据结构与算法（10页珍藏版）》请在金锄头文库上搜索。
1、第4章 数据库设计基础 11第1章 数据结构与算法考试大纲（1）算法的基本概念，算法复杂度的概念和意义。（2）数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示，线性结构与非线性结构的概念。（3）线性表的定义，线性表的顺序存储结构及其插入与删除运算。（4）栈和队列的定义，栈和队列的顺序存储结构及其基本运算。（5）线性单链表、双向链表与循环链表的结构及其基本运算。（6）树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。（7）顺序查找与二分查找算法，基本排序算法（交换类排序、选择类排序、插入类排序）。考纲提示本章主要考查数据结构及相关基本概念，几种典型的数据结构及其操
2、作，算法的概念及算法复杂度，主要的查找及排序算法。这些在新考试大纲的公共基础部分中，约占30%的比例。知识点归纳【算法的基本概念】算法是对解题方案准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。严格说来，一个算法必须具有下列5个主要特性。（1）有穷性。一个算法必须在执行有穷步之后结束（对任何合法的输入值），而且每一步都必须在有穷时间内完成。 （2）确定性。算法中每条指令必须有确切含义，且在任何条件下，算法只有惟一的一条执行路径。（3）可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。（4）有输入。一个算法有0个或多个输入
3、，这些输入取自于某个特定的对象集合。（5）有输出。一个算法有0个或多个输出，这些输出是同输入有着某些特定关系的量。综上所述，算法是一组严谨的定义运算顺序的规则，而且每一个规则都是有效且明确的，此顺序将在有限的次数下终止。【算法的复杂度】算法的复杂度是本章的重点也是难点。选用算法首先要考虑正确性，还要考虑执行算法所耗费的时间和存储空间，同时，算法应易于理解、编码和调试等。算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。1算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数f (n)。算法的时间量度记作：算
4、法的工作量= f (n)，它表示随问题规模n的增大，算法执行时间的增长率和f (n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。2算法的空间复杂度一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，即算法程序所占用的空间、初始输入数据所占的存储空间，以及算法执行过程中所需要的额外空间。【数据结构】利用计算机进行数据处理是计算机应用的一个重要领域。数据结构作为计算机的一门学科，主要研究和讨论以下3个方面的问题。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。（3）对各种数据结构进行的运
5、算。简单地说，数据结构就是问题的数据模型。一般说来，用计算机解决一个具体问题时，大致需要经历下列几个步骤。（1）首先从具体问题中抽象出一个适当的数学模型。（2）然后设计一个解此数学模型的算法。（3）最后编写程序、进行测试、调整，直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。【数据的逻辑结构】数据结构是指反映数据元素之间关系的数据集合的表示。更通俗地说，数据结构是指带有结构的数据元素之间的前后件关系。因此，所谓结构，实际上就是指数据元素之间的前后件关系。数据的逻辑结构是指数据元素之间的逻辑关系，它可以用一个数据元素
6、的集合和定义在此集合上的若干关系来表示。数据的逻辑结构是从逻辑关系上描述数据，它与数据在计算机中的存储位置无关，是独立于计算机的。【数据的存储结构】数据的存储结构是本章的重要知识点。它是数据元素及其关系在计算机存储器内的表示。数据的存储结构是逻辑结构用计算机语言的实现，即建立数据的机内表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素；在存储空间中建立各存储结点之间的关联，以表示数据元素之间的逻辑关系。其中存储结点是指一个数据元素在存储结构中的存储。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用数据的存储结构有如下4种。（1）顺序存储方式。每一个存储结
7、点只含有一个数据元素。所有的存储结点相继存储在一个连续的存储区里。用存储结点之间的位置关系表示数据元素之间的逻辑关系。（2）链式存储方式。每一个存储结点不仅含有各数据元素，还包括指针。每一个指针指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。（3）索引存储方式。每一个存储结点仅含有一个数据元素，所有的存储结点都连续存放。此外，增设一个索引表。（4）散列存储方式。每一个存储结点仅含有一个数据元素，数据元素按散列函数确定存储位置。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。【数据的运算】数据运算是对数据施加的操作。常用的运算有如下几种
8、。（1）查找运算。从结构中找出满足某种条件的结点的位置。（2）读取运算。读出结构中指定位置上的内容。（3）插入运算。在结构中的某指定位置上增加一个新的结点。（4）删除运算。撤销结构中指定位置上的结点。（5）更新运算。修改结构中某指定结点的内容。【数据结构的图形表示】一个数据结构除了用二元关系表示外，还可以直接用图形表示。图1-1是一些常见数据结构的图形表示示例。 （a）线性结构 （b）树形结构 （c）图状结构 （d）集合结构图1-1 常见数据结构的图形表示示例【线性结构与非线性结构】根据数据结构中各数据元素之间前后件关系的复杂程度，将数据结构分成两大类型：线性结构和非线性结构。1线性结构在数据
9、元素的非空有限集中，线性结构的逻辑特征如下： （1）存在惟一的一个被称做“第一个”的数据元素；（2）存在惟一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中的每个数据元素均只有一个后继。线性表是一个线性结构。2非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继。例如，树和图都是非线性结构。线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟属于线性结构还是非线性结构，要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。【线性表】线性表是最
10、简单、最常用的一种数据结构。线性表是n个数据元素的有限序列。每个数据元素的具体含义在不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至其他更复杂的信息。在不同的情况下，它可以有不同的含义。例如，26个英文字母的字母表（A，B，C，D，Z）是一个线性表，表中的数据元素是单个字母。又如，某校19982004年的计算机拥有量的变化情况，可以用线性表的形式给出：（23，35，67，156，240，287，324）。表中的数据元素是整数。【线性表的顺序存储结构】线性表的顺序存储结构指的是用一组地址连续的存储单元依次存储线性表中的数据元素。其特点如下：（1）线性表中所有元素所占的存储空
11、间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。图1-2说明了数据元素在计算机内的存储情况。其中a1，a2，an表示线性表中的数据元素。a1a2aiai-1an线性表的起始地址（基地址）图1-2 线性表的顺序存储结构示意图在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间（字节数）相等，则要在该线性表中查找某一个元素是很方便的。所有数据元素的存储位置均取决于第一个数据元素的存储位置，即：LOC(ai) = LOC(a1) + (i-1) C 基地址
12、一个数据元素所占的字节数【线性表的插入运算】插入和删除运算是线性表的基本操作。插入运算是指在结构中的某指定位置上增加一个新结点；而删除运算是指撤销结构中某结点的内容。下面依次进行详细讨论。线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表(a1，ai-1，ai，an)变成长度为n+1的线性表(a1，ai-1，b，ai，an)数据元素ai-1和ai之间的逻辑关系发生了变化。一般情况下，要在第i（1in）个元素之前插入一个新元素，首先要从最后一个（即第n个）元素开始，直到第i个，元素之间共n-i+1个元素依次向后移动一个位置，移动结束
13、后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。【线性表的删除运算】和线性表的插入运算相反，线性表的删除操作是使长度为n的线性表(a1，ai-1，ai，ai+1，an)变为长度为n-1的线性表(a1，ai-1，ai+1，an)数据元素ai-1，ai和ai+1之间的逻辑关系发生了变化。一般情况下，要删除第i（1in）个元素，要从第i+1个元素开始，直到第
14、n个元素，之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。【栈】栈是限定仅在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊的含义，称为栈顶；相应地，表头端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈的修改是按“后进先出”或“先进后出”的原则进行的。因此，栈又称为先进后出表或后进先出表。【栈的顺序存储结构】栈的顺序存储结构利用一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素，同时附设指针指示栈顶元素在顺序栈中的位置，如图1-3所示。aaa指向栈顶的指针图1-3 栈的顺序存储结构示意图在图1-3中，a1为栈底元素，an为栈顶元素。栈中的元素按照a1, a2, , an的次序进栈，退栈的第一个元素为栈顶元素an。【栈的基本运算】栈的基本运算有3种：入栈、出栈与读栈顶元素。1入栈运算入栈运算是指在栈顶插入一个新元素。可分为两个基本操作：首先将栈顶指针进一，然后将新元素插入到栈顶指针指向的位置。
