线性表的顺序存储幻灯片.ppt

线性表的顺序存储线性表的顺序存储第1页，共26页，编辑于2022年，星期一2.1 2.1 线性表的逻辑结构线性表的逻辑结构简单地说，线性表的逻辑结构是指线性表数据元素之间简单地说，线性表的逻辑结构是指线性表数据元素之间的关系。线性结构是最简单且最常用的数据结构，而线性表的关系。线性结构是最简单且最常用的数据结构，而线性表是最典型的线性结构。线性结构的特点是数据元素之间是一是最典型的线性结构。线性结构的特点是数据元素之间是一种线性关系，即一对一关系。下面从线性表的定义及基本运种线性关系，即一对一关系。下面从线性表的定义及基本运算方面来讨论它的逻辑结构。算方面来讨论它的逻辑结构。第2页，共26页，编辑于2022年，星期一2.1.1 2.1.1 线性表的定义线性表的定义线性表定义如下：线性表是具有相同数据类型的线性表定义如下：线性表是具有相同数据类型的n（n0）个数据元素的有限序列，通常记为：个数据元素的有限序列，通常记为：(a1,a2,ai-1,ai,ai+1,an)第3页，共26页，编辑于2022年，星期一2.1.2 2.1.2 线性表的数学定义和逻辑图线性表的数学定义和逻辑图从数学定义方面来说，线性表（从数学定义方面来说，线性表（Linear List）是具有相）是具有相同属性的数据元素的一个有限序列。该序列中所含元素的个同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用数叫做线性表的长度，用n表示（表示（n0）。当）。当n=0时，表示线时，表示线性表是一个空表，即表中不包含任何元素。设序列中第性表是一个空表，即表中不包含任何元素。设序列中第i个元个元素为素为ai（1in），则线性表的一般表示为：），则线性表的一般表示为：(a1,a2,ai-1,ai,ai+1,an)第4页，共26页，编辑于2022年，星期一2.1.3 2.1.3 线性表的基本操作线性表的基本操作数据结构的操作是定义在逻辑结构层次上的，而操作的数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的。因此，下面定义的线性表具体实现是建立在存储结构上的。因此，下面定义的线性表的基本操作作为逻辑结构的一部分，每一个操作的具体实现的基本操作作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。只有在确定了线性表的存储结构之后才能完成。第5页，共26页，编辑于2022年，星期一2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储是指用一组地址连续的存储单元依次线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的元素。而顺序存储结构，就是对线性表采用顺存储线性表的元素。而顺序存储结构，就是对线性表采用顺序存储方式存储数据时所使用变量的描述。下面从顺序表及序存储方式存储数据时所使用变量的描述。下面从顺序表及其基本运算两方面来讨论顺序存储结构。其基本运算两方面来讨论顺序存储结构。第6页，共26页，编辑于2022年，星期一2.2.1 2.2.1 顺序表定义顺序表定义简单地说，用顺序存储方法存储的线性表简称为顺序表简单地说，用顺序存储方法存储的线性表简称为顺序表（Sequential List）。线性表中的所有元素按其逻辑顺序相继存）。线性表中的所有元素按其逻辑顺序相继存放在一个连续的存储空间中，其存储地址与次序相同，所以也可以放在一个连续的存储空间中，其存储地址与次序相同，所以也可以说它是一种随机存取的存储结构。下面通过实例描述推导出数据元说它是一种随机存取的存储结构。下面通过实例描述推导出数据元素素ai的存储地址计算公式，并讲解其随机存取的特点。的存储地址计算公式，并讲解其随机存取的特点。第7页，共26页，编辑于2022年，星期一2.2.2 2.2.2 顺序存储结构类型顺序存储结构类型C语言中的数组在内存中占用的存储空间就是一组连续语言中的数组在内存中占用的存储空间就是一组连续的存储区域，所以，数组具有表示顺序表的数据存储区域的的存储区域，所以，数组具有表示顺序表的数据存储区域的优越特性。下面介绍在优越特性。下面介绍在C语言中，实现线性表的顺序存储结语言中，实现线性表的顺序存储结构的类型定义。构的类型定义。定义线性表的顺序存储类型时，用数组来存储线性表中定义线性表的顺序存储类型时，用数组来存储线性表中的所有元素，用整型变量来存储线性表的长度。为了便于进的所有元素，用整型变量来存储线性表的长度。为了便于进行线性表的操作，把用于存储线性表元素的数组和存储线性行线性表的操作，把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中。表长度的变量同时说明在一个记录类型中。第8页，共26页，编辑于2022年，星期一2.2.3 2.2.3 顺序表的基本运算顺序表的基本运算本节主要讨论采用顺序存储结构来实现各种基本的运算，先本节主要讨论采用顺序存储结构来实现各种基本的运算，先介绍求顺序表的长度、判断表是否为空、判断表是否为满、清空介绍求顺序表的长度、判断表是否为空、判断表是否为满、清空表、取顺序表数据元素、显示线性表等较简单的基本运算实现方表、取顺序表数据元素、显示线性表等较简单的基本运算实现方法。对顺序表的创建、查找、插入、删除等复杂操作单独分节讨法。对顺序表的创建、查找、插入、删除等复杂操作单独分节讨论。论。1 求顺序表的长度求顺序表的长度2 判断表是否为空判断表是否为空 3 判断表是否为满判断表是否为满 4 清空表清空表 5 取顺序表数据元素取顺序表数据元素6 显示线性表显示线性表第9页，共26页，编辑于2022年，星期一2.3 2.3 顺序表的建立顺序表的建立顺序表的建立是指实现顺序表的初始化并给各结点关顺序表的建立是指实现顺序表的初始化并给各结点关联相应的数据元素。上一节主要介绍顺序表的较简单的运算，联相应的数据元素。上一节主要介绍顺序表的较简单的运算，而顺序表的建立运算对数据结构初学者来说相对困难些。读而顺序表的建立运算对数据结构初学者来说相对困难些。读者要掌握者要掌握C语言程序设计方法，且具有一定的编程经验才能语言程序设计方法，且具有一定的编程经验才能独立解决上机实验过程中出现的问题。顺序表建立算法实现独立解决上机实验过程中出现的问题。顺序表建立算法实现如下：如下：void Create_List(SqList*L,int n)int i;for(i=0;idatai);L-length=n;第10页，共26页，编辑于2022年，星期一2.4 2.4 顺序表的查找顺序表的查找顺序表的查找是在指定的顺序表顺序表的查找是在指定的顺序表L中查找指定位序中查找指定位序i的数的数据元素或指定数据元素据元素或指定数据元素x的位序。若的位序。若L中存在该序号或其值与中存在该序号或其值与x相等的数据元素，则返回值为该数据元素的值或在线性表相等的数据元素，则返回值为该数据元素的值或在线性表中的位序。顺序表的查找是最基本的查找方法，主要分为按中的位序。顺序表的查找是最基本的查找方法，主要分为按位置查找元素和按内容查找元素两种操作。位置查找元素和按内容查找元素两种操作。第11页，共26页，编辑于2022年，星期一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-1;return(e);第12页，共26页，编辑于2022年，星期一2.4.2 2.4.2 按值查找元素按值查找元素按值查找元素是在顺序表中查找是否有结点值等于给按值查找元素是在顺序表中查找是否有结点值等于给定值定值x的结点，若有，则返回首次找到的其值为的结点，若有，则返回首次找到的其值为x的结点的存的结点的存储位置；如果顺序表中没有与给定值匹配的数据元素，返回储位置；如果顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。顺序表按值查找元素算法实现如一个特殊值表示查找失败。顺序表按值查找元素算法实现如下：下：int Locate_List(SqList L,DataType x)int i=0;while(iL.length&L.datai!=x)i+;if(iL.length)return(i+1);else return 0;第13页，共26页，编辑于2022年，星期一2.4.3 2.4.3 顺序表的查找操作的效率分析顺序表的查找操作的效率分析顺序表是一种随机存取结构，按位置查找时间复杂度为常顺序表是一种随机存取结构，按位置查找时间复杂度为常量量O(1)，故顺序表中按位置查找非常方便。顺序表的按值查找元，故顺序表中按位置查找非常方便。顺序表的按值查找元素算法中的主要运算是比较，比较的次数与给定值在表中的位置素算法中的主要运算是比较，比较的次数与给定值在表中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为和表长有关。当给定值与第一个数据元素相等时，比较次数为1；当与第二个数据元素相等时，比较次数为；当与第二个数据元素相等时，比较次数为2；而当给定值与最；而当给定值与最后一个元素相等时，比较次数为后一个元素相等时，比较次数为n。所以，平均比较次数为。所以，平均比较次数为（n+1）/2。故得出结论，按值查找元素算法的时间复杂度为。故得出结论，按值查找元素算法的时间复杂度为O（n），查找时间与表的长度有关。），查找时间与表的长度有关。第14页，共26页，编辑于2022年，星期一2.5 2.5 顺序表的插入与删除顺序表的插入与删除顺序表的插入与删除操作实现向表中添加新的数据元素顺序表的插入与删除操作实现向表中添加新的数据元素或删除存在的数据元素。插入与删除是表的最常用、最重要或删除存在的数据元素。插入与删除是表的最常用、最重要的两个操作，当然学习起来也是比较困难的。两个操作的实的两个操作，当然学习起来也是比较困难的。两个操作的实现可能涉及前面介绍的所有的算法。现可能涉及前面介绍的所有的算法。第15页，共26页，编辑于2022年，星期一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,ai,ai+1,an)第16页，共26页，编辑于2022年，星期一2.5.1 2.5.1 在顺序表的第在顺序表的第i i个位置插入一个元素个位置插入一个元素第17页，共26页，编辑于2022年，星期一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)第18页，共26页，编辑于2022年，星期一2.5.2 2.5.2 删除顺序表的第删除顺序表的第i i个位置元素个位置元素第19页，共26页，编辑于2022年，星期一2.5.3 2.5.3 顺序表的插入与删除操作的效率分析顺序表的插入与删除操作的效率分析本节开头提到顺序表的插入与删除操作的实现可能涉及本节开头提到顺序表的插入与删除操作的实现可能涉及前面介绍的所有的算法，通过对两算法的操作描述可知，主前面介绍的所有的算法，通过对两算法的操作描述可知，主要涉及对顺序表的判表空、判表满、取表长、查找、取值等要涉及对顺序表的判表空、判表满、取表长、查找、取值等操作，其中还附加了大量结点的移动操作。下面分别分析两操作，其中还附加了大量结点的移动操作。下面分别分析两算法的实现效率。算法的实现效率。1顺序表的插入操作算法的时间复杂度分析顺序表的插入操作算法的时间复杂度分析2顺序表的删除操作算法的时间复杂度分析顺序表的删除操作算法的时间复杂度分析第20页，共26页，编辑于2022年，星期一2.6 2.6 顺序表的典型例题顺序表的典型例题线性表是数据结构中最简单、最常用的一种线性结构，也线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。在线性表中，顺序表的结构又是最简单的，本继知识的学习。在线性表中，顺序表的结构又是最简单的，本节通过一些典型例题来掌握对顺序表的各种操作实现过程。节通过一些典型例题来掌握对顺序表的各种操作实现过程。第21页，共26页，编辑于2022年，星期一2.7 2.7 算法设计实训算法设计实训前面讨论了顺序表的各种操作实例，本节主要介绍顺序前面讨论了顺序表的各种操作实例，本节主要介绍顺序存储结构的上机实训。通过对算法设计的学习，可以理解线存储结构的上机实训。通过对算法设计的学习，可以理解线性表在顺序存储结构下的操作方法，掌握顺序存储结构的常性表在顺序存储结构下的操作方法，掌握顺序存储结构的常见算法。下面介绍采用顺序存储结构实现的学生成绩管理的见算法。下面介绍采用顺序存储结构实现的学生成绩管理的详细设计过程。详细设计过程。第22页，共26页，编辑于2022年，星期一2.7.1 2.7.1 学生成绩管理需求分析学生成绩管理需求分析学生成绩管理是学校教务部门日常工作的重要组成部分，学生成绩管理是学校教务部门日常工作的重要组成部分，其处理信息量很大。本实例的实质是完成对学生成绩信息的其处理信息量很大。本实例的实质是完成对学生成绩信息的建立、查找、插入、修改、删除等功能。首先定义学生的数建立、查找、插入、修改、删除等功能。首先定义学生的数据结构，然后将每个功能封装成函数来完成对数据的操作，据结构，然后将每个功能封装成函数来完成对数据的操作，最后完成主函数的设计来调用各个子函数，实现设计功能并最后完成主函数的设计来调用各个子函数，实现设计功能并得出运行结果。得出运行结果。第23页，共26页，编辑于2022年，星期一2.7.2 2.7.2 学生成绩管理数据结构学生成绩管理数据结构本实例操作数据是一组学生的成绩信息，每条学生的成本实例操作数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成，这组学生的成绩信息具有绩信息由学号、姓名和成绩组成，这组学生的成绩信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据具有顺序表中数据元素的性关系。由此可以看出，这些数据具有顺序表中数据元素的性质，所以该系统的数据采用顺序表来存储比较合适。在具体质，所以该系统的数据采用顺序表来存储比较合适。在具体的实践应用中，读者要学会使用的实践应用中，读者要学会使用C语言中提供的结构体和数语言中提供的结构体和数组来存储顺序表，掌握顺序存储结构的特点。组来存储顺序表，掌握顺序存储结构的特点。第24页，共26页，编辑于2022年，星期一2.7.3 2.7.3 学生成绩管理的实现学生成绩管理的实现结合学生成绩管理需求分析和增加的数据结构可实现抽结合学生成绩管理需求分析和增加的数据结构可实现抽象数据类型的描述，给出最终完善后的结构体描述及各功能象数据类型的描述，给出最终完善后的结构体描述及各功能函数的详细定义。函数的详细定义。1.抽象数据类型描述抽象数据类型描述2.主要功能模块实现主要功能模块实现第25页，共26页，编辑于2022年，星期一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第26页，共26页，编辑于2022年，星期一