绪论2013数据结构电子教案c语言版本分析.ppt

1、根据数据结构，主讲人：尹、教材、工具书及课时安排、教材数据结构(语言版)、主编清华大学出版社工具书数据结构-C语言描述耿国华主编高等教育出版社数据结构问题集(语言版)等清华大学出版社课程表理论：50学时实验：14学时考核方法：平时笔试：30%考试：70%， 本书的基本结构分为三个部分：第一部分：第二部分：基本数据结构，包括线性结构线性表、堆栈和队列、字符串、数组和广义表(第25章)； 非线性结构树和图(第6章和第7章)。第三部分：基本技术，包括：搜索技术和排序技术(第9、10和11章)。关于学习数据结构，数据结构课程：数据结构是一门介于数学、计算软件和计算机硬件之间的课程，是一门综合性的专业基

2、础课。图1.1数据结构与其他课程的关系、数据结构课程的学习目标、数据结构课程的教学目标是要求学生学会分析数据对象的特征，掌握数据组织方法和计算机表示方法，从而为应用中涉及的数据选择合适的逻辑结构、存储结构和相应的算法，掌握算法时空分析的技巧，培养良好的编程技能。第一章是绪论。1.教学内容：1 .数据结构的基本概念，如数据、数据元素、数据对象、数据结构和数据类型。2.算法和算法分析性能分析和测量：算法性能标准；空间复杂性的测量；时间复杂度测量2。教学要求：1 .理解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构和物理结构的概念，以及逻辑结构和物理结构之间的关系。了解算法3的定义、特

3、点、时间成本和空间成本。掌握计算句子频率和估计算法时间复杂度的方法。数据结构的基本概念和术语是什么？抽象数据类型的概念算法和算法分析。第1章引言，1.1什么是数据结构，1。学习数据结构的含义和要求。算法和数据结构是计算机科学的两大支柱。计算机科学的定义：早期：研究算法的科学，后来：研究数据的科学，2。数据结构是程序设计的基础程序=数据结构算法-图灵奖获得者：尼克劳斯沃思(瑞士)数据结构是设计操作系统、数据库管理系统、编译等系统程序和各种应用程序的重要基础。首先，了解数据结构的含义和要求。3.数据结构是计算机专业的一门综合性专业基础课，是计算机专业本科生的必修课，是计算机研究生入学考试的必修课，

4、是软件人才水平考试的内容，是主要软件公司的面试内容。首先，要了解数据结构的意义和要求，需要掌握各种基本的数据结构类型和相应的存储结构，以提供读写给定问题的算法的能力。选择合适的数据结构，并能够设计和分析算法。非数值计算问题：示例1电话号码查询问题：(1)顺序存储模式：遍历表(2)按姓氏索引模式：根据该表的结构和存储模式，为索引编写一个好的搜索算法。电话号码表的结构和存储方式决定了搜索的效率。非数值计算问题：例1电话号码查询问题：例2田径比赛日程安排问题(无向图着色问题):有六个比赛项目，规定每个运动员最多可以参加三个项目，并且有五个人报名参加比赛(如下表所示)。设计比赛日程，在最短的时间内完成

5、比赛。非数值计算问题：(1)让下面六个不同的代码代表不同的项目：跳高、跳远、标枪、100米、a、b、c、d、e、f (2)让顶点代表不能同时竞争的项目之间的一方。(3)某个运动员的比赛项目必须有边相连(他们不能同时比赛)。非数值计算问题解决田径比赛时间安排的问题，A，E，B，F，D，C，只需要安排四个单位的时间来比赛，例3要在N个城市之间建立一个通信网络，如何在保证N个城市连通性的前提下节省最多的资金？图1:六个城市的距离图，解决非数值计算的问题：主要考虑设计合适的数据结构和相应的算法。也就是说，我们应该首先考虑如何表达、组织和存储各种相关信息。因此，可以认为数据结构是研究非数值计算编程问题中

6、计算机的操作对象、它们之间的关系和操作的一门学科。提出的问题是：一百支钢笔一百元(一支钢笔3元，一支圆珠笔2元，一支铅笔0.5元)。问：购买计划是什么？解决方案1:采用三层循环，内循环超过100万次(101 * 101 * 101=1030301)为(x=0)；x=100x)表示(y=0；y=100y)表示(z=0；z=100z)if (x y z=100)x=20；x)表示(y=0；y=34-x；y)如果(3 * x 2 * y 0.5 *(100-x-y)=100)打印f(%d，%d，%d ，x，y，z)；结果：优化后，内循环为525次，仅运行2秒，相差1500次。思考：它能再次优化吗？2

7、.数据结构课程的形成与发展：形成阶段：20世纪60年代初，与“数据结构”相关的内容分散在操作系统、编译原理、表格处理语言等课程中。1968年，“数据结构”被纳入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念在不断扩展，包括网络、集合代数理论和关系等“离散数学结构”的内容。20世纪70年代末，中国的大学相继开设了这门课程。数据结构课程的位置：1.2基本概念和术语几个概念：数据):是信息的符号表示。在计算机科学中，它指的是可以输入计算机并由计算机程序处理的所有符号。数据元素):是数据的基本单位，通常在计算机程序中作为一个整体来考虑和处理。一个数据元素可以由几个数据项组成。数据项是不可

8、分割的最小数据单元。数据对象：具有相同属性的数据元素的集合。是数据的子集。例如，整数数据对象的集合可以表示为N0，1，2。并且该组字母字符数据对象可以表示为c=a，b，z。例如，学生卡记录表，数据结构定义1是彼此具有一个或多个特定关系的数据元素的集合。形式定义：数据结构是一个二进制的Data_Structure=(D，R)，其中D是一组有限的数据元素，R是D上的一组关系，而数据结构定义2一批按照一定的逻辑关系组织起来的数据(或一组具有结构的数据元素)应用计算机语言，并根据一定的存储表示将它们存储在计算机内存中，并在其上定义一组操作。具体来说，数据结构包括三个方面，即数据的逻辑结构、数据的存储结

9、构和应用于数据的操作(operations)。这三个方面之间的关系如下：(1)数据的逻辑结构独立于计算机，并固有于数据本身。(2)记忆结构是逻辑结构在计算机记忆中的形象，它必须依赖于计算机。(3)操作是指集体应用的一组操作。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存储结构。逻辑结构-分区方法1。集合结构中的数据元素除了属于同一类型之外，没有其他关系。其次，线性结构中的数据元素之间存在一对一的关系。3.树结构中的数据元素之间存在一对多的关系。4.图结构或网络结构中的数据元素之间存在多对多的关系。计算机中数据结构的表示(或图像)称为数据存储结构，也称为物理结构。有四种基本存储方法：(1)顺序存储方法(顺序存储结构)；(2)链接存储方法(链式存储结构)；(3)索引存储方法；(4)哈希存储方法。同一逻辑结构可以使用不同的存储方法(以上四种方法中的一种或组合)，这主要考虑了操作的方便性和算法的时间和空间要求。在顺序存储结构：中，数据元素之间的逻辑关系由数据元素在存储器中的相对位置来表示。链式存储结构：在每个数据元素中添加一个指针来存储地址，并使用这个指针来表示数据元素之间的逻辑关系。数据逻辑结构、数据存储结构、数据操作：检索、排序、插入、删除、修改等。线性结构、非线性结构、顺序存储、