计算机软件技术基础课件.ppt

课程设置算法算法基本数据结构及其运算基本数据结构及其运算查找与排序技术查找与排序技术资源管理技术资源管理技术数据库技术数据库技术应用软件设计与开发技术应用软件设计与开发技术1学习目的1、了解软件技术基础知识2、掌握数据结构的概念，几种基本结构，查找和排序方法，能编写正确算法。编写简单程序。3、掌握资源管理技术的相关知识2学习与考核 教师讲授为主 上机实验：上机语言c语言 考核方式：平时成绩20%+上机实验、完成实验报告20%+期末考试成绩60%3绪论 计算机硬件及其发展 计算机软件 数据结构、操作系统、数据库与软件工程4计算机硬件及发展l l发展历史发展历史 电子管电子管 晶体管晶体管 集成电路集成电路 超大规模集超大规模集成电路成电路l l发展路线及规律发展路线及规律 速度慢速度慢 速度快速度快 体积大容量小体积大容量小 体积小容量大体积小容量大 外设少、简单外设少、简单 外设繁多、复杂外设繁多、复杂 二进制处理原则二进制处理原则 软件从短小、精干、讲究效率到复杂可靠、兼容性强、结构性好5计算机软件l l 软件的概念 软件的概念软件是：与一系统（尤指计算机系统）有关的程序、步骤和有关文件编制的完整集合。特指特定类型计算机所使用的程序的总称，连同与计算机或程序有关的资料，例如手册、图表和操作指令。功能：针对一个系统（计算机），合理组织工作。程序设计语言的发展 程序设计语言的发展l 经历：机器语言，汇编语言，高级语言，面向对象语言软件的发展：语言的发展-操作系统的出现-数据库的出现-网络的出现6数据结构、操作系统、数据库与软件工程l 数据结构：描述数据及数据元素之间的关系，数据在计算机系统中的存储方式及数据的运算。软件技术基础的基础 软件技术基础的基础l 操作系统：方便用户有效利用各种软、硬件资源的程序的集合 建造工作环境、平台 建造工作环境、平台l 数据库：可以共享相关数据，以一定组成方式的集合 进行数据信息处理的强大应用。进行数据信息处理的强大应用。l 软件工程：软件设计的基本过程，思想和方法。7第一章算法2023/5/16算法的基本概念算法设计的基本方法算法的复杂度分析 C语言简介8算法的基本概念算法的基本特征（1）能行性（2）确定性（3）有穷性（4）拥有足够的情报算法是指解题方案的准确而完整的描述。9算法与程序相同点相同点：都是解决问题的方法和步骤：都是解决问题的方法和步骤描述方法描述方法：程序使用程序设计语言：程序使用程序设计语言 算法使用框图或其他语言算法使用框图或其他语言联系联系：程序用某种程序设计语言来实现算法：程序用某种程序设计语言来实现算法 10怎样表示一个算法1、用自然语言表示算法2、用流程图表示算法3、用伪代码表示算法4、用机器语言表示算法1 1算法设计基本方法在数据结构中常见的问题在数据结构中常见的问题创建、插入、删除、更新、检索、排序创建、插入、删除、更新、检索、排序注意：每个问题都有一种和多种算法注意：每个问题都有一种和多种算法 找到效率最高的；找到效率最高的；以最容易理解的方式设计；以最容易理解的方式设计；设计的算法不容易出错或出错情况较少。设计的算法不容易出错或出错情况较少。12算法的基本要素(1)(1)对数据对象的运算和操作：对数据对象的运算和操作：a).算术运算，加、减、乘、除等运算；b).逻辑运算，“与”、“或”、“非”等运算；c).关系运算，“大于”、“小于”、“等于”、“不等于”等运算；d).数据传输，主要包括赋值、输入、输出等操作；(2)(2)算法的控制结构算法的控制结构 13算法设计基本方法l 列举法 基本思想：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的。l 特点：算法简单；工作量大14举例：举例：设每只母鸡值设每只母鸡值33元，每只公鸡值元，每只公鸡值22元，两只小元，两只小鸡值鸡值11元。现要用元。现要用100100元买元买100100只鸡，设计买鸡方案。只鸡，设计买鸡方案。方案一假设买母鸡i只，公鸡j只，小鸡k只。procedure baijifor i=0 to 100 dofor j=0 to 100 dofor k=0 to 100 dom=i+j+kn=3i+2j+0.5kif(m=100)and(n=100)thenoutput I,j,kreturn方案二procedure baijifor i=0 to 33 dofor j=0 to 50-1.5i dok=100-i-jIf(3i+2j+0.5k=100)thenoutput I,j,kreturn152、归纳法l 基本思想 通过列举少量的特殊情况，经过分析，最后找出一般的关系。162、递归法基本思想 为了降低问题的复杂度，总是将问题组成分解，最后归纳为一个最简单的问题，当解决这个简单问题后，再沿着就原来分解的逆过程逐步进行综合，这就是递归。17例题：用递归方法求n！l 递归公式表示：18程序#include int main()int fac(int n);int n;int y;printf(“input an integer number”);scanf(“%d”,&n);y=fac(n);printf(“%d!=%dn”,n,y);Return 0;int fac(int n)int f;if(n0)printf(“n0,data error!”);else if(n=0|n=1)f=1;else f=fac(n-1)*n;return(f);19减半递推技术 所谓 所谓“减半 减半”，是指将问题的规模减半；所谓，是指将问题的规模减半；所谓“递推 递推”，就是重复减半的过程。就是重复减半的过程。举例：设两个二阶矩阵为 举例：设两个二阶矩阵为 需要 需要8 8次乘法 次乘法两个矩阵相乘只需要 两个矩阵相乘只需要7 7次乘法 次乘法设 设 n=2 n=2k k，n=2 n=2k k 阶矩阵相乘，所需要的 阶矩阵相乘，所需要的乘法次数 乘法次数M(k)M(k)M(k)=7M(k-1)=7 M(k)=7M(k-1)=72 2 M(k-2)=7 M(k-2)=7k k M(0)M(0)=7=7k kn n2.81 2.8120回溯法回溯法基本思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。211.3 算法的复杂度分析l l 算法的时间复杂度 算法的时间复杂度(算法的工作量 算法的工作量)采用算法在执行过程中所需基本运算的执行 采用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。次数来度量算法的工作量。l l 相关因素：相关因素：(1)(1)基本运算次数还与问题的规模 基本运算次数还与问题的规模n n有关。算法 有关。算法的工作量 的工作量=f(n)=f(n)(2)(2)当取决于某一个特性输入时，有两种方法来 当取决于某一个特性输入时，有两种方法来衡量工作量：衡量工作量：平均性态 平均性态 最坏情况复杂性 最坏情况复杂性 22举例：采用顺序搜索法，在长度为举例：采用顺序搜索法，在长度为nn的一维数组中的一维数组中查找值为查找值为xx的元素的元素平均性态分析：平均性态分析：设需要查找的 设需要查找的x x出现在数组中每个位置上的可能性一样，概率 出现在数组中每个位置上的可能性一样，概率为 为q/n q/n，x x不在数组中的概率为 不在数组中的概率为1-1-q q比较次数平均情况下比较次数 平均情况下比较次数23 最坏情况是发生在需要查找的最坏情况是发生在需要查找的xx是数组中的最是数组中的最后一个元素或后一个元素或xx不在数组中的时候，此时显然不在数组中的时候，此时显然（2）最坏情况复杂度24算法的空间复杂度 一般指执行这个算法所需要的内存空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。25