数据结构_软件开发

PPT 内容

1. 1数据结构 Neusoft Institute of InformationIT Education & Training
2. 21、为什么要学习《数据结构》在本专业中的地位：数据结构是主修课，4个学分,是后续课程的基础毕业后工作的需要面试题中主要考数据结构的内容工作中经常会用到数据结构的知识一、课程介绍第一章：绪论程序＝数据结构＋算法
3. 面试题目：给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：【0，1，2，3，4，5，6，7，8，9】
4. 42、如何学习《数据结构》认真听讲，勤于思考 —要想做与数据结构相关的项目，就必须首先掌握数据结构的各项知识和技能。读万卷书，不如行万里路 —数据结构有比较多的概念和知识点，因此要多编程，多实践，以加深对这些概念的理解二、课程介绍第一章：绪论
5. 53、数据结构和编程语言(C语言)的关系数据结构：是一个概念和理论的集合编程语言：对这些概念和理论进行实现，以便于在软件项目中使用。第一章：绪论数据结构C语言Java语言……实现关系
6. 64、课程讲述内容第一章绪论第二章线性表第三章栈和队列第四章树和二叉树第五章图第六章查找第七章排序第一章：绪论
7. 75、课程教学目标 ⑴理解三种数据结构：线性结构、树形结构和图形结构；掌握典型算法的基本思想。 ⑵能将各种算法用c语言程序实现并运行正确，加深理解数据结构。 ⑶灵活运用各种数据结构，设计高效的算法解决实际问题第一章：绪论
8. 81、考核方法：三、考核方法第一章：绪论平时成绩70 ％出勤率10％平时作业、测试50％课堂表现10 ％(禁止上课打游戏)项目成绩30％授课的课时：4学时/周
9. 四、课堂管理要求：以下课堂现象属于严重违纪：看视频、打游戏，扣分如下： – 第1次违纪写不少于3000字检讨！ – 第2次违纪平时成绩按0分记！ – 第3次违纪，本门课程不合格！ • 其余课堂违纪现象（例如戴耳机、玩手机）视其情节具体扣除1-10分。 • 旷课1次扣10分，旷课次数达到5次，本门课程不合格！ • 迟到5分钟扣2分，迟到10分钟扣5分，超过10分钟扣10分。
10. 10第一章绪论本章主要介绍以下内容数据结构研究的主要内容数据结构中涉及的基本概念算法的概念、描述方法以及评价标准
11. 11要能回答的问题1. 什么是数据结构？ 2. 数据结构有那些基本结构？ 3.什么是数据的物理结构和逻辑结构？ 4.数据结构主要研究什么？ 5.算法与程序的区别？ 6. 算法的特性及其评价标准？第一章：绪论
12. 12一、什么是数据结构数据结构数据结构（关系）第一章：绪论计算机科学：数据指所有能够输入到计算机中并被计算机程序处理的符号集合。
13. 13第一章：绪论数据的表现形式简单数据（数字、字符、非数字字符）例如：学号(20020001);年龄（18）；姓名（王红）；照片复杂数据例如：学生（20020001、王红、男、18）；学生信息表学号姓名性别年龄20020001王红男1820020002张明男1920020003吴宁女18
14. 14一、什么是数据结构第一章：绪论因此,数据结构是指具有某种联系的数据元素以及元素之间所构成的各种关系的集合。
15. 15二、数据结构有那些基本结构应用举例1——学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。第一章：绪论
16. 16 特点： l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； l 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； l 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。第一章：绪论
17. 17应用举例2——Windows文件系统第一章：绪论我的电脑C：\My documentWindowsD：\Jdk1.5eclipse
18. 18特点： l在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构（层次结构）； l对它的操作有：建立树形结构，输出最低层结点内容等等。第一章：绪论
19. 19第一章：绪论应用举例3——专业课程的开设软件技术专业课程的开设情况：课程编号课程名称需要先修的课程编号C1计算机文化基础无C2Java语言(初级)C1C3数据结构(Java版)C1C4Java语言(中级)C2，C3C5数据库原理及应用C3C6Java语言(高级)C4C7脚本语言C1C8Java Web程序设计C5，C6，C7
20. 20第一章：绪论特点：在求解过程中，课程之间的先后关系具有图结构的特点，因此用图形结构（网状结构）描述；对图形结构的操作有：创建图结构，按要求将图结构中的顶点进行线性排序。 C6C1C2C7C4C3C5C8
21. 21二、数据结构有那些基本结构根据数据元素间关系的基本特性，有四种基本数据（逻辑）结构：集合——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构（层次结构）——一个对多个，如树图状结构（网状结构）——多个对多个，如图第一章：绪论
22. 22数据广义：是对客观事物的符号表示。计算机科学：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素表示一个事物的一组数据，数据元素是数据的基本单位。程序中通常作为整体处理，也可称为结点、顶点、记录等。数据项构成数据元素的最小单位。也称字段或域。三、数据结构的基本概念第一章：绪论
23. 23学号姓名性别年龄20020001王红男1820020002张明男1920020003吴宁女18数据元素数据项数据第一章：绪论
24. 24数据类型数据类型：一个类型和定义在该类型上的操作集合高级语言中指数据的取值范围及其上可进行的操作的总称三、数据结构的基本概念第一章：绪论例 C语言中，提供int, char, float, double等基本数据类型，数组、结构体、共用体等构造数据类型。struct student { int num; char name[20]; float score; };
25. 25有四种基本数据逻辑结构：集合、线性结构、树形结构、图状结构逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称为逻辑结构。第一章：绪论存储结构（物理结构）是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的关系(逻辑结构)。
26. 26 数据的逻辑结构和存储结构的区别：数据的逻辑结构：它与数据的存储无关，是独立于计算机的。数据的存储结构：是逻辑结构在计算机中的实现，它是依赖于计算机的。数据的存储结构有以下几种形式顺序存储结构链式存储结构索引存储哈希存储第一章：绪论
27. 27第一章：绪论顺序存储结构：定义：将数据元素存储在一块地址连续的空间中。特点：逻辑结构上相邻的数据元素在物理上也相邻。数据间的逻辑关系表现在数据元素的存储位置关系上。案例：{A,B,C,D}用数组存储ABCD1000100110021003
28. 28第一章：绪论链式存储结构：定义：使用指针将相互关联的数据元素(节点)连接起来。节点：由数据元素域和指针域组成的一个整体。特点：逻辑结构上相邻的数据元素在物理上不一定相邻。数据间的逻辑关系表现在节点的连接关系上。案例：
29. 291028B1020A1010C ∧D1005h 数据元素域指针域 A 1020 D ∧ …….. ……. B 1028 …….. ……. C 1010 链式存储 h1005存储地址101010201028…….…….
30. 30第一章：绪论四、数据结构主要研究什么数据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的课程。数据的逻辑结构数据的存储结构数据的操作(算法)：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构
31. 31总结：1、什么是数据结构？ 2、本课程主要研究什么？ 3、什么是数据的逻辑结构和物理结构? 4、数据的逻辑结构有哪几种？存储结构有哪几种形式？ 5、算法与程序的区别和联系？ 6、算法特性和如何评价算法的好坏？第一章：绪论
32. 32作业： 1、思考本课程自己将如何学习，拟一个学习计划。 2、阅读教材第一章1-8页，完成教材29-30页习题1.6.1。 3、复习上学期学过的《C语言》课程中的函数、指针和结构体知识。第一章：绪论
33. 33复习：1、什么是数据结构？ 2、本课程主要研究什么？ 3、什么是数据的逻辑结构和物理结构? 4、数据的逻辑结构有哪几种？存储结构有哪两种形式？第一章：绪论
34. 34五、算法算法：算法是为解决一个问题而采取的方法和步骤。程序是计算机能够理解和执行的指令序列。算法与程序的区别和联系： (1) 算法的执行是有穷的，而一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 (2)程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 (3）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序. 第一章：绪论
35. 35六、算法的设计与分析算法的设计 1、通过对问题进行详细地分析，抽象出相应的数学模型； 2、确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法； 3、描述算法（C语言中的函数） 4、选用某种语言将算法转换成程序；（C语言） 5、调试并运行这些程序。第一章：绪论
36. 36算法的设计算法能用文字、高级语言、伪代码进行描述第一章：绪论六、算法的设计与分析案例：在学生信息表中,按学号进行顺序查找 NO=200020005的学生学号姓名年龄20020001王红1820020002张明1920020003吴宁1820020005林云2020020007刘强18设i=1，比较第i个元素的学号是否等于NO,如果相等，则查找成功，查找过程结束；否则，i++，继续比较。学生信息表中，所有元素的学号都不等于NO，则查找失败。
37. 37算法的基本特性（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。第一章：绪论
38. 38算法的评价标准 (1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。 (4) 高效性：有效使用存储空间和有较好的时间效率。第一章：绪论
39. 39算法的优劣：问题：求2+4+6+……+2n的值1.2 算法及算法分析算法1： int sum = 0,i; for(i=2;i<=2*n;i=i+2) {sum = sum+i;}算法2： int sum = (2+2*n)*n/2;
40. 40算法效率的度量：算法定量的评价 1.事后统计——收集此算法的执行时间和实际占用空间的统计资料。 1.2 算法及算法分析同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适。因此一般常用时间的一个数量级来衡量缺点：必须先运行根据算法描述编写的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 机器执行指令速度
41. 41 时间复杂度一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)。则时间量度记作： T(n)=O(f(n))，称作算法的时间复杂度。表示：随问题规模n的增大，执行时间的增长率和f(n)的增长率相同。通常，时间复杂度只考虑问题规模n的增长率，无需精确，故，只需求出它关于n的增长率或阶即可。1.2 算法及算法分析
42. 42计算算法时间复杂度： 1、选取算法中基本操作语句（通常是最内层循环体语句）； 2、计算该语句的频度（频度是指该语句重复执行的次数）； 3、取语句频度的最大增长率。
43. 43例 1：{++x;} 将++x看成是基本操作，则语句频度为1，其时间复杂度为Ｏ(1)，即常量阶。例 2：for(int i=1;i<=1000;i++) {++x;} 将++x看成是基本操作，则语句频度为1000，其时间复杂度仍为Ｏ(1)，即常量阶。例３：for(i=1;i<=n;++i) {++x;} 语句频度为：n　其时间复杂度为：O(n)
44. 44例４：for(i=1;i<=n;++i) 　　　　for(j=1;j<=n;++j) {++x;} 语句频度为：n2 　其时间复杂度为：O(n2) 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)　　　　　　　　例５：for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; } 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2 )/ 2 ∴时间复杂度为O(n2)，表示为：T(n)=O(n2)
45. 45常见的时间复杂度有： O(1)
46. 461.1下面程序的时间复杂度为_____。 for(i=1，i
47. 第一章绪论1.3下列程序的时间复杂度为 X=n; /*n>1*/ y=0; while((x>=(y+1)*(y+1)) y=y+1; A.O(n) B.O( ) C.O(1) D.O(n2) 1.4下列程序的时间复杂度为 int i=1; while(i<=n) i=i2; A.O(n2 ) B.O(log2n) C.O( ) D.O(n)
48. 48答案： C A B B作业：完成教材第30-32页1.6.2习题
49. 题目2：求子数组的最大和输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
50. Thank youNeusoft Institute of Information谢谢

数据结构

V587K

贡献于2016-06-05

数据结构

PPT 内容

PPT 图集

相关PPT