《数据结构知识点总结有工大老师多经验编写》由会员分享，可在线阅读，更多相关《数据结构知识点总结有工大老师多经验编写（224页珍藏版）》请在金锄头文库上搜索。
1、计算机系列课程之间的联系,数据结构涵盖的内容,二.基本概念和术语,1.数据 数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。 2.数据元素 数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项 是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。 4.数据对象 性质相同的元素的集合叫做数据对象。,5.结点 数据元素在机内的位串表示，即数据元素在计算机内的映象。 6.域/字段 当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据
2、项在计算机中的映象。 7.信息表 计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。,8.数据结构 数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。 9.逻辑结构和存储结构 (1)逻辑结构 数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。 (2)存储结构/物理结构 数据结构在计算机中的表示（映象）称为存储结构/物理结构。,1.1.1基本概念和术语,(3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结
3、构和链式结构。 顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。,1.1.1基本概念和术语,返回,1.1.2四种基本的数据结构,1.集合结构,结构中的数据元素之间除了“属于同一个集合”的关系之外，别无其他关系。关系比较松散，可用其他结构来表示。,结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。,2.线性结构,3.树型结构,结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的
4、一个元素相关。,结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。,4.网状/图型结构,返回,1.1.3数据结构的研究对象,数据结构的研究对象(研究内容),1.数据对象的结构形式,各种数据结构的性质 (逻辑结构); 2.数据对象和”关系”在计算机中的表示 (物理结构/存储结构); 3.数据结构上定义的基本操作(算法); 4.算法的效率; 5.数据结构的应用,如数据分类,检索.,返回,数据结构的作用图,数据 结构,数据关系,数 据 表 示,数 据 类 型,数学 离散数学 应用数学,硬件 存储设备 总体结构,软件 系统软件 应用软件,算法 设计 数据 运算,编码 理论
5、 数据 组合,系统设计 数据存取,2.1 算法及其性能评价准则,算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法的特征： 有穷性、确定性、 能行性、输入、 输出,算法描述： 自然语言；程序设计语言；类语言*；,一、算法、算法的特征和算法描述,常用的算法设计方法： 递归法（Recursion）、分治法(Divide-and Conquer)、 贪心法(Greedy)、动态规划(Dynamic Programming)、 搜索与遍历、回溯（Backtracking）、解空间局部搜索 近似算法(Approximation
6、)、在线算法（On-Line）等,2.2 算法时间复杂性分析方法,定理2.1 若 A（n）=amnm+a1n+a0 是关于n的m次多项式，则 A（n）=（nm） *此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关 （1）表示实践复杂性为常数 常见的时间复杂性及其比较 （1） （n） （n） （n） （nn） （n2） （n3） （2n）,设T1(n)=O( f(n) )，T2(n)=O( g(n) )，则 加法规则：T1(n)+T2(n) = O( max f(n), g(n) ) 乘法规则：T1(n)*T2(n) = O( f(n)* g(n) ) 1. 表
7、达式和赋值语句:O(1),2. 语句序列:用加法规则,取耗时最多语句. 3. 条件语句:O(1) 4. FOR语句:O(N*M)N为循环次数,M为体内时间最多的语句 5. WHILE语句:找出与循环次数有关的变量,通过计算找出上下限.,例: x=n; y=0; while (x=(y+1)(y+1) y=y+1; 时间复杂性为O（,s = 0 ; f(n) = 1; T2(n) = O(f(n) = O(1)常量阶,）,for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j ) +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n
8、) = O(n2) 平方阶,for ( i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ; k = n; +k ) cij += aik * bkj ; f(n) = 2n3+3n2+2n+1; T4(n) = O(f(n) = O(n3) 立方阶,for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T1(n) = O(f(n) = O(n) 线形阶,第三章 线性表（Liner List）,知识点： 线性表的逻辑结构和各种存储表示方法 定义在逻辑结构上的各种基本运算（操作） 在
9、各种存储结构上如何实现这些基本运算 各种基本运算的时间复杂性,重点： 熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析,难点： 使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题,3.1 抽象数据型线性表,定义 线性表是由n(n0)个相同类型的元素组成的有序集合。 记为： ( a1,a2,a3,ai-1,ai,ai+1, an ),其中： n为线性表中元素个数，称为线性表的长度； 当n=0时，为空表，记为（ ）。 ai为线性表中的元素，类型定义为elementtype a1为表中第1个元素，无前驱元素；an为表中最后一个 元素，无后继元素；对于ai-1,ai,ai+1(1
10、in)，称ai-1 为ai的直接前驱，ai+1为ai的直接后继。(位置概念！） 线性表是有限的，也是有序的。,3.1 抽象数据型线性表,线性表 LIST = ( D , R) D = ai | ai Elementset , i = 1, 2, , n, n 0 R = H H = | ai-1, ai D , i = 2 , , n ,操作：设L的型为LIST线性表实例，x 的型为elementtype的元素 实例，p 为位置变量。所有操作描述为： Insert(x, p, L) Locate(x, L) Retrieve(p, L) Delete(p, L) Previous(p, L),
11、 Next(p, L) MakeNull( L) First( L) End(L),数学模型,3.1 抽象数据型线性表,举例：设计函数 Deleval（LIST ,3.2 线性表的实现,问题：确定数据结构（存储结构）实现型LIST，并在此基础上 实现各个基本操作。,存储结构的三种方式： 连续的存储空间（数组） 静态存储 非连续存储空间指针（链表） 动态存储 游标（连续存储空间+动态管理思想） 静态链表,3.2.1 指针和游标,指针：地址量，其值为另一存储空间的地址； 游标：整型指示量，其值为数组的下标，用以表示指定元素 的“地址” 或 “位置”（所在的数组下标）,3.2.2 线性表的数组实现,
12、顺序表： 把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。,特点： 元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）； 是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。,3.2.2 线性表的数组实现,类型定义： # define maxlength 100 struct LIST elementtype elements maxlength; int last; ; 位置类型： typedef int position; 线性表 L: LIST L;
13、表示： L.elementsp / L的第p个元素 L.last L的长度，最后元素的位置,3.2.2 线性表的数组实现,操作：, void Insert ( elementtype x, position p, LIST /时间复杂性：O(n),position Locate ( elementtype x , LIST L ) position q ; for ( q = 1; q = L.last ; q+ ) if ( L.elements q = x ) return ( q ) ; return ( L.last + 1 ); /时间复杂性：O(n),3.2.2 线性表的数组实现,
14、elementtype Retrieve ( position p , LIST L ) if ( p L.last ) error( “指定元素不存在” ) ; else return ( L.elements p ) ; /时间复杂性：O(1), void Delete( position p , LIST /时间复杂性：O(n),3.2.2 线性表的数组实现, position Previous( position p , LIST L ) if ( ( p L.last ) ) error ( “前驱元素不存在” ) ; else return ( p 1 ); /时间复杂性：O(1)
15、, position End( LIST L ) return( L.last + 1 ); / O(1), position First( LIST L ) return ( 1 ); /复杂性：O(1),position Next( position p , LIST L ) if ( ( p = L.last ) ) error ( “前驱元素不存在” ) ; else return ( p + 1 ); /时间复杂性：O(1), position MakeNull( LIST /时间复杂性：O(1),3.2.2 线性表的数组实现,3.2.3 线性表的指针实现,单链表：一个线性表由若干个结点组成，每个结点均含有两个域： 存放元素的信息域和存放其后继结点的指针域，这样就形成一个 单向链接式存储结构，简称单向链表或单向线性链表。,结构特点： 逻辑次序和物理次序不一定相同； 元素之间的逻辑关系用指针表示； 需要额外空间存储元素之间的关 系； 非随机存储结构,3.2.3 线性表的指针实现,操作讨论：,3.2.3 线性表的指针实现,插入元素:,p,(a) 表头插入元素,(b) 中间插入元素,(c) 表尾插入元素,q = new cellt
