《第1章 数据结构与算法.doc》由会员分享，可在线阅读，更多相关《第1章 数据结构与算法.doc（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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。平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。【栈】栈是限定仅在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊的含义，称为栈顶；相应地，表头端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈的修改是按“后进先出”或“先进后出”的原则进行的。因此，栈又称为先
15、进后出表或后进先出表。【栈的顺序存储结构】栈的顺序存储结构利用一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素，同时附设指针指示栈顶元素在顺序栈中的位置，如图1-3所示。aaa指向栈顶的指针图1-3 栈的顺序存储结构示意图在图1-3中，a1为栈底元素，an为栈顶元素。栈中的元素按照a1, a2, , an的次序进栈，退栈的第一个元素为栈顶元素an。【栈的基本运算】栈的基本运算有3种：入栈、出栈与读栈顶元素。1入栈运算入栈运算是指在栈顶插入一个新元素。可分为两个基本操作：首先将栈顶指针进一，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不
16、能再进行入栈操作。2退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变量。可分为两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一。当栈顶指针为0时，说明栈空，不能进行退栈操作。3读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。【队列】队列是限定仅在表的一端进行插入，而在表的另一端删除数据元素的线性表。在队列中，允许插入的一端叫做队尾，允许删除的一端叫做队头。【队列的顺序存储结构】与栈的存储结构相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依
17、次存放从队头到队尾的元素之外，还需要附设两个指针，分别指示队头元素和队尾元素的位置。与栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这与日常生活中的排队是一样的，早进入队列的早离开。【队列的基本运算】队列的基本运算有入队和退队两种。1入队运算入队运算是指在队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一，然后将新元素插入到队尾指针指向的位置。2退队运算退队运算是指在队头位置退出一个元素并赋值给指定的变量。这个运算有两个基本操作：首先将队头指针进一，然后将队头指针指向的元素赋给指定的变量。【线性单链表】线性表的链式存储结构的特点是用一组任意的存
18、储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储信息）。这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域：（1）存储数据元素信息的域称为数据域；（2）存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。N个结点链接成一个链表，即为线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。通常以线性表中第一个数据元素的存储地址作为线性表的地址，称
19、做线性表的头指针。有时，为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。整个链表存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”。【循环链表】循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中的其他结点。循环链表和单链表的差别仅在于判断链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。【双向链表】以上讨论的链式存储结构的结点中，只有一个指示直接后继的指针域
20、，由此从某个点出发，只能顺指针往后寻查其他结点。若要寻查结点的直接前驱，则需要从表头指针出发，这样影响查找效率。为了克服单链表这种单向性的缺点，可利用双向链表。在双向链表的结点中，有两个指针域，其一指向直接后继，另一个指向直接前驱。【链表的基本操作】链表的基本操作可以分为“插入”和“删除”两种。1插入操作假设要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其链表存储结构中指向结点a的指针。如图1-4（a）所示。为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而
21、实现3个元素a、b和x之间逻辑关系的变化。插入后的链表如图1-4（b）所示。a bppaxb（a）插入前 （b）插入后图1-4 链表的插入操作2删除操作反之，如图1-5所示，在线性表中删除元素b时，为在链表中实现元素a、b和c之间逻辑关系的变化，仅须修改结点a中的指针域即可。apbc图1-5 链表的删除操作【树及其基本概念】树是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次性。图1-6表示了一棵一般的树。由此图可以看出，在用图形表示树这种数据结构时，很像自然界中的树。树是n(n0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当
22、n1时，其余结点可分为m（m0）个互不相交的有限集T1, T2, , Tm。其中，每个有限集本身又是一棵树，并且称为根的子树。在图1-6中可以看到树的根结点A及子树（a）。有关树的基本术语有很多，其中常用的有以下几种。（1）结点。包含一个数据元素及若干指向其子树的分支。（2）结点的度。结点拥有的子树数。如在图1-6中，结点A的度为3，C的度为1。（3）叶子。度为0的结点称为叶子。如在图1-6中，E、I、J、G、H都是叶子结点。ACGHDBEFIJ(a)(b)（a）（b）图1-6 树的结构示例（4）孩子和双亲。结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。同一个双亲的孩子之间互称
23、为兄弟。例如，在图1-6中，F为子树（a）的根，同时F又是B的孩子，而A是B、C、D的双亲，B、C、D互为兄弟。（5）层次。结点的层次从根开始定义，根为第一层，根的孩子为第二层。若某结点在第i层，则其子树的根就在第i+1层。（6）深度。树中结点的最大层次称为树的深度或高度。如图1-6中的树深度为4。【二叉树】二叉树及其相关的概念和操作是本章中非常重要的知识点。二叉树是另一种树形结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。图1-7是一棵二叉树的示例。RTLTR左子树右子树R1R2L1L2L3L4图1-7 二叉树示例【二叉树的存储结构】1二叉树的顺序存
24、储结构在二叉树的第零层有20=1个结点即根结点。第一层根据根结点的子结点的个数不同有1或2个结点。第二层的结点总数为14不等，最大值4只有当根结点及其两个子结点都拥有最多的子结点数目（即两个子结点）时才能达到。一般情况下，二叉树的第n层的结点数可以在12n之间变化。每层平均的结点数定义为树的密度。树的密度也可看作是对树的规模（结点数目）相对于树的深度的衡量。在图1-8中，树A有9个结点，深度为3；而树B有5个结点，深度为4。后者是一种特殊的情况，称为退化树，因为只有一个叶结点，且每一个非叶结点只有一个子结点。n结点退化树的深度为n-1。可以看出，退化的树和链表是等价的。AFGCBDEHI树 A
25、9个结点，深度为3ABCDE树 B5个结点，深度为4图1-8 二叉树和退化树作为一种数据结构，高密度的树更加重要，因为它能够更紧密地将结点聚集在根结点的周围。这样访问数据的路径就可以尽可能地短。更精确地说，退化树的密度是一种极端情况。另一个极端，深度为n的完全的二叉树的第0层到第n-1层的结点是满的，而在第n层，叶子结点则占据了最左边的位置。最大的深度为n的完全二叉树在第n层有2n个结点。在这样的二叉树中，每个内部结点有两个子结点。图1-9区分了完全和非完全二叉树。BDAEHIJCFG完全二叉树(深度2)具有所有可能的结点BADECFG完全二叉树(深度3)BDAEHIC非完全二叉树(深度3)层次2遗漏结点BDAEHIKCFG非完全二叉树(深度3)层次3的结点不在最左边的位置HIDEBACHDBAEKICFG图1-9 完全二叉树和非完全二叉树2二叉树的链式存储结构在二叉树的二叉链表存储中，通常采用的方法是：每个结点中设置3个域，即值域、