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

1数据结构NeusoftInstituteofInformationITEducation&Training1数据结构NeusoftInstituteofInf2

姓名：李德光

系部：计算机系

办公地址：

C7201

E--mail:lideguang@一、自我介绍第一章：绪论2姓名：李德光一、自我介31、为什么要学习《数据结构》在本专业中的地位：数据结构是主修课，4个学分,是后续课程的基础毕业后工作的需要面试题中主要考数据结构的内容工作中经常会用到数据结构的知识二、课程介绍第一章：绪论程序＝数据结构＋算法31、为什么要学习《数据结构》二、课程介绍第一章：绪论程序＝42、如何学习《数据结构》学好理论，掌握算法

—要想做与数据结构相关的项目，就必须首先掌握数据结构的各项知识和技能。将算法用一种程序设计语言实现

—数据结构有比较多的概念和知识点，因此要多编程，多实践，以加深对这些概念的理解二、课程介绍第一章：绪论42、如何学习《数据结构》二、课程介绍第一章：绪论53、数据结构和编程语言(C语言)的关系

数据结构：是一个概念和理论的集合

编程语言：对这些概念和理论进行实现，以便于在软件项目中使用。第一章：绪论数据结构C语言Java语言……实现关系53、数据结构和编程语言(C语言)的关系第一章：绪论数据结构64、课程讲述内容第一章绪论第二章线性表第三章栈和队列第四章串第六章树和二叉树第七章图

第九章查找第十章内部排序第一章：绪论64、课程讲述内容第一章：绪论75、课程教学目标⑴理解三种数据结构：线性结构、树形结构和图形结构；掌握典型算法的基本思想。⑵能将常用算法用c语言程序实现并运行正确，加深理解数据结构。⑶灵活运用各种数据结构，设计高效的算法解决实际问题第一章：绪论75、课程教学目标第一章：绪论81、考核方法：三、考核方法第一章：绪论平时成绩60％出勤率10％平时作业、测试40％课堂表现10％期末考试40％授课的课时：4学时/周81、考核方法：三、考核方法第一章：绪论平时成绩60％出勤91、座位前排不留空，后排不坐人四、课堂要求第一章：绪论看视频、打游戏，扣分如下：第1次违纪写不少于3000字检讨！第2次违纪平时考勤和课堂表现按0分记！第3次违纪，本门课程不合格！其余课堂违纪现象（例如戴耳机、玩手机）视其情节具体扣除1-10分。旷课1次扣10分，旷课次数达到5次，本门课程不合格！迟到5分钟扣2分，迟到10分钟扣5分，超过10分钟扣10分。2、课堂违纪处理：91、座位前排不留空，后排不坐人四、课堂要求第一章：绪论看视10第一章绪论

本章主要介绍以下内容数据结构研究的主要内容数据结构中涉及的基本概念算法的概念、描述方法以及评价标准10第一章绪论本章主要介绍以下内容11要能回答的问题1.什么是数据结构？2.数据结构有那些基本结构？3.什么是数据的物理结构和逻辑结构？4.数据结构主要研究什么？5.算法与程序的区别？6.算法的特性及其评价标准？第一章：绪论11要能回答的问题1.什么是数据结构？第一章：绪论12一、什么是数据结构数据结构数据结构（关系）第一章：绪论计算机科学：数据指所有能够输入到计算机中并被计算机程序处理的符号集合。12一、什么是数据结构数据结构数据结构（关系）第一章：绪论计13第一章：绪论数据的表现形式简单数据（数字、字符、非数字字符）例如：学号(20020001);年龄（18）；姓名（王红）；照片复杂数据

例如：学生（20020001、王红、男、18）；

学生信息表学号姓名性别年龄20020001王红男1820020002张明男1920020003吴宁女1813第一章：绪论数据的表现形式学号姓名性别年龄200200014一、什么是数据结构第一章：绪论因此,数据结构是指具有某种联系的数据元素以及元素之间所构成的各种关系的集合。14一、什么是数据结构第一章：绪论因此,数据结构是指具有某种15二、数据结构有那些基本结构应用举例1——学籍档案管理

假设一个学籍档案管理系统应包含如下表所示的学生信息。第一章：绪论15二、数据结构有那些基本结构应用举例1——学籍档案管理第一16

特点：

l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；l 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；l 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。第一章：绪论16特点：第一章：绪论17应用举例2——Windows文件系统第一章：绪论我的电脑C：\MydocumentWindowsD：\Jdk1.5eclipse17应用举例2——Windows文件系统第一章：绪论我的电脑18特点：l在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构（层次结构）；l对它的操作有：建立树形结构，输出最低层结点内容等等。第一章：绪论18特点：第一章：绪论19第一章：绪论应用举例3——专业课程的开设软件技术专业课程的开设情况：课程编号课程名称需要先修的课程编号C1计算机文化基础无C2Java语言(初级)C1C3数据结构(Java版)C1C4Java语言(中级)C2，C3C5数据库原理及应用C3C6Java语言(高级)C4C7脚本语言C1C8JavaWeb程序设计C5，C6，C719第一章：绪论应用举例3——专业课程的开设软件技术专业课程20第一章：绪论特点：在求解过程中，课程之间的先后关系具有图结构的特点，因此用图形结构（网状结构）描述；对图形结构的操作有：创建图结构，按要求将图结构中的顶点进行线性排序。

C6C1C2C7C4C3C5C820第一章：绪论特点：C6C1C2C7C4C3C5C21二、数据结构有那些基本结构根据数据元素间关系的基本特性，有四种基本数据（逻辑）结构：集合——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构（层次结构）——一个对多个，如树图状结构（网状结构）——多个对多个，如图第一章：绪论21二、数据结构有那些基本结构根据数据元素间关系的基本特性，22数据

广义：是对客观事物的符号表示。

计算机科学：指所有能够输入到计算机中并被计算机程序处理的符号集合。

数据元素

表示一个事物的一组数据，数据元素是数据的基本单位。程序中通常作为整体处理，也可称为结点、顶点、记录等。数据项

构成数据元素的最小单位。也称字段或域。

三、数据结构的基本概念第一章：绪论22数据三、数据结构的基本概念第一章：绪论23学号姓名性别年龄20020001王红男1820020002张明男1920020003吴宁女18数据元素数据项数据第一章：绪论23学号姓名性别年龄20020001王红据类型

数据类型：一个类型和定义在该类型上的操作集合高级语言中指数据的取值范围及其上可进行的操作的总称三、数据结构的基本概念第一章：绪论例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体等构造数据类型。structstudent{intnum;charname[20];floatscore;};24数据类型三、数据结构的基本概念第一章：绪25有四种基本数据逻辑结构：集合、线性结构、树形结构、图状结构逻辑结构

数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称为逻辑结构。第一章：绪论存储结构（物理结构）

是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的关系(逻辑结构)。25有四种基本数据逻辑结构：逻辑结构第一章：绪论存储结构（26数据的逻辑结构和存储结构的区别：

数据的逻辑结构：它与数据的存储无关，是独立于计算机的。数据的存储结构：是逻辑结构在计算机中的实现，它是依赖于计算机的。数据的存储结构有以下几种形式

顺序存储结构链式存储结构

索引存储哈希存储第一章：绪论26数据的逻辑结构和存储结构的区别：第一章：绪论27第一章：绪论顺序存储结构：定义：将数据元素存储在一块地址连续的空间中。特点：逻辑结构上相邻的数据元素在物理上也相邻。数据间的逻辑关系表现在数据元素的存储位置关系上。案例：{A,B,C,D}用数组存储ABCD100010011002100327第一章：绪论顺序存储结构：{A,B,C,D}用数组存储A28第一章：绪论链式存储结构：定义：使用指针将相互关联的数据元素(节点)连接起来。节点：由数据元素域和指针域组成的一个整体。特点：逻辑结构上相邻的数据元素在物理上不一定相邻。数据间的逻辑关系表现在节点的连接关系上。案例：28第一章：绪论链式存储结构：291028B1020A1010C∧D1005h数据元素域指针域

A

1020

D∧

……..

…….

B

1028

……..

…….

C1010

链式存储

h1005存储地址101010201028…….…….291028B1020A1010C∧D1005h数据元30第一章：绪论四、数据结构主要研究什么数据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的课程。数据的逻辑结构数据的存储结构数据的操作(算法)：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构30第一章：绪论四、数据结构主要研究什么数据的逻辑结构31总结：1、什么是数据结构？2、本课程主要研究什么？