星如雨

Appearance

顺序表 ​

data structure

顺序表定义 ​

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

静态数组和动态数组的区别 ​

一维数组可以是静态分配的，也可以是动态分配的。

静态分配 ​

由于数组大小和空间已经固定，所以一旦空间占满，在加入新的数据就会产生 数据溢出，进而导致程序运行崩溃。

动态分配 ​

存储数组的空间是由程序执行过程通过动态存储分配语句分配的，一旦数据空间沾满，就可以另辟新的一块更大的存储空间，用以代替原来的存储空间，达到扩充空间的目的。

顺序表空间分配 ​

cpp
#define ElementType int
#define MaxSize 100
// 静态空间分配
typedef struct {
  ElementType data[MaxSize];     // 定义顺序表元素
  int lenght;                    // 当前元素长度
}SeqList;
// 动态空间分配

typedef struct {
  ElementType *data;             // 定义顺序表元素
  int MaxLen;                    // 顺序表最大长度
  int lenght;                    // 当前元素长度
}SeqList;
#define ElementType int
#define MaxSize 100
// 静态空间分配
typedef struct {
  ElementType data[MaxSize];     // 定义顺序表元素
  int lenght;                    // 当前元素长度
}SeqList;
// 动态空间分配

typedef struct {
  ElementType *data;             // 定义顺序表元素
  int MaxLen;                    // 顺序表最大长度
  int lenght;                    // 当前元素长度
}SeqList;

顺序表优点 ​

  • 随机访问，通过首地址和元素位序可快速找到指定元素
  • 存储密度高，每个节点只存储数据元素
  • 逻辑上相邻的元素物理上也相邻

顺序表缺点 ​

  • 插入和删除需要移动大量元素
  • 需要连续内存空间