C语言第一章详解ppt课件.ppt

《C语言第一章详解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructuresLec1概述1算法+数据结构=程序——尼克劳斯·沃斯（NiklausWirth）2关于本课程课程性质：必修课时：30+30考核方式：笔试成绩(60%)+课程实验成绩(30%)+作业成绩(10%)3课程定位数据结构学科的地位•综合性的专业基础课•介于数学、计算机硬件和计算机软件之间的核心课程•不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础•本课程的先修课程：离散数学、C语言•本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等4知识点测试需要提前掌握的内容熟练掌握

2、C编程语言，特别是结构体、指针、函数、数组，能设计简单的算法；掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念，熟练应用反证法和数学归纳法等数学证明方法。测试设计一个算法，顺序读入的三个整数X,Y和Z，然后按照从大到小的顺序依次输出。T(n)=T(n/2)+C,T(1)=0，将T(n)表示为n的表达式5本课程的内容框架数据结构基础数据结构应用数据结构非线性结构线性结构线性表栈队列串数组广义表树二叉树图查找内部排序外部排序文件动态存储管理6第一章概述本章内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.

3、2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求71.1什么是数据结构1.用来组织数据的理论和具体方法，使得数据可以高效地存储和操作2.应用这些数据结构设计高效的算法示例有3000个文本文件，平均每个文件有20行，每行10个单词，从这些文件中找出所有"hello"出现的地方。假设比较一个单词是否和“hello”匹配需要1秒，应该如何解决这个问题，解决方案完成这项任务需要多少时间？8方案1：顺序比较每个单词3000*20*10*1=600000秒≈166小时方案2：对单词进行排序采用折半（二分）查找方法例如：在数字序列[5812151517232527]中查找25

4、25?15151723252725?2323252725?25此时完成刚才的任务需要log2600000=19秒91.1什么是数据结构计算机解决问题的过程具体问题数学模型抽象建模数据结构数据结构算法数据结构算法分析与设计程序设计程序问题求解描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。101.1什么是数据结构非数值型计算问题举例：学籍管理(信息处理类问题)学生信息：课程信息：选课信息：SnoCnoGrade95001c19295001c26595002c29095002c573SnoSnameSsexSageSdept95001李勇男20CS95002

5、刘晨女19IS95003王敏女18MA95004张立男19ISCnoCnameCreditc1数据库4c2数学4c3信息系统4c4操作系统3c5数据结构4c6编译原理3111.1什么是数据结构非数值型计算问题举例：博弈类问题S0S11S10S1n……………………SK1Sqr……SK1Sqr……SK1Sqr……121.1什么是数据结构非数值型计算问题举例：最短路径问题西安上海北京成都武汉广州14008006002000120010006008001000131.1什么是数据结构什么是数据结构数据结构是一门研究非数值计算的程序设计问题中计算机操作的对象（数据）间的逻辑结构和物理结构以及它

6、们之间相互关系，对这种结构进行定义并实现相应运算的学科。141.2基本概念和术语基本概念数据(Data)：指所有能输入到计算机中并被计算机程序加工处理的符号的总称。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等能通过编码而被加工的数据形式。数据元素(DataElement)：数据的基本单位，数据集合中的元素。数据项(DataItem)：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。数据对象(DataObject)：性质相同的数据元素的集合，是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。151.2基

7、本概念和术语逻辑结构内涵：数据元素之间的关系，或称为“结构”。分类：集合：松散的关系线性结构：一对一的关系树形结构：一对多的关系网状结构：多对多的关系描述性定义：用自然语言描述相互之间存在一种或多种特定关系的数据元素的集合。•形式化定义：Data_Structure=（D，S）D={数据元素的有限集合}S={数据集D上关系的有限集合}161.2基本概念和术语存储结构(物理结构)：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：顺序存