数据结构--线性表的顺序存储（2）

一、什么是顺序表

　　线性表的顺序存储类型又称之为顺序表，他是在内存中一块连续的区域，其中的每个元素不仅在表中是相邻的，他们的物理地址也是相邻的，我们一般在c语言中使用的数组就属于顺序表，注意线性表中的元素位序是从1开始二数组中的元素下标是从0开始，线性表中每个元素占据相同大小的地址空间。

　　

 二、顺序表的特点

　　1.顺序表准重要的特点是能进行随机访问，通过元素下标寻找元素，其时间复杂度为O(1)。

　　2.因为顺序表是在物理空间上相邻存储，所以顺序表的存储密度很高。

　　3.顺序表在进行插入和删除的时候需要移动大量元素。

三、静态顺序表的初始化

#define MaxSize 50            //顺序表的最大长度

typedef int ElemType; /*ElemType是数据的类型，我们这里用int类型表示*/

typedef struct {
    ElemType data[MaxSize];        //顺序表的元素
    int length;        //顺序表的长度
}SqList;            //顺序表的类型标识

四、静态顺序表的插入和删除

　　顺序表因为其插入或者删除其中一个元素都要对后面的元素进行顺序的调整，消耗非常大的，如果我们在一个有n个元素的顺序表在第一个位置插入元素，我们需要把下标元素n-1到0全部往后移动一个单位，删除也是同样的道理，需要把元素向前移动一位，所以插入和删除的平均时间复杂度为O(n)。

 插入和删除的代码

Status InsertList(SqList *L, int i, ElemType e) {  //插入

    int j;
    if (i > L->length+1||i<1||L->length==MaxSize)        //判断要插入的位置不能大于顺序表的长度
        return -1;

    for (j = L->length - 1; j >= i - 1; j--) {
        L->data[j + 1] = L->data[j];
    }
    L->data[i - 1] = e;
    L->length++;
    
    return 1;
}

Status DeleteElem(SqList *L, int i, ElemType *e) {  //删除
    
    ElemType *temp_data ;

    if (i > L->length || i<0 || L->length == MaxSize)        //判断要删除的位置不能大于顺序表的长度
        return -1;

    temp_data = L->data[i-1];
    *e = temp_data;                    //使用指针赋值给指针

    for (i=i-1; i <= L->length-1; i++) {
    
        ElemType temp = L->data[i+1];        //i位后的元素每一个向前移动一位
        L->data[i] = temp;
    }

    L->length--;
    return 1;

}

五、顺序表的其它操作

seqList.h
#include<stdio.h>

#define MaxSize 50            //顺序表的最大长度

typedef int Status; /* Status是函数的类型,其值是函数结果状-1为出现错误1为正常态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE 其中1为TRUE 0为FALSE */

typedef int ElemType; /*ElemType是数据的类型，我们这里用int类型表示*/

typedef struct {
    ElemType data[MaxSize];        //顺序表的元素
    int length;        //顺序表的长度
}SqList;            //顺序表的类型标识

void InitList(SqList *L); //初始化线性表
int Length(SqList L);//返回线性表的长度
int LocateElem(SqList L, ElemType e);//查找元素e在表中的位置
ElemType GetElem(SqList L, int i);//获取表中第i个位置的元素，并返回
Status InsertList(SqList *L, int i, ElemType e);//在表L中第i个位置插入元素e
Status DeleteElem(SqList *L, int i, ElemType *e);//删除表中第i个元素，并用e返回其值
void PrintList(SqList L);//输出线性表的所有元素
Boolean IsEmpty(SqList *L);//判断线性表是否为空
Status DestroyList(SqList *L);//销毁线性表，并释放所占用的空间

函数文件

seqList.c

#include"seqList.h"

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

int Length(SqList L) { //返回线性表的长度
    return L.length;
}

int LocateElem(SqList L, ElemType e) { //查找元素e在表中的位置
    int i;
    for (i = 0; i<L.length; i++) {
        if (L.data[i] == e)
            return i+1;
    }
    return -1;
}

ElemType GetElem(SqList L, int i) { //获取表中第i个位置的元素，并返回
    if (i<0 || i >= L.length)
        return -1;
    return L.data[i-1];
}


void PrintList(SqList L) { //输出线性表的所有元素
    int i;
    
    for (i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
}

Boolean IsEmpty(SqList *L) { //判断线性表是否为空
    if (L->length<=0)        //因为线性表没有初始化时长度数值为小于等0
        return 1;
    else
        return 0;
}

Status DestroyList(SqList *L) { //销毁线性表，并释放所占用的空间

    L->length = 0;            //顺序存储的线性表销毁只需使长度为0即可，因为是静态的空间在创建时就被分配了

    return 1;
}

主函数文件

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

int main() {
    int i;
    int array[] = { 0,1,2,3,4,5 };
    ElemType e;
    SqList sq;
    
    InitList(&sq);
    
    for (i = 1; i < 6; i++) {
        InsertList(&sq, i, array[i]);
    }

    PrintList(sq);
    printf("
");
    printf("线性表的长度为%d
", Length(sq));
    printf("定位元素5的位置为%d
", LocateElem(sq, 5));
    printf("获取第2个位置的元素为%d
", GetElem(sq, 2));
    DeleteElem(&sq, 2, &e);
    printf("删除表中位置为2的元素，其值为%d 删除后的表为", e);
    PrintList(sq);
    printf("
");
    if (IsEmpty(&sq) == 1)
        printf("此表为空
");
    else
        printf("此表不为空
");

    printf("销毁线性表");
    if (DestroyList(&sq) == 1)
        printf("销毁成功!
");
    else
        printf("销毁失败");
}