数据结构-基本概念.ppt

《数据结构-基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表第三章栈和队列第四章树第五章图第六章排序第七章查找第一章概述第二部分数据结构1.1基本概念数据是客观事物的符号表示。能输入到计算机中并被计算机程序处理的符号的总称。数据是信息的载体。数据学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...例1：学生成绩第一章概述例2：声音、图象数据元素数据元素是数据的基本单位。它也可以再由不可分割的数据项组成数据对象性质相同的数据元素的集合。例：一个班级的成绩表可以看作一个数据对象。一个图片、声音…..数据元

2、素集合（也可称数据对象）中各元素的关系。相互之间存在特定关系的数据元素集合。数据结构从三个方面研究数据结构：逻辑结构存储结构算法数据元素之间具有的逻辑关系(结构)。线性关系(线性结构)：数据元素间为严格的一对一关系。树形结构：数据元素间为严格的一对多关系。逻辑结构图状结构（或网状结构）：数据元素间为多对多关系非线性结构具有某种逻辑结构的数据在计算机存储器中的存储方式。顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。用一组地址任意的存储单元依次存放数据元素，数据元素之间的

3、逻辑关系通过指针间接地反映。存储结构逻辑结构：线性结构(线性表)a1a2a3a30…d1d2d3d4…d30a2a1a3a4a30存储结构:1.顺序存储结构:学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...例：2.链式存储结构:…d1d2d3d4a1a2a3a30∧list…a2a1a4a3d4d1d5d3算法数据的处理方法（算法）。查找：数学成绩前三名的同学学号姓名语文数学C语言6201001张三8554926201002李四9284646201

4、003王五8774736201004...例：添加：来了一个新同学1.研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储器内的存储方式。3.研究如何在数据的各种结构(逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。数据结构课程研究的主要内容(算法)(逻辑结构)(存储结构)1.2算法及其描述输入一个完整的算法应该满足下面五个基本标准：有效性确定性有穷性输出一.算法及其性质(2).算法是指令的有限序列，其中每一条指令表示一个或多个操作。1.算法的定义2.算法的性质(1).算法是对特定问题求解步骤的一种描述。二

5、.算法的描述(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.设

6、计一种既脱离某种具体的程序设计语言，又具有各种程序设计语言的共同特点的形式化语言来描述类C语言一.算法格式函数类型函数名（形式参数及其说明）{内部参数说明；语句序列；}1.3类C语言简介二.语句1.赋值语句：(1)if条件表达式{语句串；}(2)if条件表达式{语句串1；}else{语句串2；}变量名=表达式2.条件语句(两种)3.循环语句(三种)do{语句串；}while(循环条件)for(赋初值表达式；条件表达式；修改表达式){语句串;}while(循环条件){语句串；}switch(表达式){case判定值1：语句串1；bre

7、ak;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[

8、i,j]=C[i,j]+A[i,k]*B[k,j];}}例1.4算法分析1、正确性2、可读性3、健壮性4、效率与低存储量需求效率指的是算法执行时间。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。算法设计的要求