线性表

定义

线性表是具有相同类型的n(n>0)个元素的有限序列，其中n为表长，当n=0时，该表为空表

若L命名为线性表，则一般表示为

• 前续节点
• 后续节点

基本操作

• InitList(&L):初始化表。构造一个空的线性表
• DestoryList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间
• LocateElem(L,e):按值查找。在表中L查找具有给定关键字值的元素
• GetElem(L,i):按位查找，获取表L中第i个位置的元素的值
• ListIntsert(&L,i,e):插入操作，在表L中的第i个位置插入制定元素e
• ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
• PrintList(L):输出操作
• Empty(L):判空操作
• Length(L):求表长

线性表的顺序存储

• 逻辑顺序和物理顺序是相同的
• 第n个元素的内存地址 = LOC(A)+(n-1)*sizeof(ElemType)

数组静态分配

#define MaxSize
typedef struct{
    ElemType data[MaxSize]; //固定空间
    int length;
}sqlList;

数组动态分配

#define MaxSize 50
typedef struct{
    ElemType *data; //没有固定空间，动态分配
    int length;
}sqlList;`

线性表的链式存储(单链表)

• 通过指针实现线性逻辑关系

typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;

线性表的顺序表示(数组)=

数组

数组是由相同类型的元素的集合所组成的一种线性数据结构,当我们创建一个数组时,在内存里面是分配了一块连续的内存空间来存储的,当我们获取数组中的元素时,可以通过元素的索引计算出该元素对应的存储地址.

核心规则

• 数组在内存里面是一块连续的内存空间
• 数组里存的元素类型是相同的
• 数组是通过索引来获取对应的元素

基本操作

操作	说明
InitList(&L)	初始化表。构造一个空的线性表
DestoryList(&L)	销毁操作。销毁线性表，并释放线性表L所占用的内存空间
LocateElem(L,e)	按值查找。在表中L查找具有给定关键字值的元素
GetElem(L,i)	按位查找，获取表L中第i个位置的元素的值
ListIntsert(&L,i,e)	插入操作，在表L中的第i个位置插入制定元素e
ListDelete(&L,i,&e)	删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
PrintList(L)	输出操作
Empty(L)	判空操作
Length(L)	求表长

数组特性

• 数组在通过索引读写元素的时候非常快，但是在插入、删除元素的时候就比较慢了
• 数组扩容比较麻烦

数组的创建

https://zhuanlan.zhihu.com/p/363343364

double[] numbers = new double[8];

double balance[] = {1000.0, 2.0, 3.4, 7.0, 50.0, 49.0, 98.4, 78.98};

当我们执行上面的代码的时候,就会在内存里面申请一个长度为8,数据类型为double的数组,它在内存里面是以一段连续的内存空间来标识。

question: 为什么必须指定数组的数据类型？

如果我们在创建一个数组的时候不指定数据类型，那么意味着我是无法知道未来这个数组会存储什么数据的，如果在我不知道需要存储什么数据的情况下又如何知道我要向内存申请多大的空间来创建这个数组呢？显然这么一思考答案就不言而喻了。好了，现在我们已经知道了数组在创建的时候就指定了能存储的数据类型了，那么创建数组的时候，只需要稍微计算一下就能知道需要向内存申请的空间大小了，比如new int[8] 我会向内存申请一个8*4 字节的大小的内存空间(int类型数据占用4字节)。

数组读写元素的过程

数组插入元素的过程

数组删除元素的过程

数组的扩容

因为数组内存连续性的要求,所以在申请内存的时候必须指定数组的空间大小,而这个空间大小在申请后就已经固定无法变更,所以数组自己无法扩容,只是我们人为用逻辑的方式对数组进行扩容，我们可以通过创建一个更大的新数组，然后把原数组的元素一个个迁移到新数组上来，通过这种方式进行人为的扩容

线性表的链表示(链表)

链表

链表是一种不要求内存连续的顺序存储的数据结构,他的数据节点可以分布在内存中的各个地方,节点之间是各自记录下一个元素的指针,通过指针把所有节点串联起来组成了一条链式的结构

组成部分
一个完整的链表需要由以下几个部分组成:

• 头指针
• 节点
  • 头节点
  • 首元节点
  • 其他节点

基本操作

操作	说明
List_Init(LinkList &L)	创建
List_HeadInsert(LNode &L)/List_TailInsert(LNode &L)	插入(头插法/尾插法)
List_deleate(ElemType e)	删除
LNode *GetElem(LinkList L,int i) / LNode *LocateElem(LinkList L,ElemType e)	查找(按序号/按值查找)
Length(&L)	求表长
Empty(&L)	判空操作

• 头插法
  从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头节点之后，逆序的链表
• 尾插法
  从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾结点之后，顺序的链表

单链表

双向链表(双链表)

循环链表

• 单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。
• 多重链的循环链表——将表中结点链在多个环上。

约瑟夫环

静态链表