数据库结构第一单元复习讲解.ppt

第一单元复习 绪论、线性结构的 存储及其基本运算 一、课程目的意义 数据结构是普通高校计算机专业和信息管理专业一门必修的核心课程。(专业基础课) 数据结构研究数据的逻辑结构、在计算机中的存储结构以及各种非数值运算的算法。使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课打下良好的基础。 二、基 本 术 语 数据 数据元素 数据处理（检索、插入、删除、…） 数据结构（逻辑结构与存储结构） 数据类型与抽象数据类型 数据结构的描述法： 图形表示——用小圆圈表示数据(称为结点或顶点)、用连接小圆圈的边或弧表示数据之间的关系。 例：讨论某单位人事表中的各种关系 1：姓名贵贱关系 （集合结构） 2：年龄大小关系 （线性结构） 3：领导与被领导关系 （树形结构） 4：朋友关系 （图形结构） 三、计算时间复杂性的数量级 一个算法的时间复杂性的计算是相当繁琐的。实际上，一般只要求计其数量级即可。 一个函数f(n)的数量级表示法 若f(n)/g(n) ? k (n?∞，k?0)则记 f(n)=O(g(n)) 如4n+4=O(n), 4n2+5n+2=O(n2)等 直接求算法的时间复杂性的数量级 不必对算法的每一步都进行详细分析，只需分析算法中的主要部分：对循环语句分析循环体内简单操作的执行次数，对递归函数分析其调用的次数等等 一个算法的时间复杂性可以分为最好、最差和平均三种情况讨论。 四、 线性表的逻辑结构 1、线性表：由n(n≥0)个同类型元素的组成有限序列。线性表可简称为表，记作 L=（a1,a2 ,… ai,ai+1,…,an) 其中n称为线性表L的长度，n=0时称为空表。 2、线性表的特点:当表非空时,(1)存在唯一的一个被称为“表首”的元素;(2)存在唯一的一个被称为“表尾”的元素;(3)除表首元素外,表中的每一个元素均只有一个直接前驱;(4)除表尾元素外,表中的每一个元素均只有一个直接后继。 3、线性表的图形表示 五、线性表的基本运算 构造空的线性表L： InitList(L) 求线性表的长度： ListLength(L) 读出表L中第i个位置的元素:  GetNode(L,i) 求表L中值为x元素的位置：  LocateNode(L,x) 在表L的i处插入x： InsertList (L, x, i) 删除表L位置i的元素： DeleteList (L, i) 六、调用基本函数举例 例 设线性表L0的元素是整数：L0=（25，38, 19, 42, 33），试给出对L0调用上述基本函数的一些方法及结果。 k=ListLength(L0); //k=5,这是表L0的长度 k= LocateNode(L0,42,)；//k=4 InsertList (L0, 65,3)；//结果 L0=(25,38 ,65,19,42,33) ListDelete(L0, 3)； //结果L0=(25,38 ,42,33) 将L0改为L0=(2,4,6,8,…,100):InitList(L0);for( i=1;i=50;i++) InsertList (L0,2*i, i)； 将另一个同类型的线性表L1接在L0的后面，而L1仍保持不变: m=ListLength(L0); n=ListLength(L1);  for( i=1;i=n;i++)  InsertList (L0, GetNode(L1, i) , m+i)； 七 线性表的顺序存储 1、将线性表的数据元素按逻辑顺序依次存放到一组地址连续的存储单元里。这样的线性表又称为顺序表 2、假设表A=(a1,a2,…,an)的每个元素占用c个存储单元,则线性表的存储示意图如图2-1(P14)。而且每个元素的存储地址可通过下式计算： LOC(ai)= LOC(a1)+(i-1)*c 1≤i ≤n 3、顺序表通常用一个结构体来定义： typedef struct { DataType data[ListSize]; int length; } SeqList ; 4、在顺序存储下基本运算的实现 八 线性表的链接存储 1. 用一组任意的存储单元来存放线性表的结点。为了能正确表示结点之间的逻辑关系，在存储每个结点的同时，还必须存储指示其直接后继结点的地址的信息，这个信息叫做指针或链，这两部分信息组成了链表的结点结构。 2. 单链表的一般图形 设线性表 L=（a1,a2 ,… ,an)，则其图形为 3、单链表的结点定义typede