顺序表(顺序存储)

逻辑上相邻的两个元素在物理位置上也相邻。

提示

线性表的顺序存储又称为顺序表。

顺序存储优缺点

笔记

1. 可以随机存取表中任意一个元素。

   根据表头元素地址和元素序号计算出对应元素的地址。
   如：

2. 存储密度高，每个节点只存储数据元素。

警告

1. 插入和删除需要操作移动大量元素。
2. 线性表变化较大时，难以确定存储空间的容量
3. 需要分配一整段连续的存储空间，不够灵活，可能产生碎片。

提示

顺序表的动态分配，并不是链式存储，它只是分配空间的大小可以在运行时动态决定。
如：
一维数组，可以静态分配，也可以动态分配。
静态分配时，由于数组的大小和空间事先固定，一旦空间占满，在加入新的数据就会产生溢出，进而导致程序崩溃。
而动态分配时，存储数组的空间是在程序执行过程中通过动态分配存储分配语句进行分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而到达扩充存储空间的目的，而不需要为线性表一次性地划分所有空间。

时间复杂度

插入元素

1. 最好情况：在表尾插入/删除元素，不需要移动元素，时间复杂度为O(1);
2. 最坏情况：在表头插入/删除元素，所有元素都需要往后移动，时间复杂度为O(n);
3. 平均情况，在插入/删除位置概率均等的情况下，平均移动元素的次数为n/2，时间复杂为O(n)。

删除元素

1. 最好情况：在表尾删除元素，不需要移动元素，时间复杂度为O(1);
2. 最坏情况：在表头删除元素，所有元素都需要往后移动，时间复杂度为O(n);
3. 平均情况，在删除位置概率均等的情况下，平均移动元素的次数为(n-1)/2，时间复杂为O(n)。

顺序表的动态空间申请

点击查看

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

#define InitSize 10 //定义线性表初始化长度，可用于动态申请空间
#define ElementType int //定义线性表元素类型，可用于灵活控制结构体参数数据类型

typedef struct { // 使用 typedef 定义别名时，结构体内无结构体本身指针时，可以省略结构体名称
    ElementType *data; // 使用指针，可动态申请数据内存大小
    int MaxSizes,len;  // 动态空间数值最大容量与当前个数
}Sq; // 结构体别名

int main() {
    Sq S; // 定义结构体变量
    // 动态分配结构体数据存储大小
    S.data = (ElementType*)malloc(sizeof(ElementType)*InitSize);
    return 0;
}

顺序表增删改查

点击查看

使用C++

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

#define InitSize 100 //定义线性表初始化长度，可用于动态申请空间
#define ElementType int //定义线性表元素类型，可用于灵活控制结构体参数数据类型

typedef struct { // 使用 typedef 定义别名时，结构体内无结构体本身指针时，可以省略结构体名称
    ElementType *data; // 使用指针，可动态申请数据内存大小
    int length;  // 动态空间数值最大容量与当前个数
}SqList; // 结构体别名
// 打印顺序表内所有数据
void printSqList(SqList &L){
    if(L.length ==0){
        printf("暂无数据！");
    } else {
      printf("结构体内容为：");
      for (int i = 0; i < L.length; ++i) {
//        printf("链表第%d个元素值为：%d\n",i+1,L.data[i]);
          printf("%4d",L.data[i]); // 打印到一排，每个数据占4列
      }
      printf("\n");
    }
}
// 顺序表插入，第一个参数为顺序表指针，第二个参数为插入位置，第三个为插入的数据
bool listInsert(SqList &L,int i,ElementType e){ // bool 是c++ 语法，c若向使用，需引入stdbool.h C99
    if (i<1 || i >L.length+1) // 判断插入位置是否合法。
        return false;
    if(L.length >= InitSize) // 超出存储空间
        return false;
    for (int j = L.length; j >=i ; j--) {//从后移动数据元素至插入位置
        L.data[j]=L.data[j-1]; // 数据后移
    }
    L.data[i-1]=e; // 掺入数据，因为数值下标从0开始，所以-1
    L.length++; //增加链表长度
    return true;
}
// 查找数据
int locateElement(SqList L,ElementType e){
    if(L.length ==0)
        return -1;
    for (int i = 0; i < L.length; ++i) {
        if(L.data[i] == e)
            return i+1; // 数值下标从0开始
    }
}

// 更新元素数据
bool editElement(SqList &L,int i,ElementType e){
    if(i<1 || i >L.length+1)// 判断删除位置是否正确
        return false;
    if(L.length == 0) // 结构体中无无数据
        return false;
    L.data[i-1] = e; //更新元素的值
    return true;
}
// 删除顺序表元素
bool deleteElement(SqList &L,int i,ElementType &e){ // 因为要改变e的值，所以这里要&引用
    if(i<1 || i >L.length+1)// 判断删除位置是否正确
        return false;
    if(L.length == 0) // 结构体中无无数据
        return false;
    e = L.data[i-1]; //提取删除的数据
    for (int j = i-1; j < L.length; j++) {
        L.data[j] = L.data[j+1];
    }
    L.length--; //减少结构体长度
    return true;
}

int main() {
    SqList S; // 定义结构体变量
    // 初始化链表空间，动态分配结构体数据存储大小
    S.data = (ElementType*)malloc(sizeof(ElementType)*InitSize);
    S.length=0; // 初始化链表长度
    int tmp=34;

    if(listInsert(S,1,tmp)){
        printSqList(S);
    }else{
        printf("插入失败！\n");
    }

    int locat = locateElement(S,tmp);
    if(locat >= 0 ){
        printf("数据%d在结构体中第%d位！\n",tmp,locat+1);
    }else{
        printf("数据%d不存在结构体中！\n",tmp);
    }

    tmp = 56;
    if(editElement(S,1,tmp)){
        printSqList(S);
    }else{
        printf("更新失败！\n");
    }

    int del;
    if(deleteElement(S,1,del)){
        printSqList(S);
        printf("删除数据：%d 成功！\n",del);
    } else{
        printf("删除失败！\n");
    }
    return 0;
}