chapt2线性表一

1、第二章 线性表 线性表概念及其逻辑结构 线性表的存储结构 顺序存储 链式存储 数组 一维数组 结构数组 二维数组 链表 循环链表 静态链表 线性表应用实例 有序线性表1线性表（一） 线性表概念及其逻辑结构 线性表的存储结构 顺序存储 链式存储 数组 一维数组 结构数组 二维数组21 线性表及其逻辑结构一、线性表概念与特性线性表是最简单、最常用的一种数据结构 。通常线性表只被广泛地定义为是“n个元素的有限序列”，n0，表示线性表元素个数 ，也称线性表的表长。线性表中数据元素之间的关系是线性排列的有次序关系，除了首元素和尾元素之外，其它数据元素都是首尾相接的。 线性表的逻辑结构简单，便于实现存储和

2、操作。在实际应用中被广泛采用。线性表可以按照其逻辑顺序在计算机内实现顺序存储。也可不按照逻辑顺序，以链式结构动态地存储。常用的数据结构诸如数组、堆栈、队列等都被称为线性表。3二、线性表逻辑结构特征均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。线性关系：数据元素之间的相对位置是线性的。首元素与尾元素唯一；除尾元素元素之外，各元素均有唯一的直接后继。除首元素之外，各元素均有唯一的直接前驱。有序性：各数据元素在线性表中的位置只取决于它们的序。有限长度：是 n个同类元素的有限集合。当线性表元素个数 n=0时称为空表。非空的线性表（n0）记作

3、： (a1 ， a2，an) 。通常可用二元组表示为L=(D，R)。4三、线性表的基本操作 1）Setnull（L） 置空表 （初始化线性表L为空表） 2）ListLength（L） 求表长度；求表中元素个数 3）GetElem（L，i，e） 取表中第i个元素（1in） 4）PriorElem（L，i） 取i的前趋元素 5）NextElem（L，i） 取i的后继元素 6）LocateElem（L，e） 返回指定元素在表中的位置 7）ListInsert（L，i，e）插入元素 8）ListDelete（L，e） 删除元素 9）ListEmpty（L） 判别表是否为空 10）ClearList（L

4、）清除所有元素 11）InitList（&L）同第一个，初始化线性表为空 12）ListTraverse（L）遍历输出所有元素 13）Find（L，e）查找并返回元素 14）ListUpdate（L，e）修改元素 15）ListSort（L）对所有元素重新按给定的条件排序 5四、线性表的抽象数据类型描述抽象数据类型线性表描述为： ADT List 数据对象：D=ai|1in, n0, ai属于ElemType类型 数据关系：R=| ai, ai+1D, i=1,n-1 基本运算： Setnull（L） /置空表 （初始化线性表L为空表） ListLength（L） / 求表长度；求表中元素个数

5、 GetElem（L，i,，e） /取表中第i个元素（1in） ADT List62 线性表的存储结构一、线性表的两种存储结构线性表基本存储结构有两种：顺序存储结构链式存储结构 顺序存储的线性表称为顺序表。是静态存储模式，符合静态存储特性。典型的数据结构如一维数组，以及由它描述（仿真，即实现映像存储）的较为高级的数据结构，如数组栈、数组队列、堆、基于数组的图形等。链式存储的线性表称为链表。是动态存储模式。符合动态存储特性。典型的数据结构如单链表，以及由它描述的较为高级的数据结构以及复杂链表，如链栈、链队列、多重链表、循环链表等。7二、线性表的存储结构特性1、顺序存储结构顺序存储结构属于静态内存

6、配置，使用一组连续的存储单元存储元素，这种存储结构基本特点是：逻辑上相邻的元素，物理存储位置相也相邻。所需存储空间需要在数据操作之前申请。程序运行中数据空间通常无变化，或通过动态数组申请增补空间。元素存储位置与其在线性表中的逻辑序相关联（如为逻辑位置的函数），通常以一维数组下标（整型向量）来表示。数据元素具备随机访问特性。 顺序存储空间计算：假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（字节数）为sizeof(ElemType)，整个线性表n个元素所占用存储空间的大小为 ：n*sizeof(ElemType)82、链式存储结构特性链表是链式存储的结构，属于动态内存配置，

7、使用一组任意的存储单元存储元素。这组存储单元可以是连续的，也可以是不连续的。这种存储结构基本特点是：逻辑上相邻的元素在物理位置上并不需要相邻。所需内存空间动态配置，可在程序运行过程中申请存储空间。可随时释放不需要的内存空间。元素存储位置以数据结点中的指针值（整型）来表示。数据元素不具备随机访问特性。链式存储空间管理： 欲创建新结点s，则使用如下方式申请存储空间： s=(LinkList *)malloc(sizeof(LinkList);释放结点s所占用的存储空间： free(s);93 数组数组是最基础和重要的数据结构之一。一维数组这种最简单的数据结构通常被用作描述占用连续内存空间的线性表存

8、储映像。一、数组概念及特性数组(Arry)是数据结构中最基本的结构类型，是存储同一类型数据的数据结构。它是一种循序式的结构。几乎所有的程序设计语言都允许用数组来描述数据。数组特性：同类型元素；循序结构（可实现顺序存储）； （对元素的）随机访问特性（因其循序性）。对于每一个数组元素而言，都有一个索引值（Index）和一个内容值（Value） ，表示其相对位置和相应的数据。数组使用的是一种静态的内存空间配置，需要程序设计者事先定义好数据类型和所需要的内存空间的大小，程序在编译过程中会自动按照事先的定义配置内存空间。 10静态的内存空间配置缺乏使用弹性。设计程序时，若使用数组存储数据（比如执行过程中

9、的某个结果或最终结果），如果事先定义的数组空间过小，使用时就容易造成程序的执行错误，反之如果定义的数组空间过大，则造成内存空间的浪费。正因为数组的这种静态的内存空间配置，所以针对数组通常只做两种运算：给定一组下标，存取相应的数据元素。给定一组下标，修改相应数据元素中某个数据项的值。 二、一维数组 1、数组的说明 象对变量一样, 数组也必须在使用之前先定义。数组的定义包括：( 1 ) 数组元素的类型说明( 2 ) 存储在数组中的最大元素个数的说明。一个典型的数组定义为: 数据类型 数组名 长度 11通常使用数组的下标值，也就是索引值来标识某个数组的元素。例如 a5。2、数组元素的存储 在一维数组

10、中，一旦数组元素a1的存储地址LOC(a1)确定，并假设每个数据元素占用k个存储单元，则任一数据元素ai 的存储地址LOC(ai)就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in)【例】声明一个长度为10的整型一维数组（10个数据元素），数组名NumberA。 int NumberA10；按照C语言数组元素下标从0开始，则有如下公式：NumberAi的内存位置 = 数组首元素位置 + ( i 声明数据类型所占内存的大小 )123、字符型一维数组字符数组用于存放字符串和字符型数据。有两种用法：一是当作字符的数组来使用。这时的用法与整数的数组、 实数的数组等相同，对字

11、符数组的输入、输出、赋值、引用等都是针对单个的元素进行。二是更为重要的用法即存储、处理字符串。这时它除了可以像普通数组一样使用外，还可以把字符串作为一个整体进行操作。字符串常量与字符串变量 ：字符串常量是用双引号包围的字符序列。存储字符串常量时，系统会在字符序列后自动加上 0 标志字符串的结束。字符串的长度定义为字符串中的有效字符数，不包括结束标志0和双引号。 C语言中所谓的字符串变量是以0作为结束标志的字符数组，用于存储和处理字符串常量。在书中统称为字符串的，既可能是字符串常量也可能是存储了字符串常量的字符串变量，即特殊的字符数组。 13字符数组的初始化说明 (1) 用字符对字符数组初始化。

12、这时把字符数组当作普通数组看待, 产生的数组不会有结束符0。 例：char rat5=H,E,L,L,O;(2) 用字符串常量对字符数组初始化。这时把字符数组当作字符串变量看待。 例：char panic6=“HELLO“; （或char panic6=“HELLO“; ） 这时存放在数组panic中的字符包含结束标志0，因此与初始化(1)等价。 指定了数组的长度，那么其大小不得小于初始化字符串的长度。多余的元素位置被系统自动初始化为0。 14【例】初始化字符数组： static char word=H,e,l,l,o,!; (静态全局变量) 按照这个语句, 内存中将实际保留六个字符的空间。如

13、下图： 为了打印出数组 word 的内容, 我们访问数组的每一个元素, 且用 %c 格式显示它。可以使用下面的语句: for(i=0;ii，或ji）。存储方法：可以设计一个一维数组，按照以行为主序或以列为主序将其压缩存储到一维数组上，以节省空间。 对一个大小为n*n的方阵： 转换成以行为主的一维数组： Dataij的位置=n+(n-i+1)*i/2+(j-i) （即为一维数组的Index ） 转换成以列为主的一维数组： Dataij的位置=j*(j+1)/2+i （即为一维数组的Index ）26【例】设计一个将上三角数组转换成以列为主序的一维数组的程序。 1）声明所需数组空间，依据是欲存储元素个数n*(1+n)/2。n为方阵的行或列数。 2）利用两层循环（i、j控制）遍历原三角数组中的每一笔数据，当满足条件ij时,即当元素的行数小于等于列数时，则将元素存储于一维数组的j*(j+1)/2+i位置，即为其index。 程序主要语句：for(i=0