【考研数据结构知识点详解及整理——C语言描述】第二章 线性表的顺序表示

25计算机考研，数据结构知识点整理（内容借鉴了王道408＋数据结构教材），还会不断完善所整理的内容，后续的内容也会不断更新（可以关注），若有错误和不足欢迎各位朋友指出!

 

目录

一.线性表的顺序存储结构

1.地址的计算

2.线性表顺序存储的表示

---

计算机中主要有两种基本的存储结构用于存放线性表：顺序存储结构和链式存储结构

一.线性表的顺序存储结构

（1）线性表的顺序表示又称为顺序存储结构或顺序映像

（2）线性表的顺序存储是指：用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素在储在相邻的物理存储单元中，即通过数据元素物理存储的相邻性来反映数据元素之间逻辑上的相邻关系。

（3）采用顺序存储结构存储的线性表通常简称为顺序表（关系线性化，结点顺序存）

（4）顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

1.地址的计算

（1）每个数据元素的存储位置都和顺序表的起始位置相差一个和该数据元素的位序成正比的常数，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

（2）注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的

2.线性表顺序存储的表示

假定线性表的元素类型为ElemType，则

静态分配的顺序表存储结构描述为：

#define MaxSize 50  //定义线性表的最大长度
typedef struct{
   ElemType data[MaxSize];  //顺序表的元素
   int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义
 

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

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

动态分配的顺序表存储结构描述为：

#define InitSize 100  //表长度的初始定义
typedef struct{  
  ElemType *data;  //指示动态分配数组的指针
  int MaxSize,length;  //数组的最大容量和当前个数
}SeqList;  //动态分配数组顺序表的类型定义

C的初始动态分配语句为：

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

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

顺序表的主要优点：

①可进行随机访问，可通过首地址和元素序号可以在O(1)时间内找到指定的元素;

②存储密度高，每个结点只存储数据元素。

顺序表的缺点也很明显：

①元素的插入和删除需要移动大量的元素，插入操作平均需要移动 n/2 个元素，删除操作平均需要移动(n-1)/2个元素;

②顺序存储分配需要一段连续的存储空间，不够灵活。