线性表

一、前言

    线性结构的特点：

        在数据元素的非空有限集合中，

            1、存在唯一的一个被称为“第一个”的数据元素；

            2、存在唯一的一个被称为“最后一个”的数据元素；

            3、除第一个之外，集合中的每个元素均只有一个前驱；

            4、除最后一个元素外，集合中每一个数据元素都有一个后继；

二、类型定义

    1、概念：一个线性表是n个数据元素的有限序列。

        例如,26个英文字母的字母表（A,B,C,,,,,Z）是一个线性表，表中的数据元素为单个字母字符。

    2、在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。

    3、线性表的特点：

            同一个线性表中的元素必须具有相同的特性，即属于同一个数据对象，相邻数据元素之间存在着序偶关系，若将线性表记为：

    （a1,a2,a3,……an）；

    则表中的a1是a2的直接前驱元素，a2是a1的直接后继元素

    4、线性表的长度：线性表中数据元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表

    5、位序：ai是第i个数据元素，称i是数据元素ai在线性表中的位序。

    6、抽象数据类型线性表的定义如下：

       ADT List

{

数据对象：D={ai|ai属于ElemSet,i=1,2,3,......n,n>=0}

数据关系：R1={<ai-1,ai>|ai-1，ai属于D,i=2....,n}

基本操作：

InitList(&L)

操作结果：构造一个空的线性表

DestroyList(&L)

初始化条件：线性表已经存在

操作结果：销毁线性表

ClearList(&L)

初始化条件：线性表已经存在

操作结果：将L重置为空表

ListEmpty(L)

初始条件：线性表已经存在

操作结果：返回L中元素的个数。

GetElem(L,i,&e)

初始条件：线性表已经存在，1<=i<=ListLength(L)

操作结果：用e返回线性表L中第i个元素的值

LocateElem(L,e,compare())

初始条件：线性表L已经存在，compare()是数据元素判定函数

操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的元素不存在，则返回值为0

PriorElem(L,cur_e,&pre_e)

初始条件：线性表已经存在

操作结果：若cur_e是L中的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义

NextElem(L,cur_e,&next_e)

初始条件：线性表已经存在

操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义

ListInsert(&L,i,e)

初始条件：线性表L已经存在，1<=i<=ListLength(L)+1

操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1

ListDelete(&L,i,&e)

初始条件：线性表已经存在且非空，1<=i<=ListLength(L)

操作结果：删除L中第i个元素，并用e返回其值，L的长度减1

ListTraverse(L,visit())

初始条件：线性表已经存在

操作结果：依次对L的每个元素调用函数Visit().一旦visit()失败，则操作失败

}ADT List

    7、线性表组合

        已知La,Lb，求La = LaULb