顺序表的实现——数据结构

线性表

线性表的定义和基本操作

线性表的定义

线性表（Linear List）的定义

​ 线性表是一个具有相同数据类型的n(n≥0) 个数据元素的有限序列，其中n为表长，当 n = 0 时，线性表是一个空表 。若用 L 命名线性表，则一般表示为：

​ L = ( a₁, a₂, a₃, a₄,…,a_n)

​ 几个概念：

• a_i是线性表中的“第i个”元素线性表中的次序
• a₁是表头元素 ，a_n是表尾元素
• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的基本操作

线性表的基本操作

​ 一个数据结构最基本的操作是指其最核心、最基本的操作。其他较复杂的操作可以通过调用其基本操作来实现。线性表的基本操作如下：

• InitList(&L) 初始化表，构造一个空的线性表L,并分配内存空间。
• Destroy(&L) 销毁操作。销毁线性表，并释放线性表L所占用内存空间。
• Listlnsert(&L,i,e) 插入操作。在表L中第i个位置上插入指定元素e。
• ListDelete(&L,i,&e) 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
• LocateElem(L,e) 按值查找操作。在表L中查找具有给定关键字值的元素。
• GetElem(L,i) 按位查找操作。获取表L中第i个位置的元素的值。

其他操作：

• Length(L) 求表长。返回线性表 L的长度，即L中数据元素的个数。
• PrintLIst(L) 输出操作。按前后顺序输出线性表L的所有元素值。
• Empty(L) 判空操作。若L为空表，则返回true 否则返回false

Tips：

• 对数据的操作——创销、增删改查
• C语言函数的定义—— <返回值类型> 函数名 （<参数类型> 参数 …）
• 实际开发中，可以根据实际需求定义其他的基本操作
• 函数名和参数形式、命名都可以更改 （但命名需要有可读性）
• 什么时候要传入引用“&” ——对参数的修改结果需要“带回来“(cpp)

对数据结构基本操作的作用

• 团队合作编程，定义的数据结构可以能够方便的使用（封装）。
• 将常用操作/运算封装成函数，避免重复工作，降低出错风险。

线性表的顺序表示

顺序表的定义

顺序表 —— 用顺序存储的方式实现线性表

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

顺序表的实现——静态分配

#define MaxSize 10				//定义最大长度
typedef struct{					ElemType data[MaxSize];		//用静态的“数组”存放数据元素int length;					//顺序表的当前长度
}SqList;						//顺序表的类型定义(静态分配方式)

#include<stdio.h>
#define MaxSize 10	//定义最大长度
typedf struct{int data[MaxSize];	//用静态的数组存放数据元素int length;			//顺序表的当前长度
}SqList;				//顺序表的类型定义void InitList(SqList &L){for (int i = 0; i < MaxSize; ++i) {L.data[i] = 0;  //将所有数据元素设置为默认初始值L.length = 0;	//顺序表初始长度为0}
}int main(){SqList  L;      //声明一个顺序表InitList(L);    //初始化顺序表return 0;
}

是否可以不设置默认初始值？

将设置默认初始值语句删除，并打印整个数组

#define MaxSize 10
#include<stdio.h>
typedef struct{int data[MaxSize];int length;
}SqList;
void InitList(SqList &L){L.length = 0;   //顺序表初始长度为0
}
int main(){SqList L;InitList(L);for (int i = 0; i < MaxSize; ++i) {printf("%d\n",L.data[i]);	//尝试“违规”打印整个数组//正常来讲，遍历需要i<L.length}
} 
-1539310592
212
-497739960
32758
-427333024
674
0
1
-497741824
32758

如果“数组“存满了怎么办？

顺序表的长度刚开始确定后就无法更改，即存储空间是静态的

若刚开始便声明很大的数组长度，则会造成内存的浪费

顺序表的实现——动态分配

Key: 动态申请和释放内存空间

C语言中，
使用malloc、free函数可以实现动态申请和释放内存空间
Cpp中，
使用new、delete关键字

#define InitSize 10 //顺序表的初始长度
typedf struct{ElemType *data;	//指示动态分配数组的指针int MaxSize;	//顺序表的最大容量int length;		//顺序表的当前长度
}SeqList;			//顺序表的类型定义（动态分配方式）

顺序表的实现——动态分配

//顺序表的实现——动态分配
#define InitSize 10 //默认的最大长度
#include<stdio.h>
#include<stdlib.h>
typedef struct{int *data;  //指示动态分配数组的指针int MaxSize;    //顺序表的最大容量int length;     //顺序表的当前长度
}SeqList;void InitList(SeqList &L){//使用malloc函数申请一片连续的存储空间L.data = (int *)malloc(InitSize *Sizeof(int));L.length = 0;L.MaxSize = InitSize;
}//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){int *p = L.data;L.data = (int *)malloc((L.MaxSize+len)*(sizeof(int)));for (int i = 0; i < L.length; ++i) {L.data[i] = p[i];   //将数据复制到新区域——时间开销大}L.MaxSize = L.MaxSize + len;    //将顺序表最大长度增加到lenfree(p);						//释放原来的内存空间
}int main(){SeqList L;  //声明一个顺序表InitList(L);IncreaseSize(L,5);return 0;	
}

顺序表的特点

• 随机访问 。即可以在O(1)时间内找到第i个元素
• 存储密度不高。每个节点只存储数据元素
• 拓展容量不方便。（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）