数据结构c语言第1章--绪论

第1章绪论教学目的和要求：•了解数据结构的基本概念。•了解算法分析的基本概念和基本方法。重点和难点：•数据结构的基本概念及各种常见数据结构。•时间复杂度的概念。1.1什么是数据结构英文名：DataStructure本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。计算机处理问题的分类1.数值计算问题运算对象是简单的整型、实型或布尔型数据，数学模型是数学方程。例游泳池的长len和宽wide，求面积area。（1）建立数学模型问题涉及的对象：游泳池的长len宽wide，面积area；对象之间的关系：area=lenwide（2）设计求解问题的方法——算法（3）编程main(){intlen,wide,area;scanf(“%d%d%\n”,&len,&wide);area=len*wide;printf(“area=%d”,area);}（4）调试程序，测试程序，得出结果数值计算类问题：计算机主要是进行大量的算术运算。2.非数值计算问题运算对象包括字符、文字、图形、图像、语音等。数据元素之间的相互关系一般无法用数学方程加以描述。主要考虑的是对相关的各种信息如何表示、组织和存储，即数据结构。例1某班学生基本情况登记表线性表非数值计算的程序设计问题举例表学生基本情况登记表001003002004006005008007学生间学号顺序关系是一种线性结构关系设表中的记录是按学生的学号顺序排列学号姓名专业政治面貌001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机党员……………………008刘亮计算机党员①数据模型二维表②算法结点例2家族的族谱树假设某家族有10个成员：A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。特点：分层多支结构JIACBDHGFE图家族树①数据模型树（层次）结构②算法博弈树问题—游戏例3交通咨询问题在交通咨询系统中，我们可以采用一种图的结构来表示实际的交通网络。图图交通网AEDBCF3010020601051050①数据模型图结构②算法染色问题1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数字；字符串；声音；图像；视频……1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素：数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。数据可以由1到n个数据项构成。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素：数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。数据可以由1到n个数据项构成。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素：数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。数据可以由1到n个数据项构成。数据项：是数据不可分割的最小单位。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素：数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。数据可以由1到n个数据项构成。数据项：是数据不可分割的最小单位。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素：数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。数据可以由1到n个数据项构成。数据项：是数据不可分割的最小单位。数据对象：是性质相同的数据元素的集合，是数据的一个子集。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。等价定义：数据结构是一种数据对象，其中的数据元素相互之间具有一种或者多种特定的关系。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。教师基本信息表假设我们要编制一个程序，用以存储和查询教师的基本信息。请问数据对象、数据元素、数据项各指什么？1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。教师基本信息表数据对象1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。教师基本信息表数据元素1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。教师基本信息表数据元素中的每一项都是数据项1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。1.2基本概念和术语本书的定义：是相互之间存在一种或者多种特定关系的数据元素的集合。（1）关系：数据元素a和数据元素b有某种关系R，可以记作aRb。离散数学上会有对关系的详细定义。大家也可查阅百度百科、维基百科。（2）关系的复杂性决定了数据结构的复杂程度，也决定了后续算法的复杂性。结构的定义数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有下列四类基本的结构：(1)集合结构：结构中的数据元素除了“同属于一个集合”的关系外，再无其它关系(2)线性结构：结构中的数据元素之间存在着一对一的邻接关系(3)树形结构：结构中数据元素之间存在着一对多的关系(4)图状结构或网状结构：结构中数据元素间存在着多对多的关系1.2基本概念和术语本书中涉及到的关系：（1）没有关系（2）1对1的关系（3）1对n的关系（4）n对n的关系数据结构(DataStructure)：是指相互之间有一种或多种特定关系的数据元素的集合。数据结构通常包括三个方面的内容：数据的逻辑结构和数据的物理结构及数据的运算。1.数据的逻辑结构（LogicalStructure)是以抽象的数学模型来描述数据结构中数据元素之间的逻辑关系，它与数据的存储无关。通常用二元组来描述这种关系：Data_Structure=(D,R)其中，D是数据元素的有限集，R是D上关系的有限集。例1：学生基本情况登记表的数据结构001003002004006005008007如果我们使用二元组来表示上述的线性结构，则可表示为Liner_List=(D,R)其中：D={001,002,003,004,005,006,007,008}R＝{001,002,002,003,003,004,004,005,005,006,006,007,007,008}学号姓名专业政治面貌001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机党员……………………008刘亮计算机党员例2：家族的族谱的数据结构JIACBDHGFE图家族树上述结构可以形式定义为：Tree=(D,R)其中：D={A,B,C,D,E,F,G,H,I,J}R＝{A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J}例3：交通网的数据结构AEDBCF3010020601051050图交通网可形式化定义成：Graph=(D,R)其中：D={A，B，C，D，E，F}R={A,C,A,E,A,F,B,C,C,D,D,F,E,D,E,F}数据的逻辑结构只抽象反映数据元素的逻辑关系，是数据本身所固有的，是独立于计算机的。我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构——数据的物理结构，或称存储结构。2.数据的存储结构(StorageStructure)数据的逻辑结构在计算机内的存储表示(或称映象）称为数据的存储结构，又称为物理结构。在计算机内部主要是顺序存储和链式存储这两种结构来表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定的逻辑结构，而算法的实现则取决于依托的存储结构。1）顺序存储结构：将数据元素按逻辑顺序存入计算机存储器的连续存储单元中；特点：逻辑上相邻的数据元素物理地址必相邻。在C语言中，顺序存储结构用一维数组来描述。存储地址存储内容顺序存储LoLoc(ai)=Lo+(i-1)*m例：有n个数据的逻辑顺序（a1,a2,a3,…,an)a1a2aian…………Lo+mLo+(i-1)*mLo+(n-1)*m2）链式存储结构:借助指示元素存储地址的指针表示数据元素间的逻辑关系。为数据结构的每个结点元素附加一个数据项，其中存放一个与其相邻接的元素的地址（指针），通过指针得到下一个相关元素的实际存储地址，每个结点由数据域和指针域组成。特点：逻辑上相邻的元素物理地址未必相邻。存储地址13451351…….1400…….1536存储内容指针a11400an∧……..…….a21536……..…….a31351链式存储h数据的逻辑结构a1∧ana2a3…例：有n个数据的逻辑顺序（a1,a2,a3,…,an)3.数据的运算是指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行的。数据的运算是通过算法来描述的。对数据进行的运算主要有：检索、排序、插入、删除、修改等。数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储结构链式存储结构线性表栈队列树形结构图形结构数据结构的三个方面：索引存储结构散列存储结构数据结构与算法密切相关算法设计逻辑结构算法实现存储结构1.3算法描述和分析一、算法（algorithm）——就是对求解问题步骤的一种描述。是解决问题的一个策略。一个算法必须满足以下五个重要特性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。算法中每一条指令必须有确切的含义。不存在二义性。且在每种情况下，算法只有唯一的一条执行路径。算法是可以被执行的，即算法描述的操作都可以通过已实现的基本运算执行有限次来实现的。（1）有穷性（2）确定性（3）可行性与程序的区别1.2基本概念和术语一般说来，需要考虑如何设计数据结构的程序，要处理的对象往往是大量的数据；因此在计算机上编程实现时要考虑数据在内存中的存储形式；在内存中数据的存储结构有两种，一种是全部数据占据连续的内存空间，称之为顺序存储结构；一种是通过指针将数据链接起来，称之为链式存储结构。1.3抽象数据类型1.3抽象数据类型抽象数据类型（AbstractDataType，ADT）：指一个数学模型及定义在该模型上的一组操作。本书是从抽象数据类型的角度，分别讨论线性表、栈、队列、字符串、数组、树、二叉树、图等数据结构及其应用的。抽象数据类型的核心在于抽象二字，与具体的计算机语言无关。再高级的思想都要“落地生根”，都要在计算机中实现，因此，我们还是要依托某种“计算机语言”来实现各种数据结构1.3抽象数据类型目前用来描述“抽象数据类型”的最理想的工具是“类”，即C++或者java中类的概念；然而，就当前大家对计算机语言的掌握程度，应该说是“C语言”掌握的最好；所以采用C语言描述的数据结构教材最适合大多数同学；学有余力的同学可以结合C++或者其他语言中的“类”来实现数据结构。1.3抽象数据类型抽象数据类型的定义格式：抽象数据类型名{数据对象：对数据对象的描述；数据关系：对数据关系的定义；基本操作：基本操作的定义}1.3抽象数据类型抽象数据类型的定义格式：抽象数据类型名{数据对象：对数据对象的描述；数据关系：对数据关系的定义；基本操作：基本操作的定义}数据结构1.3抽象数据类型抽象数据类型的定义格式：抽象数据类型名{数据对象：对数据对象的描述；数据关系：对数据关系的定义；基本操作：基本操作的定义}用函数表示1.4算法和