算法与数据结构算法与流程图

算法与流程图第章图与网定义和术语1/38目标数据构造与算法C程序基本构造用流程图描述算法用C语言描述算法图与网定义和术语22/38引例：首先分析学籍档案类问题。设一种班级有50个学生，这个班级学籍表如表所示。我们能够把表中每个学生信息当作一种统计，表中每个统计又由7个数据项组成。该学籍表由50个统计组成，统计之间是一种次序关系。这种表一般称为线性表，数据之间逻辑构造称为线性构造，其主要操作有检索、查找、插入或删除等。学籍表序号学号姓名性别英语数学物理0120230301李明男8691800220230302马琳男7683855020230350刘薇薇女889390数据构造基本概念和术语6-1图与网定义和术语33/38又如，对于学院行政机构，能够把该学院名称当作树根，把下设若干个系当作它树枝中间结点，把每个系分出若干专业方向当作树叶，这样就形成一种树型构造，如下列图所示。树中每个结点能够包括较多信息，结点之间关系不再是次序，而是分层、分叉构造。树型构造主要操作有遍历、查找、插入或删除等。数据构造基本概念和术语6-2图专业设置图与网定义和术语44/38最后分析交通问题。假如把若干个城镇当作若干个顶点，再把城镇之间道路当作边，它们能够组成一种网状图，这种关系称为图型构造或网状构造。这是一种图论方面问题。交通图存放和管理确实不属于单纯数值计算问题，而是一种非数值信息处理问题。数据构造基本概念和术语6-3图交通示意图图与网定义和术语55/38一般来说，数据构造研究是一类一般数据表达及其有关运算操作。数据构造是一门主要研究如何合理地组织数据，建立合适数据构造，提升计算机执行程序所用时间效率和空间效率学科。数据构造基本概念和术语6-466/38数据(Data)-----描述客观事物数字、字符以及所有能够输入到计算机中并被计算机处理信息总称。数据元素(DataElement)------是数据基本单位，在计算机中一般作为一种整体进行考虑和处理。数据元素除了能够是一种数字或一种字符串以外，它也能够由一种或多种数据项组成。数据项(DataItem)---是有独立含义数据最小单位，有时也称为字段(Field)。数据构造基本概念和术语6-5图与网定义和术语77/38数据对象(DataObject)---是具有相同性质数据元素集合，是数据一种子集。例如，整数数据对象是集合N={0，±1,±2,…}，字母字符数据对象是集合C={'A','B',…,'Z'}。本节学籍表也可当作一种数据对象。数据构造(DataStructure)---是带有构造数据元素集合，它是指数据元素之间互相关系，即数据组织形式、存放形式以及定义在它们之上一组运算。无论是存放构造设计，还是运算算法设计，都必须考虑存放空间开销和运行时间效率。数据构造基本概念和术语6-6图与网定义和术语88/38在处理实际问题时，当确定了数据构造之后，需深入研究与之有关一组操作(也称运算)，主要有插入、删除、排序、查找等。为了实现某种操作(如查找)，经常需要设计一种算法。算法(Algorithm)是对特定问题求解步骤一种描述，是指令有限序列。描述算法需要一种语言，能够是自然语言、数学语言或者是某种计算机语言。什么是算法图与网定义和术语99/38(1)输入：一种算法应当有零个、一种或多种输入。(2)有穷性：一种算法必须在执行有穷步骤之后正常结束，而不能形成无穷循环。(3)确定性：算法中每一条指令必须有确切含义，不能产生多义性。(4)可行性：算法中每一种指令必须是切实可执行，即标准上能够通过已经实现基本运算执行有限次来实现。(5)输出：一种算法应当最少有一种输出，这些输出是同输入有某种特定关系量。算法特性图与网定义和术语1010/38算法设计要求正确性 程序对于典型、苛刻而带有刁难性几组输入数据能够得出满足规格说明要求结果可读性健壮性 当输入数据非法时，能够适本地做出反应或者进行处理，而不会产生莫名其妙结果效率与低存放量需求图与网定义和术语1111/38算法实现文档伪代码N-S图流程图代码自然语言1212/38算法例子从键盘中输入100个整数，对其中正整数进行累加，最后输出成果。图与网定义和术语1313/38算法描述（自然语言）1、输入一种数；2、假如该数>0,累加它；3、假如100个数没有输入完，转步骤1;4、输入完100个数后，输出累加和。图与网定义和术语1414/38算法描述（流程图）1515/38算法描述（N-S流程图）图与网定义和术语1616/38算法C语句实现图与网定义和术语1717/38流程图符号符号说明程序开始或结束计算步骤输入/输出指令判断和分支连接符流程线1818/38C程序基本构造次序构造选择构造循环构造图与网定义和术语1919/38次序构造3-1次序构造流程图：图与网定义和术语2020/38次序构造3-22121/38次序构造3-3图与网定义和术语2222/38选择构造2-1选择构造流程图：图与网定义和术语2323/38选择构造2-22424/38循环构造2-1循环构造流程图：图与网定义和术语2525/38循环构造2-2从键盘输入9个数，找出最大值图与网定义和术语2626/38流程图画法演示使用visio画流程图……2727/38如何选择描述数据构造和算法语言是十分主要问题。在Windows环境下涌现出一系列功能强大、面向对象描述工具，如VisualC++，BorlandC++，VisualBasic，VisualFoxPro等。近年来在计算机科学研究、系统开发、教学以及应用开发中，C语言使用越来越广泛。因此，我们能够采取C语言进行算法描述。为了能够简要扼要地描述算法，突出算法思绪，一般有下列商定：用C语言实现算法5-1图与网定义和术语2828/38(1)问题规模尺寸用MAXSIZE表达，商定在宏定义中已经预先定义过，例如：#defineMAXSIZE100(2)数据元素类型一般写成ELEMTP，能够以为在宏定义中预先定义过，例如：#defineELEMTPint在上机试验时根据需要，可临时用其他某个详细类型标识符来替代。用C语言实现算法5-22929/38(3)一种算法要以函数形式给出：类型标识符函数名(带类型说明形参表){语句组}例如：intadd(inta,intb){intc;c=a+b;return(c);}除了形参类型说明放在圆括号中之外，在描述算法函数中其他变量类型说明一般省略不写，这样使算法处理过程愈加突出明了。用C语言实现算法5-33030/38(4)有关数据存放构造类型定义以及全局变量说明等均应在写算法之前进行说明。下面例子给出了书写算法一般步骤。例1.1有n个整数，将它们按由大到小次序排序，并且输出。分析：n个数据逻辑构造是线性表(a1,a2,a3,…,an)；选用一维数组作存放构造。用C语言实现算法5-43131/38用C语言实现算法5-5/*数组a数据由主函数提供*/3232/38著名计算机科学家N.沃思提出了一种有名公式：算法+数据构造=程序。由此可见，数据构造和算法是程序两大要素，二者相辅相成，缺一不可。一种数据构造优劣是在实现其多种运算算法中体现。对数据构造分析实质上也就是对实现其多种运算算法分析。评价一种算法应从四个方面进行：正确性、简单性、运行时间、占用空间。但主要看这个算法所要占用机器资源多少。而在这些资源中时间和空间是两个最主要方面，因此算法分析中最关怀也就是算法所需时间代价和空间代价。算法分析4-13333/38

1.空间所谓算法空间代价(或称空间复杂性)，是指当问题规模以某种单位由1增至n时，处理该问题算法实现所占用空间也以某种单位由1增至f(n)，并称该算法空间代价是f(n)。算法分析4-23434/38

2.时间(1)语句频度(FrequencyCount)：指是在一种算法中该语句反复执行次数。(2)算法渐近时间复杂度(AsymptoticTimeComplexity)：算法中基本操作反复执行次数根据算法中最大语句频度来估算，它是问题规模n某个函数f(n)，算法时间量度记作T(n)=O(f(n))，表达伴随问题规模n增大，算法执行时间增加率和f(n)增加率相同，称作算法渐近时间复杂度，简称时间复杂度。时间复杂度往往不是精确执行次数，而是估算数量级。它着重体现是伴随问题规模增大，算法执行时间增加变化趋势。算法分析4-33535/38例如，在下列三个程序段中：(a)x=x+1;(b)for(i=1;i<=n;i++)x=x+1;(c)for(j=1;j<=n;j++)for(k=1;k<=n;k++)x=x+1;语句x=x+1频度分别为1、n和，则(a)、(b)、(c)