第一章  数据结构与算法
第一节  算法
一、算法的基本概念
所谓算法是指解题方案的准确而完整的描述。
1、算法的基本特征:(1)可行性(2)确定性(3)有穷性(4)拥有足够的情报
2、算法的基本要素
(1)算法中对数据的运算和操作
算术运算，逻辑运算，关系运算，数据传输
(2)算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。一个算法可以用顺序、选择、循环三种基本控制结构组合而成。
2、算法设计的基本方法
(1)列举法(2)归纳法(3)递推(4)递归(5)减半递推技术
二、算法复杂度
1、算法的时间复杂度：指执行算法所需要的计算工作量。用算法在执行过程中所需基本运算的次数来衡量算法的工作量。
方法：平均性态，最坏情况复杂性
2、算法的空间复杂度：指执行这个算法所需的内存空间。
第二节  数据结构的基本概念
一、什么是数据结构
数据结构是指相互有关联的数据元素的集合。
如：(1)春、夏、秋、冬  (2)父亲、儿子、女儿
(1)数据元素有共同的特征
(2)各个元素之间存在着某种关系(联系)。用前后件关系来描述。如：夏是秋的前件，秋是夏的后件。父亲是儿子和女儿的前件，儿子和女儿都是父亲的后件
1、数据的逻辑结构
数据结构是指带有结构的数据元素的集合。一个数据结构应包含以下两方面的信息：
(1)表示数据元素的信息
(2)表示各数据元素之间的前后件关系，前后件关系是逻辑关系，与它们在计算机中的存储位置无关。
数据的逻辑结构反映数据元素之间的逻辑关系。
2、数据的存储结构
数据的逻辑结构在计算机中的存放形式称为数据的存储
结构，也称数据的物理结构。
采用不同的存储结构，数据处理的效率不同。
一般情况下，数据的逻辑结构和存储结构是不同的。
二、数据结构的图形表示
每一个数据元素用中间标有元素值的方框表示，称为数据结点，简称结点。用一条有向线段从前件结点指向后件结点。
在数据结构中，没有前件的结点称为
根结点，没有后件的结点称为终端结
点(也称为叶子结点)。其他结点一
般称为内部结点。
插入与删除是对数据结构的两种基本运算
还有查、分类、合并、分解、复制和修改等运算
三、线性结构与非线性结构
根据各数据元素之间前后件关系，将数据结构分为：
线性结构与非线性结构
线性结构满足以下两个条件：
(1)有且只有一个根结点
(2)每一个结点最多只有一个前件，也最多有一个后件
线性结构又称为线性表。
第三节  线性表及其顺序存储结构
一、线性表的基本概念
线性表是由n个数据元素a1，a2,…an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。
特征：(1)有且只有一个根结点a1 ，它无前件。
      (2)有且只有一个终端结点an ，它无后件。
      (3)其它结点有且只有一个前件和一个后件。
线性表中结点的个数n称为线性表的长度，n为0称为空表
二、线性表的顺序存储结构
线性表的顺序存储结构具有以下特点
(1)线性表中所有元素所占的存储空间是连续的。
(2)线性表各数据元素在存储空间中是按逻辑顺序依次存放的。
三、线性表的插入运算
要在第i个元素前插入一个新元素，要从最后一个元素开始，直到第n-i+1个元素依次向后移动一个位置,第i个位置就被空出，然后将新元素插入到第i项。
四、线性表的删除运算
要删除第i个元素，要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。
第四节  栈和队列
一、栈及其基本运算
栈是一种特殊的线性表。一端是封闭的，不允许进行插入与删除，另一端是开口的，允许进行插入与删除。如：子弹夹
栈中的元素遵循“先进后出”或“后进先出”的原则
二、队列及其基本运算
队列是指允许在一端进行插入，而在另一端进行删除的线性表。
允许插入的一端称为队尾，允许删除的一端称为排头(也称为队头)。      遵循“先进先出”或“后进后出”的原则，体现了“先来先服务”的原则
第五节  线性链表
一、线性表的缺点
(1)插入与删除的效率低
(2)线性表的存储空间不便于扩充
(3)不便于对存储空间的动态分配
二、线性链表的概念
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域。另一部分用于存放指针，称为指针域。
二、线性链表的概念
线性表的链式存储结构称为线性链表。
在线性链表中，各数据元素之间的前后件关系由各结点的指针域来表，指向第一个结点的指针HEAD称为头指针。
第六节  树与二叉树
一、树的基本概念
树是一种简单的非线性结构，所有元素之间的关系具有明显的层次特征。
1、树的基本术语
(1)每一个结点只有一个前件，称为该结点的父结点
(2)没有前件的结点只有一个，称为根结点
(3)每一个结点可以有多个后件，称为该结点的子结点
(4)没有后件的结点称为叶子结点
(5)每一个结点所拥有的后件个数称为该结点的度，叶子结点的度为0
(6)所有结点中的最大的度称为树的度
(7)树的最大层次称为树的深度
(8)在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。
二、二叉树及其基本性质
1、什么是二叉树
(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树，称为左子树与右子树即每一个结点的度最大为2
2、二叉树的基本性质
(1)在第k层上，最多有2k-1(k≥1)个结点
(2)深度为m的二叉树最多有2m-1个结点
(3)度为0的结点(即叶子结点)比度为2的结点多1个
(4)具有n个结点的二叉树，其深度至少为[log2n]+1
其中[log2n]表示的log2n整数部分。
3、满二叉树与完全二叉树
(1)满二叉树指，除最后一层外，每一层上的所有结点都有两个子结点。即每一层上的结点数均达到最大值。
    满二叉树的第k层上有有2k-1个结点
    深度为m的满二叉树有2m-1个结点
二叉树的基本性质
(2)完全二叉树指，除最后一层外，每一层上的结点数均达到最大值。在最后一层上只缺少右边的若干结点。
满二叉树是完全二叉树，但完全二叉树一般不是满二叉树
三、二叉树的遍历(递归方法)
(1)前序遍历(2)中序遍历(3)后序遍历
第七节  查技术
查是指在一个给的数据结构中查某个指定的元素。
1、顺序查
顺序查一般是指在线性表中查指定的元素。
过程：从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等则表示到(查成功)。若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示没有到要的元素(查失败)。
2、二分法查
二分法查只适用于顺序存储的有序表。
方法：设有序线性表的长度为n，被查元素为x
(1)将x与线性表的中间项进行比较；
(2)做中间项等于x，则说明查到，查结束；
(3)若x小于中间项，则线性表的前半部分以相同的方法继续进行查。  (4)若x大于中间项，则线性表的后半部分以相同的方法继续进行查。
第八节  排序技术
一、交换类排序法
1、冒泡排序法2、快速排序法
二、插入类排序法
1、简单插入排序法2、希尔排序法
三、选择类排序法
思想：扫描整个线性表，从中选中最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法。
1、简单选择排序法2、堆排序法
以上各种查方法中的一种的运算次数最大为n(n-1)/2次
第二章  程序设计基础
第一节  程序设计方法与风格
一、程序设计方法
(1)结构化程序设计方法(2)面向对象程序设计方法
二、程序设计风格
指编写程序时所表现出的特点、习惯和逻辑思路。程序设计的风格总体而言应该强调简单和
清晰，程序必须是可以理解的。
即：清晰第一、效率第二
第二节  结构化程序设计
一、结构化程序设计的原则
(1)自顶向下(2)逐步求精(3)模块化(4)限制使用goto语句
二、结构化程序设计的基本结构与特点
(1)顺序结构(2)选择结构(3)循环结构
第三节  面向对象程序设计
一、对象
是系统中用来描述客观事物的一个实体，它由一组表示
静态特征的属性和它可执行的一组操作组成。
如：一辆汽车是一个对象，它包含了汽车的属性(颜
，型号)及其操作(启动，刹车)。
一个窗口是一个对象，它包含了窗口的属性(大小，颜
，位置)及其操作(打开，关系)
特点：(1)分类性(2)多态性(3)封装性(4)模块独立性好
二、类和实例:类是具有共同属性、共同方法的对象的集合。类是对象的抽象，而一个对象则是其对应类的一个实例。
三、方法:对象所具有的操作。
四、继承:是使用已有的类定义作为基础建立新类的定义技术。
五、多态性:同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。
第三章  软件工程基础
第一节  软件工程基本概念
一、软件定义与软件特点
软件是包括程序、数据及相关文档的完整集合。
包括：(1)机器可执行的程序与数据。(2)机器不可执行的，与软件开发、运行、维护、使用等相关的文档。
特点：(1)软件是一种逻辑实体，不是物理实体，具有抽象性。
(2)软件的生产与硬件不同，没有明显的制作过程。一旦开发成功，可以大量拷贝。(3)软件在运行、使用期间不存在磨损与老化问题(4)软件的开发、运行对计算机系统有依赖性
(5)软件复杂性高，成本昂贵
二、软件危机与软件工程
软件危机是泛指在计算机软件的开发和维护过程中所遇
到的一系列严重问题。
软件工程的核心思想是把软件产品看作一个工程产品来
处理。以期达到工程项目的三个基本要素：进度、经费
和质量目标。
三、软件生命周期
将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。(1)可行性研究与计划制定(2)需求分析(3)软件设计(4)软件实现(5)软件测试(6)运行与维护
四、软件工程的目标
在给定成本、进度的前提下，
开发出具有有效性、可靠
性、可理解性、可维护性、
可适应性、可移植性和可互
操作性且满足用户需求的产品。
第二节  结构化分析方法
一、需求分析与需求分析方法
1、需求分析：指用户对目标软件
系统在功能、行为、性能、设计

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。