2018-05-28 线性表

2018-05-29  本文已影响0人  多佳小昕
一、线性表：
  1. 定义：由零个或多个数据元素组成的有限序列。
判断
  1. 数据类型
    是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
    例如很多编程语言的整型，浮点型，字符型这些指的就是数据类型。
  2. 抽象
    是指抽取出事物具有的普遍性的本质。它要求抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节。
    意义在于数据类型的数学抽象特性。
    描述抽象数据类型的格式：
ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作
endADT

二、抽象数据类型

  1. ADT 线性表（List）
  2. Data
    线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
  3. Operation
    InitList(*L): 初始化操作，建立一个空的线性表L。
    ListEmpty(L): 判断线性表是否为空表，若线性表为空，返回true，否则返回false。
    ClearList0(*L): 将线性表清空。
    GetElem(L,i,*e): 将线性表L中的第i个位置元素值返回给e。
    LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
    ListInsert(*L,i,e): 在线性表L中第i个位置插入新元素e。
    ListDelete(*L,i,*e): 删除线性表L中第i个位置元素，并用e返回其值。
    ListLength(L): 返回线性表L的元素个数。
  4. endADT
    基本实现：
void unionL(List *La, list Lb)
{
    int La_len, Lb_len, i;

    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);

    for( i=1; i <= Lb_len; i++ )
    {
        GetElem(Lb, i, &e);
        if( !LocateElem(*La, e) )
        {
            ListInsert(La, ++La_len, e);
        }
    }
}

三、顺序存储结构

线性表有两种物理存储结构：顺序存储结构和链式存储结构。
物理上的存储方式事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。

  1. 顺序存储结构
    指的是用一段地址连续的存储单元依次存储线性表的数据元素。
    线性表（a1,a2,…,an）的顺序存储如下：线性表有两种物理存储结构：顺序存储结构和链式存储结构。
    线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
    线性表（a1,a2,…,an）的顺序存储如下：


    image.png

    对数组进行封装：

#define MAXSIZE 20    
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;    // 线性表当前长度
} SqList;

顺序存储结构封装需要三个属性：
存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
线性表的最大存储容量：数组的长度MaxSize。
线性表的当前长度：length。
数组的长度与线性表的当前长度需要区分一下：数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会变化的。

  1. 地址计算方法

LOC(ai) = LOC(a1) + (i-1)*c

通过这个公式，我们可以随时计算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么它的存储时间性能当然就为0(1)，我们通常称为随机存储结构。
实现GetElem的具体操作：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

// Status 是函数的类型，其值是函数结果状态代码，如OK等。
// 初始条件：顺序线性表L已存在，1 <= i <= ListLength(L)
// 操作结果：用e返回L中第i个数据元素的值。
// 判断：错误情况，否则把L中data相应的下标返回给e指针。
Status GetElem(SqList L, int i, ElemType *e)
{
    if( L.length==0 || i<1 || i>L.length )
    {
        return ERROR;
    }
    *e = L.data[i-1]
    return OK;
}
  1. 获得元素操作
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L)。 */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1。*/

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;
    if( L->length == MAXSIZE )  // 顺序线性表已经满了
    {
        return ERROR;
    }
    if( i<1 || i>L->length+1)   // 当i不在范围内时
    {
        return ERROR;
    }
    if( i <= L->length )   // 若插入数据位置不在表尾
    {
        /* 将要插入位置后数据元素向后移动一位 */
        for( k=L->length-1; k >= i-1; k-- )
        {
            L->data[k+1] = L->data[k];
        }
    }
    L->data[i-1] = e;  // 将新元素插入
    L->length++;
    return OK;
}

/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;
    if( L->length == 0 )
    {
        return ERROR;
    }
    if( i<1 || i>L->length )
    {
        return ERROR;
    }
    *e = L->data[i-1];
    if( i < L->length )
    {
        for( k=i; k < L->length; k++ )
        {
            L->data[k-1] = L->data[k];
        }
    }
    L->length--;
    return OK;
}

存取/在最后删除插入元素：O(1)
删除、插入：平均时间复杂度：O(n)


优点：
无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速地存取表中任意位置的元素。
缺点：
插入和删除操作需要移动大量元素。
当线性表长度变化较大时，难以确定存储空间的容量。
容易造成存储空间的“碎片”。

四、链式存储结构

  1. 特点
  1. 我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点(Node)。
  1. 头指针与头结点
  1. 单链表存储结构
单链表
typedef struct Node
{
ElemType data;      // 数据域
struct Node* Next;  // 指针域
} Node;
typedef struct Node* LinkList;

p->data = ai，那么p->next->data = ?
答案：p->next->data = ai+1。

/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */

Status GetElem( LinkList L, int i, ElemType *e )
{
    int j;
    LinkList p;
    p = L->next;
    j = 1;
    while( p && j<i )
    {
        p = p->next;
        ++j;
    }
    if( !p || j>i )
    {
        return ERROR;
    }
    *e = p->data;
    return OK;
}

时间复杂度为O(1 )

上一篇下一篇

猜你喜欢

热点阅读