文章目录
前言
一、与数据结构相关的概念的介绍
1、数据结构的定义
2、数据、数据元素、数据项、数据对象及其关系
3、数据结构的两个层次——逻辑结构与存储结构
（3）数据的运算
（4）数据结构的三要素
（5）数据类型
二、抽象数据类型的表现与实现
1、抽象数据类型的定义
2、抽象数据类型的描述方法
三、算法与算法分析
1、算法定义及其特性
2、算法的分析
总结
前言
数据结构第一章绪论的内容，主要包括与数据结构相关的概念的介绍、对数据结构三要素的理解、抽象数据类型、算法以及算法分析。
一、与数据结构相关的概念的介绍
1、数据结构的定义
（1）从学科意义上——数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
（2）从概念定义上——数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（换句话说，数据结构就是带“结构”的数据元素的集合。这个“结构”指的就是元素之间的关系。）
2、数据、数据元素、数据项、数据对象及其关系
（1）数据——所有能输入到计算机中去的描述客观事物的符号。包括数值型数据和非数值型数据。
（2）数据元素——数据的基本单位，也成为结点或者记录。
（3）数据项——数据的最小单位，也成为域。
（4）三者之间的关系——数据>数据元素>数据项。（例如学生花名册>学生个人信息>学号）
（5）数据对象——相同特性数据元素的集合，是数据的一个子集。
3、数据结构的两个层次——逻辑结构与存储结构
（1）逻辑结构——数据元素间抽象化的相互关系，与数据的存储无关，独立与计算机，它是从具体问题抽象出来的数学模型。（说白了就是元素之间的关系）
划分方法有两种。
一种是分为线性结构和非线性结构。
线性结构——有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 例如：线性表、栈、队列、串。
非线性结构----一个结点可能有多个直接前趋和直接后继。 例如：树、图。
一种是按照元素间的关系分为四种结构。
集合——数据元素间除“同属于一个集合”外，无其它关系
线性结构——一个对一个，如线性表、栈、队列
树形结构——一个对多个，如树
图形结构——多个对多个，如图
（2）存储结构（物理结构）——数据元素及其关系在计算机存储器中的存储方式。（怎么在计算机中存储这几个元素还有他们之间的关系）
可分为两种结构。
顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。
链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系。
（3）数据的运算
逻辑结构和存储结构都相同，但运算不同，则数据结构不同。
对于一种数据结构，常见的运算有——排序、插入、删除、修改、查找
（4）数据结构的三要素
逻辑关系（唯一）、存储结构（不唯一）、运算的实现（依赖于存储结构）
（5）数据类型
数据类型是一组性质相同的值的集合，以及定义于这个集合上的一组运算的总称。
例如，C语言中：
基本数据类型：char int float double voi
构造数据类型：数组、结构体、共用体、文件
用户也可用typedef自己定义数据类型。
typedef struct{
int num;
char name[20];
float score;
}STUDENT;
STUDENT stul,stu2, *p;
二、抽象数据类型的表现与实现
1、抽象数据类型的定义
抽象数据类型——指一个数学模型以及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。
例：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型。
数据结构+定义在此数据结构上的一组操作=抽象数据类型
2、抽象数据类型的描述方法
（1）形式定义——ADT= (D, S, P) 其中D为数据对象，S为D上的关系集，P为D上的操作集。
（2）常用定义格式：
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT抽象数据类型名
基本操作的定义格式：
基本操作名（参数表）1.赋值参数 2.引用参数，以“＆”打头
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉
注：
1.赋值参数只为操作提供输入值2.引用参数，以“&”打头，除可提供输入值外，还将返回操作结果。
3、传递引用给函数与传递指针效果是一样的，形参变化，实参也发生变化。&
4、引用类型作形参，在内存中并没有产生实参的副本，它直接对实参操作，而一般变量作参数形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本
5、指针参数虽然也能达到使用引用效果，但在被调函数中使用“*指针变量名”的形式进行运算，很容易产生错误且程序的阅读性较差，另一方面在主调函数的调用点处，必须用变量地址作为实参
数据元素被约定为ElemType类型，用户需要根据具体情况自行定义该数据类型。
（3）举例：
例：抽象数据类型三元组的定义：
（下面所提到的基本操作中的InitTriple以及Get等都可以理解为我们所要写的函数的函数名，而操作结果就是我们所写的函数所要有的功能。在实际写代码的时候以下这些是不用写的。）
ADT Triplet{
数据对象：D={e1,e2,e3|e1,e2,e3∈Elemset}
数据关系：R1={,}
基本操作：
InitTriplet(&T,v1,v2,v3)
操作结果：构造了三元组T，元素e1，e2和e3分别被赋以参数v1,v2和v3的值。
Destroy Triplet (&T)
操作结果：三元组T被销毁。
Get (T,i,&e)
初始条件：三元组T已存在，1<=i<=3.
操作结果：用e返回T的第i元的值。
Put(&T,i,e)
初始条件：三元组T已存在，1<=i<=3
操作结果：改变T的第i元的值为e。
IsAscending(T)
初始条件：三元组T已存在。
操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。
三、算法与算法分析
1、算法定义及其特性
（1）算法的定义——一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。
（2）算法的特性
输入：有0个或多个输入
输出：有一个或多个输出（处理结果）
确定性：每步定义都是确切、无歧义的
有穷性：一个算法必须总是（对任何的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。（算法应在执行有穷步后结束）
可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
（3）算法的评价
正确性——算法应当满足具体问题的需求。a.程序不含语法错误；b.程序对于几组输入数据能够得出满足规格说明要求的结果；c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满意规格说明要求的结果；d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
可读性
健壮性——当输入数据非法时，算法也能适当地做出反应或者进行处理，而不会产生莫名其妙的输出结果。
效率与低存储量需求——执行时间短，所需存储量低。
2、算法的分析
以该基本操作重复执行的次数作为算法的时间量度。
算法的时间量度记作T(n)=O(f(n)),称为时间复杂度。常见的有O(1),O(n),O(n²),O(log n)。
空间复杂度 S(n)=O(f(n))。包括输入数据所占空间、程序本身所占空间、辅助变量所占空间。
总结
数据结构第一章绪论的内容，主要包括与数据结构相关的概念的介绍、对数据结构三要素的理解、抽象数据类型、算法以及算法分析。
