C语言-公共基础

1、Linyi university Department of Computer Science公共基础知识公共基础知识临沂大学信息学院临沂大学信息学院 公共基础知识公共基础知识 公共基础知识公共基础知识 公共基础知识公共基础知识 公共基础知识公共基础知识程序设计的基本概念程序设计的基本概念CPU内存磁盘程序设计的基本概念程序设计的基本概念v人和计算机交流的语言，但计算机值只识别人和计算机交流的语言，但计算机值只识别0和和1。程序设计的基本概念程序设计的基本概念n给定一个问题n分析问题（算法）n编程（用一种计算机语言）n编程的方法：结构化的方法、面向对象的方法编程的方法：结构化的方法、面向对象的

2、方法 第第1章数据结构与算法章数据结构与算法algorithm1 1、算法的基本概念、算法的基本概念 算法算法解题方案的准确而完整的描述解题方案的准确而完整的描述 算法具有可行性、可行性、确定性确定性、有穷性有穷性、输入输入和输出输出（拥有足够的情报）等4个重要特性。第第1章数据结构与算法章数据结构与算法（1 1）时间复杂度）时间复杂度v时间复杂度时间复杂度指执行算法所需要的基本元算次数来度量v常用的度量方法：平均性态、最坏情况复杂性第第1章数据结构与算法章数据结构与算法（2 2）空间复杂度）空间复杂度n 一般是指执行这个算法所需要的内存空间。n所需内存空间包括：n算法程序所占的空间、n输入的

3、初始数据所占的存储空间n算法执行过程所需要的额外存储空间。第第1章数据结构与算法章数据结构与算法-1.2数据结构数据结构Data Structure1 1、数据结构的基本概念、数据结构的基本概念n数据结构是指相互关联的数据元素的集合n数据结构分为数据结构分为数据的逻辑结构数据的逻辑结构和和数据的物理结构数据的物理结构。1.2数据结构数据结构（1 1）数据的逻辑结构：）数据的逻辑结构：指数据元素之间的前后件关系指数据元素之间的前后件关系冬冬春春夏夏秋秋例例1：一年四季的逻辑结构：一年四季的逻辑结构 父亲父亲儿子儿子女儿女儿例2：家庭成员数据结构可表示成1.2数据结构数据结构（2 2）数据的物理结

4、构）数据的物理结构n数据的逻辑结构在计算机存储空间的存放形式称为数据的逻辑结构在计算机存储空间的存放形式称为数据的物理结构（也称为数据的存储结构）数据的物理结构（也称为数据的存储结构）1.2数据结构数据结构2、几个术语：n前件（或前驱）n后件（或后继）n根结点n叶子结点冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿1.2数据结构数据结构数据结构分为：数据结构分为：线性结构与非线性结构：线性结构与非线性结构：3 3、线性结构与非线性结构：、线性结构与非线性结构：n线性结构线性结构n有且只有一个根结点有且只有一个根结点n每一个结点最多有一个前件，也最多有一个后件。每一个结点最多有一个前件，也最多有一个后

5、件。n注意：在线性结构中插入或删除任何一个结点后还注意：在线性结构中插入或删除任何一个结点后还应是线性的。应是线性的。D DA AB BC Cn非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。1.3线性表（线性表（Linear List）三、线性表三、线性表：具有线性结构的有限序列。 1 1、线性表的特点：、线性表的特点： （1 1）有且只有一个根结点，它无前件；）有且只有一个根结点，它无前件； （2 2）有且只有一个终端结点，它无后件；有且只有一个终端结点，它无后件； （3 3）除根结点和终端结点外，其它所有结点有且）除根结点和终端结点外，其它所有结点有且 仅有一个前件也有且

6、只有一个后件。仅有一个前件也有且只有一个后件。 冬冬春春夏夏秋秋1.3线性表（线性表（Linear List）2、线性表的、线性表的 顺序存储结构n顺序存储结构特点：顺序存储结构特点：（1）所有元素所占的存储空间是连续的。）所有元素所占的存储空间是连续的。（2）各数据元素在存储空间中是按逻辑顺序）各数据元素在存储空间中是按逻辑顺序依次存放的。依次存放的。1.3线性表（线性表（Linear List）3 3、 插入 与与 删除 操作操作（1 1）插入）插入（假设原表中有（假设原表中有n个元算）个元算）n插入插入一个元素时移动元素的数目：插入插入一个元素时移动元素的数目：n最少移动的元素数目：最少

7、移动的元素数目：0 0个个n插入时最多移动的元素数目：插入时最多移动的元素数目：n个个n插入时平均移动的元素数目：插入时平均移动的元素数目：n/2个个1.3线性表（线性表（Linear List）（2）删除（假设原表中有）删除（假设原表中有n个元算）个元算）n删除一个元素时移动的数据元素数目删除一个元素时移动的数据元素数目n删除时最少移动的元素数目：删除时最少移动的元素数目：0个个n删除时最多移动的元素数目：删除时最多移动的元素数目：n-1个个n删除时平均移动的元素数目：删除时平均移动的元素数目：n-1/2个个1.4栈和队列栈和队列四、堆栈和队列的定义四、堆栈和队列的定义1、栈、栈n栈是限定只

8、能在表的一端进行插入和删除的特殊的栈是限定只能在表的一端进行插入和删除的特殊的线性表。线性表。n栈是：先进后出栈是：先进后出(FILO)ntop、bottom指针指针nbottom指针不动、指针不动、top指针根据入栈和出栈来回移动指针根据入栈和出栈来回移动 a1 a2 . an进栈进栈出栈出栈栈顶栈顶栈底栈底topbottom1.4栈和队列栈和队列n栈的运算（1）入栈（2）出栈（或退栈）（3）读栈n上溢、下溢上溢、下溢队列队列2 2、队列：、队列：n限定只能在一端进行插入，在表的另一端进行删除的限定只能在一端进行插入，在表的另一端进行删除的线性表线性表 。（队头出队，队尾入队）。（队头出队，

9、队尾入队）n此种结构称为此种结构称为先进先出（先进先出（FIFO）表）表。 a1 , a2 , a3 , a4 , an-1 , an 队头队尾n front和 rear指针nFront总是指向队头元素的前一个空间nrear指向队尾最后一个元素n队列的主要运算队列的主要运算（1）入队）入队 从队尾入队从队尾入队（2）退队（出队）退队（出队） 从对头出队从对头出队FEDCBAH12345678910frontrear队头队尾n循环队列 FEDCBAH12345678910frontrearFEDCBAH12345678910front入队X,Y,Z 元素后的指针变化XYZrear初始队列YXFE

10、DCBAZ12345678910frontrear H元算退队后的指针变化H队列队列总结（假设队列的总空间个数为m）：n循环队列采用顺序存储结构n队尾rear指针值可以比对头front指针值大，队尾rear指针值可以比对头front指针值小。n如rear=front则队列为空，或满队，元素个数为0或mn如rearfront则对中的元素个数为rear-frontn如rearfront则对中的元素个数为m-front+rear1.5线性链表线性链表1 1、线性链表的基本概念：、线性链表的基本概念：n线性表的链式存储结构称为线性链表。 单向链表单向链表双向链表双向链表1.5线性链表线性链表v循环链表

11、：循环链表：1.5线性链表线性链表v 链接存储结构特点链接存储结构特点：n比顺序存储结构占用的空间多(每个节点都由数据域和指针域组成)。n逻辑上相邻的节点物理上不必相邻：即存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系顺序可以不一致。n插入、删除灵活： (不必移动节点，只要改变节点中的指针)。n查找结点时链式存储要比顺序存储慢。1.6树与二叉树树与二叉树n树的基本概念：树的基本概念：n树是一种非线性数据结构，它的每一个结点，都可以有不止一个后件，除根外的所有结点，都有且只有一个前件。42316789101213145An基本概念n度：一个结点所拥有的后件个数为该结点的度n树的

12、度：在一棵树中所有结点中的最大的度n深度：树的最大层次42316789101213155n一棵二叉树每个结点的度有几种情况？n三种情况：度为0，度为1，度为2n所以一棵二叉树的总结点数为：n度为0的结点数+度为1的结点数+度为2的结点数n二叉树1.6树与二叉树树与二叉树n二叉树的性质：二叉树的性质：l在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多 一个。l例子例子1 1：某二叉树中度为2的结点有18个，则该二叉树中有 19 19 个叶子结点。1.6树与二叉树树与二叉树n满二叉树与完全二叉树满二叉树与完全二叉树l满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。l完

13、全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。l注意：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。v完全二叉树的特点：完全二叉树的特点：除最后一层外，每一层都取最大结点数，除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置最后一层结点都集中在该层最左边的若干位置1.6树与二叉树树与二叉树性质性质2 2：满二叉树的第i层上有2 i-1（i 1）个结点423167891011121314155第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。1.6树与二叉树树与二叉树性质性质

14、3 3：深度为深度为h h的满二叉树中含有的满二叉树中含有2 2h h-1 -1个结点个结点423167891011121314155此树的深度此树的深度h=4h=4，共有，共有2 24 4-1=15-1=15个节点。个节点。1.6树与二叉树树与二叉树n二叉树的遍历n二叉树的遍历是指不重复地访问二叉树中的所有结点。1、前序遍历2、中序遍历3、后序遍历1.6树与二叉树树与二叉树考试题目：考试题目：1 1、设一棵二叉树的中序遍历结果为、设一棵二叉树的中序遍历结果为DBEAFC,DBEAFC, 前序遍历结果为前序遍历结果为ABDECFABDECF，则后序遍历结，则后序遍历结 果为：果为： DEBFC

15、ADEBFCA 1.6树与二叉树树与二叉树2、一棵二叉树有25个结点，其中5个是叶子结点，则度为1的结点数为（ ） 例题讲解例题讲解1、设一棵完全二叉树共有700个结点，则 在该二叉树中有 350 350 个叶子结点。2、在深度为5的满二叉树中，叶子结点的 个数为（ C C ） A) 32 B) 31 C) 16 D) 15例题讲解例题讲解1 1、设一棵二叉树的中序遍历结果为、设一棵二叉树的中序遍历结果为DBEAFC,DBEAFC, 前序遍历结果为前序遍历结果为ABDECFABDECF，则后序遍历结，则后序遍历结 果为：果为： DEBFCADEBFCA 2 2、已知一棵二叉树前序遍历和中序遍历

16、分别、已知一棵二叉树前序遍历和中序遍历分别 为为ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，则该二叉树，则该二叉树 的后序遍历为（的后序遍历为（ B B ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCA B) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG1.7查找技术查找技术n查找查找又称为检索又称为检索 1 1、查找的概念、查找的概念 2 2、查找的分类、查找的分类l查找可分为查找可分为顺序查找顺序查找和和二分法查找二分法查找两种。两种。l顺序查找比较的次数最坏情况下为顺序

17、查找比较的次数最坏情况下为n n次次l二分查找的次数最坏情况下为二分查找的次数最坏情况下为log2n次次.l二分查找的前提是：二分查找的前提是：数据必须是有序的。数据必须是有序的。1.7查找技术查找技术3、查找的注意事项n如采用顺序存储，如果是有序线性表有序线性表，则可以采用二分法查找或顺序查找，二分查找最坏查找次数为二分查找最坏查找次数为：loglog2 2n n次，顺序查找最坏查找次数为：次，顺序查找最坏查找次数为：n n次次；如果是无；如果是无序的序的只能用顺序查找，最坏查找次数为：n次。n如采用链式存储，不管数据是有序的还是无序的，则只能采用顺序查找，最坏查找次数为：n n次次1.8排

18、序技术排序技术1 1、交换类排序：、交换类排序：（1 1）冒泡排序法：最坏比较次数为）冒泡排序法：最坏比较次数为n(n-1)/2n(n-1)/2（2 2）快速排序法：是对冒泡排序的改进）快速排序法：是对冒泡排序的改进, ,最坏比较最坏比较次数为次数为n(n-1)/2n(n-1)/21.8排序技术排序技术2 2、插入类排序、插入类排序：(1)简单插入排序法最坏情况需要n(n-1)/2次比较；(2)希尔排序法最坏情况需要o（n 1.5）次比较。1.8排序技术排序技术3 3、选择类排序：、选择类排序： （1）简单选择排序法最坏情况需要n(n-1)/2次比较；（2）堆排序法最坏情况需要o（nlog2

19、n）次比较。第第2章程序设计基础章程序设计基础一、程序设计方法与风格一、程序设计方法与风格 1 1、程序设计方法、程序设计方法n结构化方法结构化方法n面向对象的方法面向对象的方法2、程序设计的良好风格、程序设计的良好风格n清晰第一、效率第二清晰第一、效率第二n程序应简单、可读性好、易于使用和维护，程序应简单、可读性好、易于使用和维护，第第2章程序设计基础章程序设计基础1、原则、原则n自顶向下、逐步求精、模块化、限制使用自顶向下、逐步求精、模块化、限制使用GOTO语句语句2、结构化程序的、结构化程序的基本结构基本结构程序结构仅由程序结构仅由顺序顺序、选择选择和和循环循环3种结构复合而成种结构复合

20、而成二、结构化程序设计二、结构化程序设计 第第2章程序设计基础章程序设计基础三、面向对象的程序设计方法三、面向对象的程序设计方法n面向对象的方法以对象为核心，结构化的程序设计方法以对象为核心，结构化的程序设计方法以算法为核心以算法为核心第第2章程序设计基础章程序设计基础2 2、几个术语：、几个术语：n对象：n属性：对象所包含的信息。n操作：描述了对象的功能n封装性n类：类是一组具有相同属性和相同操作的对象的集合。n类和对象的关系：对象是类的实例。n消息：对象之间传递的信息n继承：使用已有的类定义作为基础建立新类。n多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。第第3章软件

21、工程基础章软件工程基础一、基本概念一、基本概念 1、软件的定义n软件：是包括程序、数据和有关文档的完整集合。n软件分类：系统软件、应用软件、支撑软件第第3章软件工程基础章软件工程基础2、软件危机与软件工程、软件危机与软件工程n软件危机：软件危机：泛指在计算机软件的开发和维护过程中所泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题（遇到的一系列严重问题（成本高、质量难以保证、生成本高、质量难以保证、生产率低等产率低等）。）。 n软件工程：软件工程：软件工程是指应用工程、科学、数学的原软件工程是指应用工程、科学、数学的原理与方法研制、维护计算机软件的有关技术及管理方理与方法研制、维护计算机

22、软件的有关技术及管理方法。法。第第3章软件工程基础章软件工程基础3、软件生命周期、软件生命周期n软件生命周期n概念：将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。n阶段：分为软件定义、软件开发及软件运行维护3个时期。n6个主要活动阶段：个主要活动阶段：n可行性研究与计划制定可行性研究与计划制定n需求分析需求分析n概要设计概要设计n详细设计详细设计n实现实现n软件测试软件测试n使用使用n维护维护n退役退役定义阶段开发阶段维护阶段第第3章软件工程基础章软件工程基础n利用软件工程的原理如何进行软件开发? 首先进行：需求分析n什么是需求分析什么是需求分析 确定系统具备哪些功能、

23、软件系统必须做什么。确定系统具备哪些功能、软件系统必须做什么。n需求分析阶段的工作需求分析阶段的工作 （1）需求获取）需求获取 （2）需求分析）需求分析 （3）编写需求规格说明文档）编写需求规格说明文档 （4）需求评审）需求评审第第3章软件工程基础章软件工程基础l采用的方法采用的方法 结构化分析方法结构化分析方法、面向对象的分析方法 第第3章软件工程基础章软件工程基础二、结构化分析方法二、结构化分析方法1 1、结构化分析方法用到的工具：、结构化分析方法用到的工具：n数据流图数据流图(DFD)：用来描述数据流从输入到输出的变换流程。n（数据流图：参看课本（数据流图：参看课本69 图图3.4）n数

24、据字典数据字典(DD)：对DFD中出现的被命名的图形元素的确切解释。加工（转换）数据流存储文件（数据源）源，潭第第3章软件工程基础章软件工程基础三、结构化设计方法三、结构化设计方法 从工程管理的观点看，软件设计包括：概要设计和详细设计从工程管理的观点看，软件设计包括：概要设计和详细设计1、软件设计的基本原理、软件设计的基本原理n模块独立性：模块独立性： n模块独立性度量的两个标准：内聚性、耦合性n模块独立性度量原则：高内聚低耦合第第3章软件工程基础章软件工程基础2、概要设计、概要设计n概要设计任务概要设计任务n设计软件体系结构：设计软件体系结构：划分模块以及模块层次结构划分模块以及模块层次结构

25、临沂大学教务系统学生管理教师管理职工管理系院管理后勤管理第第3章软件工程基础章软件工程基础2、详细设计n详细设计的任务：为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。n常用的设计工具n程序流程图程序流程图： n参看教材P81图3.18n N-S图nPAD图：教材P81-83加工步骤控制流逻辑条件第第3章软件工程基础章软件工程基础n表格工具：判定表n语言工具：PDL(伪码）第第3章软件工程基础章软件工程基础四、软件测试四、软件测试 1、软件测试是为了发现错误而执行程序的过程；2、软件测试的方法 （1）静态测试与动态测试 （2）白盒测试与黑盒测

26、试n白盒测试：将软件看成透明的白盒，根据软件产品的内部工作过程，检查内部成分，以确认每种内部操作是否符合设计规格要求。n方法有：逻辑覆盖、基本路径测试n黑盒测试：对软件已经实现的功能是否满足需求进行测试。n方法有：等价类划分法、边界值法、错误推测法、因果图法第第3章软件工程基础章软件工程基础3、软件测试的实施、软件测试的实施n单元测试：对软件设计的各模块测试。n集成测试：把模块组装起来同时进行测试。n确认测试：检查软件产品的功能和性能是否符合需求定义n系统测试：在实际运行环境下对整个系统进行测试第第3章软件工程基础章软件工程基础五、程序调试五、程序调试 n 任务任务任务是诊断和改正程序中的错误

27、任务是诊断和改正程序中的错误n 软件调试方法软件调试方法 1 1、强行排错法、强行排错法2 2、回溯法、回溯法3 3、原因排除法、原因排除法（演绎、归纳、二分法（演绎、归纳、二分法) )第第4章数据库设计基础章数据库设计基础（一）数据库系统的基本概念（一）数据库系统的基本概念 1 1、几个术语、几个术语n 数据库(DB：DataBase):有结构的数据集合n 数据库管理系统(DBMS：DataBase Management System)n 数据库管理员(DBA： DataBase Administrator)n 数据库系统（DBS: DataBase System）nDB+DBMS+DBA+

28、计算机（硬件、软件）n 数据库应用系统（DBAS: DataBase Application System）第第4章数据库设计基础章数据库设计基础2 2、 数据库系统的基本特点：数据库系统的基本特点：n数据的高共享性与低冗余性；n数据独立性（数据与程序间的互不依赖性）n数据的物理独立性n数据物理结构改变的改变不影响应用程序n数据的逻辑独立性n数据逻辑结构改变的改变不影响应用程序第第4章数据库设计基础章数据库设计基础3 3、数据库系统的内部结构体系数据库系统的内部结构体系( (三级模式三级模式) )n 概念概念模式：模式：它反映了设计者的数据全局逻辑结构它反映了设计者的数据全局逻辑结构n 外外模

29、式：模式：它反映了用户部分数据的逻辑结构。它反映了用户部分数据的逻辑结构。n 内内模式：模式：反映了数据在计算机中的实际存储形式（物理存储反映了数据在计算机中的实际存储形式（物理存储结构与物理存取方法）。结构与物理存取方法）。第第4章数据库设计基础章数据库设计基础（二）数据模型（二）数据模型 数据库设计的核心1 1、数据模型的基本概念、数据模型的基本概念n定义：数据模型是数据特征的抽象n数据模型分类：n概念模型n逻辑数据模型（数据模型）n层次、网状、关系n物理模型2、概念模型表示工具：、概念模型表示工具：E-R模型（实体联系模型）模型（实体联系模型）E-RE-R图的一个实例图的一个实例: :学

30、生课程联系学生课程联系的概念模型的概念模型mnn实体：用矩形框表示；n属性：用椭圆表示n联系：用菱形框表示n一对一（1：1）n一对多（1：M或M：1）n多对多（M：N）3 3、关系模型（具有坚实的理论基础）、关系模型（具有坚实的理论基础）n关系的数据结构：关系的数据结构：n采用二维表来表示采用二维表来表示，每一个二维表称为一个每一个二维表称为一个关系关系。学 号姓 名年 龄性 别系 名年 级2005004王小明王小明19女女社会学社会学20052005006黄大鹏20男商品学20052005008张文斌18女法律2005第第4章数据库设计基础章数据库设计基础第第4章数据库设计基础章数据库设计基

31、础职工号姓名职 称工 资扣 除实 发基 本津 贴职务房 租水 电86051陈 平讲 师13051200501601122283此表是否是关系表？为什么？此表是否是关系表？为什么？第第4章数据库设计基础章数据库设计基础n基本概念：基本概念：n键或码n候选键或候选码n主键或主码n外键或外码、n全码或全键学 号姓 名年 龄性 别系 名年 级2005004王小明王小明19女女社会学社会学20052005006黄大鹏20男商品学20052005008张文斌18女法律2005第第4章数据库设计基础章数据库设计基础n关系中的数据约束：关系中的数据约束：n实体完整性约束n参照完整性约束n用户定义的完整性约束。

32、学生（学生（学号学号，姓名，性别，专业号，年龄），姓名，性别，专业号，年龄）专业（专业（专业号专业号，专业名），专业名）完整性实例完整性实例第第4章数据库设计基础章数据库设计基础（三）关系代数（三）关系代数 n关系代数的基本运算关系代数的基本运算并、差、交、投影运算 选择运算、笛卡儿积运算、除、连接1、并（、并（Union）ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1a1b2c2a1b3c2a2b2c1ABCa1b2c2a1b3c2a2b2c1RSRS （1）两个关系列个数必须一致（2）并运算结果：列个数列名不变；记录为两个表中的记录之和并去掉重复的2. 差差(续续)ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1ABCa1b2c2a1b3c2a2b2c1RSR-S （1）两个关系列数必须一致（2）差运算结果：列数列名不变；记录为属于关系R而不属于S的记录。3. 交交 (续续)ABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1RSR S （1）两个关系列数必须一致（2）交运算结果：列数列名不变；记录为两个表中所共有的记录。4、投影、投影:A(R) ABa11a12a23（1）投影运算结果： 列数是原