第2篇 线性表的顺序存储.ppt

第2章 线性表的顺序存储 线性表有两种存储方法：顺序存储和链式存储。线性表的顺序存储是指在计算机中用一组地址连续的存储单元依次存储数据元素来表示线性表。换句话说，就是将线性表中的数据元素一个接着一个地存放在某个存储区域中。本章主要讲解线性表的逻辑结构特性、顺序存储结构及它的基本运算和实现算法。 2.1 线性表的逻辑结构 简单地说，线性表的逻辑结构是指线性表数据元素之间的关系。线性结构是最简单且最常用的数据结构，而线性表是最典型的线性结构。线性结构的特点是数据元素之间是一种线性关系，即一对一关系。下面从线性表的定义及基本运算方面来讨论它的逻辑结构。 2.1.1 线性表的定义 线性表定义如下：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为： (a1,a2,…ai-1,ai,ai+1,…an) 2.1.2 线性表的数学定义和逻辑图 从数学定义方面来说，线性表（Linear List）是具有相同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示（n≥0）。当n=0时，表示线性表是一个空表，即表中不包含任何元素。设序列中第i个元素为ai（1≤i≤n），则线性表的一般表示为： (a1,a2,…ai-1,ai,ai+1,…an) 2.1.3 线性表的基本操作 数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的。因此，下面定义的线性表的基本操作作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。 2.2 线性表的顺序存储结构 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的元素。而顺序存储结构，就是对线性表采用顺序存储方式存储数据时所使用变量的描述。下面从顺序表及其基本运算两方面来讨论顺序存储结构。 2.2.1 顺序表定义 简单地说，用顺序存储方法存储的线性表简称为顺序表（Sequential List）。线性表中的所有元素按其逻辑顺序相继存放在一个连续的存储空间中，其存储地址与次序相同，所以也可以说它是一种随机存取的存储结构。下面通过实例描述推导出数据元素ai的存储地址计算公式，并讲解其随机存取的特点。 2.2.2 顺序存储结构类型 C语言中的数组在内存中占用的存储空间就是一组连续的存储区域，所以，数组具有表示顺序表的数据存储区域的优越特性。下面介绍在C语言中，实现线性表的顺序存储结构的类型定义。 定义线性表的顺序存储类型时，用数组来存储线性表中的所有元素，用整型变量来存储线性表的长度。为了便于进行线性表的操作，把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中。 2.2.3 顺序表的基本运算 本节主要讨论采用顺序存储结构来实现各种基本的运算，先介绍求顺序表的长度、判断表是否为空、判断表是否为满、清空表、取顺序表数据元素、显示线性表等较简单的基本运算实现方法。对顺序表的创建、查找、插入、删除等复杂操作单独分节讨论。 1． 求顺序表的长度 2 ．判断表是否为空 3 ．判断表是否为满 4 ．清空表 5 ．取顺序表数据元素 6 ．显示线性表 2.3 顺序表的建立 顺序表的建立是指实现顺序表的初始化并给各结点关联相应的数据元素。上一节主要介绍顺序表的较简单的运算，而顺序表的建立运算对数据结构初学者来说相对困难些。读者要掌握C语言程序设计方法，且具有一定的编程经验才能独立解决上机实验过程中出现的问题。顺序表建立算法实现如下： void Create_List(SqList *L,int n) { int i; for (i=0;in;i++) scanf(%d,L-data[i]); L-length=n; } 2.4 顺序表的查找 顺序表的查找是在指定的顺序表L中查找指定位序i的数据元素或指定数据元素x的位序。若L中存在该序号或其值与x相等的数据元素，则返回值为该数据元素的值或在线性表中的位序。顺序表的查找是最基本的查找方法，主要分为按位置查找元素和按内容查找元素两种操作。 2.4.1 按位置查找元素 顺序表是一种随机存取结构，所以在顺序表中按位置查找元素非常容易，只要查找位置合法，可直接返回对应的数据元素。 按位置查找元素算法实现如下： DataType Locate_List (SqList L ,int i) { DataType e; if(i1||i Length_List(L)) { printf(输入的位置非法!); return 0; } e=L.data[i-1]; return (e);