（一）（C语言）实现顺序表（静态分配）的基本操作（初始化、判断是否为空，打印表，插入和删除等）讲解（含相关C语言代码讲解及运行结果）_顺序表初始化

（一）（C语言）实现顺序表（静态分配）的基本操作（初始化、查找、打印表、插入和删除等）讲解（含C语言完整代码讲解及运行结果）

一、顺序表

       线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。因此，顺序表的特点是表中元素的逻辑顺序和其物理顺序相同。

1.顺序表（静态分配）

#define Maxsize 10    //定义线性表的最大长度
typedef struct
{
    ElemType data[MaxSize];  //顺序表的元素(Elemtype为元素的类型，可替换为int,char,float等)
    int length;              //顺序表的当前长度（表中元素个数）
}SqList;                     //顺序表的类型定义

       一维数组可以静态分配，也可以动态分配。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会溢出，进而导致程序崩溃。

2.顺序表（动态分配） 

#define InitSize 100    //表长度的初始定义
typedef struct
{
    int *data;       //指示动态分配数组的指针,这里的int可替换为其他类型
    int length;      //数组的当前个数
    int MaxSize;     //数组的最大容量
}SeqList;             //动态分配数组顺序表的类型定义
 
//C语言的初始动态分配语句：
L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);//动态申请一整片的内存空间
 
//初始化为
void InitList(SeqList *L){
    (*L).data=(int*)malloc(InitSize*sizeof(int));//这里的int可替换为其他类型
    (*L).length=0;
    (*L).MaxSize=InitSize;
}

       在动态分配时，存储数组的空间在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用于替换原来的存储空间，从而达到扩充存储数组空间的目的，不需要为线性表一次性地划分所有空间。

       注：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

二、顺序表相关操作（静态分配）

1.初始化

代码如下（示例）：

//初始化
bool InitList(SqList *L){
    for (int i = 0; i < MaxSize; i++)
    {
        (*L).data[i]=0;              //利用循环将表中的数据都为0
    }
    (*L).length=0;                   //将length也置为0，意思是当前表中无数据
    return true;
}

2.插入

由于在位序为i的位置，增加一个元素，则原来位序为i及位序i之后的元素都要往后移一位，将位序i给空出来，用来存放要插入的新元素。例：位序i后一位为i+1，位序i的要往后移一位，就是将位序i处的值放在位序为i+1处，因为数组中下标从0开始的，则在数组中表现为data[i]=data[i-1];

// 插入
bool ListInsert(SqList *L,int i,int e){
    if(i<1||i>(*L).length+1){
   printf("要插入的位置错误\n");  //只能在表中第一个元素和（最后一个元素的后一位）两者之间插入，
   return false;                 //按位序的话，i的值要满足1<=i<=length+1
    }
    if((*L).length>=MaxSize) {
        printf("存储空间已满！\n");      //如果length大于等于Maxsize说明表已满，插入数据失败
        return false;
    }
      int  j;
      for ( j=(*L).length; j>=i; j--)    //从最后一位开始到第i位（包括第i位），从后往前，
      {                       //将值往后移一位，从而将第i位给空出来（这里的i都为位序，从1开始）
        (*L).data[j]=(*L).data[j-1];     
      }
      (*L).data[i-1]=e;                  //将要插入的值放入位序为i中，即在数组中为data[i-1]
      (*L).length++;                     //由于表插入了一个元素，故length的值要加1
      return true;
}

3.删除

由于删除了一个元素，表中会空出来一个位置，即位序i会空出来，这时候就需要将位序i之后的值往前移一位 ，例：位序i后一位为i+1，要往前移一位，就是将位序i+1处的值放在位序为i处，因为数组中下标从0开始的，则在数组中表现为data[i-1]=data[i];

// 删除
bool ListDelete(SqList *L,int i,int *e){
    if(i<1||i>(*L).length){
        printf("要删除的位置错误\n");  //判断i值是否合法
        return false;
    }
    (*e)=(*L).data[i-1];              //将位序i中的值赋予e,用于返回
    int j;                          
    for (j=i;j<(*L).length;j++)       //利用循环从位序为i处到位序为的length最后一个元素,从前往后依次往前移动一个元素
    {                         
         (*L).data[j-1]=(*L).data[j];    
    }                                   
    (*L).length--;                    //由于删除一个元素，所以length减一    
    return true;
}

4.打印表

//打印表
void printList(SqList L){
    for (int i = 0; i < L.length; i++)         //i值从0开始
    {
        printf("第%d的值为：%d\n",i+1,L.data[i]); //利用数组下标依次将表中数据元素打印出来
    }
    if(L.length==0){
        printf("表中没有数据！\n");    //length为0时，此时表中无数据元素
    }
}

5.查找（按位查找和按值查找）

//查找
//1.按位查找
bool GetElem(SqList L,int i){
    if (i<1||i>L.length)
    {   
        printf("要查询的值的位置不合法！\n");
        return false;       //如果i值不合法（i只能在1<=i<=length内），则查找失败
    }
    printf("表中第%d个元素为：%d\n",i,L.data[i-1]);//输出表中位序为i的值
    return true;
}
//2.按值查找
bool LocateElem(SqList L,int e){
     if (L.length==0)
     {
        return false;
     }
     for (int i = 0; i < L.length; i++)//利用循环依次查找表中数据元素
     {
         if (L.data[i]==e)             //并依次和要查找的e值进行比较，如果相同则在表中找到e值，输出    
         {
            printf("此值%d为表中第%d个元素\n",e,i+1);
            return true;
         }
     }
}

三、完整代码讲解（C语言） 

在主函数中，为了方便我就设计插入了两个值，然后依次打印表中数据，按位查找，按值查找，删除，打印表进行。

#include<stdio.h>
#include<stdbool.h>   //如果要用bool类型，要加上这个头文件
#include<stdlib.h>
// 顺序表（静态分配）
#define MaxSize 10
typedef struct
{
    int data[MaxSize];
    int length; 
}SqList;
//初始化
bool InitList(SqList *L){
    for (int i = 0; i < MaxSize; i++)
    {
        (*L).data[i]=0;              //利用循环将表中的数据都为0
    }
    (*L).length=0;                   //将length也置为0，意思是表中无数据
    return true;
}
// 判断顺序表是否为空
int IsEmpty(SqList L){
    if (L.length==0)
    {
       return 111;
    }
    else
    {
        return 000;
    }   
}
//打印表
void printList(SqList L){
    for (int i = 0; i < L.length; i++)         //i值从0开始
    {
        printf("第%d的值为：%d\n",i+1,L.data[i]); //利用数组下标依次将表中数据元素打印出来
    }
    if(L.length==0){
        printf("表中没有数据！\n");    //length为0时，此时表中无数据元素
    }
}
// 插入
bool ListInsert(SqList *L,int i,int e){
    if(i<1||i>(*L).length+1){
        printf("要插入的位置错误\n");  //只能在表中第一个元素和（最后一个元素的后一位）两者之间插入，
        return false;                //按位序的话，1<=i<=length+1
    }
    if((*L).length>=MaxSize) {
        printf("存储空间已满！\n");      //如果length大于等于Maxsize说明表已满，插入数据失败
        return false;
    }
      int  j;
      for ( j=(*L).length; j>=i; j--)    //从最后一位开始到第i位（包括第i位），从后往前，
      {                                  //将值往后移一位，从而将第i位给空出来（这里的i都为位序，从1开始）
        (*L).data[j]=(*L).data[j-1];     
      }
      (*L).data[i-1]=e;                  //将要插入的值放入位序为i中，即在数组中为data[i-1]
      (*L).length++;                     //由于表插入了一个元素，故length的值要加1
      return true;
}
// 删除
bool ListDelete(SqList *L,int i,int *e){
    if(i<1||i>(*L).length){
        printf("要删除的位置错误\n");  //判断i值是否合法
        return false;
    }
    (*e)=(*L).data[i-1];              //将位序i中的值赋予e,用于返回
    int j;                          
    for (j=i;j<(*L).length;j++)       //利用循环从位序为i处到位序为的length最后一个元素,从前往后依次往前移动一个元素
    {                         
         (*L).data[j-1]=(*L).data[j];    
    }                                   
    (*L).length--;                    //由于删除一个元素，所以length减一    
    return true;
}
//查找
//1.按位查找
bool GetElem(SqList L,int i){
    if (i<1||i>L.length)
    {   
        printf("要查询的值的位置不合法！\n");
        return false;       //如果i值不合法（i只能在1<=i<=length内），则查找失败
    }
    printf("表中第%d个元素为：%d\n",i,L.data[i-1]);//输出表中位序为i的值
    return true;
}
//2.按值查找
bool LocateElem(SqList L,int e){
     if (L.length==0)
     {
        return false;
     }
     for (int i = 0; i < L.length; i++)//利用循环依次查找表中数据元素
     {
         if (L.data[i]==e)             //并依次和要查找的e值进行比较，如果相同则在表中找到e值，输出    
         {
            printf("此值%d为表中第%d个元素\n",e,i+1);
            return true;
         }
     }
}
int main(){
    SqList L;
    // 初始化
    InitList(&L);
    // 判断是否为空
    int ret;               //用来接收判断表是否为空的数据
    ret=IsEmpty(L);
    printf("ret= %d\n",ret);   //表为空输出“111”，表不为空输出“000”
 
    // 第一次插入数据
    printf("输入要插入的位置：\n");
    int i;int e;
    scanf("%d",&i);         //输入要插入的位置
    printf("输入要插入的值：\n");
    scanf("%d",&e);         //输入插入的值
    ListInsert(&L,i,e);
    // 打印表
    printList(L);
 
    //第二次插入数据
    printf("输入要插入的位置：\n");
    scanf("%d",&i);         
    printf("输入要插入的值：\n");
    scanf("%d",&e);          
    ListInsert(&L,i,e);
    // 再次打印表
    printList(L);
 
    //按位查找
    printf("输入要查询第几位的值：\n");
    scanf("%d",&i);
    GetElem(L,i);
    //按值查找
    printf("输入要查询的值：\n");
    scanf("%d",&e);
    LocateElem(L,e);
    
    // 删除数据
    printf("输入要删除的位置：\n");
    int n;int e3;                 //e3用来接收删除所返回的要删除的值
    scanf("%d",&n);               //输入要删除第几个值
    ListDelete(&L,n,&e3);
    printf("删除的值为：%d\n",e3);  //输出e3
    // 打印表
    printList(L);
 
    system("pause");
}

结果如下： 

---

总结

顺序表的优点：

            1.存储密度大：每个存储结点只存储数据本身

            2.可以随机存取表中任一元素

顺序表的缺点：

            1.在插入、删除某一元素时，需要移动大量元素

            2.大片连续空间分配不方便

            3.改变容量不方便

---

文章还有瑕疵，请各位指正。

链表的操作和链表的一些不易理解的知识会在下一篇介绍，如：LNode *和LinkList的区别，和在C语言中如何实现链表的操作。