计算机软件基础-数据结构与算法_计算机数据结构与算法

第二章 数据结构和算法

基本概念

数据结构研究的内容

数据结构三个组成部分

逻辑关系
我们不关心数据在磁盘怎么放，只关心各数据本身之间的关系。

存储结构
数据在计算机中的物理存储。

因为顺序存储时在内存或磁盘中分配的位置是连续，所以再装进去一个元素就需要新建一个更大的，把上一个拿出来放进这个更大的。所以说顺序存储在新增时没有链式的效率快。但是顺序存储查找时快。

数据运算

线性表的逻辑结构

线性表（逻辑结构）的存储结构分为顺序表和链表
每种逻辑结构都有这两种存储结构，链式也可以有顺序

—以下是线性表的存储（物理）结构----

顺序表

优势就是，每个元素在存储地址时是紧挨着的。如果知道a元素的地址想查找下一个，那么直接拿a地址的下一个地址的值即可。
数组就是顺序表实现的 顺序表的缺点就是如果在中间插入一个元素那么后面的所有元素都需要往后面移动一位。删除的话后面的元素也需要向前移动

链表

线性链表也叫链表，存储结构是不连续的。
链表有一个头，里面的数据域是空的

如果删除链表中的b，那么只需要把a的指针域指向c（也就是存c的地址）


双链表
和单向链表的区别是它有两个指针域。一个指向上一个元素的地址，另一个指向下一个元素地址。
优点：在遍历时如果遍历到a2时后想要往前遍历a1可以实现。如果使用单向链表那么需要重新再遍历一次才能找到a1.

循环链表
这个图有点不对，最后一个元素应该指向a0的地址

栈

读取信息时只能在栈顶读取信息。
是一种操作受限的线性数据结构，因为它只能在一端插入和删除元素
1
2

类似弹夹的结构
栈也可采取顺序存储和链式存储的结构，栈底是第一个元素也是从0开始的位置


top始终指向栈顶的元素

只能看栈顶的元素，下面元素的操作不了

栈的应用 栈里面存的是临时变量
如果在main方法中给fac方法传5，那么在fac中n是5，当准备再次调用fac时，就会把5放到系统的栈里面保存。当算到1时需要复制给m时，就会把栈中的2拿出来乘以1算出结果再乘以栈中拿出来的3，一直到5。
当然像int n = 0 这种变量也会放到栈中保存以便于使用。

队列

删除数据只能在队头也就出队。插入元素时只能放到队尾，不能在其他位置插入。
1

队尾指针指向的是尾元素的下一快区域，所以它指向的永远是空元素。也就是初始化队列时为什么队尾指针指向第一个元素。
并且队列的指针是变化的，它不是固定指向一个位置

该队列一共有6个元素。如下图(3)，a1a2出队了那么队头指向的是a3的位置，a4a5a6入队了，
那么再进来一个元素时就会放到0的位置。因为队列操作是通过循环的方式，当0到5的位置都占满后，
再放进去元素会从第一个位置放置
1
2
3
4
5
6

以下是队列存储的方式为顺序存储结构时的理解

注意看队头和队尾的指针在图中指向的位置

当空队列和满队列队头和队尾指向一个区域
1

字符串

采用链式存储结构是上图中的形式 cher *s = “Hello”，采用链式的好处就是当给Hello继续增加串时，可以通过链式存储连接起来。因为定义字符数组初始化时长度是固定，链式存储是最方便的，也就是通过数据域和指针域连接。如变成"quxingtao Hello"。
结构如下


不可变的串是通过顺序存储方式也就是数组类的形式。而可变的串是通过链表实现的，可实现添加修改删除。

数组和矩阵

这是一个二维数组的存储方式，存储时会有行和列，一般语言是行优先。数组是每个元素是不能分开存储的。
也就是先按行存然后再连着下一行继续存。
如果把这个线展开那么就是一个一维数组了。
1
2
3

矩阵

树

根节点只有后继节点，没有前驱节点。
子树的根节点有且只有一个前驱，可有多个或没有后继节点

适合用于层次关系的描述
节点：包含数据和指向其分支节点的信息
叶子节点：就是没有后继指向的节点，度为0.
1
2
3
4
5
6

不是直接相连的两个节点是子孙和祖先的关系。

度

树的存储
顺序存储。
利用数组的方式，比如A是数组中0的位置 他的双亲(parent)是-1，-1就代表它是根节点。BCD的位置是数组中的123，它们的双亲是数组中0的位置也就是A。

链式存储方式是常用的
孩子存储结构属于链式存储，根节点A有三个孩子，那么它有三个指针域指向三个孩子的位置，^代表是空的指针。

二叉树

二叉树：要求每个节点的孩子（后继）最多有两个，而且两个孩子分左和右
满二叉树：是所有节点都有两个左右孩子节点，并且所有的叶子节点都在最底层。
完全二叉树：在满二叉树的基础上，去掉一些叶子节点，但是只能从最右侧拽掉
1
2
3

最常用是完全二叉树

看上图节点中编号，是在满二叉树中从大编号开始去掉就也就是在最后一层的右侧去掉节点，去掉15，14，13，12。
1

遍历

先序遍历，就是先遍历根节点然后遍历左节点再遍历右
1

哈夫曼树

哈夫曼树：又被称作最优二叉树，也就是权值最优。
描述的是节点间组成的一条路径，保证前面节点是后面节点的双亲，也就是一条线沿下去的。
路径长度：两点指点的边数有几个。
带权路径长度：就是树中节点赋予一个值，叫做权，并且用权乘以树的根节点
到某个节点之间的长度表示带权路径长度。

树的带权路径长度：为树中所有叶子结点的带权路径长度之和
1
2
3
4
5
6
7

不同的结构，


步骤：拿出权值最小的两个节点作为左、右子树，构造一个树a。a树的根节点的权就是两个节点的权值之和。23467中，23拿出来构造5。这时23已经用了变成5，那么用5467继续按这种方式构造，最后构成的树连起来

如发电报，通过哈夫曼树设计编码
如下图右侧的树。每一个叶子节点代表一个字母，从根节点走到字母组成的数组就是编码

图的定义

图是由顶点和边的集合组成。
1

无向图：没有方向的边
有向图：有方向的边，有向图中边也叫做弧。比如a到b有边，那么b到a不一定有边
1
2

完全图、入度、出度
入度就是这个点指向它的边有几条，出度反之。
1
2

弧：有向边的另种叫法
路径：顶点到另个顶点经过的所有点
路径长度：就是路径之间边的个数
1
2
3

连通、强连通、网
1

图的存储

邻接矩阵存储：
图是由顶点和边组成的，就可以用矩阵存储。比如有100个点那么生成的图就是100*100这个大，
如果某两个顶点有边就表示1否则就表示0。
1
2
3

邻接表存储：
采用链表结构
1
2

图的遍历

深度遍历 相当于查地下党。
1

从任个顶点a开始遍历，找跟顶点相邻的所有点，有三个bcd。然后再随机找到b先遍历,再把b点相邻的所有点都找到c。再遍历c,把c相邻的所有点都找到，
一条道查到底之后，再往回返上一次c相邻其他没遍历的点都遍历，再返回b相邻的塔里没遍历的点，继续遍历，最后看是不是都查完。	

比如先从v1开始遍历，再从v2开始。输出的结构是v1 v2 v5 v6 v4 v3
1
2
3
4

程序也可能这样遍历

广度遍历 随机遍历一个点，然后把与它关联的点都放到队列里面去处理，给队列去遍历。每个点都是这样就能全部遍历了。
1

图的应用

干一件事时分成三部，三部由三个人做，但是第二部不许要第一步完成后才能继续进行，第三步不受影响就可以做，
那么这个事做多长时间。
1
2

顺序查找

静态查找：就是查找表的数据不变化。

动态查找：查找表同时，再随之增加或删除。当查询一个数据k，如果查到了就不进行别的操作，
如果没查到就会把k的值存下来

适用于数据量不是太多的情况
1
2
3
4
5
6

折半查找（二分查找）

前提：数据有序，适用于顺序存储的查找。  最大的缺点：存储的数据不适合频繁修改。只使用于不变的数据结构，
如历史数据
1
2

下面代码需要注意：取中间位置数k时，如果总数是奇数那么取k就一个数。如果总数是偶数那么取k是两个数，
但是这个类型用的是int，所以总数是偶数时取k会拿两个中间数前面那个(5 / 2 = 2)。取到k时会先比较是不是需要
找的数，如果不是再继续比较大于还是小于时就不需要在包括k了。
1
2
3

一千个数查找只需要10次，一百万个数查找只需要20次，十个亿多的数查找，只需要30次。
1

分块查找

要求：分块有序

需要有索引，也就是每个块中的最大值
1
2
3

每个块之间是有顺的但是块内的数之间是无序的，如何做到按块有序？保证后一个块中的任意一个数都
比前一个块的最大数要大。
每块的最大数也就是索引
这样我们就可以先用二分查找定位到块后，在通过顺序查找取块内的元素，
也就是索引必须用的顺序存储，那么块内（也就是存储的数据）可以用链式存储也可以用顺序
1
2
3
4
5

插入数据时，块内是可以有空区域可以直接插入块内即可。弥补了二分查找。
1

二叉排序树查找

上面三种查找都是用静态数据查找。
通过树的结构实现查找，适用于动态查找，如查找时可以实现动态的往结构插入或删除数据。
1
2

实现二叉排序树的条件
左树所有节点要小于根节点，右树则大于根节点，并且左右子树也为二叉树
1
2

查找的方式类似于二分查找
如果这个树的左右子树分布平均，那么他的查询效率是和二分查找是一样的。但是一般左右都是不平均的，所以
出现了平衡树和B树，以保证从根节点开始左右子树分布差不多。
1
2
3

一个数如果查询不到，就可以直接插入到结构里。

二叉排序树的构造过程

哈希表查找

每个数据元素通过算法算出来关键字（也就是Map中的key,键），这样查找时直接通过关键字就可定位数据元素位置

适合少量数据的查找
1
2
3

在用哈希表时不应该有键是重复的。
哈希表中的冲突是极少的，如果有冲突，那么一个键对应的地址中有多个数据元素（地址中的多个元素以链表方式存储），
在通过键找到地址后还需要再比较。
1
2
3

选择排序

我们排序是这样的，已经排过序的应该划掉
1

计算机排序是不能浪费额外的空间，所以通过交换位置
最后一个数不需要排序，他就是最大的
1
2

k用于记录“小数”的位置，用于”小数“和”大数“之间位置互换。
1

冒泡排序

每两个数进行比较，小的放前面大的放后面。这样比到头之后最大数就会在尾的位置。
1

如果发现这次排序没有位置发生变化就停止，如下图最多排序6次，最好一次。
并且第一次排序比6个位置也就是冒泡5次，第二次比5个位置冒泡4次，依次递减。
1
2

有的时候比这个时间复杂度要低
1

插入排序

一个数就认为是有序的。第一次两个位置的数开始排序，小的数插入到前面，大的数往后移动。第二次前三个位置排序，第三次前4个数排序……
1

R[0]的含义是：一般是数组的第一个位置当作临时存储空间，小数往前插入时用于装载这个数值，不用于存放数值只装临时插入的数。
1

二层for循环中，比如是3，需要和前面的数进行比较如果3是小的，那么前面的数往后移动

快速排序

引用广泛

比k小的数都放到k的左侧，大的放右侧，分为了两部分。再分别把每部分小的放到K2左侧大的放右侧。
1

三条语句分别含义：找到中间位置，10的位置。调用左侧的快速排序，调用右侧的快速排序。
1

如何找到中间位置的函数：左右侧分别两个指针，拿到第一个位置的元素k，从左边这个数找如果小于k那么这个数位置	
k时不动，当这个数大于k时左指针指向这个数然后变成从右侧开始找，如果这个数大于k那么不动，如果小于k那么右
指针指向这个数并且和左指针指向的数互换位置，交换后再继续往中间找
1
2
3

数据库技术

数据模型

规范化理论

设计不合理有以下问题

三范式：
1、数据不可再拆分
2、非主键必须完全依赖于主键
3、非主键不能传递的依赖于主键
1
2
3
4

依赖的意思是如果学号（主键）确定了那么对应的姓名也是确定的，那么姓名依赖于学号，也就是平凡依赖。
如果两个字段没有交际产生依赖就是非平凡依赖。

外键就是在本表中不是主键，但是是其他表中的主键。
1
2
3
4

如下午中图中的学院不符合第一范式，因为它可以再分。也就是我们使用一个字段时只能使用这个字段的含义不能使用字段的其中一部分。
1

第二范式，非主键的字段完全依赖于主键就满足第二范式。
如下图中学号和课程号两个字段中，每个字段都可以对应多个另一个字段。如果学号和课程号都是主键那么姓名就
部份依赖于学号，只能分开两个表。
1
2
3

非主键a字段依赖于非主键b，但是b依赖于主键c，那么就产生传递依赖。就是不满足三范式。它应该依赖于主键
如下图中，分割成两个表后满足了第二范式。但是左表不满足第三范式，左表中的宿舍字段依赖于班级字段，
把左表中的班级和宿舍再分成一张表那么就符合第三范式了。

如果三张表拆开后没有联系了，那么就需要一张表的一个字段在其他表中也出现。
1
2
3
4
5

SQL语言概述

需求分析和概念结构设计

多对多关系：。
1

1、

图书表a和借书人表b是多对多，那么通过借书表当作关联表，借书表中的主键由a和b主键的组合而成，并且借书表也有				
它独自的属性。
1
2

2、

一对多关系：第二种常用
1

物理结构设计与实现阶段

安全性和完整性

并发控制和事务处理

脏读就是你读的数据是5，但是已经被别人改了，那么就叫做脏读。
1

排它锁：如果你要改数据那么就不允许别人读出来，解决这样的锁就叫做排它锁。
1

数据库备份与恢复

软件工程概述

软件的概念

软件的分类



软件的特点，软件的性质


软件的发展




软件危机

软件工程定义



软件工程三要素

软件工程基本目标

软件工程的原则

软件工程模式

开发方法

传统软件工程模式


现代软件工程模式

现代软件工程模式基本要点

现代软件工程模式主要任务之系统分析

现代软件工程模式主要任务之系统设计

现代软件工程模式主要任务之系统测试

现代软件工程模式主要任务之软件组件

现代软件工程模式主要任务之人员的组织管理

软件的生存周期

1计划阶段

2需求分析阶段

3设计阶段

4编码阶段

测试阶段

维护阶段

开发模型

软件开发模型的定义

经典开发模型

瀑布模型


增量模型或渐增模型


原型模型

螺旋模型

构建组装模型

RUP模型



XP模型，也叫极限编程

开发模型选择

传统软件开发方法概述

传统软件开发方法–结构化开发方法的核心

软件开发方法的组成

结构化开发方法的优点

1、软件项目计划

软件项目计划阶段步骤

软件项目计划的可行性研究



软件项目计划的可行性研究步骤

2、需求分析

需求分析目的

需求分析重要性


需求分析困难性

需求分析的需求分类

需求分析的分析原则

需求分析的分析方法

需求分析的分析模型

3、系统设计

系统设计–设计流程

系统设计–设计目标


系统设计–设计原则

系统设计–设计模型


系统设计–设计方法

系统设计–设计过程


系统设计–总体设计


系统设计–详细设计



系统设计–用户界面设计

4、编码

程序设计语言的特点






编码风格

编码原则

5、测试

测试用例



调试策略

测试原则

测试分类

测试方法

6、维护

维护的类型


软件可维护性



维护的困难

面向对象开发方法概述

传统软件开发方法存在问题







uml

OO技术



oo技术的基本原理




面向对象方法的组成





分析与设计


面向对象的优点



实体对象与对象


对象的三个特征

对象的特点



服务和消息








类

ooa的特点

OO方法的特点

面向对象分析OOA

面向对象设计OOD