数据结构教程--李春葆版（总结）之线性表-顺序存储结构概念

超、凢脫俗 2022-10-03 00:42 157阅读 0赞

**本文的主要内容来自数据结构教程--李春葆版，由“你是木头人”博主进行总结。**

### **线性表的顺序存储结构** ###

**性质：**

**线性表所占用存储空间大小：**

n乘以sizeof(ElemType),其中n表示线性表的长度，ElemType是线性表中的数据元素。

**表中某数据元素的存储地址：**

LOC(A)+i\*sizeof(ElemType)（其中LOC(A)表示为起始位置，i为顺序表的下标序号）

### **线性表的顺序存储结构定义：** ###

typedef struct
    {
    ElemType data[MaxSize]; //线性表的元素
    int length;             //线性表的长度
    }SqList;

**线性表的顺序存储结构，如图所示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70][]

### **建立顺序表** ###

void CreateList(SqList *&L.ElemType a[],int n)//在长度为n的数组a中建立顺序表
    {
    int i;
    L=(SqList*)malloc(sizeof(SqList));  //分配线性表的顺序存储空间
    for(i=0;i<n;i++)
    L->data[i]=a[i];                   //把内容逐一存放在线性表的数组data之中
    L->length=n;                       //把该长度保存在线性表的结构体里
    }

**建立顺序表，如线性表的顺序存储结构图所示。**

### **初始化顺序表** ###

void InitList(SqList *&L)
    {
    L=(SqList*)malloc(sizeof(SqList));
    L->length=0;//只开辟内存但没有内容，要设置为空线性表，即长度置为0.
    }

**初始化顺序表，如图所示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1][]

### **销毁线性表** ###

void DestroyList(SqList *&L)
    {
    free(L);//销毁mallo申请的一块内存就相当于销毁线性表。
    }

### **判定线性表是否为空表** ###

bool ListEmpty(SqList *L) //判线性表是否为空表
    {
             return(L->length==0);
    }

### **线性表的长度** ###

int ListLength(SqList *L)  //求线性表的长度
    {
             return(L->length);
    }

### **输出线性表** ###

void DispList(SqList *L)   
     {
             int i;
             if (ListEmpty(L)) return;
             for (i=0;i<L->length;i++)
                       printf("%c ",L->data[i]);
             printf("\n");
    }

### **已知线性表的第i****个元素，求该位置的元素值。** ###

bool GetElem(SqList *L,int i,ElemType &e)
    {
             if (i<1 || i>L->length)
                       return false;                      
             e=L->data[i-1];                                     
             return true;                                 
    }

### **已知线性表的元素值，求该元素值的位置。** ###

int LocateElem(SqList *L, ElemType e)   
     {
             int i=0;
             while (i<L->length && L->data[i]!=e)
                       i++;                                        //查找元素e
             if (i>=L->length)                           //未找到时返回0
                       return 0;
             else
                       return i+1;                                    //找到后返回其逻辑序号
    
    }

### **插入数据元素** ###

bool ListInsert(SqList *&L,int i,ElemType e)   
     {
             int j;
             if (i<1 || i>L->length+1)
                       return false;                       //参数错误时返回false
             i--;                                         //将顺序表逻辑序号转化为物理序号
             for (j=L->length;j>i;j--)  //将data[i]及后面元素后移一个位置
                       L->data[j]=L->data[j-1];
             L->data[i]=e;                                //插入元素e
             L->length++;                                //顺序表长度增1
             return true;                                  //成功插入返回true
    }

**插入数据元素，如图所示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 3][]

### **删除数据元素** ###

bool ListDelete(SqList *&L,int i,ElemType &e)       
     {
             int j;
             if (i<1 || i>L->length)                 //参数错误时返回false
                       return false;
             i--;                                   //将顺序表逻辑序号转化为物理序号
             e=L->data[i];
             for (j=i;j<L->length-1;j++)          //将data[i]之后的元素前移一个位置
                       L->data[j]=L->data[j+1];
             L->length--;                                  //顺序表长度减1
             return true;                                  //成功删除返回true
    }

**删除数据元素，如图所示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70]: /images/20220109/b65b01d9783040c2ace7cdcf0b5b5703.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1]: /images/20220109/946788f1ca39486bb84f69666e8e2b87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 2]: /images/20220109/f5c7aac5cf3a441e95832d952f2859b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 3]: /images/20220109/1e07205339d9466da08e3edd5c6a8301.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 4]: /images/20220109/5f3662a44a22423fbef8a824e5eab368.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 5]: /images/20220109/7d9ed45b8bff4e0b8a9f797c61c3bbcc.png