线性表的顺序存储

线性表需要学习的内容

image.png

线性表的定义

. 首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。

2. 然后，线性表强调是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

如果用数学语言来进行定义：

若将线性表记为(a1, ……, ai-1, ai, ai+1, ……,an),则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当丨=1, 2, ……, n-1时，ai有且仅有一个直接后继，当i=2, 3, ……, n时，ai有且仅有一个直接前驱。

所以线性表元素的个数n (n>0)定义为线性表的长度，当n=0时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

这就是线性表的定义

线性表的抽象定义类型ADT

    ADT 线性表 (List)
Data
Operation  
    void initList(*L);  //创建并初始化一个空线性表，如果成功返回true，修改表传指针   
    bool listEmpty(L);  //判断一个线性表是否为空，不修改表传值   
    void clearList(*L); //清空一个线性表，成功返回true   
    bool getElem(L,i,*e);   //从某个位置取出元素并赋值给e(i的范围是[1,L.length])，修改e的值所以传递一个指针，成功返回true  
    int locateElem(L,e);    //查找线性表中是否有e，如果有返回它的位置(从1开始)，否则返回0表示失败  
    bool listInsert(*L,i,e);    //插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1]) ，成功返回true   
    bool listDelete(*L,i,*e);   //删除在第i个位置上的元素(i的取值范围是[1,L.length]),删除的元素赋给e，成功返回true  
   int listLength(L);   //返回线性表的元素个数  
endADT

实现两个线性表集合A和B的并集操作

void unionL(List *la,List lb){  
int index;  
int laLength = listLength(*la); //得到a的长度，需要一个线性表而不是一个地址   
int lbLength = listLength(lb);}   
ElemType e; //声明一个元素   
  
 for(index=1;index<=lbLength;index++){  //遍历lb   
    getElem(lb,index,&e);   //依次得到lb中的元素   
    if(!locateElem(*la,e)){ //检查是否在la中出现   
        listInsert(la,++laLength,e);    //没有出现则插入队尾，前自增！   
    }  
 } 
}

对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、Listlnsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构，说白了，就是在内存中找了块地方，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中

线性表的顺序存储的结构体定义为：

  #define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType;   /* ElemType类型根据实际情况而定，这里假设为int */

typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length;             /* 线性表当前长度 */
}SqList;

描述顺序存储结构需要三个属性：

存储空间的起始位置：数组data,它的存储位置就是存储空间的存储位置。

线性表的最大存储容量：数组长度MaxSize。

线性表的当前长度：length。

线性表的初始化

初始化就是建立一个空线性表，那直接把长度置为0就行了

 /* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}

这里 InitList(SqList *L) 用了地址传递

因为要初始化，要对线性表本身进行操作，所以不能用值传递。值传递不会改变实参的值嘛。地址传递的话呢，实际上在函数内部执行了这么一个操作：L = &L. 所以操作函数内部的L，也就相当于操作外部的线性表L。其实地址传递也是值传递。不过这个值是地址而已。

就是说，需要修改表的就传指针，不需要修改表的传值就行了。

#include "stdio.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType;   /* ElemType类型根据实际情况而定，这里假设为int */
typedef int Status;     /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length;             /* 线性表当前长度 */
}SqList;

/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
    L->length=0;
    return OK;
}

int main()
{
    SqList L;
    ElemType e;
    Status i;

    i=InitList(&L);
    printf("初始化L后：L.length=%d\n",L.length);
}

程序运行结果：

初始化L后：L.length=0

函数内部 L->length=0; 使用箭头，而在外面调用的时候 L.length 用实心点在函数内部，传递的参数是 *L，那么L就是指针。指针需要用->指向成员。而在外部的L是实体对象，实体对象则用实心点来指向成员。

线性表插入数据元素

当时ADT是这么设计插入操作的：bool listInsert(*L,i,e); //插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1])，成功返回true.

插入算法的思路：

如果插入位置不合理，抛出异常；

如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；

将要插入元素填入位置i处；

表长加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;
}

给线性表随机赋10个值

//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
    L.data[i] = rand()%100;
    L.length++;
    }
    return L;
}

// 调用
L = Create(L);

每插入一个元素，注意表长要加1. 下面是遍历操作的函数：

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i < L.length;i++)
        visit(L.data[i]);
printf("\n");
return OK;
}

Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}

线性表置为空的操作
ADT里判断线性表是否为空的函数设计如下：bool listEmpty(L); //判断一个线性表是否为空，不修改表传值

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

其实就是判断表的长度是否为0而已。将表置空的函数就更简单了，直接将长度赋值为0即可。

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{ 
L->length=0;
return OK;
}

函数调用

i=ClearList(&L);
printf("清空L后：L.length=%d\n",L.length);

注意这里是使用地址传值，毕竟要对表进行清空操作，所以这里不用值传递。
这两个函数如果要测试的话可以自行加入到刚刚的完整可运行代码里。

线性表的查找功能
如何设计查找功能的函数呢。首先参数，我们需要传入线性表L，仅仅查找的话是不需要对表进行变化的，所以用值传递就行。然后就是传入需要查找元素的位置 i，最后还需要一个参数 *e，这个需要用地址传递，因为要保存函数的查找结构。所以函数设计如下：

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
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;
}

调用如下：

SqList L;
ElemType e;
int pos;

printf("你要查找第几个元素？ ");
scanf("%d",&pos);
GetElem(L,pos,&e);
printf("第%d个元素的值为：%d\n",pos,e);

线性表是从1开始的
查找蛮简单的，就是 *e=L.data[i-1]; 把线性表数据数组的第 i 个，也就是下标 i - 1 的元素赋值给 *e; 只是要注意，保存数据的 e 需要地址传值。

还有一个查找需求，就是知道一个数值，查找这个值是否在表中。函数原型，int locateElem(L,e); //查找线性表中是否有e，如果有返回它的位置(从1开始)，否则返回0表示失败。

 /* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
        return 0;
for(i=0;i < L.length;i++)
{
    if (L.data[i]==e)
    break;
}
if(i>=L.length)
        return 0;

return i+1;
}

线性表的删除
删除算法的思路：

  1. 如果删除位置不合理，抛出异常；
  2. 取出删除元素；
  3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
  4. 表长减1。
 /* 初始条件：顺序线性表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;
}

参数设计与插入函数一样，从第 i-1 （数组有0下标）个元素开始，将后一个元素挪前一个位置。最后线性表长度减一。

完整的可运行程序如下：

#include "stdio.h"

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

#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType;   /* ElemType类型根据实际情况而定，这里假设为int */
typedef int Status;     /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
    ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
    int length;             /* 线性表当前长度 */
}SqList;

/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
    L->length=0;
    return OK;
}

//顺序表的建立
SqList Create(SqList L)
{
    int i;
    srand((unsigned)time(NULL));
    for(i=0; i < 10; i++)
    {
        L.data[i] = rand()%100;
        L.length++;
    }
    return L;
}

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
    L->length=0;
    return OK;
}

Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i < L.length;i++)
            visit(L.data[i]);
    printf("\n");
    return OK;
}

/* 初始条件：顺序线性表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;
}

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
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;
}

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
        return 0;
    for(i=0;i < L.length;i++)
    {
        if (L.data[i]==e)
                break;
    }
    if(i>=L.length)
            return 0;

    return i+1;
}

int main()
{
    SqList L;
    ElemType e;
    Status i;
    char opp;
    int j,k;
    int pos;
    ElemType value;

    i=InitList(&L);
    printf("初始化成功，L.length=%d\n",L.length);
    printf("\n1.遍历线性表 \n2.线性表赋值 \n3.清空线性表 \n4.线性表插入 \n5.查找表中元素 \n6.判断元素是否在表中 \n7.删除某个元素 \n0.退出 \n请选择你的操作：\n");
while(opp != '0'){
    scanf("%c",&opp);
    switch(opp){
        case '1':
            ListTraverse(L);
            printf("\n");
            break;

        case '2':
            L = Create(L);
            printf("创建随机链表：L.data=");
            ListTraverse(L);
            printf("\n");
            break;

        case '3':
            i=ClearList(&L);
            printf("清空L后：L.length=%d\n",L.length);
            ListTraverse(L);
            printf("\n");
            break;


        case '4':
            printf("请输入插入元素位置：");
            scanf("%d",&pos);
            printf("请输入插入元素的值：");
            scanf("%d",&value);
            i = ListInsert(&L,pos,value);
            printf("插入完毕，现在线性表为：\n");
            ListTraverse(L);
            printf("\n");
            break;

        case '5':
            printf("你要查找第几个元素？ ");
            scanf("%d",&pos);
            GetElem(L,pos,&e);
            printf("第%d个元素的值为：%d\n",pos,e);
            break;

        case '6':
            printf("输入你想知道是否在表中的数值： ");
            scanf("%d",&e);
            k=LocateElem(L,e);
            // 这里假定随机数组中的元素互不重复
            if(k)
                printf("值为%d是表中的第%d个元素\n",e,k);
            else
                printf("没有值为%d的元素\n",e);
            break;

        case '7':
            printf("要删除第几个元素？");
            scanf("%d",&pos);
            ListDelete(&L,pos,&e);
            printf("删除完毕，现在线性表为：\n");
            ListTraverse(L);
            printf("\n");
            break;

        case '0':
            exit(0);
    }
 }
}

线性表顺序存储结构的优缺点
从优点开始说。当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素。接下来谈谈缺点。如我们所见，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。
优点：
具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出；
缺点：
顺序存储插入与删除一个元素，必须移动大了的数据元素，以此对大的线性表，特别是在元素的插入和删除很频繁的情况下，采取顺序存储很是不方便，效率低；
顺序存储空间容易满，出现上溢，程序访问容易出问题，顺序存储结构下，存储空间不便扩充；
顺序存储空间的分配问题，分多了浪费，分少了空间不足上溢。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,905评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,140评论 2赞 379
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,791评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,483评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,476评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,516评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,905评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,560评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,778评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,557评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,635评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,338评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,925评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,898评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,142评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,818评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,347评论 2赞 342