《第1讲：课程概述和数据结构基本概念课件》由会员分享，可在线阅读，更多相关《第1讲：课程概述和数据结构基本概念课件（33页珍藏版）》请在金锄头文库上搜索。
1、IT Education & Training1数据结构数据结构 Neusoft Institute of InformationIT Education & TrainingIT Education & Training2 姓姓 名：名：李德光 系系 部：部：计算机系 办公地址：办公地址： C7201 E-mail:E-mail: 一、一、自我介绍自我介绍第一章：绪论第一章：绪论IT Education & Training31 1、为什么要学习、为什么要学习数据结构数据结构在本专业中的地位：数据结构是主修课，在本专业中的地位：数据结构是主修课，4 4个学个学分分, ,是后续课程的基础是后续
2、课程的基础 毕业后工作的需要毕业后工作的需要 面试题中主要考数据结构的内容面试题中主要考数据结构的内容工作中经常会用到数据结构的知识工作中经常会用到数据结构的知识二、二、课程介绍课程介绍第一章：绪论第一章：绪论程序数据结构算法程序数据结构算法IT Education & Training42 2、如何学习、如何学习数据结构数据结构学好理论，掌握算法学好理论，掌握算法 要想做与数据结构相关的项目，就必须首先掌握数首先掌握数据结构的各项知识和技能据结构的各项知识和技能。将算法用一种程序设计语言实现将算法用一种程序设计语言实现数据结构有比较多的概念和知识点，因此要多编要多编程，多实践，以加深对这些概
3、念的理解程，多实践，以加深对这些概念的理解二、二、课程介绍课程介绍第一章：绪论第一章：绪论IT Education & Training53 3、数据结构和编程语言、数据结构和编程语言( (C C语言语言) )的关系的关系 数据结构：数据结构：是一个概念和理论的集合是一个概念和理论的集合 编程语言：编程语言：对这些概念和理论进行实现，以便于在软对这些概念和理论进行实现，以便于在软件项目中使用。件项目中使用。第一章：绪论第一章：绪论数据结构数据结构C语言Java语言实现关系实现关系IT Education & Training64 4、课程讲述内容、课程讲述内容第一章第一章 绪论绪论第二章第二章
4、 线性表线性表第三章第三章 栈和队列栈和队列第四章第四章 串串第六章第六章 树和二叉树树和二叉树第七章第七章 图图 第九章第九章 查找查找第十章第十章 内部排序内部排序第一章：绪论第一章：绪论IT Education & Training75 5、课程教学目标、课程教学目标理解三种数据结构：线性结构、树形结构和图形结构；理解三种数据结构：线性结构、树形结构和图形结构；掌握典型算法的基本思想。掌握典型算法的基本思想。能将常用算法用能将常用算法用c c语言程序实现并运行正确，加深理解语言程序实现并运行正确，加深理解数据结构。数据结构。灵活运用各种数据结构，设计高效的算法解决实际问灵活运用各种数据结
5、构，设计高效的算法解决实际问题题第一章：绪论第一章：绪论IT Education & Training81 1、考核方法：、考核方法：三、考核方法三、考核方法第一章：绪论第一章：绪论平时成绩平时成绩60 出勤率出勤率10平时作业、测试平时作业、测试40课堂表现课堂表现10 期末考试期末考试40n授课的课时：授课的课时：4学时学时/周周IT Education & Training91 1、座位前排不留空，后排不坐人、座位前排不留空，后排不坐人四、课堂要求四、课堂要求第一章：绪论第一章：绪论看视频、打游戏，扣分如下：看视频、打游戏，扣分如下：第第1次违纪写不少于次违纪写不少于3000字检讨！字检
6、讨！第第2次违纪平时考勤和课堂表现按次违纪平时考勤和课堂表现按0分记！分记！第第3次违纪，本门课程不合格！次违纪，本门课程不合格！其余课堂违纪现象（例如戴耳机、玩手机）视其情节具体扣除其余课堂违纪现象（例如戴耳机、玩手机）视其情节具体扣除1-10分。分。旷课旷课1次扣次扣10分，旷课次数达到分，旷课次数达到5次，本门课程不合格！次，本门课程不合格！迟到迟到5分钟扣分钟扣2分，迟到分，迟到10分钟扣分钟扣5分，超过分，超过10分钟扣分钟扣10分。分。2 2、课堂课堂违纪处理：违纪处理：IT Education & Training10第一章第一章 绪论绪论本章主要介绍以下内容本章主要介绍以下内容
7、l数据结构研究的主要内容数据结构研究的主要内容l数据结构中涉及的基本概念数据结构中涉及的基本概念l算法的概念、描述方法以及评价算法的概念、描述方法以及评价标准标准IT Education & Training11要能回答的问题1. 什么是数据结构？2. 数据结构有那些基本结构？3.什么是数据的物理结构和逻辑结构？4.数据结构主要研究什么？5.算法与程序的区别？6.算法的特性及其评价标准？第一章：绪论第一章：绪论IT Education & Training12一、什么是数据结构一、什么是数据结构数据结构数据结构数据数据结构（关系）结构（关系）第一章：绪论第一章：绪论计算机科学：数据指所有能够输
8、入到计算机中并被计计算机科学：数据指所有能够输入到计算机中并被计算机程序处理的符号集合。算机程序处理的符号集合。IT Education & Training13第一章：绪论第一章：绪论数据的表现形式数据的表现形式简单数据（数字、字符、非数字字符）简单数据（数字、字符、非数字字符） 例如：学号例如：学号(20020001);(20020001);年龄（年龄（1818）；姓名（王红）；照片）；姓名（王红）；照片复杂数据复杂数据 例如：学生（例如：学生（2002000120020001、王红、男、王红、男、1818）；）； 学生信息表学生信息表学号学号姓名姓名性别性别年龄年龄20020001王红男
9、1820020002张明男1920020003吴宁女18IT Education & Training14一、什么是数据结构一、什么是数据结构第一章：绪论第一章：绪论因此因此,数据结构数据结构是指具有某种联系的是指具有某种联系的数数据元素据元素以及元素之间所构成的各种以及元素之间所构成的各种关关系系的集合。的集合。IT Education & Training15二、数据结构有那些基本结构二、数据结构有那些基本结构应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的假设一个学籍档案管理系统应包含如下表所示的学生信息。学生信息。第一章：绪论第一章：绪论IT Education &
10、Training16特点：特点： l l 每个学生的信息占据一行，所有学生的信息按学号顺序依每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；次排列构成一张表格； l l 表中每个学生的信息依据学号的大小存在着一种前后关系，表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的这就是我们所说的线性结构线性结构； l l 对它的操作通常是插入某个学生的信息，删除某个学生的对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。信息，更新某个学生的信息，按条件检索某个学生的信息等等。第一章：绪论第一章：绪论IT E
11、ducation & Training17应用举例2Windows文件系统文件系统第一章：绪论第一章：绪论我的电脑C：My documentWindowsD：Jdk1.5eclipseIT Education & Training18特点：特点： l l在求解过程中，所处理的数据之间具有层次关系，这是我在求解过程中，所处理的数据之间具有层次关系，这是我们所说的们所说的树形结构树形结构（层次结构）（层次结构）； l l对它的操作有：建立树形结构，输出最低层结点内容等等。对它的操作有：建立树形结构，输出最低层结点内容等等。第一章：绪论第一章：绪论IT Education & Training19第
12、一章：绪论第一章：绪论应用举例3专业课程的开设专业课程的开设软件技术专业课程的开设情况：软件技术专业课程的开设情况：课程编号课程名称需要先修的课程编号C1计算机文化基础无C2Java语言(初级)C1C3数据结构(Java版)C1C4Java语言(中级)C2，C3C5数据库原理及应用C3C6Java语言(高级)C4C7脚本语言C1C8Java Web程序设计C5，C6，C7IT Education & Training20第一章：绪论第一章：绪论特点：特点： 在求解过程中，课程之间的先后关系具有图结构的特点，因此在求解过程中，课程之间的先后关系具有图结构的特点，因此用用图形结构（网状结构）图形结
13、构（网状结构）描述；描述；对图形结构的操作有：创建图结构，按要求将图结构中的顶点进对图形结构的操作有：创建图结构，按要求将图结构中的顶点进行线性排序。行线性排序。 C6C1C2C7C4C3C5C8IT Education & Training21二、数据结构有那些基本结构二、数据结构有那些基本结构根据数据元素间关系的基本特性，有四种根据数据元素间关系的基本特性，有四种基本数据基本数据（逻辑）结构：（逻辑）结构：集合集合数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，无外，无其它关系其它关系线性结构线性结构一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列树形结构树形结构（
14、层次结构）（层次结构）一个对多个，如树一个对多个，如树图状结构图状结构（网状结构）（网状结构）多个对多个，如图多个对多个，如图第一章：绪论第一章：绪论IT Education & Training22数据数据 广义：广义：是对客观事物的符号表示。是对客观事物的符号表示。计算机科学：计算机科学：指所有能够输入到计算机中并被计算机程序处理的指所有能够输入到计算机中并被计算机程序处理的符号集合符号集合。 数据元素数据元素 表示一个事物的表示一个事物的一组数据一组数据，数据元素是数据的，数据元素是数据的基本单位基本单位。程序中通程序中通常作为整体处理，也可称为结点、顶点、记录等。常作为整体处理，也可称
15、为结点、顶点、记录等。数据项数据项 构成数据元素的最小单位。也称字段或域。构成数据元素的最小单位。也称字段或域。三、数据结构的基本概念三、数据结构的基本概念第一章：绪论第一章：绪论IT Education & Training23学号姓名性别年龄20020001王红男1820020002张明男1920020003吴宁女18数据元素数据元素数据项数据项数据数据第一章：绪论第一章：绪论IT Education & Training24数据类型数据类型 数据类型：一个类型和定义在该类型上的操作集合数据类型：一个类型和定义在该类型上的操作集合高级语言中指数据的高级语言中指数据的取值范围取值范围及其上可
16、进行的及其上可进行的操作操作的总称的总称三、数据结构的基本概念三、数据结构的基本概念第一章：绪论第一章：绪论例例 C C语言中，提供语言中，提供int, char, float, doubleint, char, float, double等基本数据类型等基本数据类型，数组、结构体、共用体等数组、结构体、共用体等构造数据类型构造数据类型。struct student int num; char name20; float score;IT Education & Training25有四种基本数据逻辑结构：集合、线性结构、树形结构、图状结构逻辑结构逻辑结构 数据结构中所说的数据结构中所说的“关系关系”实际上是指数据元素实际上是指数据元素之间的逻辑关系，又称为逻辑结构。之间的逻辑关系，又称为逻辑结构。第一章：绪论第一章：绪论存储结构（物理结构存储结构（物理结构） 是指数据结构在计算机存储器中的具体实现。与孤立的数据是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要
