搜索
课堂讲义哈尔滨工业大学计算机科学与技术学院计算机系列课程之间的联系课堂讲义哈尔滨工业大学计算机科学与技术学院数据结构涵盖的内容课堂讲义哈尔滨工业大学计算机科学与技术学院二.基本概念和术语1.数据数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。2.数据元素数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。4.数据对象性质相同的元素的集合叫做数据对象。课堂讲义哈尔滨工业大学计算机科学与技术学院5.结点数据元素在机内的位串表示，即数据元素在计算机内的映象。6.域/字段当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据项在计算机中的映象。7.信息表计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。课堂讲义哈尔滨工业大学计算机科学与技术学院8.数据结构数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。9.逻辑结构和存储结构(1)逻辑结构数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。(2)存储结构/物理结构数据结构在计算机中的表示（映象）称为存储结构/物理结构。1.1.1基本概念和术语课堂讲义哈尔滨工业大学计算机科学与技术学院(3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结构和链式结构。顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。1.1.1基本概念和术语返回课堂讲义哈尔滨工业大学计算机科学与技术学院1.1.2四种基本的数据结构1.集合结构结构中的数据元素之间除了“属于同一个集合”的关系之外，别无其他关系。关系比较松散，可用其他结构来表示。结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。2.线性结构课堂讲义哈尔滨工业大学计算机科学与技术学院3.树型结构结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。4.网状/图型结构返回课堂讲义哈尔滨工业大学计算机科学与技术学院1.1.3数据结构的研究对象数据结构的研究对象(研究内容)1.数据对象的结构形式,各种数据结构的性质(逻辑结构);2.数据对象和”关系”在计算机中的表示(物理结构/存储结构);3.数据结构上定义的基本操作(算法);4.算法的效率;5.数据结构的应用,如数据分类,检索.返回课堂讲义哈尔滨工业大学计算机科学与技术学院数据结构的作用图数据结构数据关系数据表示数据类型数学离散数学应用数学硬件存储设备总体结构软件系统软件应用软件算法设计数据运算编码理论数据组合系统设计数据存取课堂讲义哈尔滨工业大学计算机科学与技术学院2.1算法及其性能评价准则算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。算法的特征：①有穷性、②确定性、③能行性、④输入、⑤输出算法描述：①自然语言；②程序设计语言；③类语言*；一、算法、算法的特征和算法描述常用的算法设计方法：①递归法（Recursion）、②分治法(Divide-andConquer)、③贪心法(Greedy)、④动态规划(DynamicProgramming)、⑤搜索与遍历、⑥回溯（Backtracking）、⑦解空间局部搜索⑧近似算法(Approximation)、⑨在线算法（On-Line）等课堂讲义哈尔滨工业大学计算机科学与技术学院2.2算法时间复杂性分析方法定理2.1若A（n）=amnm+…+a1n+a0是关于n的m次多项式，则A（n）=О（nm）*此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关•О（1）表示实践复杂性为常数•常见的时间复杂性及其比较О（1）О（㏒㏒n）О（㏒n）О（n）О（n㏒n）О（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.表达式和赋值语句: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（n①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))=O(n2)平方阶④for(i=1;i=n;++i)for(j=1;j=n;++j){c[i][j]=0;for(k=1;k=n;++k)c[i][j]+=a[i][k]*b[k][j];}→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)线形阶课堂讲义哈尔滨工业大学计算机科学与技术学院第三章线性表（LinerList）课堂讲义哈尔滨工业大学计算机科学与技术学院知识点：线性表的逻辑结构和各种存储表示方法定义在逻辑结构上的各种基本运算（操作）在各种存储结构上如何实现这些基本运算各种基本运算的时间复杂性重点：熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题课堂讲义哈尔滨工业大学计算机科学与技术学院3.1抽象数据型线性表[定义]线性表是由n(n≥0)个相同类型的元素组成的有序集合。记为：(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。②ai为线性表中的元素，类型定义为elementtype③a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1in)，称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|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),Next(p,L)⑥MakeNull(L)⑦First(L)⑧End(L)数学模型课堂讲义哈尔滨工业大学计算机科学与技术学院3.1抽象数据型线性表举例：设计函数Deleval（LIST&L,elementtyped)，其功能为删除L中所有值为d的元素。voidDeleval(LIST&L,elementtyped){positionp;p=First(L);while(p!=Ennd(L)){if(same(Retrieve(p,L),d))Delete(p,L);elsep=Next(p,L);}}课堂讲义哈尔滨工业大学计算机科学与技术学院3.2线性表的实现问题：确定数据结构（存储结构）实现型LIST，并在此基础上实现各个基本操作。存储结构的三种方式：①连续的存储空间（数组）→静态存储②非连续存储空间——指针（链表）→动态存储③游标（连续存储空间+动态管理思想）→静态链表3.2.1指针和游标指针：地址量，其值为另一存储空间的地址；游标：整型指示量，其值为数组的下标，用以表示指定元素的“地址”或“位置”（所在的数组下标）课堂讲义哈尔滨工业大学计算机科学与技术学院3.2.2线性表的数组实现第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤last顺序表：把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。特点：元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。课堂讲义哈尔滨工业大学计算机科学与技术学院3.2.2线性表的数组实现第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤last类型定义：#definemaxlength100structLIST{elementtypeelements[maxlength];intlast;};位置类型：typedefintposition;线性表L:LISTL;表示：L.elements[p]//L的第p个元素L.lastL的长度，最后元素的位置课堂讲义哈尔滨工业大学计算机科学与技术学院3.2.2线性表的数组实现操作：①voidInsert(elementtypex,positionp,LIST&L){positionq;if(L.last=maxlength–1)error(“表满”)；elseif((pL.last+1)||(p1))error(“指定位置不存在”)；else{for(q=L.last;q=p;q--)L.elements[q+1]=L.elements[q];L.last=L.last+1;L.elements[p]=x;}}//时间复杂性：O(n)第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤last课堂讲义哈尔滨工业大学计算机科学与技术学院②positionLocate(elementtypex,LISTL){positionq;for(q=1;q=L.last;q++)if(L.elements[q]==x)return(q);return(L.last+1);}//时间复杂性：O(n)3.2.2线性表的数组实现③elementtypeRetrieve(positionp,LISTL){if(pL.last)error(“指定元素不存在”);elsereturn(L.elements[p]);}//时间复杂性：O(1)第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤last课堂讲义哈尔滨工业大学计算机科学与技术学院④voidDelete(positionp,LIST&L){positionq;if((pL.last)||(p1))error(“指定位置不存在”)；else{L.last=L.last–1;for(q=p;q=L.last;q++)L.el