考研数据结构笔记（3）

存储结构

顺序结构

定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列(每个数据元素所占空间一样大)。

顺序表一一用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

sizeof(int)= 4B
sizeof(Customer)= 8B

基本操作的实现

静态分配

ElemType可以为int类型，float类型。

代码样例：

在main函数中首先声明一个Sqlist L;(声明一个顺序表)，则在内存中分配存储顺序表L的空间。包括:MaxSize*sizeof(ElemType)和存储length的空间,data[]数组的每个元素为4个字节。initlist进行顺序表的初始化。（设置数据元素的默认值为0）

该步骤出现错误，i值范围应该为L.length，为具体顺序表长度。

如果删去设置数据元素的默认值的步骤。以下代码会出脏数据。

即对data[]数据内容会出现奇怪的数据（脏数据）。

问题

如果“静态数组”存满了怎么办?

可以放弃治疗，顺序表的表长刚开始确定后就无法更改(存储空间是静态的)

下面介绍动态分配内存。

动态分配

定义一个指针data,指向顺序表的第一个元素，

代码功能

定义一个动态分配的顺序表。

初始化顺序表。

增加动态数组的长度。

主函数

还有函数的头文件

内存展示：

首先进入主函数，seqlist函数用来声明一个顺序表，调用initlist函数申请一片内存空间并初始化顺序表，data指针指向data[0],调用increasesize函数，data指针先指向*P,函数新申请一片空间并让data指向第一个元素，for循环复制原来的函数值，最后free函数释放的原来的顺序表空间。

顺序表的特点:

• 随机访问，即可以在 o(1) 时间内找到第i个元素。
• 存储密度高，每个节点只存储数据元素。
• 拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)。
• 插入、删除操作不方便，需要移动大量元素。

顺序表小结

顺序表的插入删除

插入

ListInsert(&Li,e): 插入操作。在表L中的第i个位置上插入指定元素e。

代码实现：

由于用存储位置的相邻来体现数据元素之间的逻辑关系，所以数据元素相邻同样也存储位置的相邻。

内存分配：

我们现在在b,d元素之间插入c,表示在data[1]后面插入一个元素，则原来data[2]及以后的元素全部后移一位，然后将c插入到data[2]中。然后length+1。

整体代码实现：

代码改进：用户交互时给予提示

删除

ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。

将元素c删除,并将后面的元素依次向前移一位。

代码实现：

首先定义一个顺序表并初始化，然后插入数据，调用listdelete函数将第三个元素删除并将后面的元素依次向前移动。（先移动前面的元素，再移动后面的元素）

小结

顺序表的查找

按位查找

GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。、

静态分配代码：

动态分配代码：

解释了当初为什么malloc函数前面要强制转为int*

时间复杂度

按值查找

按值查找操作。在表L中查找具有给定关键字值的元素LocateElem(L,e):

假设按值查找int类型数字9，但是“==”无法用于结构体数据相同，只能依次比较结构体数据相同或者定义方法来判断。

时间复杂度O(n)

小结