大学科目《大学计算机基础》第1-8章课件（439页）.ppt

7.1.2程序设计语言机器语言汇编语言高级语言面向过程程序设计面向对象程序设计机器语言：由二进制编码指令构成的语言。优点：执行效率高。缺点：难修改，可移植性差。汇编语言：用一些便捷的英文字母和符号串来替换一些具有制定内容的指令的二进制串。优点：较之机器语言虽然各方面都得到了极大的改进，提高了编码的效率，执行效率比较高。缺点：仍然十分依赖机器硬件，可移植性依旧很差。高级语言：由自然语言和数学公式表示的语言。优点：更加接近于人类的自然语言，同时又不依赖于计算机硬件，编出的程序能在所有计算机上使用。缺点：高级语言程序需要编译后才能执行，执行效率比较低。面向过程程序设计：以事件为中心的编程思想，为了处理待解决的问题，首先需要分析出解决这个问题所需要的步骤，然后通过编写程序，把这些步骤实现，最后通过依次调用这些步骤最终实现解决问题的目的面向对象程序设计：设计一些通用的功能模块，它们与具体的应用无关，但是能够通过相互组合来完成具体的应用功能。功能模块可以被重复使用。对使用者来说，只需要知道这些功能模块实现的功能、如何连接这些功能模块、如何完成模块与模块之间的数据传递。至于模块如何实现其功能，使用者完全不用关心。7.2数据结构基础数据结构作为一门学科研究的是：非数值计算的程序设计问题中计算机的操作对象。这些操作对象之间的关系和操作。“数据结构”在计算机专业学习系统中是一门具有综合性的基础课。与计算机软硬件都有密切的关系。可以这么认为：数据结构是介于数学、计算机软件和计算机硬件三者之间的一门核心课程。7.2.1数据结构7.2.2基本概念和术语数据（data）：信息的载体，它能够被计算机识别、存储和加工处理。数据元素（dataelement）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据结构（datastructure）是数据元素的集合，这些数据元素不是孤立的，而是存在着一种或者多种特定关系。数据结构的逻辑结构和物理结构逻辑结构：从具体问题抽象出来的数学模型，是从用户角度看到的数据元素之间的关系。常用的逻辑结构有：集合：构成结构的数据元素之间除了同属于一个集合的关系外，没有其他关系。线性结构：数据元素之间存在着一对一的关系。包括线性表、栈、队列、数组、字符串等。树形结构：数据元素之间存在着一对多的关系。图形结构：该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。物理结构：数据在计算机中的存储表示。7.2.3线性表线性结构：在非空有限集中，有一个唯一的“头结点”，即有且只有一个数据元素被称为“第一个”；有一个“尾节点”，即有且只有一个数据元素被称作“最后一个”；除了第一个元素，每个元素只有一个前驱，除了最后一个元素，每个元素只有一个后继。线性表的顺序表示：指在内存中，用一段连续的地址，按照线性表中元素的顺序来存储元素。线性表顺序存储结构的插入和删除在线性表中插入数据元素就是说在线性表的任意位置上插入一个新的数据，例如第i个数据元素和第i+1个数据元素之间插入b。因为增加了一个新的数据，所以线性表的长度就由n变为了n+1。线性表（a1，…，ai，ai+1，…，an）变为线性表（a1，…，ai，b，ai+1，…，an）除非数据要插入的位置在数据的最后面（即插入的位置在i=n+1），否则由于内存的位置不可变，必须移动插入位置之后的元素来给要插入的数据让位置。删除的过程与插入相反：为了删除线性表中的第i个元素（1≤i≤n），我们需要将第i+1到第n个元素之间的所有元素依次往前移动一个单元。7.2.4栈和队列a3a2a1出栈入栈top栈和队列：是一种操作受限的线性表。（1）栈的操作原则：先进后出，后进先出。栈的尾端称为栈顶（top），栈的表头称为栈底（bottom）。不含元素的空表称为空栈。（2）队列的操作原则：只允许在表的一端进行插入，在另一端进行删除。先进先出的线性表。在队列中允许插入的一端称为队尾，允许删除的一端称为队头。队列示意图a1a2a3a4a5入队出队7.2.5树树形结构：该结构的数据元素之间存在着一对多的关系。KNLADBCEFGHIJMO树结构中的部分术语树的结点：一个数据元素和它所有的指向其子树的分支。结点的度：结点挂接的子树数。树的度是指所有结点的度的最大值。一个节点的子树的根称为该节点的孩子，对应的，这个结点称为孩子的双亲。树的深度：树中结点