线性表顺序表示和实现（C语言)（一）-阿里云开发者社区

线性表顺序表示和实现（C语言）

线性表是最常用且最简单的一种数据结构。简而言之，一个线性表是n个数据元素的有限序列

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

实现工具：dev

顺序表示要实现的功能：

1.构造一个空的线性表

2. 对线性表进行赋值

3. 对线性表进行销毁

4. 对线性表进行重置

5. 判断线性表是否为空

6. 获取线性表的长度

7. 获取线性表某一位置对应的元素

8. 在线性表某一位置插入元素

9. 删除线性表某一位置的元素

10. 求线性表某一元素的前驱

11. 求线性表某一元素的后继

12. 打印线性表

13. 退出

准备工作：

1.在dev新建一个Source File文件即可

File>new>Source File

代码实现：

在实现程序时导入的头文件有

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>

在这里我调用windows头文件是为了在后面的代码中修改控制台的名称，在实现线性表的顺序结构时真正用到的只有前三个头文件

在写代码之前先对一些表示结果状态的字符进行预定义

//函数结果状态字符 
#define TRUE     1     //代码中出现TRUE相当于出现了1 
#define FALSE    0     //出现FALSE相当于出现了0 
#define OK       1     //出现OK相当于出现了1 
#define ERROR    0     //出现ERROR相当于出现了0 
#define INFEASIBLE    -1
#define OVERFLOW      -2 .
typedef int Status;
typedef int ElemType;

在这里使用了typedef定义了Status和ElemType为int类型，也就是说之后的代码当中如果出现了Status和ElemType，它们与int作用相同

1. 线性表的动态分配顺序存储结构

#define LIST_INIT_SIZE    100     //线性表存储空间的初始分配量 
#define LISTINCREMENT     10      //线性表存储空间的分配增量 
typedef struct{
  ElemType *elem;          //存储空间的基址 
  int length;              //当前线性表的长度
  int listsize;            //当前线性表的存储容量          
}SqList;

2. 构造一个空的线性表

//构造一个空的线性表
Status InitList_Sq(SqList &L){
  L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));      //L.elem为首元素的地址 
  if(!L.elem){            //如果存储空间分配失败，L.elem为NULL
  printf("存储空间分配失败\n");
  exit(OVERFLOW);         
  }
  L.length = 0;            //当前线性表为空表，即线性表长度为0
  L.listsize = LIST_INIT_SIZE;           //给线性表分配初始容量
  printf("一个空的线性表已经构建成功\n");      //输出空线性表构建成功的提示消息 
  return OK; 
}

在构造空线性表时参数加&符号表示引用传递，确保形参和实参同时改变

L.elem为线性表首元素的地址，L.length为当前线性表的长度，L.listsize为顺序表当前分配空间的大小

我们现在来简单的介绍一下sizeof函数

sizeof函数：获取数据在内存中所占用的存储空间（以字节为单位来计数）

图示：

3. 对线性表进行赋值

Status ValueList_Sq(SqList &L){
  int i,j;
  printf("请输入线性表元素的个数：");
  scanf("%d",&i);
  if(i > L.listsize)                     //如果当要输入的元素个数大于内存大小时 
  {
    while(1)             //一直开辟新空间，直到开辟的空间大于需要的空间为止
    {
      if(i > L.listsize){
        L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
        L.listsize += LISTINCREMENT;
      }
      else
      break;
    }
  }
  for(j = 0;j < i;j++){
    printf("请输入第%d个元素：",j + 1);
      scanf("%d",&L.elem[j]); 
  } 
  L.length = i;          //赋值完成后，修改并保存线性表的长度 
  printf("赋值成功\n");
  return OK; 
}

这里的形参同样要加&符号来确保形参与实参同时改变

进行线性表赋值操作时用到了realloc函数，在这里简单的介绍一下realloc函数的作用

realloc()函数：重新分配空间

参数：原空间基址，现需空间大小
返回值：1. 成功：新空间地址(本质上是一个数值) 2. 失败：NULL

当我们在输入线性表元素个数大于构造空线性表给线性表分配初始容量时，要一直开辟新空间，直到开辟的空间大于需要的空间为止

4.对线性表进行销毁

Status DistoryList_Sq(SqList &L){
  if(!L.elem){ 
    printf("您还未建立线性表，请先建立线性表\n");
    return ERROR; 
  } 
  free(L.elem);            //使用free函数，将之前动态分配的内存还给系统 
  L.elem = NULL;           //重置elem的值为Null 
  L.length = 0;            //将线性表的元素个数重置为0
  L.listsize = 0;          //将线性表的存储容量重置为0 
  printf("线性表已经销毁\n"); 
  return OK;
}

在销毁线性表时，首先先对线性表是否存在进行判断，如果线性表不存在，L.elem为NULL，所以此时！L.elem为true，执行后面的return ERROR;

L.elem中存储的是初始化是动态分配内存首元素的地址，free函数的作用就是将之前动态分配的内存还给系统，但是在调用free函数之后，虽然归还了内存，但是L.elem中仍然指向原来的地址，而这个地址在归还内存之后程序便无权进行访问，所以此时L.elem就成了一个野指针，我们重置L.elem为NULL就是为了防止发生野指针访问的情况，接着将线性表元素的个数L.length和存储容量L.listsize重置为0

5. 对线性表进行重置

//对线性表进行重置StatusClearList_Sq(SqList&L){
if(L.elem){                  //如果线性表存在 L.length=0;            //将线性表的元素个数重置为0printf("线性表已重置\n");
returnOK;
    }
elseprintf("线性表不存在，无法重置\n");
returnOK;
}

重置线性表时仍然先对线性表是否存在进行判断，如果线性表存在只需将线性表元素个数L.length重置为0即可，不需要改变其它变量

7. 判断线性表是否为空

//判断线性表是否为空StatusListEmpty_Sq(SqListL){
if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在 if(L.length!=0){               //如果线性表中元素为0，即L.length的值为0时说明线性表是空表 printf("线性表不是空表\n");
returnFALSE; 
            }
elseprintf("线性表是空表\n");
returnTRUE;
    }
elseprintf("线性表不存在，无法判断\n");
returnOK; 
}

判断线性表是否为空只需要看线性表当中的元素个数L.length是否为0即可，如果为0，则说明线性表是空表；不等于0则说明该线性表不为空

8. 获取线性表的长度

//获取线性表的长度StatusListLength_Sq(SqListL){
if(L.elem){              //判断当前线性表存在 intK;
K=L.length;        //将线性表的元素个数赋值给Kprintf("线性表长度为%d\n",K); 
returnOK; 
    }
elseprintf("线性表不存在，无法判断\n");
returnOK;
}

线性表的长度是由当前线性表中的元素个数来体现的，所以获取线性表的长度仅需定义一个int类型变量，并将L.length赋值给K即可

9. 获取线性表某一位置对应的元素

//获取线性表某一位置对应的元素StatusGetElem_Sq(SqListL,intindex){
intNum;
if(index<=0||index>L.length){              //如果要获取元素的位置是否出界 printf("请输入一个有效的数字\n");
returnERROR;
    }
elseNum=L.elem[index-1];
printf("第%d个位置的元素为：%d\n",index,Num);
returnOK;
}

同样地，获取线性表某一位置对应的元素时先判断要获取的位置是否合法，和判断线性表的长度一样，只需要将L.elem[index-1]位置的元素赋值给一个int型变量Num即可（index-1是因为数组元素的下标是从0开始的）

10. 在线性表某一位置插入元素

//在线性表某一位置插入元素StatusListInsert_Sq(SqList&L,inti,ElemTypee){
ElemType*newbase;
int*q,*p; 
if(i<1||i>L.length+1)         //判断插入位置的index值是否合法      returnERROR; 
if(L.length>=L.listsize){         //如果当前线性表存储空间已满，增加分配 newbase= (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)  {                 //如果存储空间分配失败，则执行异常退出 printf("存储空间分配失败\n");
exit(OVERFLOW);
        }
L.elem=newbase;               //新的存储空间基址  L.listsize+=LISTINCREMENT; 
    }
q=&(L.elem[i-1]);                 //L.elem[index-1]为数组中的最后一个元素，q为要插入的位置 for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1) =*p;                    //要插入位置以及之后的位置向后移 *q=e;                             //将e插入到想要插入的位置 ++L.length;                         //插入新的元素之后表长加1 printf("元素插入成功\n");
returnOK;
}

在线性表中的某一位置插入一个元素，同样要先判断要插入的位置是否合法，接着就是判断线性表是否已满，如果线性表没有存储位置，则需要通过realloc函数重新分配一块空间，要想在某一位置插入一个元素，首先要将这个想要插入元素的位置空出来，所以在插入元素时

要先从表尾开始到想要插入元素的位置将元素依次向后移动一位

realloc函数如果分配空间成功的话返回的就是新空间的地址，但是本质上是一个数值，因此就需要进行强制类型转换，将数值改成指针类型

图示

在这里要强调一点这一条语句，为什么不直接将newbase直接赋值给L.elem，要先进行判断是否分配存储成功？

if(!newbase) { //如果存储空间分配失败，则执行异常退出

printf(“存储空间分配失败\n”);

exit(OVERFLOW);

}

L.elem = newbase;

如果分配空间失败，此时的newbase的值为NULL，所以此时L.elem就会被赋值为NULL，原信息丢失

插入元素后，表长加一

11 删除线性表某一位置的元素

//删除线性表某一位置的元素StatusDeleteList_Sq(SqList&L,inti){
int*p,*q;
if(i<1||i>L.length){            //如果要删除的位置不合法printf("请输入一个有效数字\n"); 
returnERROR;
    } 
p=&(L.elem[i-1]);                 //p为被删除元素的位置q=L.elem+L.length-1;            //将表尾元素的位置赋值给qfor(++p;p<=q;p++)
*(p-1) =*p;                    //被删除的元素之后的元素全部左移 --L.length;                           //表长减1 printf("第%d个元素删除成功\n",i);
returnOK;
}

L.elem + L.length - 1为表尾元素，删除元素相比起插入元素要简便些，不需要进行后移操作，数据向前覆盖，删除完成后表长减1即可。如果有需要的话，可以单独定义一个int类型的变量在进行删除操作之前将要删除的元素赋值给该变量。

12. 求线性表某一元素的前驱

//求线性表某一元素的前驱StatusPriorElem_Sq(SqListL,inti){
intK;
if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在if(i<=1||i>L.length+1)              //判断输入的i值是否合法 printf("请输入一个有效数字\n");
K=L.elem[i-2];        //将第i个元素的前一个元素赋值给Kprintf("第%d个位置的直接前驱为：%d\n",i,K); 
    }
elseprintf("线性表不存在，无法判断\n");
returnOK;
}

求前驱时除了要判断线性表是否存在外，只需要将L.elem[i-2]赋给int型变量K即可

13. 求线性表某一元素的后继

//求线性表某一元素的后继 StatusNextElem_Sq(SqListL,inti){
intK;
if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在if(i<=1||i>L.length-1)              //判断输入的i值是否合法 printf("请输入一个有效数字\n");
K=L.elem[i];        //将第i个元素的后一个元素赋值给Kprintf("第%d个位置的直接后继为：%d\n",i,K); 
    }
elseprintf("线性表不存在，无法判断\n");
returnOK;
}

求后继和求前驱除了在元素位置上有区别外，其余的思路都一致，在此不多做赘述

14. 打印线性表

//打印线性表StatusPrintList_Sq(SqListL){
printf("当前线性表的元素为：");
for(intK=0;K<L.length;K++)      //遍历当前线性表 printf("  %d",L.elem[K]);
printf("\n");                        //换行 returnOK;
}

线性表顺序表示和实现（C语言)（一）