学习笔记-数据结构-线性表（2024-04-25）

顺序表内存分配和空间初始化

静态分配

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

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

一维数组可以是静态分配的，也可以动态分配的。对数组进行静态分配时，因为数组的大小和空间已经事先固定，所以一旦空间占满，再加入新数据就会产生溢出，进而导致程序崩溃。
而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的，而不需要一次性地划分所有空间。

动态分配

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

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

初始内存分配

C的初始动态分配语句为

L.data=(ELemType *)malloc(sizeof(Elemtype)*InitSize);
1

C++的初始分配语句为

L.data=new Elemtype[InitSize];
1

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

顺序表的初始化

静态分配的初始化

//SqList L;//声明一个顺序表
void InitList(SqList &L)
{
	L.length=0;//顺序表初始长度为0
}
1
2
3
4
5

动态分配的初始化

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0。MaxSize指示顺序表当前分配的存储空间的大小，一旦因插入元素而空间不足，就进行再分配。

void InitList(SeqList &L)
{
	L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);//分配存储空间
	L.length=0;//顺序表初始长度为0
	L.MaxSize=InitSize;//初始存储容量
}
1
2
3
4
5
6