数据结构C语言版讲义

下载后可任意编辑第一章 绪论第一节 什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。 数学模型：用符号、表达式组成的数学结构，其表达的内容与所讨论对象的行为、特性基本一致。信息模型：信息处理领域中的数学模型。 数据结构：在程序设计领域，讨论操作对象及其之间的关系和操作。忽略数据的具体含义，讨论信息模型的结构特性、处理方法。第二节 概念、术语一、有关数据结构的概念 数据：对客观事物的符号表示。 例：生活中还有什么信息没有被数字化？ 身份证，汽车牌号，电话号码，条形代码…… 数据元素：数据的基本单位。相当于"记录"。 一个数据元素由若干个数据项组成，相当于"域"。 数据对象：性质相同的数据元素的集合。 数据结构：相互之间存在特定关系的数据集合。 四种结构形式：集合、线性、树形、图(网)状 形式定义：(D，S，P) D：数据元素的集合(数据对象) S：D 上关系的有限集 P：D 上的基本操作集 逻辑结构：关系 S 描述的是数据元素之间的逻辑关系。 存储结构：数据结构在计算机中的存储形式。 顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系： 逻辑结构：描述、理解问题，面对问题。 存储结构：便于机器运算，面对机器。程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念 数据类型：值的集合和定义在该值集上的一组操作的总称。1下载后可任意编辑 包括：原子类型、结构类型。 抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。 核心：是逻辑特性，而非具体表示、实现。课程任务：学习 ADT、实践 ADT。如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……实践指导：为了代码的复用性，采纳模块结构。 如：C 中的头文件、C++中的类第三节 ADT 的表示与实现本教材中，算法书写习惯的约定。数据元素类型 ElemType：int,float,char, char[] ……引用参数 &算法：void add(int a,int b,int &c) { c=a+b; }程序：void add(int a,int b,int *p_c){ *p_c=a+b; }第四节 算法的描述及分析一、有关算法的概念 算法：特定问题求解步骤的一种描述。 1)有穷性 2)确定性 3)可行性二、算法设计的要求好算法： 1)正确性 2)可读性 3)健壮性 4)高效，低存储三、时间复杂度 事前估算：问题的规模，语言的效率，机器的速度 时间复杂度：在指定的规模下...