文档介绍：公共基础知识部分
公共基础知识部分
算法与数据结构
1
程序设计基础
2
软件工程
3
第一章数据结构与算法
算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作;
一个算法还具有下列五个重要特性:有穷性、确定性、可行性、输入、输出。
考点1 算法
算法的基本要素:①算法中对数据的运算和操作;②算法的控制结构
算法的复杂度:①时间复杂度;②空间复杂度。
考点2 数据结构
定义一、数据元素集合(也可称数据对象)中各元素的关系。
定义二、相互之间存在特定关系的数据元素的集合。
数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
考点2 数据结构
数据结构的三个基本层次:
数据的逻辑结构、数据的存储结构(物理结构)、数据相关算法集合
逻辑结构
“数据结构”定义中的“关系”指数据元素间的逻辑关系,故也称数据结构为逻辑结构
存储结构
顺序存储结构
数据结构在计算机中的表示称为物理结构。又称存储结构。
链式存储结构
数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构。
:有始有终,前后连接(称为前趋和后继)
:一个元素有多个前趋或后继
考点2 数据结构
数据结构
数据的存储方法(物理结构),分为四类:
(主要用于线性表或者数组)
:采用指针方式
(需要建立单独的索引文件, 索引一般形式:关键字、地址)
(根据元素的关键字通过事先编制好的散列函数直接给出该单元存储地址)
数据
下个地址
数据结构
线性表的基本操作及存储结构
线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。
线性表的顺序存储是指在内存中用一组地址连续的存储单元依次存储线性表的各数据元素。
特点是:线性表中所有元素所占的存储空间是连续的;线性表中各元素在存储空间中是按逻辑顺序依次存放的。
数据结构
线性表的基本操作:
存取
插入
删除
合并
分拆
查找
复制
排序
求线性表的长度