数据库第2章1顺序表.pptVIP

* 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 排序 目 录 数据结构课程的起点： 什么是 线性结构？ * 线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 →可表示为：（a1 , a2 , ……, an） 简言之，线性结构反映结点间的逻辑关系是 的。 特点① 只有一个首结点和尾结点； 特点② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。 线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------ 线性表 一对一 (1:1) * 第2章 线性表 2.1 线性表的逻辑结构及运算 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例 * （a1, a2, … ai-1，ai, ai＋1 ，…, an） 2.1.1 线性表的逻辑结构 线性表的定义：用数据元素的有限序列表示 n=0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标，是元素的序号，表示元素在表中的位置 n为元素总个数，即表长。n≥0 空表 线性终点 * （ A, B, C, D, …… , Z） 学号 姓名 性别 年龄 班级 012003010622 陈建武 男 19 2003级电信0301班 012003010704 赵玉凤 女 18 2003级电信0302班 012003010813 王 泽 男 19 2003级电信0303班 012003010906 薛 荃 男 19 2003级电信0304班 012003011018 王 春 男 19 2003级电信0305班 ： ： ： ： ： 例2 分析学生情况登记表是什么结构。 分析：数据元素都是同类型（记录），元素间关系是线性的。 分析： 数据元素都是同类型（字母）， 元素间关系是线性的。 注意：同一线性表中的元素必定具有相同特性 ！ 例1 分析26 个英文字母组成的英文表是什么结构。 * “同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。 × 是指各元素具有相同的数据类型 试判断下列叙述的正误： * 线性表的主要运算有如下几种： 1.Initiate(L) （或Setnull(L)）初始化：构造一个空的线性表L。 2. Insert(L,i,x) 插入：在给定的线性表L中，在第i个元素之前插入数据元素x。线性表L长度加1。 3. Delete(L,i) 删除：在给定的线性表L中，删除第i个元素。线性表L的长度减1。 4. Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。 * 5. Length(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。 6. Get(L,i) 存取：对给定线性表L，返回第i（0≤i≤Length(L)-1）个数据元素，否则返回Null。 * 例3：利用线性表的基本运算来实现清除表L中多余的重复节点。 实现该算法的基本思想：从表L的第一个节点（i=1）开始，逐个检查 i 位置以后的任一位置 j ，若两节点相同，则将位置j上的节点从表L中删除，当 j 遍历了 i 后面的所有位置之后， i位置上的节点就成为当前表L中没有重复值的节点，然后将 i 向后移动一个位置，重复上述过程，直至i 移到表L的最后一个位置为止。 * ? PURGE(L) /*删除线性表L中重复出现的多余节点*/ Linear_list *L; { int i=1,j,x,y; while( iLENGTH(L)) /*每次循环都使当前第i个节点是无重复值点*/ {x=GET(L,i); /*取当前第 i 个节点*/ j=i+1; while(j=LENGTH(L)) {y=GET(L,j); /*取当前第 j 个节点*/ if (x==y)DELETE(L,j); /*删除当前第 j 个节点*/ else j++; } i++; } } /*PURGE*/ *