第1页，共37页，星期日，2025年，2月5日成绩如何评定？平时成绩：40%考勤：10%作业：30%期末考试：60%第2页，共37页，星期日，2025年，2月5日教材和参考书黄国瑜，数据结构（C语言版），清华大学出版社严蔚敏，数据结构，清华大学出版社张瑞军，数据结构（C语言描述），清华大学出版社数据结构基础（C语言版)，[美]EllisHorowitz，清华大学出版社
第3页，共37页，星期日，2025年，2月5日第一章数据结构的基本概念1.1何谓数据结构1.2算法1.3程序结构化设计风格1.4程序分析的方法1.5时间复杂度分析1.6渐进式表示法第4页，共37页，星期日，2025年，2月5日1.1数据结构计算机解决问题的步骤：分析问题，建立数学模型：界定问题的输入输出边界，抽取问题的实质，对问题进行抽象，形成相应的数学模型。确定数据结构：设计合适的数据结构对解决问题所需的数据及数据之间的关系进行存储，描述出其相应的逻辑结构及存储结构。算法设计：根据问题要求和数据结构的特点来选择和设计算法，同时要考虑算法的效率和占用内存空间。编程实现第5页，共37页，星期日，2025年，2月5日1.1数据结构例子：新生入学注册学号的编码规则。采用入学年份+学院编号+专业编号+流水号的编码方式学号姓名学院编号专业编号性别出生年月200805165001赵飞霞5165女1988.5………………学院编号学院名称5管理学院……专业编号专业名称165财务管理……第6页，共37页，星期日，2025年，2月5日1.1数据结构确定数据结构。设计适当的数据格式来存储和表达这些信息算法设计。主要涉及学生信息的增加、删除、修改、查询等操作程序设计第7页，共37页，星期日，2025年，2月5日1.1数据结构数据结构这门学科主要完成以下工作：数据集合中个数据元素之间的逻辑关系，即数据的逻辑结构在对数据集合进行访问和处理时，个数据元素在计算机物理介质中的实际存储，即数据的物理结构对数据集合中个数据元素的各种运算第8页，共37页，星期日，2025年，2月5日1.1数据结构数据：对客观事物的符号表示，它描述客观事物的数值、字符等所有输入到计算机中并能被计算机所接受和处理的符号的集合数据类型：程序语言中变量所能表示并存储的数据种类在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义第9页，共37页，星期日，2025年，2月5日1.1数据结构数据对象（数据实体）：是性质相同的数据元素的集合。是数据的一个子集。整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}数据结构：数据实体中元素之间的关系，包括数据的表示法（逻辑结构和存储结构）和运算数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。第10页，共37页，星期日，2025年，2月5日1.1数据结构数据的逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合：结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构：结构中的数据元素之间存在一对一的关系。三、树状结构：结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构：结构中的数据元素之间存在多对多的关系。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。第11页，共37页，星期日，2025年，2月5日1.2算法数据结构与算法是有紧密联系的。对于某一问题，如果使用计算机求解，其本质上是对某一种或几种数据结构施加一些运算。程序=数据结构+算法算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。第12页，共37页，星期日，2025年，2月5日1.2算法算法是指为了完成某项特定工作所设计出的一连串用来说明工作是如何被完成的步骤。算法必须满足下列几个条件：输入：有零个或多个输入数据输出：具有一个以上的结果输出定义明确：每一个步骤的语句必须很明确，不允许有二义性有限性：对所有情形都能在执行有限步之后结束有效性：每一个步骤必须是基本的、可执行的（feasible）指令（即使是用纸和笔也可以完成计算）第13页，共37页，星期日，2025年，2月5日1.2算法用来写算法的方式：条列式的步骤流程图：以图形