线性表的顺序存储.ppt

《线性表的顺序存储.ppt》由会员分享，可在线阅读，更多相关《线性表的顺序存储.ppt（26页珍藏版）》请在三一办公上搜索。

1、第2章 线性表的顺序存储,线性表有两种存储方法：顺序存储和链式存储。线性表的顺序存储是指在计算机中用一组地址连续的存储单元依次存储数据元素来表示线性表。换句话说，就是将线性表中的数据元素一个接着一个地存放在某个存储区域中。本章主要讲解线性表的逻辑结构特性、顺序存储结构及它的基本运算和实现算法。,2.1 线性表的逻辑结构,简单地说，线性表的逻辑结构是指线性表数据元素之间的关系。线性结构是最简单且最常用的数据结构，而线性表是最典型的线性结构。线性结构的特点是数据元素之间是一种线性关系，即一对一关系。下面从线性表的定义及基本运算方面来讨论它的逻辑结构。,2.1.1 线性表的定义,线性表定义如下：线性

2、表是具有相同数据类型的n（n0）个数据元素的有限序列，通常记为：(a1,a2,ai-1,ai,ai+1,an),2.1.2 线性表的数学定义和逻辑图,从数学定义方面来说，线性表（Linear List）是具有相同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示（n0）。当n=0时，表示线性表是一个空表，即表中不包含任何元素。设序列中第i个元素为ai（1in），则线性表的一般表示为：(a1,a2,ai-1,ai,ai+1,an),2.1.3 线性表的基本操作,数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的。因此，下面定义的线性表的基本操

3、作作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。,2.2 线性表的顺序存储结构,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的元素。而顺序存储结构，就是对线性表采用顺序存储方式存储数据时所使用变量的描述。下面从顺序表及其基本运算两方面来讨论顺序存储结构。,2.2.1 顺序表定义,简单地说，用顺序存储方法存储的线性表简称为顺序表（Sequential List）。线性表中的所有元素按其逻辑顺序相继存放在一个连续的存储空间中，其存储地址与次序相同，所以也可以说它是一种随机存取的存储结构。下面通过实例描述推导出数据元素ai的存储地址计算公式，并讲解

4、其随机存取的特点。,2.2.2 顺序存储结构类型,C语言中的数组在内存中占用的存储空间就是一组连续的存储区域，所以，数组具有表示顺序表的数据存储区域的优越特性。下面介绍在C语言中，实现线性表的顺序存储结构的类型定义。定义线性表的顺序存储类型时，用数组来存储线性表中的所有元素，用整型变量来存储线性表的长度。为了便于进行线性表的操作，把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中。,2.2.3 顺序表的基本运算,本节主要讨论采用顺序存储结构来实现各种基本的运算，先介绍求顺序表的长度、判断表是否为空、判断表是否为满、清空表、取顺序表数据元素、显示线性表等较简单的基本运算实现

5、方法。对顺序表的创建、查找、插入、删除等复杂操作单独分节讨论。1 求顺序表的长度2 判断表是否为空 3 判断表是否为满 4 清空表 5 取顺序表数据元素6 显示线性表,2.3 顺序表的建立,顺序表的建立是指实现顺序表的初始化并给各结点关联相应的数据元素。上一节主要介绍顺序表的较简单的运算，而顺序表的建立运算对数据结构初学者来说相对困难些。读者要掌握C语言程序设计方法，且具有一定的编程经验才能独立解决上机实验过程中出现的问题。顺序表建立算法实现如下：void Create_List(SqList*L,int n)int i;for(i=0;idatai);L-length=n;,2.4 顺序表的

6、查找,顺序表的查找是在指定的顺序表L中查找指定位序i的数据元素或指定数据元素x的位序。若L中存在该序号或其值与x相等的数据元素，则返回值为该数据元素的值或在线性表中的位序。顺序表的查找是最基本的查找方法，主要分为按位置查找元素和按内容查找元素两种操作。,2.4.1 按位置查找元素,顺序表是一种随机存取结构，所以在顺序表中按位置查找元素非常容易，只要查找位置合法，可直接返回对应的数据元素。按位置查找元素算法实现如下：DataType Locate_List(SqList L,int i)DataType e;if(i Length_List(L)printf(输入的位置非法!);return 0

7、;e=L.datai-1;return(e);,2.4.2 按值查找元素,按值查找元素是在顺序表中查找是否有结点值等于给定值x的结点，若有，则返回首次找到的其值为x的结点的存储位置；如果顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。顺序表按值查找元素算法实现如下：int Locate_List(SqList L,DataType x)int i=0;while(iL.length,2.4.3 顺序表的查找操作的效率分析,顺序表是一种随机存取结构，按位置查找时间复杂度为常量O(1)，故顺序表中按位置查找非常方便。顺序表的按值查找元素算法中的主要运算是比较，比较的次数与给定值在表

8、中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为1；当与第二个数据元素相等时，比较次数为2；而当给定值与最后一个元素相等时，比较次数为n。所以，平均比较次数为（n+1）/2。故得出结论，按值查找元素算法的时间复杂度为O（n），查找时间与表的长度有关。,2.5 顺序表的插入与删除,顺序表的插入与删除操作实现向表中添加新的数据元素或删除存在的数据元素。插入与删除是表的最常用、最重要的两个操作，当然学习起来也是比较困难的。两个操作的实现可能涉及前面介绍的所有的算法。,2.5.1 在顺序表的第i个位置插入一个元素,顺序表的插入运算是指在顺序表的第i（1in+1）个位置上，插入一个新结点x

9、，使长度为n的线性表：(a1,a2,ai-1,ai,ai+1,an)变成长度为n+1的线性表：(a1,a2,ai-1,x,ai,ai+1,an),2.5.1 在顺序表的第i个位置插入一个元素,2.5.2 删除顺序表的第i个位置元素,顺序表的删除操作是指将表中第i个数据元素从顺序表中删除，删除后使原表长为n的表：(a1,a2,ai-1,ai,ai+1,an)变成长度为n-1的线性表：(a1,a2,ai-1,ai+1,an),2.5.2 删除顺序表的第i个位置元素,2.5.3 顺序表的插入与删除操作的效率分析,本节开头提到顺序表的插入与删除操作的实现可能涉及前面介绍的所有的算法，通过对两算法的操作

10、描述可知，主要涉及对顺序表的判表空、判表满、取表长、查找、取值等操作，其中还附加了大量结点的移动操作。下面分别分析两算法的实现效率。1顺序表的插入操作算法的时间复杂度分析2顺序表的删除操作算法的时间复杂度分析,2.6 顺序表的典型例题,线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。在线性表中，顺序表的结构又是最简单的，本节通过一些典型例题来掌握对顺序表的各种操作实现过程。,2.7 算法设计实训,前面讨论了顺序表的各种操作实例，本节主要介绍顺序存储结构的上机实训。通过对算法设计的学习，可以理解线性表在顺序存储结构下的操作方法

11、，掌握顺序存储结构的常见算法。下面介绍采用顺序存储结构实现的学生成绩管理的详细设计过程。,2.7.1 学生成绩管理需求分析,学生成绩管理是学校教务部门日常工作的重要组成部分，其处理信息量很大。本实例的实质是完成对学生成绩信息的建立、查找、插入、修改、删除等功能。首先定义学生的数据结构，然后将每个功能封装成函数来完成对数据的操作，最后完成主函数的设计来调用各个子函数，实现设计功能并得出运行结果。,2.7.2 学生成绩管理数据结构,本实例操作数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成，这组学生的成绩信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看

12、出，这些数据具有顺序表中数据元素的性质，所以该系统的数据采用顺序表来存储比较合适。在具体的实践应用中，读者要学会使用C语言中提供的结构体和数组来存储顺序表，掌握顺序存储结构的特点。,2.7.3 学生成绩管理的实现,结合学生成绩管理需求分析和增加的数据结构可实现抽象数据类型的描述，给出最终完善后的结构体描述及各功能函数的详细定义。1.抽象数据类型描述2.主要功能模块实现,2.8 本章小结,线性表是最简单、最基本、最常用的数据结构，线性表的特点是数据元素之间存在一对一的线性关系，也就是说，除第一个和最后一个数据元素外，其余数据元素都有且只有一个直接前驱和直接后继。定义如下：线性表是具有相同数据类型的n（n0）个数据元素的有限序列，通常记为：（a1，a2，ai-1，ai，ai+1，an）用二元组表示为：L=(A，R)其中，A=ai|1in，n0，aiElemTypeR=|1in-1,