计算机软件基础知识概要
否则,不能称为线性结构。 学 生 成 绩 表
学号 9861109 9861107 9861103 姓名 张卓 刘忠赏 胡孝臣 成绩 100 95 86
树形结构
树形结构
非线性 结构
全校学生档案管理的树形结构的组织方式
树形结构
A
D
B C E F G H
A B C E D F H
树形结构 —结点间具有分层次的连接关系
٭2.算法的控制结构
▪ 算法中各操作之间的执行顺序 ▪ 描述算法的工具通常有传统流程图、N-S结构化流 程图、算法描述语言等 ▪ 算法可以用顺序、选择、循环三种基本机构组合 而成。
算法基本设计方法
(1)列举法:根据问题,列举所有可能的情况,并用问题 中给定的条件检验哪些是需要的,哪些是不需要的。 (2)归纳法:通过列举少量的特殊情况,经过分析,最后 找出一般的关系。 (3)递推:是指从已知的初始条件出发,逐次推出所要求 的各中间结果和最后结果。 (4)递归:将问题逐层分解的过程。 (5)减半递推技术: “减半”,是指将问题规模减半, 而问题性质不变; “递推”,是指重复“减半”过程。 (6)回溯法:分析问题,找出一个解决总线索,然后沿着 这个线索逐步试探。
٭基本特性
▪ ▪ ▪ ▪ 可行性:根据实际问题设计的算法,执行得到满意结果 确定性:每一步骤必须有明确定义,不允许有多义性。 有穷性:算法必须能在有限的时间内做完。 输入和输出:拥有足够的情报,方可执行。
算法的基本要素
٭1.对数据对象的运算和操作
▪ ▪ ▪ ▪ 算术运算:+、-、×、÷等 逻辑运算:>、<、=、>=、<=、!=等 关系运算:and、or、not等 数据传输:w、r等
1
计算机软件基础知识
软件基础
算法
算法的基本概念
٭算法:是一组有穷指令集,是解题方案的准确而完 整的描述。通俗地说,算法就是计算机解题的过程。 算法不等于程序,也不等于计算方法,程序的编制 不可能优于算法的设计。 ٭算法的基本特征:是一组严谨地定义运算顺序的规则,每
一个规则都是有效的,是明确的,此顺序将在有限的次数下终 止。算法不等于程序,程序不可能优于算法。
数据结构基本概念
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
对数据结构中的节点进行操作处理 (插入、删除、修改、查找、排序)
数据结构研究的主要内容
数据结构主要研究以下三个方面的问题: ٭数据的逻辑结构:数据集合中各元素的信息,及元 素之间所固有的逻辑关系(前后件关系)
٭数据的存储结构:各数据元素在计算机中的存储关 系
图形结构
图形结构:节点间的连接任意
1
4
D={ 1 , 2 , 3 , 4}
R={(1,2) , (1,3) , (1,4) , (2,3) 2
1 D={ 1 , 2 , 3 } R={ (1,2) , (2,3) , (3,2) , (1,3) } 2 3 有向图
3
(3,4) , (2,4) } 无向图
顺序存储与链式存储
顺序存储
٭
存储地址 存储内容 Lo Lo+m
元素1 元素2 ……..
常用于线性数据结构, 将逻辑上相邻的数据元 素存储在物理上相邻的 存储单元里。
三个弱点
插入或删除操作时,需 移动大量元数。 ٭长度变化较大时,需按 最大空间分配。 ٭表的容量难以扩充
٭
Lo+(i-1)*m
算法效率度量——算法的复杂度
算法的复杂度:时间复杂度、空间复杂度
٭算法的时间复杂度
▪ 算法时间复杂度是指执行算法所需要的计算工作量。 ▪ 工作量用算法所执行的基本运算次数来度量,而算法所执 行的基本运算次数是问题规模的函数,即 算法的工作量=f(n)
٭算法空间复杂度
▪ 算法空间复杂度是指执行这个算法所需要的内存空间。 ▪ 存储空间包括:①算法程序所占的空间、 ②输入数据所 占的空间、③算法执行过程中所需要的额外空间
元素i
……..
Lo+(n-1)*m 元素n Loc(a)=Lo+(i-1)*m
每个元 素所占 用的存 储单元 个数
顺序存储与链式存储
1345 元素1 1400
head
元素2 1536 元素3 1346 元素4
∧
存储地址
1345 1346
存储内容
图形结构
2、数据的存储结构
A 顺序存储
B 链式存储
3、数据的运算:检索、排序、插入、删除、修改等。
线性结构和非线性结构
线性结构条件
(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 (3)首节点无前件,尾节点无后件。
非线性结构:不满足线性结构条件的数据结构 注意:在一个线性结构中插入或删除任何一个节点后还应是线性结构;
数据结构基本概念
数据结构是一门研究数据组织、存储和运 算的一般方法的学科。
整数(1,2) 能输入到计算机中 、实数(1.1,1.2) 并能被计算机程序处理的 字符串(Beijing)、 符号的集合。 图形、声音。
数据结构基本概念
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
计算机管理图书问题 图书馆里有各种卡片:有按书名编排的、有按作 者编排的、有按分类编排。 如何将查询图书的这些信息存入计算机中既要考 虑查询时间短,又要考虑节省空间
数据结构基本概念
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
最简单的办法之一是建立一张表,每一本书的信 息在表中占一行,如
数据结构基本概念
数据元素在 计算机中的表示
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的? 目的不同,最佳的存储方方法就不同。 从大到小排列:9,8,7,6,5,4,3,2,1,0 输出偶数:0,2,4,6,8,1,3,5,7,9
٭对各种数据结构进行的运算
主要目的是为了提高数据的效率。所谓提高数据处理的效
率,主要包括两个方面:一是提高数据处理的速度,二是尽量节省在 数据处理过程中所占用的计算机存储空间。
数据结构类型
线性表 A.线性结构 栈 队 B.非线性结构
1.数据的逻辑结构
数 据 结 构 的 三 个 方 面
树形结构