Fork me on GitHub

线性表

发表于 | 分类于 | 浏览 次

简介

什么是线性表？

线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。
在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。

线性结构的特点为

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

  1. 集合中存在唯一的一个“第一元素”
  2. 集合中存在唯一的一个“最后元素”
  3. 除最后元素在外，具有唯一的后继
  4. 除第一元素之外，均有唯一的后继

线性表的类型定义

介绍

  1. 数据表是最常用且最简单的一种数据结构。
  2. 在稍复杂的线性表中，一个数据元素可以由若干个数据项（item）。在这种情况下，常把数据元素成为记录（record）,含大量记录的线性表又称为文件（file）。
  3. 线性表定义如下：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表
    表中相邻元素之间存在着顺序关系。将ai-1 称为ai 的直接前趋，ai+1 称为ai 的直接后继。就是说：对于ai，当i=2，…，n 时，有且仅有一个直接前趋ai-1.，当i=1，2，…，n-1 时，有且仅有一个直接后继ai+1，而a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。

抽象数据类型线性表的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ADT List  {  
   数据对象：D = {ai|ai∈EleamSet,i = 1,2,...,n,n>=0}
   数据关系：R1 = {<ai-1,ai>|ai-1,ai∈D,i = 2,...,n}
   基本操作：
    InitList (&L);
        操作结果：构造一个空线性表L  
    DestroyList(&L);
        初始条件：线性表L已存在
        操作结果：销毁线性表L  
    ClearList(&L);
        初始条件：线性表L已存在
        操作结果：将L重置为空表  
    ListEmpty(L);
        初始条件：线性表L已存在
        操作结果：判断若存在的表L为空表，返回TRUE，否则返回FALSE  
    Listlength(L);
        初始条件：线性表L已存在
        操作结果：返回线性表L中的数据元素个数  
    GetElem(L,i,&e);
        初始条件：线性表L已存在，1<=i<=ListLength(L)
        操作结果：用e返回L中第i个数据元素的值  
    LocateElem(L,e,compare());
        初始条件：线性表L已存在,compare()是数据元素判定函数
        操作结果：返回l中第一个与e满足关系compare（）的元素的位序。若这样的数据元素不存在，则返回值为0  
    PriorElem(L,cur_e,&pre_e);
        初始条件：线性表L已存在
        操作结果：若cur_e是L的数据元素（不是第一个），则用pre_e返回它的前驱，否则操作失败，pre_e无定义
    NextElem(L,cur_e,&next_e);
        初始条件：线性表L已存在
        操作结果：若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);
        初始条件：线性表L已存在且非空
        操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1  
    ListTraverse(L,vist());
        初始条件：线性表L已存在
        操作结果：依次对L的每个数据元素调用vist()。一旦visit()失败，则操作失败  
}ADT List

合并线性表LA和LB

假设利用两个线性表LA和LB分别表示两个集合A和B（即线性表中的数据元素即为集合中的成员），现要求一个新的集合A = A∪B。
操作：扩大线性表LA，将存在于线性表LB中而不存在线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插之。
算法描述如下：

1
2
3
4
5
6
7
8
9
void union(List &La,List Lb){
  //将所有在线性表Lb中但不在La中的数据元素插入到La中
  La_len = ListLength(La);Lb_len = ListLength(Lb);//求线性表的长度
  for(i = 1;i <= Lb_len;i++){
      GetElem(Lb,i,e);
      if(!LocateElem(La,e,equal))
          ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之
  }
 }//union

该程序的时间复杂度为O( ListLength(La)* ListLength(Lb))

合并LA和LB为新的线性表LC

已知线性表LA和LB中的数据元素按非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按非递减有序排列。
基本算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void MergeList(List La,List Lb,List &Lc){
	//已知线性表LA和LB中的数据元素按非递减有序排列
	//归并La和Lb得到新的线性表Lc,Lc的数据元素也非递减有序排列
	InitList(Lc);
	i = j = 1;
	k = 0;
	La_len = ListLength(La);Lb_len = ListLength(Lb);//求线性表的长度
	while((i<=La_len) && (j<=Lb_len)){//La和Lb均非空
		GetElem(La,i,ai);
		GetElem(Lb,j,bj);
		if(ai <= bj){
			ListInsert(Lc,++k,ai);
			++i;
		}else{
			ListInsert(Lc,++k,bj);
			++j;
		}
	}
	while(i <= La_len){
		GetElem(La,i++,ai);
		ListInsert(Lc,++k,ai);
	}
	while(i <= Lb_len){
		GetElem(Lb,j++,bj);
		ListInsert(Lc,++k,bj);
	}
}//MergeList

该程序的时间复杂度为O(ListLength(La)+ ListLength(Lb))

线性表的顺序表示和实现

线性表的顺序存储

  1. 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
  2. 假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。
    则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：
    LOC(ai+1) = LOC(ai) + L
    一般来说，线性表的第i个数据元素ai的存储位置为
    LOC(ai) = LOC(a1) + (i-1)*L
    式中LOC(ai)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。
  3. 线性表的这种（第二条）机内表示称作线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。
  4. 线性表的顺序存储结构示意图如下:

1

线性表的顺序表示与实现代码

  1. c语言动态分配的一维数组

    1
    2
    3
    4
    5
    6
    7
    8
    // --------线性表的动态分配顺序存储结构--------
    #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
    #define LISTINCREMENT 10  // 线性表存储空间的分配增量
    typedef struct {
        ElemType *elem; // 数据元素的地址
        int   length; // 当前长度
        int   listsize;//当前分配的存储容量(以sizeof(ElemType)为单位)
    }

  2. 线性表顺序表示操作实例代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    /***
     *Arrlist.h
     *Purpose:
     *   线性表顺序存储结构的创建、数据插入、数据获取、获取长度、删除数据、清空数据、销毁顺序存储结构方法的实现
     ***/
    #include <stdio.h>
    #include <stdlib.h>
    #include "string.h"

    #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
    #define LISTINCREMENT 10   // 线性表存储空间的分配增量

    // 函数结果状态代码
    #define TRUE 1
    #define FALSE 0
    #define OK  1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERLOW -2

    // Status 是函数的类型, 其值是函数结果状态代码
    typedef int Status;
    typedef int ElemType;

    // -----线性表的动态分配顺序存储结构-----
    typedef struct
    {
        ElemType * elem; // 存储空间基址
        int length;      // 当前长度
        int listsize;    // 当前分配的存储容量(以sizeof(ElemType)为单位)
    }SqList;

    // 操作结果：构造一个空的线性表L
    Status InitList(SqList *L){
        // 为结构体中的存储空间分配内存
        L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
        if(! L->elem) exit(OVERLOW); // 存储分配失败

        L->length = 0; // 空表长度为0
        L->listsize = LIST_INIT_SIZE; // 初始存储容量
        return OK;
    }// InitList_sq

    // 初始条件：线性表L已存在
    // 操作结果：销毁线性表L
    Status DestroyList(SqList *L){
        // 判断指针是否为空
        if (L == NULL) {
            return ERROR;
        }
        // 释放calloc, malloc, realloc动态分配的空间
        free(L->elem);
        L->elem = NULL;
        L->length = 0;
        L->listsize = 0;
        return OK;
    }// DestroyList

    // 初始条件：线性表L已存在
    // 操作结果：将L重置为空表。
    Status ClearList(SqList *L){
        // 判断指针是否为空
        if (L == NULL) {
            return ERROR;
        }

        L->length = 0;
        return OK;
    }// ClearList

    // 初始条件：线性表L已存在
    // 操作结果：若L为空表，则返回TRUE,否则返回FALSE
    Status ListEmpty(SqList L){
        if (L.length == 0)
            return TRUE;
        else
            return FALSE;
    }// ListEmpty

    // 初始条件：线性表L已存在
    // 操作结果：返回L中数据元素个数
    Status ListLength(SqList L){
        return L.length;
    }

    // 初始条件：线性表L已存在, 1<=i<=ListLength(L)
    // 操作结果：用e返回L中第i个数据元素的值
    Status GetElem(SqList L, int i, ElemType *e){
        if (i<1 || i>L.length)
            exit(ERROR);
        *e =* (L.elem+i-1);
        return OK;
    }

    // 初始条件：线性表L已存在，compare()是数据元素判定函数(满足为1,否则为0)。
    // 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0.
    Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType,ElemType)){
        ElemType *p;
        int i = 1; // i的初值为第一个元素的位序
        p = L.elem; // p的初值为第一个元素的存储位置
        while (i <= L.length && !compare(*p++,e)) {
            ++i;
        }

        if (i<=L.length)
            return i;
        else
            return ERROR;

    }

    // 初始条件：线性表L已存在
    // 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
    Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e){
        int i = 2;
        ElemType *p = L.elem + 1;
        while (i <= L.length && *p!=cur_e) {
            p++;
            i++;
        }
        if (i>L.length)
            return INFEASIBLE;
        else{
            *pre_e = *--p;
            return OK;
        }
    }

    // 初始条件：线性表L已存在
    // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后续，否则操作失败,next_e无定义
    Status NextElem(SqList L, ElemType cur_e, ElemType *next_e){
        int i = 1;
        ElemType *p = L.elem;
        while (i < L.length && *p!=cur_e) {
            i ++;
            p ++;
        }

        if (i == L.length)
            return INFEASIBLE;
        else{
            *next_e = *++p;
            return OK;
        }
    }

    // 初始条件：线性表L已存在,1<=i<=ListLength(L)+1
    // 操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1
    Status ListInsert(SqList *L, int i, ElemType e){
        ElemType *newbase,*q,*p;
        if(i<1 || i>L->length+1)
            return ERROR; // i值不合法
        if(L->length>=L->listsize) // 当前存储空间已满,增加分配
        {
            newbase = (ElemType *)realloc(L->elem,(L->listsize + LISTINCREMENT) * sizeof(ElemType));
            if(!newbase) exit(OVERLOW); // 存储分配失败
            L->elem = newbase; // 新基址
            L->listsize += LISTINCREMENT; // 增加存储容量
        }

        q=L->elem+i-1; /* q为插入位置 */
        for(p=L->elem+L->length-1;p>=q;--p) /* 插入位置及之后的元素右移 */
            *(p+1)=*p;
        *q=e; /* 插入e */
        ++L->length; /* 表长增1 */
        return OK;
    }


    // 初始条件：线性表L已存在且非空，1,=i<=ListLength(L)
    // 操作结果：删除L的第i个数据元素，并用e返回其值,L的长度-1
    Status ListDelete(SqList *L, int i, ElemType *e){
        ElemType *p, *q;

        if (i<1 || i>L->length)
            return ERROR; // i值不合法
        p = L->elem+i-1; // p为被删除元素的位置
        *e = *p; // 被删除元素的值赋给e
        q = L->elem + L->length - 1; // 表尾元素的位置

        for (++p; p<=q; ++p) { // 被删除元素之后的元素左移
            *(p-1) = *p;
            L->length--; // 表长-1
        }
        return OK;
    }

    // 初始条件：线性表L已存在
    // 操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败
    Status ListTraverse(SqList L, void(*vi)(ElemType*)){
        ElemType *p;
        int i;
        p = L.elem;
        for (i=1; i<=L.length; i++) {
            vi(p++);
        }

        printf("\n");
        return OK;
    }

  3. 测试代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    //
    //  main.c
    //  arrlist
    //


    #include <stdio.h>
    #include "Arrlist.h"

    // 判断是否相等的函数，Union()用到
    Status equal(ElemType c1,ElemType c2)
    {
        if(c1==c2)
            return TRUE;
        else
            return FALSE;
    }

    // 将所有在线性表Lb中但不在La中的数据元素插入到La中
    void Union(SqList *La,SqList Lb)
    {
        ElemType e;
        int La_len,Lb_len;
        int i;
        La_len=ListLength(*La); // 求线性表的长度
        Lb_len=ListLength(Lb);
        for(i=1;i<=Lb_len;i++)
        {
            GetElem(Lb,i,&e); // 取Lb中第i个数据元素赋给e
            if(!LocateElem(*La,e,equal)) // La中不存在和e相同的元素,则插入之
            {
               ListInsert(La,++La_len,e);
            }

        }
    }

    void print(ElemType *c)
    {
        printf("%d ",*c);
    }

    int main(int argc, const char * argv[]) {
        // insert code here...
        printf("Testing start!\n");
        SqList La,Lb;
        ElemType t1,t2,t3;
        t1 = 10;
        t2 = 20;
        t3 = 30;
        int t1_length,t2_length,t3_length, i;

        // 构造一个空的线性表La
        InitList(&La);
        // 插入数据元素t1
        ListInsert(&La, 1, t1);
        // 获取线性表长度
        t1_length = ListLength(La);
        // 插入数据元素t2
        ListInsert(&La, 2, t2);
        t2_length = ListLength(La);
        // 插入数据元素t3
        ListInsert(&La, 3, t3);
        t3_length = ListLength(La);
        // 输出每次插入新元素后 表L的长度变化
        printf("t1_length=%d,t2_length=%d,t3_length=%d\n",t1_length,t2_length,t3_length);

        // 输出表La的内容
        printf("La= ");
        ListTraverse(La,print);

        // 在表Lb中插入5个元素
        InitList(&Lb);
        for (i=1; i<=5; i++) {
            ListInsert(&Lb, i, 2 * i);
        }

        // 输出表Lb的内容
        printf("Lb= ");
        ListTraverse(Lb, print);
        // 输出表Lb长度
        printf("Lb length = %d\n",ListLength(Lb));

        // La U Lb
        Union(&La, Lb);

        //输出新表L的内容
        printf("new La= ");
        ListTraverse(La,print);
        printf("end!!!\n");
        return 0;
    }

  4. 运行结果，如下图所示：

2

时间复杂度

插入算法的时间性能分析

顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x ，从ai 到an 都要向下移动一个位置，共需要移动n－i＋1个元素，而i 的取值范围为：1<= i<= n+1，即有n＋1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：

3

因此，在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为Ｏ(n)。

删除算法的时间性能分析

与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an 都要向上移动一个位置，共移动了n-i 个元素，所以平均移动数据元素的次数：

4

因此，顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。

结语

接下来，我将继续学习线性表的链式表示和实现

最近访客

本文地址：https://tonynyl.github.io/2017/04/27/线性表/
转载请注明出处，谢谢！

坚持原创技术分享，您的支持将鼓励我继续创作！
显示 Gitment 评论
0%