第2章__线性表的顺序存储(精品).ppt

《第2章__线性表的顺序存储(精品).ppt》由会员分享，可在线阅读，更多相关《第2章__线性表的顺序存储(精品).ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 线性表的顺序存储线性表的顺序存储线性表有两种存储方法：顺序存储和链式存储。线线性表有两种存储方法：顺序存储和链式存储。线性表的顺序存储是指在计算机中用一组地址连续的存储单元性表的顺序存储是指在计算机中用一组地址连续的存储单元依次存储数据元素来表示线性表。换句话说，就是将线性表依次存储数据元素来表示线性表。换句话说，就是将线性表中的数据元素一个接着一个地存放在某个存储区域中。本章中的数据元素一个接着一个地存放在某个存储区域中。本章主要讲解线性表的逻辑结构特性、顺序存储结构及它的基本主要讲解线性表的逻辑结构特性、顺序存储结构及它的基本运算和实现算法。运算和实现算法。2.1 2.1

2、线性表的逻辑结构线性表的逻辑结构简单地说，线性表的逻辑结构是指线性表数据元素简单地说，线性表的逻辑结构是指线性表数据元素之间的关系。线性结构是最简单且最常用的数据结构，而线之间的关系。线性结构是最简单且最常用的数据结构，而线性表是最典型的线性结构。线性结构的特点是数据元素之间性表是最典型的线性结构。线性结构的特点是数据元素之间是一种线性关系，即一对一关系。下面从线性表的定义及基是一种线性关系，即一对一关系。下面从线性表的定义及基本运算方面来讨论它的逻辑结构。本运算方面来讨论它的逻辑结构。2.1.1 2.1.1 线性表的定义线性表的定义线性表定义如下：线性表是具有相同数据类型的线性表定义如下：线

3、性表是具有相同数据类型的n（n0）个数据元素的有限序列，通常记为：）个数据元素的有限序列，通常记为：(a1,a2,ai-1,ai,ai+1,an)2.1.2 2.1.2 线性表的数学定义和逻辑图线性表的数学定义和逻辑图从数学定义方面来说，线性表（从数学定义方面来说，线性表（Linear List）是具）是具有相同属性的数据元素的一个有限序列。该序列中所含元素有相同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用的个数叫做线性表的长度，用n表示（表示（n0）。当）。当n=0时，表时，表示线性表是一个空表，即表中不包含任何元素。设序列中第示线性表是一个空表，即表中不包含任何

4、元素。设序列中第i个元素为个元素为ai（1in），则线性表的一般表示为：），则线性表的一般表示为：(a1,a2,ai-1,ai,ai+1,an)2.1.3 2.1.3 线性表的基本操作线性表的基本操作数据结构的操作是定义在逻辑结构层次上的，而操数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的。因此，下面定义的线作的具体实现是建立在存储结构上的。因此，下面定义的线性表的基本操作作为逻辑结构的一部分，每一个操作的具体性表的基本操作作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。实现只有在确定了线性表的存储结构之后才能完成。2.2 2.

5、2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储是指用一组地址连续的存储单元线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的元素。而顺序存储结构，就是对线性表采依次存储线性表的元素。而顺序存储结构，就是对线性表采用顺序存储方式存储数据时所使用变量的描述。下面从顺序用顺序存储方式存储数据时所使用变量的描述。下面从顺序表及其基本运算两方面来讨论顺序存储结构。表及其基本运算两方面来讨论顺序存储结构。2.2.1 2.2.1 顺序表定义顺序表定义简单地说，用顺序存储方法存储的线性表简称为顺序表简单地说，用顺序存储方法存储的线性表简称为顺序表（Sequential List）。线性

6、表中的所有元素按其逻辑顺序相继存）。线性表中的所有元素按其逻辑顺序相继存放在一个连续的存储空间中，其存储地址与次序相同，所以也可以放在一个连续的存储空间中，其存储地址与次序相同，所以也可以说它是一种随机存取的存储结构。下面通过实例描述推导出数据元说它是一种随机存取的存储结构。下面通过实例描述推导出数据元素素ai的存储地址计算公式，并讲解其随机存取的特点。的存储地址计算公式，并讲解其随机存取的特点。2.2.2 2.2.2 顺序存储结构类型顺序存储结构类型C语言中的数组在内存中占用的存储空间就是一组连语言中的数组在内存中占用的存储空间就是一组连续的存储区域，所以，数组具有表示顺序表的数据存储区域续

7、的存储区域，所以，数组具有表示顺序表的数据存储区域的优越特性。下面介绍在的优越特性。下面介绍在C语言中，实现线性表的顺序存储语言中，实现线性表的顺序存储结构的类型定义。结构的类型定义。定义线性表的顺序存储类型时，用数组来存储线性定义线性表的顺序存储类型时，用数组来存储线性表中的所有元素，用整型变量来存储线性表的长度。为了便表中的所有元素，用整型变量来存储线性表的长度。为了便于进行线性表的操作，把用于存储线性表元素的数组和存储于进行线性表的操作，把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中。线性表长度的变量同时说明在一个记录类型中。2.2.3 2.2.3 顺序表的基本

8、运算顺序表的基本运算本节主要讨论采用顺序存储结构来实现各种基本的运算，本节主要讨论采用顺序存储结构来实现各种基本的运算，先介绍求顺序表的长度、判断表是否为空、判断表是否为满、清先介绍求顺序表的长度、判断表是否为空、判断表是否为满、清空表、取顺序表数据元素、显示线性表等较简单的基本运算实现空表、取顺序表数据元素、显示线性表等较简单的基本运算实现方法。对顺序表的创建、查找、插入、删除等复杂操作单独分节方法。对顺序表的创建、查找、插入、删除等复杂操作单独分节讨论。讨论。1 求顺序表的长度求顺序表的长度2 判断表是否为空判断表是否为空 3 判断表是否为满判断表是否为满 4 清空表清空表 5 取顺序表数

9、据元素取顺序表数据元素6 显示线性表显示线性表2.3 2.3 顺序表的建立顺序表的建立顺序表的建立是指实现顺序表的初始化并给各结点顺序表的建立是指实现顺序表的初始化并给各结点关联相应的数据元素。上一节主要介绍顺序表的较简单的运关联相应的数据元素。上一节主要介绍顺序表的较简单的运算，而顺序表的建立运算对数据结构初学者来说相对困难些。算，而顺序表的建立运算对数据结构初学者来说相对困难些。读者要掌握读者要掌握C语言程序设计方法，且具有一定的编程经验才语言程序设计方法，且具有一定的编程经验才能独立解决上机实验过程中出现的问题。顺序表建立算法实能独立解决上机实验过程中出现的问题。顺序表建立算法实现如下：

10、现如下：void Create_List(SqList*L,int n)int i;for(i=0;idatai);L-length=n;2.4 2.4 顺序表的查找顺序表的查找顺序表的查找是在指定的顺序表顺序表的查找是在指定的顺序表L中查找指定位序中查找指定位序i的数据元素或指定数据元素的数据元素或指定数据元素x的位序。若的位序。若L中存在该序号或其中存在该序号或其值与值与x相等的数据元素，则返回值为该数据元素的值或在线相等的数据元素，则返回值为该数据元素的值或在线性表中的位序。顺序表的查找是最基本的查找方法，主要分性表中的位序。顺序表的查找是最基本的查找方法，主要分为按位置查找元素和按内容

11、查找元素两种操作。为按位置查找元素和按内容查找元素两种操作。2.4.1 2.4.1 按位置查找元素按位置查找元素顺序表是一种随机存取结构，所以在顺序表中按位顺序表是一种随机存取结构，所以在顺序表中按位置查找元素非常容易，只要查找位置合法，可直接返回对应置查找元素非常容易，只要查找位置合法，可直接返回对应的数据元素。的数据元素。按位置查找元素算法实现如下：按位置查找元素算法实现如下：DataType Locate_List(SqList L,int i)DataType e;if(i Length_List(L)printf(输入的位置非法输入的位置非法!);return 0;e=L.datai

12、-1;return(e);2.4.2 2.4.2 按值查找元素按值查找元素按值查找元素是在顺序表中查找是否有结点值等于按值查找元素是在顺序表中查找是否有结点值等于给定值给定值x的结点，若有，则返回首次找到的其值为的结点，若有，则返回首次找到的其值为x的结点的的结点的存储位置；如果顺序表中没有与给定值匹配的数据元素，返存储位置；如果顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。顺序表按值查找元素算法实现回一个特殊值表示查找失败。顺序表按值查找元素算法实现如下：如下：int Locate_List(SqList L,DataType x)int i=0;while(iL.leng

13、th&L.datai!=x)i+;if(iL.length)return(i+1);else return 0;2.4.3 2.4.3 顺序表的查找操作的效率分析顺序表的查找操作的效率分析顺序表是一种随机存取结构，按位置查找时间复杂度为顺序表是一种随机存取结构，按位置查找时间复杂度为常量常量O(1)，故顺序表中按位置查找非常方便。顺序表的按值查找，故顺序表中按位置查找非常方便。顺序表的按值查找元素算法中的主要运算是比较，比较的次数与给定值在表中的位元素算法中的主要运算是比较，比较的次数与给定值在表中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为置和表长有关。当给定值与第一个数据元

14、素相等时，比较次数为1；当与第二个数据元素相等时，比较次数为；当与第二个数据元素相等时，比较次数为2；而当给定值与；而当给定值与最后一个元素相等时，比较次数为最后一个元素相等时，比较次数为n。所以，平均比较次数为。所以，平均比较次数为（n+1）/2。故得出结论，按值查找元素算法的时间复杂度为。故得出结论，按值查找元素算法的时间复杂度为O（n），查找时间与表的长度有关。），查找时间与表的长度有关。2.5 2.5 顺序表的插入与删除顺序表的插入与删除顺序表的插入与删除操作实现向表中添加新的数据顺序表的插入与删除操作实现向表中添加新的数据元素或删除存在的数据元素。插入与删除是表的最常用、最元素或删除

15、存在的数据元素。插入与删除是表的最常用、最重要的两个操作，当然学习起来也是比较困难的。两个操作重要的两个操作，当然学习起来也是比较困难的。两个操作的实现可能涉及前面介绍的所有的算法。的实现可能涉及前面介绍的所有的算法。2.5.1 2.5.1 在顺序表的第在顺序表的第i i个位置插入一个元素个位置插入一个元素顺序表的插入运算是指在顺序表的第顺序表的插入运算是指在顺序表的第i（1in+1）个位置上，插入一个新结点个位置上，插入一个新结点x，使长度为，使长度为n的线性表：的线性表：(a1,a2,ai-1,ai,ai+1,an)变成长度为变成长度为n+1的线性表：的线性表：(a1,a2,ai-1,x,

16、ai,ai+1,an)2.5.1 2.5.1 在顺序表的第在顺序表的第i i个位置插入一个元素个位置插入一个元素2.5.2 2.5.2 删除顺序表的第删除顺序表的第i i个位置元素个位置元素顺序表的删除操作是指将表中第顺序表的删除操作是指将表中第i个数据元素从顺序个数据元素从顺序表中删除，删除后使原表长为表中删除，删除后使原表长为n的表：的表：(a1,a2,ai-1,ai,ai+1,an)变成长度为变成长度为n-1的线性表：的线性表：(a1,a2,ai-1,ai+1,an)2.5.2 2.5.2 删除顺序表的第删除顺序表的第i i个位置元素个位置元素2.5.3 2.5.3 顺序表的插入与删除操

17、作的效率分析顺序表的插入与删除操作的效率分析本节开头提到顺序表的插入与删除操作的实现可能本节开头提到顺序表的插入与删除操作的实现可能涉及前面介绍的所有的算法，通过对两算法的操作描述可知，涉及前面介绍的所有的算法，通过对两算法的操作描述可知，主要涉及对顺序表的判表空、判表满、取表长、查找、取值主要涉及对顺序表的判表空、判表满、取表长、查找、取值等操作，其中还附加了大量结点的移动操作。下面分别分析等操作，其中还附加了大量结点的移动操作。下面分别分析两算法的实现效率。两算法的实现效率。1顺序表的插入操作算法的时间复杂度分析顺序表的插入操作算法的时间复杂度分析2顺序表的删除操作算法的时间复杂度分析顺序

18、表的删除操作算法的时间复杂度分析2.6 2.6 顺序表的典型例题顺序表的典型例题线性表是数据结构中最简单、最常用的一种线性结构，线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。在线性表中，顺序表的结构又是最简单的，后继知识的学习。在线性表中，顺序表的结构又是最简单的，本节通过一些典型例题来掌握对顺序表的各种操作实现过程。本节通过一些典型例题来掌握对顺序表的各种操作实现过程。2.7 2.7 算法设计实训算法设计实训前面讨论了顺序表的各种操作实例，本节主要介绍前面讨论了顺序表

19、的各种操作实例，本节主要介绍顺序存储结构的上机实训。通过对算法设计的学习，可以理顺序存储结构的上机实训。通过对算法设计的学习，可以理解线性表在顺序存储结构下的操作方法，掌握顺序存储结构解线性表在顺序存储结构下的操作方法，掌握顺序存储结构的常见算法。下面介绍采用顺序存储结构实现的学生成绩管的常见算法。下面介绍采用顺序存储结构实现的学生成绩管理的详细设计过程。理的详细设计过程。2.7.1 2.7.1 学生成绩管理需求分析学生成绩管理需求分析学生成绩管理是学校教务部门日常工作的重要组成学生成绩管理是学校教务部门日常工作的重要组成部分，其处理信息量很大。本实例的实质是完成对学生成绩部分，其处理信息量很

20、大。本实例的实质是完成对学生成绩信息的建立、查找、插入、修改、删除等功能。首先定义学信息的建立、查找、插入、修改、删除等功能。首先定义学生的数据结构，然后将每个功能封装成函数来完成对数据的生的数据结构，然后将每个功能封装成函数来完成对数据的操作，最后完成主函数的设计来调用各个子函数，实现设计操作，最后完成主函数的设计来调用各个子函数，实现设计功能并得出运行结果。功能并得出运行结果。2.7.2 2.7.2 学生成绩管理数据结构学生成绩管理数据结构本实例操作数据是一组学生的成绩信息，每条学生本实例操作数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成，这组学生的成绩信息的成绩信息由

21、学号、姓名和成绩组成，这组学生的成绩信息具有相同特性，属于同一数据对象，相邻数据元素之间存在具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据具有顺序表中数据元素序偶关系。由此可以看出，这些数据具有顺序表中数据元素的性质，所以该系统的数据采用顺序表来存储比较合适。在的性质，所以该系统的数据采用顺序表来存储比较合适。在具体的实践应用中，读者要学会使用具体的实践应用中，读者要学会使用C语言中提供的结构体语言中提供的结构体和数组来存储顺序表，掌握顺序存储结构的特点。和数组来存储顺序表，掌握顺序存储结构的特点。2.7.3 2.7.3 学生成绩管理的实现学生成绩管理的实

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