数据结构-线性表-顺序表1

一.线性表

线性表是最基础，最简单的数据结构，是由n个相同特性的元素构成的有限序列，常见的线性表有：顺序表，链表，栈，队列，字符串等等。

线性表的逻辑结构一定是线性结构，但是物理结构不一定是连续的，线性表在物理上存储时，通常以连续存储和链式存储的方式存储。

二.顺序表

1.定义：顺序表是一段物理地址连续存储的内存单元依次存储数据元素的线性结构，一般情况下用数组来存储。

2.和数组的异同

1.关系：数组是底层连续的内存容器，顺序表示依托数组封装而成的数据结构。

2.数组：语言基础类型，容量固定，只提供下标访问，无有效长度记录，没有增删，扩容等封装逻辑。

3.顺序表：数据结构，区分总容量与当前有效长度，自带增删查改，判空，动态扩容等功能。

4.共同点：物理空间连续，支持下标随机访问，中间插入删除都需要挪动元素。

5.总结：顺序表的底层结构是数组，对数的封装，实现了增删查改等接口。

3.顺序表的分类

1.静态顺序表：使用定长数组存储元素。

#define MAXSIZE 100 // 固定最大容量 typedef struct StaticSeqList { int arr[MAXSIZE]; int size; // 当前有效元素个数 } SList;

缺陷：空间给少了不够用，给多了造成浪费。

2.动态顺序表：底层使用堆上动态开辟的数组，初始容量较小，元素存满时自动重新申请更大的内存，拷贝数据，释放就内存，运动时可动态扩容。

typedef struct DynamicSeqList { int* arr; // 指向堆区动态数组 int size; // 当前有效元素个数 int capacity;// 当前总容量 } DList;