文档介绍：公共基础知识—— 基本数据结构与算法
ESS—数据库基础知识
本章的重要性
经统计本章在理论考试中占10%左右即4个左右的选择题。
本章在考试中只涉及笔试题目,上机不考。
ESS—数据访问页
关键考点
顺序存储与链式存储的基本概念
栈、队列的基本概念与基本操作
循环队列元素个数的计算
算法时间、空间复杂度的概念
几种查找与排序的比较次数
二叉树的遍历
二叉树结点个数的计算
基本数据结构与算法
算法
算法的基本概念
算法:解题方案的准确而完整的描述。
算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。算法不等于程序,程序不可能优于算法。
基本特性(P1)
可行性:根据实际问题设计的算法,执行得到满意结果
确定性:每一步骤必须有明确定义,不允许有多义性。
有穷性:算法必须能在有限的时间内做完。
拥有足够的情报:输入和输出,方可执行。
基本数据结构与算法
算法
算法的复杂度:时间复杂度、空间复杂度
算法的时间复杂度
算法时间复杂度是指执行算法所需要的计算工作量。
工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即
算法的工作量=f(n)
算法空间复杂度
算法空间复杂度是指执行这个算法所需要的内存空间。
存储空间包括:①算法程序所占的空间、②输入数据所占的空间、③算法执行过程中所需要的额外空间。。
基本数据结构与算法
数据结构主要研究以下三个方面的问题
数据的逻辑结构:数据集合中各元素的信息,及元素之间所固有的逻辑关系(前后件关系)
数据的存储结构:各数据元素在计算机中的存储关系
对各种数据结构进行的运算
主要目的是为了提高数据的效率。所谓提高数据处理的效率,主要包括两个方面:一是提高数据处理的速度,二是尽量节省在数据处理过程中所占用的计算机存储空间。
数据结构研究的主要内容
基本数据结构与算法
数据元素(Data Element)
数据元素是数据的基本单位,即数据集合中的个体。
有时一个数据元素可由若干数据项(Data Item)组成。数据项是数据的最小单位。
数据元素亦称节点或记录。
数据结构的基本概念
基本数据结构与算法
2、数据的存储结构
3、数据的运算:检索、排序、插入、删除、修改等。
A 顺序存储
B 链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面
数据结构类型
基本数据结构与算法
线性结构和非线性结构
线性结构条件
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。
(3)首节点无前件,尾节点无后件。
非线性结构:不满足线性结构条件的数据结构
注意:在一个线性结构中插入或删除任何一个节点后还应是线性结构;否则,不能称为线性结构。
学生成绩表
86
胡孝臣
9861103
95
刘忠赏
9861107
100
张卓
9861109
成绩
姓名
学号
基本数据结构与算法
线性结构和非线性结构
全校学生档案管理的树形结构的组织方式
非线性结构
树形结构