第1讲：课程概述和数据结构基本概念课件.ppt

1,数据结构,Neusoft Institute of Information,IT Education&Training,2,姓 名：李德光 系 部：计算机系 办公地址：C7201 E-mail:,一、自我介绍,第一章：绪论,3,1、为什么要学习数据结构在本专业中的地位：数据结构是主修课，4个学分,是后续课程的基础 毕业后工作的需要 面试题中主要考数据结构的内容工作中经常会用到数据结构的知识,二、课程介绍,第一章：绪论,程序数据结构算法,4,2、如何学习数据结构学好理论，掌握算法 要想做与数据结构相关的项目，就必须首先掌握数据结构的各项知识和技能。将算法用一种程序设计语言实现 数据结构有比较多的概念和知识点，因此要多编程，多实践，以加深对这些概念的理解,二、课程介绍,第一章：绪论,5,3、数据结构和编程语言(C语言)的关系 数据结构：是一个概念和理论的集合 编程语言：对这些概念和理论进行实现，以便于在软件项目中使用。,第一章：绪论,6,4、课程讲述内容第一章 绪论第二章 线性表第三章 栈和队列第四章 串第六章 树和二叉树第七章 图 第九章 查找第十章 内部排序,第一章：绪论,7,5、课程教学目标理解三种数据结构：线性结构、树形结构和图形结构；掌握典型算法的基本思想。能将常用算法用c语言程序实现并运行正确，加深理解数据结构。灵活运用各种数据结构，设计高效的算法解决实际问题,第一章：绪论,8,1、考核方法：,三、考核方法,第一章：绪论,平时成绩60,出勤率10平时作业、测试40课堂表现10,期末考试40,授课的课时：4学时/周,9,1、座位前排不留空，后排不坐人,四、课堂要求,第一章：绪论,看视频、打游戏，扣分如下：第1次违纪写不少于3000字检讨！第2次违纪平时考勤和课堂表现按0分记！第3次违纪，本门课程不合格！其余课堂违纪现象（例如戴耳机、玩手机）视其情节具体扣除1-10分。旷课1次扣10分，旷课次数达到5次，本门课程不合格！迟到5分钟扣2分，迟到10分钟扣5分，超过10分钟扣10分。,2、课堂违纪处理：,10,第一章 绪论,本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准,11,要能回答的问题,1.什么是数据结构？2.数据结构有那些基本结构？3.什么是数据的物理结构和逻辑结构？4.数据结构主要研究什么？5.算法与程序的区别？6.算法的特性及其评价标准？,第一章：绪论,12,一、什么是数据结构,数据结构,数据,结构（关系）,第一章：绪论,计算机科学：数据指所有能够输入到计算机中并被计算机程序处理的符号集合。,13,第一章：绪论,数据的表现形式简单数据（数字、字符、非数字字符）例如：学号(20020001);年龄（18）；姓名（王红）；照片复杂数据 例如：学生（20020001、王红、男、18）；学生信息表,14,一、什么是数据结构,第一章：绪论,因此,数据结构是指具有某种联系的数据元素以及元素之间所构成的各种关系的集合。,15,二、数据结构有那些基本结构,应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学生信息。,第一章：绪论,16,特点：l每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；l表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；l对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,第一章：绪论,17,应用举例2Windows文件系统,第一章：绪论,18,特点：l在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构（层次结构）；l对它的操作有：建立树形结构，输出最低层结点内容等等。,第一章：绪论,19,第一章：绪论,应用举例3专业课程的开设,软件技术专业课程的开设情况：,20,第一章：绪论,特点：在求解过程中，课程之间的先后关系具有图结构的特点，因此用图形结构（网状结构）描述；对图形结构的操作有：创建图结构，按要求将图结构中的顶点进行线性排序。,21,二、数据结构有那些基本结构,根据数据元素间关系的基本特性，有四种基本数据（逻辑）结构：集合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构（层次结构）一个对多个，如树图状结构（网状结构）多个对多个，如图,第一章：绪论,22,数据 广义：是对客观事物的符号表示。计算机科学：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素 表示一个事物的一组数据，数据元素是数据的基本单位。程序中通常作为整体处理，也可称为结点、顶点、记录等。数据项 构成数据元素的最小单位。也称字段或域。,三、数据结构的基本概念,第一章：绪论,23,数据元素,数据项,数据,第一章：绪论,24,数据类型 数据类型：一个类型和定义在该类型上的操作集合 高级语言中指数据的取值范围及其上可进行的操作的总称,三、数据结构的基本概念,第一章：绪论,例 C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体等构造数据类型。,struct student int num;char name20;float score;,25,有四种基本数据逻辑结构：集合、线性结构、树形结构、图状结构,逻辑结构 数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称为逻辑结构。,第一章：绪论,存储结构（物理结构）是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的关系(逻辑结构)。,26,数据的逻辑结构和存储结构的区别：数据的逻辑结构：它与数据的存储无关，是独立于计算机的。数据的存储结构：是逻辑结构在计算机中的实现，它是依赖于计算机的。数据的存储结构有以下几种形式 顺序存储结构 链式存储结构 索引存储 哈希存储,第一章：绪论,27,第一章：绪论,顺序存储结构：定义：将数据元素存储在一块地址连续的空间中。特点：逻辑结构上相邻的数据元素在物理上也相邻。数据间的逻辑关系表现在数据元素的存储位置关系上。案例：,A,B,C,D,用数组存储,28,第一章：绪论,链式存储结构：定义：使用指针将相互关联的数据元素(节点)连接起来。节点：由数据元素域和指针域组成的一个整体。特点：逻辑结构上相邻的数据元素在物理上不一定相邻。数据间的逻辑关系表现在节点的连接关系上。案例：,29,1028,B,1020,A,1010,C,D,1005,h,链式存储,h,1005,存储地址,1010,1020,1028,.,.,30,第一章：绪论,四、数据结构主要研究什么 数据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的课程。,31,总结：,1、什么是数据结构？2、本课程主要研究什么？3、什么是数据的逻辑结构和物理结构?4、数据的逻辑结构有哪几种？存储结构有哪几种形式？,第一章：绪论,32,作业：1、上网或查阅书籍了解数据结构这门课程的学习意义。2、阅读教材第一章1-17页;3、复习上学期学过的C语言课程中的函数、指针，预习结构体知识。,第一章：绪论,Thank you,Neusoft Institute of Information,谢谢,