数据结构-基本概念

第二章线性表第三章栈和队列第四章树第五章图第六章排序第七章查找第一章概述第二部分数据结构1.1基本概念•数据是客观事物的符号表示。•能输入到计算机中并被计算机程序处理的符号的总称。•数据是信息的载体。数据学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...例1：学生成绩第一章概述例2：声音、图象数据元素•数据元素是数据的基本单位。•它也可以再由不可分割的数据项组成数据对象性质相同的数据元素的集合。例：一个班级的成绩表可以看作一个数据对象。一个图片、声音…..•数据元素集合（也可称数据对象）中各元素的关系。•相互之间存在特定关系的数据元素集合。数据结构从三个方面研究数据结构：逻辑结构存储结构算法•数据元素之间具有的逻辑关系(结构)。线性关系(线性结构)：数据元素间为严格的一对一关系。树形结构：数据元素间为严格的一对多关系。逻辑结构图状结构（或网状结构）：数据元素间为多对多关系非线性结构具有某种逻辑结构的数据在计算机存储器中的存储方式。顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。存储结构逻辑结构：线性结构(线性表)a1a2a3a30…d1d2d3d4…d30a2a1a3a4a30存储结构:1.顺序存储结构:学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...例：2.链式存储结构:…d1d2d3d4a1a2a3a30∧list…a2a1a4a3d4d1d5d3算法数据的处理方法（算法）。查找：数学成绩前三名的同学学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...例：添加：来了一个新同学1.研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储器内的存储方式。3.研究如何在数据的各种结构(逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。数据结构课程研究的主要内容(算法)(逻辑结构)(存储结构)1.2算法及其描述输入一个完整的算法应该满足下面五个基本标准：有效性确定性有穷性输出一.算法及其性质(2).算法是指令的有限序列，其中每一条指令表示一个或多个操作。1.算法的定义2.算法的性质(1).算法是对特定问题求解步骤的一种描述。二.算法的描述(1)M除以N，将余数送中间变量R；(2)测试余数R是否等于零？a)若R等于零，求得的最大公因子为当前N的值,算法到此结束。b)若R不等于零，将N送入M，将R送N，重复算法的(1)和(2)。1.采用自然语言来描述问题：求两个正整数M与N的最大公因子。2.采用程序流程图的形式来描述M除以N的余数送R余数R为0否？将N送M将R送N输出N的值结束开始yesnoCOMFACTOR(intM,intN){intR;while(1){R=M%N;if(R==0)returnN;M=N;N=R;}}3.采用某种具体程序语言来描述4.设计一种既脱离某种具体的程序设计语言，又具有各种程序设计语言的共同特点的形式化语言来描述类C语言一.算法格式函数类型函数名（形式参数及其说明）{内部参数说明；语句序列；}1.3类C语言简介二.语句1.赋值语句：(1)if条件表达式{语句串；}(2)if条件表达式{语句串1；}else{语句串2；}变量名=表达式2.条件语句(两种)3.循环语句(三种)do{语句串；}while(循环条件)for(赋初值表达式；条件表达式；修改表达式){语句串;}while(循环条件){语句串；}switch(表达式){case判定值1：语句串1；break;case判定值2：语句串2；break;............case判定值n：语句串n；default：语句串n+1;break;}4.情况语句1、/*注释内容*/2、//1、字符：函数getchar()、putchar()实现2、其他数据：函数scanf()、printf()实现表)5.输入/输出语句6.注释求两个n阶矩阵的乘积：MATRIX(intA[],intB[],intC[],intn){for(i=1;i=n;i++)for(j=1;j=n;j++){C[i,j]=0;for(k=1;k=n;k++)C[i,j]=C[i,j]+A[i,k]*B[k,j];}}例1.4算法分析1、正确性2、可读性3、健壮性4、效率与低存储量需求效率指的是算法执行时间。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。算法设计的要求是指对算法质量优劣的评价。3．其他方面。如算法的可读性、可移植性以及易测试性的好坏。2．依据算法编写的程序在计算机中占存储空间多少的度量，称之为空间复杂度。1．依据算法编写的程序在计算机中运行时间多少的度量，称之为时间复杂度。除正确性外，应从三个方面分析一个算法：算法分析一.时间复杂度2.源程序编译的强弱以及所产生的机器代码质量的优劣。3.机器执行一条指令的时间长短。4.程序中语句的执行次数。1.问题的规模。一个程序在计算机中运行时间的多少与诸多因素有关，其中主要有：以语句执行的次数的多少作为算法的时间量度的分析方法称为频度统计法。一条语句的频度是指该语句被执行的次数，而整个算法的频度是指算法中所有语句的频度之和。频度统计法--------------------------n+1--------------n(n+1)----------------------------n2------n2(n+1)----n3算法的频度:f(n)=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1例：MATRIX(intA[],intB[],intC[],intn){for(i=1;i=n;i++)for(j=1;j=n;j++){C[i,j]=0;for(k=1;k=n;k++)C[i,j]=C[i,j]+A[i,k]B[k,j];}}当n→∞时，有f(n)/g(n)=常数≠0，则称函数f(n)与g(n)同阶,或者说，f(n)与g(n)同一个数量级，记作f(n)=O(g(n))称上式为算法的时间复杂度,或称该算法的时间复杂度为O(g(n))。其中,n为问题的规模(大小)的量度。算法的时间复杂度为O(n3)lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)=2n→∞n→∞符号O的的数学定义1.5基本算法枚举法归纳法回溯法模拟法枚举法从集合中一一列举各个元素–如果不知道一个命题是否为真,利用一一列举每一个元素的方法,如果都为真,找不到反例,则此命题为真–百鸡问题公鸡每只5元,母鸡每只3元,小鸡3只1元,问100元钱买100只鸡能有多少种买法.–x+y+z=100–5x+3y+z/3=100归纳法数学归纳法递推法递归法回溯法迷宫问题模拟法