计算机软件技术基础

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