公共基础知识教案

《公共基础知识教案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一部分三、算法程序二数据结构+算法基本了解数据结构的基本概念深刻理解线性表及其顺序存储结构深刻理解栈和队列深刻理解五、线性链表基本了解六.树与二叉树熟练应用第一节算法算法的基本概念所谓算法是指解决方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到止确的结果，则称这个问题是算法可解的。例如：把两个容器的液体交换一下。它的算法是：算法和程序是不太一样的。程序可以作为算法的某种计算机语言的实例化。算法是对问题的具体分析过程，是一个步骤的序列。程序通常还需要考虑其它细节问题，因为我们必须要考虑计算机系统的具体运行环境。算法的基木特征是：可行性：

2、算法是可行的确定性：算法的每一步必须有明确定义，不允许冇模棱两可的解释，更不允许有多义性有穷性：算法必须在有限的吋间内做完，也就是说执行有限个步骤后终止拥有足够的情报：不同的输入会有不同的结果输出综上所述：算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此规则序将在有限的次数下终止。二.算法复杂度时间复杂度:执行算法所需要的计算工作量，也就是步骤有限。空间复杂度:执行算法所需要的内存空间。第二节数据结构的基本概念一.什么是数据结构利用计算机进行数据处理时，我们经常面对的是海量的数据，这些数据元素都要存储到计算机中，那么这些数据如何组织是进行数据处理的第一步。存储都做不

3、到，怎么可能处理好呢？可以说，大量的数据元素如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。一句话，程序执行的效率与数据的存储结构密切相关。例如，校园的图书馆。对于图书馆而言，数据元素就是一本本的书。对这些数据元素存储时，必须要考虑：1、节省空间。2、方便查找和统计。因此，我们需要认真研究一下数据的存储问题。数据结构研究的就是如何把数据保存到计算机中，主要涉及到三个方面的问题：•数据集合中各数据元素之间本来就有的逻辑关系，即数据的逻辑结构；•在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；•对各种存储结构进行运算。讨论这些问题主要目

4、的是为了提高书本处理的效率，并且节省图书馆的存储空间。说到底什么是数据结构？数据结构就是相互有关联的数据元素的集合。在深入学习数据结构之前，我们先要掌握数据结构的几个概念:1.数据元素：一般来说，现实世界中客观存在的一切个体都可以是数据元素，例如：描述一年四季的季节名：春、夏、秋、冬可以作为季节的数据元素；表示数值的各个数18、11、35、23、16可以作为数值的数据元素；表示家族成员的各成员名父亲、儿子、女儿可以作为家族成员的数据元素。总之，在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素，数据元素一般称之为元素。2.数据的逻辑结构：前面我们已经提到，数据结构是指相互有关联的数据元

5、素的集合。更通俗地讲，数据结构是带有结构的数据元素的集合。例如，我们前面提到的一年四季的季节名：春、夏、秋、冬。“春”是“夏”的前驱，“夏”是“春”的后继；同样,“夏”是“秋”的前驱，“秋”是“夏”的后继。数据元素之间的前驱、后继关系就是数据的逻辑结构，这与它们在计算机中的存储位置无关。3.数据的物理结构：在利用计算机进行数据处理时，总是要考虑被处理的各数据是如何存放在计算机的存储空间的；并且，各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定相同，而且一般也是不可能相同。数据的逻辑结构在计算机存储空间的存放形式称之为数据的存储结构。也称之为数据的物理结构。一.数据的逻辑结构的分类如

6、果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据结构屮各数据元素Z间前后件关系的复杂程度，一般把数据结构分为两个大的类型：线性结构和非线性结构。线性结构也称之为线性表：应该满足以下两个条件：•有且只有一个根结点；•每一个结构最多只能有一个前驱，也最多只能有一个后继。例如：买火车票时排的长队就是一个线性的结构。很多数据结构并不是线性的，例如：反映家族成员间辈分关系的数据结构。第三节线性表及其顺序存储结构一、线性表的基本概念线性表是最简单、最常用的数据结构。是由n个数据元素ai,a2,.・・，&□组成的一个有限序列，表中的每一个数据元素，除第一个外，有且只有一个前驱，除

7、最后一个之外,有且只有一个后继。例如，下面有一个表格：姓名学号性别年龄健康状况王强800356男19良好刘建平800357男20一般赵军800361女19良好葛文华800367男21较差我们曾经提到过，对于数据库表来说，每一条记录是一个整体。因此，在数据库表中，数据元素不再是简单项，每个数据元素都由五个数据项组成。从数据结构的观点來研究这个表，我们可以认为这是一个由多个记录构成的线性表。二、线性表