数据结构项目教程项目一

数据结构项目教程主讲人：***电话：****邮箱:******教学概要•数据结构课程的性质：•数据结构是计算机及相关专业的一门专业必修核心课程，在整个计算机科学体系中占有重要地位。是培养程序员、软件设计师、系统分析师等一门重要的课程。•主要教学内容：•本书主要讲授数据结构的基础知识，线性表、对队、栈、二叉树、图、排序和查找的基础知识。•本书教学重点、难点：•重点：二叉树•难点：图•学习方法：•学好此课程，需要有较好的逻辑思维能力，需要逐步掌握分析问题，解决问题的方法与步骤。•多进行上机操作训练，把书上的项目变成自己掌握的知识•多进行网上搜索学习。•不懂不多问，记住老师的联系方法，多与教师相互研讨•学习要求：•严格出勤，完成相应的项目与任务•考试形式：•本课程考试采取*****考试形式，其中理论成绩占总成绩****分，实验成绩****分，平时成绩占****分。项目一认识数据结构与算法•项目目标•★知识目标•（1）理解和掌握结构中的基本概念•（2）理解和掌握线性结构、树形结构和图形结构的概念和二元组的表示方法•（3）理解算法评价的规则，算法时间复杂度和空间复杂度的概念和数量级的表示方法•★技能目标：•（1）具有对现实世界的数据进行抽象表示的能力•（2）具有对算法时间复杂度和空间复杂度进行简单分析的能力•★素质目标：•（1）培养正确的认识计算机中数据的表示与存储方法。•（2）培养团队协作精神•（3）培养分析问题解决问题的能力•教学内容：•任务1：简单学生成绩管理系统•任务2学生成绩统计•任务3学生成绩查询•教学重点：•数据结构的基本概念、数据的逻辑结构、数据的存储结构•教学难点：•算法描述、算法分析•教学时数：•理论：***节，实验***节，自学***节任务1简单学生成绩管理系统•任务简介•设计一个简单的学生成绩管理系统，能存储学生的学号、姓名及各科成绩，并进行输出。•任务分析•要存储学生的学号、姓名及各科成绩，可以利用C语言提供的结构体(构造体)数据类型来实现。然后进行输入存储在结构体类型中。再进行输出。•任务实现•如今，互联网正在改变着人们传统的生活方式，在云计算机和大数据时代，计算机处理的对象不仅是简单的数值和字符，而且还包括文本、图形、图像、声音、视频等多媒体数据，其数据的结构也变得愈加复杂，这就给程序设计带来了一些新的问题。•为了设计编写一个性能良好的程序，不仅要根据实际情况掌握至少一种适合的计算机高级语言或开发工具，更重要的是研究数据的不同结构和组织方法以及进行数据处理的不同算法，通过分析和比较选择出较好的设计方案。这正是数据结构这门课程所要解决的问题。子任务1：数据结构课程的地位•数据结构是计算机及相关专业的一门专业必修核心课程，在整个计算机科学体系中占有重要地位，也是全国计算机专业考研的一门专业基础课程。是培养程序员、软件设计师、系统分析师等一门重要的课程。•数据结构课程涉及多方面的知识，如计算机硬件范围内的存储装置与存取方法，软件范围中的文件系统，数据的动态管理，信息检索、数据表示，云计算机与大数据等。数据结构课程也是后继课程如操作系统、数据库原理、编译原理、人工智能、云计算机与大数据等课程的先修课程。•数据结构课程不仅讲授数据在计算机中的组织与表示方法及相关运算，更重要的是培养学生提高分析问题和解决问题的能力，培养良好的计算机科学的职业素养子任务2什么是数据结构•例1.1学生信息登记表线性结构•例1.2计算机存储设备文件目录结构树形结构•例1.3Internet网络系统问题图形结构•综合以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。•数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等的学科。•数据结构研究的主要内容：•(1)对所加工的对象进行逻辑组织。•(2)把加工对象存储到计算机中去。•(3)数据运算。子任务3数据结构的基本概念•1.数据（Data）•是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称•2.数据元素（DataElement）•是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理•一个数据元素可包含一个或多个数据项(DataItem)。数据项是数据的不可分割的最小单位•3.数据对象（DataObject）•性质相同的数据元素的集合，是一个数据的子集•4.数据类型（DataType）•一组性质相同的值的集合以及定义于这个值的集合上的一组操作的总称•5.数据结构（DataStructure）•指相互之间存在一种或多种特定关系的数据元素的集合。它是按照某种关系把数据组织起来，以一定的存储方式把它们存储在计算机存储中，并依据此数据定义了一个运算的集合。在任何问题中，数据元素都不是孤立存在的，而是它们之间存在某种关系，数据元素之间的这种相互关系就称为结构。•数据结构的形式定义为：数据结构是一个二元组•Data_Stru=(D,S)•其中D是数据元素的有限集合，S是D上关系的有限集合。•例1.4假设需要编制一个事务管理系统，管理学校科学研究课题小组的各个项事务，则首先要为程序的操作对象——课题小组设计一个数据结构，假设每个小组由1位教师组成、1-3名研究生组成及1-6名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。由可以如下定义数据结构：Group=（D,S）其中D={T,G1,…,Gn,S11,…,Snm}其中1≤n≤3,1≤m≤2;R={R1,R2}R1={T,Gi|1≤i≤n};R2={Gi,Sij|1≤i≤n,1≤i≤m}任务2学生成绩统计•任务简介•此任务要求在任务1基础上实现对学生的成绩求平均值，并进行输出。•任务分析•利用结构体对学生信息进行存储后，读取学生成绩信息，进行累加求和，再计算平均值。通过此任务，明确学生数据的逻辑结构与在计算机中的存储结构。•任务实现•程序运行结果子任务1数据的逻辑结构•数据的逻辑结构是指数据元素之间的逻辑关系。常见的逻辑结构有集合结构、线性结构、树形结构和图结构。•1.集合结构（SetStructure）：在该逻辑结构中，只有数据元素集D，而关系集为空集，即R={}。也就是说，结构中的数据元素除了同属于一个集合外，数据元素之间没有其他关系。•2.线形结构（LineStructure）：•在该结构中，除了第一个元素（记录）外，其他各元素（记录）都有唯一的前驱；除了最后一个元素（记录）外，其他各元素（记录）都有唯一后继；第一元素无前驱，最后一个元素无后继。数据各元素之间存在一对一的关系，在后面章节中研究的线性表、队列、栈等属于线性结构。•3.树形结构（TreeStructure）：•在该结构中，有且只有一个根结点，其余所有结点有且只有一个唯一的前驱，但可以有多个后继结点。数据中各元素之间存在一对多的关系，如一个组织机构的领导管理模式、一个家族的血缘关系等。在后面章节研究的树、二叉树就属于树形结构。•4.图形结构（GraphStructure）:•在该结构中，各元素之间可以有多个前驱和多个后继。数据中各元素之间存在多对多的关系。如一个城市之间的道路交通，是一种图形结构子任务2数据的存储结构•数据的存储结构又称为数据的物理结构（DataPhysicalStructure），•是数据在计算机中的存储表示，它包括数据本身在计算机中存储方式，以及数据之间的逻辑关系在计算机中的表示。因此，数据的存储结构是依赖于计算机的。•1.顺序存储结构•该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑结构以存储单元的邻接关系来体现，由此得到的存储方式表示称为顺序存储结构（SequentialStorageStructure），通常顺序存储结构是借助于程序语言的向量来描述的。该方法主要用于线性的数据结构•2.链式存储结构•该方法不要求逻辑上相邻的结点其物理位置上相邻，结点间的逻辑关系是由附加的指针表示的，由此得到的存储表示称为链式存储结构（LinkedStorageStructure），通常要借助于程序语言的指针类型来描述它•3.索引存储结构•该存储方法是指在存储结点的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：(关键字，地址)，关键字能唯一标识一个结点的数据项•稠密索引（DenseIndex）•稀疏索引（SparseIndex）•4.散列存储结构•该存储方法的基本思想是根据结点的关键字直接计算该结点的存储地址。任务3学生成绩查询•任务简介•根据任务1中简单的学生成绩管理系统，实现输入一个学生的学生学号，查询这个学生的相关信息。•任务分析•学生成绩的查询是指根据关键字查找匹配的相关信息。不同的查询方法，程序执行的效率会不一样。这里只是用一个简单的顺序查询方法实现，更多的查询方法以后面章节中用专门讲解。•任务实现•程序运行结果子任务1算法定义与特征•算法（Algorithm）•是对特定问题求解步骤的一种描述。通俗地讲，一个算法就是一个求解问题的方法。更严格地说，算法是由若干条指令组成的有限序列，其中每一条指令表示一个或多个操作。•算法特征：•1.有穷性•2.确定性•3.可行性•4.输入•5.输出•算法的含义与程序区别子任务2算法描述•算法可以使用各种不同的方法来描述•自然语言•程序流程图•N-S图•程序设计语言•伪代码语言•举例说明子任务3算法分析•评价一个算法:•主要考虑如下三点：•（1）执行算法所耗费的时间。•（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。•（3）算法应当易于理解，易于编码，易于调试等等。•选用一个存储空间小、运行时间短、其性能也好的算法。然而，实际上很难做到十全十美•因此我们只能根据具体情况有所侧重。若该程序使用次数较少，则力求算法简明易懂，易于转换为机器可执行的程序。对于反复多次使用的程序，应尽可能选用快速的算法。•1.时间复杂度•一个算法所耗费的时间，应该是该算法中每条语句执行时间之和，而每条语句的执行时间是该语句的执行次数（也称为频度（FrequencyCount））与该语句一次执行所需时间的乘积。•我们假设每条语句一次执行所需时间是单位时间•一个算法的时间耗费就是该算法中所有语句的频度之和•该算法中所有语句的频度之和（即算法的时间耗费）为•T(n)=2n3+3n2+2n+1•上述算法的时间复杂度为O(n3)•例1.6分析下列程序段的时间复杂度•for(i=0;i=n;i++)•{•sum=sum+i;•}例1.7分析下列程序段的时间复杂度i=s=0;while(sn){i++:s+=i;}•2.算法的空间复杂度•一个算法的空间复杂度记作S(n)，是指该算法在运行过程中所耗费的辅助存储空间，它也是问题规模n的函数。若一个算法所耗费的辅助空间与问题规模n无关，记作s(n)=O(1)。•算法所耗费的存储空间包括3部分，即算法本身所占用的存储空间、算法的输入/输出所占用的存储空间和算法在运行过程中临时占用的辅助存储空间项目小结•数据结构课程是计算机及相关专业的一门专业必修核心课程，在整个计算机科学体系中占有重要地位，学好此门课程对后继课程的学习非常重要。本项目讲解了数据结构课程的地位、数据结构的基本概念，数据结构研究的主要内容是数据的逻辑结构、数据的存储结构及其运算。数据的逻辑结构主要有线性结构、树形结构和图形结构。数据的存储结构主要有顺序存储、链式存储、索引和散列存储等。在书写算法时，需要考虑算的时间复杂度和空间复杂度，需要学会对一个算法的时间复杂度和空间复杂度进行分析，从而减少一个算法的时空量，提高算法效率。作业：•P12-24:•1-4题