c语言 第二章 数据结构及其运算.ppt

第一章 算法 第二章 数据结构及其运算 第三章 查找与排序 第四章 数据库技术 第五章 软件工程 ;; 数据结构的基本概念 线性表 栈 队列 数组 树与二叉数 图 ;为什么要学数据结构？ 数据结构研究什么？ 重新理解算法。 如何分析算法的优劣？;第一问题：为什么要学数据结构;现实中对象之间的关系;实际问题中对象之间的关系——学生成绩管理;实际问题中对象之间的关系;实际问题中对象之间的关系;第一问题：为什么要学数据结构;第二问题数据结构研究什么;§2.1 数据结构的基本概念; 数据项(Data items)是数据具有意义的最小单位。 数据对象(Data Objects)是具有相同特性的数据元素的集合，数据的子集。 例如有 数据集合 D={0,1,2,3,…,A,B,C,…,Z} 则 正整数 N={1,2，…,} 字母 C={A,B,C,…,Z} 是数据对象，数据对象是数据的一个子集。 数据结构(Data structure ) 是指带结构的数据元素的集合;数据结构的研究内容;关于数据结构中的结构;数据结构的二元组表示 DS=(D, R) 其中D是数据元素的集合，R是D上关系的集合。 D={di| 1≤i≤n, n≥0} R={rj| 1≤j≤m, m≥0} 其中D上的关系r是序偶的集合，对于r中任一序偶 x，y (x，y?D)，我们把x叫做序偶的第一元素，把y叫做序偶的第二元素，又称序偶的第一元素为第二元素的直接前驱，第二元素为第一元素的直接后继。 ; 例1 一年四季的数据结构可以表示成： DS=(D，R) D={春，夏，秋，冬} R={春，夏，夏，秋，秋，冬} ;例2 n维向量x=(x1，x2，…… ，xn)的数据结构： X=(D，R) D={x1，x2，…… ，xn} R={x1，x2，x2，x3，…… ，xn-1，xn} ;例3 家庭成员的数据结构： B=(D，R) D={父亲，儿子，女儿} R={(父亲，儿子)，(父亲，女儿)};例4 m×n阶矩阵 ; 其数据结构为： DS=(D, R) D={A1，A2，…，Am} R={（A1，A2），（A2，A3），…，（Ai， Ai+1），…，（Am-1，Am） } 数据结构A中的每一个数据元素Ai(i=1,2,,m)又是 另一个数据结构，其数据元素的集合为： DSi=(Di, Ri ) Di={ai1，ai2，…，ain} Ri={(ai1，ai2)，（ai2，ai3）,…,(ai，n-1，an)} ;§2.2 线性表 1、线性表的定义 线性表是由n(n≧)个数据元素(结点) a1，a2， …an组成的有限序列。一般记为 (a1，a2，…an) 其中： n：数据元素的个数，也称表的长度。 空表：n=0，记为（） ;2、线性表的特征 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋a i-1和一个直接后继ai+1。 ;3、线性表的基本运算 (1) 插入 按位置插入 按值插入 (2) 删除 按位置删除 按值删除 (3) 查找 按位置查找 按值查找 (4) 其他运算 求表长，分拆，合并，排序，逆转，复制，访问表中结点 ;; 顺序表特点 结点的逻辑次序和物理次序相同 随机存取 高级程序设计语言提供的数组类型可以直接定义顺序 存储结构的线性表，使程序实现十分方便。 顺序表的地址关系 假设线性表的每个元素存储需占用K个字节，并以 所占的第一个单元的存储地址作为数据元素的存储 位置，则有： ADR(ai)=ADR(a1)+(i-1)*K; 顺序表的基本运算 （1）定义表 #define Max 10 int V[Max]; （2）初始化表 typedef int ET; #includestdio.h void init_sq_list(ET *V, int m, int *n) { V=(ET *)malloc(