逻辑结构--线性表的定义

线性表是具有数据类型的n(n 0)个数据元素的有限序列。n为表长，n=0时称为空表。

相同数据类型：每个元素所占空间一样大；
有限：长度必须有限，比如所有整数就不是个线性表
序列：必须有次序

是线性表的”第i个“元素线性表中的位序；
是表头元素，是表尾元素。注意线性表的位序是从1开始，数组下标是从0开始；
除表头外，每个元素都有直接前驱；除表尾外，每个元素都有直接后继；

运算--线性表的基本操作

基本操作是指最核心、最基本的操作。其他复杂操作都可以通过调用基本操作来实现。

所有基本操作都可以归结为创建、销毁、增删改查

创建和销毁：
- InitList(&L):初始化表。构造一个空的线性表L，分配内存空间；
- DestoryList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间；
增删操作
- ListInsert(&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；

存储结构

顺序表

顺序表的定义

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

顺序表的特点：

随机访问：因为在内存中连续存储，所以在时间内即可找到第i个元素,代码实现data[i-1];
存储密度高，每个节点只需要存储数据元素本身
拓展容量不方便，即使是动态存储，拓展长度的时间复杂度也很高，因为需要复制原来的元素；
插入、删除操作不方便，需要移动大量的元素；

静态分配

静态分配就是用数组的方式来实现顺序表。

#define MaxSize 10    //定义最大长度
typedef struct {
	ElemType 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);
}

顺序表的局限性：顺序表的表长在刚开始确定后就无法更改。

动态分配

#define InitSize 10    //顺序表的初始长度

typedef struct {
  ElemType *data;     //指示动态分配数组的指针
  int MaxSize;        //顺序表的最大容量
  int length;         //顺序表的当前长度
}SeqList;

//C语言动态申请和释放内存空间--malloc、free
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

//C++动态申请和释放内存空间--new、delete
L.data=new ElemType[InitSize];

#define InitSize 10    //顺序表的初始长度

typedef struct {
	int *data;     //指示动态分配数组的指针
	int MaxSize;        //顺序表的最大容量
	int length;         //顺序表的当前长度
}SeqList;

void InitList(SeqList& L) {
	L.data = (int*)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}

//增加动态数组长度
void IncreaseSize(SeqList& L, int len)
{
	int* p = L.data;    //p和L.data指向同一个地址位置
	L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));   //L.data指向新的地址空间
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];   //将数据复制到新区域
	}
	L.MaxSize = L.MaxSize + len;   //顺序表最大长度增加len
	free(p);          //释放原来的内存空间
}

int main() {

	SeqList L; //声明顺序表
	InitList(L); //初始化顺序表

	IncreaseSize(L, 5);
}

动态存储不是链表，物理结构没有发生变化，都是连续的地址空间。只是可以运行时动态决定分配的内存地址空间。

基本操作

插入

实现在顺序表L中的()位置插入元素。要注意代表线性表的位序，是从1开始的，而内部使用的数组下标是从0开始的。

bool ListInsert(SqList& L, int i, Elemtype e)
{
	//首先判断i的范围是否有效
	if (i<1 || i>L.length + 1)   //用i>length+1是要保证线性表内部数据必须连续，当前长度为length，最多只能在length+1处插入
		return false;
	if (L.length >= MaxSize)   //存储空间已满
		return false;

	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];    //i位置后面的元素挨个后移。注意数组下标
	}

	L.data[i - 1] = e;      //i位置插入e，注意数组下标
	L.length++;				//线性表长度++
	return true;
}

时间复杂度计算最深层循环，即元素后移时的次数

最好时间复杂度：表尾插入，i=n+1（length+1），不需要后移，时间复杂度;
最坏时间复杂度：表头插入，i=1,原有的n个元素都需要向后移动，时间复杂度；
平均时间复杂度：新元素插入到任何一个位置的概率都相同，即i=1,2,3,……,length+1的概率都是p=1/(n+1)，每个相加，等差数列求和，得n/2,所以时间复杂度;

删除

实现删除顺序表L中第（）个位置的元素，用引用变量e返回。

bool ListDelete(Sqlist &L, int i, ElemType& e)
{
	//首先判断参数合法性
	if(i < 1 || i > L.length)
		return false;

	e = L.data[i-1];        //将被删除的元素赋值给e，注意数组下标和顺序表次序

	for(int j = i; j < L.length; j++)
	{
		L.data[j-1] = L.data[j];        //将第i个位置后的元素前移
	}

	L.length--;
	return true;
}

时间复杂度的耗时和插入一样，在元素移动上：

最好时间复杂度：表尾删除，i=n，无需移动元素，时间复杂度为；
最坏时间复杂度：表头删除，i=1，需要移动除了表头外的所有元素，时间复杂为；
平均时间复杂度:；

按位查找

获取表L中第i个位置的元素的值。

如果顺序表是静态分配的，那么可以直接用数组下标来取。要注意数组下标和位序的区别。

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int length;
}Sqlist;

ElemType GetElem(Sqlite L, int i)
{
	//这里可以补上对i合法性的判断
	return L.data[i-1];
}

动态分配时，依旧可以用数组下标来取值。

#define InitSize 10
typedef struct{
	ElemType *data;
	int MaxSize;
	int length;
}Seqlist;

ElemType GetElem(Seqlist L, int i)
{
	//这里可以补上对i合法性的判断
	return L.data[i-1];
}

按位查找的时间复杂度为。这就是顺序表随机存取的特性。顺序表在内存中都是连续存放的，可以根据起始地址和数据元素大小立即找到第个元素。

按值查找

在顺序表L中找到第一个元素等于的元素，并返回其位序。

int LocateElem(Sqlite L, ElemType e)
{
	int i;
	for(i = 0; i < L.length; i++)
		if(L.data[i] == e)
			return i+1;    //返回的是位序

	return 0;
}

注意：上面那个是伪代码，==只能用于基本数据类型，如果是类似于结构体那样的，C语言要自己挨个比较成员变量，C++需要重载==运算符。

时间复杂度：

最好时间复杂度：查找的元素在表头，只需要比较一次，时间复杂度；
最坏时间复杂度：查找的元素在表尾，循环比较n次，时间复杂度；
平均时间复杂度：;

链式存储

顺序表的优点是可以随机存取，存储密度高，但顺序表的缺点是要求大片的连续存储空间，改变容量很不方便，且插入和删除操作需要移动大量的元素。

链式存储的线性表，每个需要使用连续地址单元，通过链建立逻辑关系。每个节点除了存放数据元素之外，还存放指向下一个节点的指针。优点是不要求大片连续地址空间，改变容量方便，但缺点是不可随机存取，而且要耗费一定空间存放指针。

单链表

单链表定义

线性表的链式存储又称为单链表。

//单链表的定义
typedef struct LNode{
	ElemType data;        //数据域
	struct LNode *next;   //指针域
}LNode, *LinkList;

//表示一个单链表，只需要声明一个头指针L，指向单链表的第一个节点
LNode* L;
LinkLisk L;

//LNode*和LinkLisk一个意思，不过代码中一般用LNode*来强调这是一个结点，用LinkList来强调这是一个单链表。

单链表有两种实现方式，一种是带头节点，一种是不带头节点：

不带头节点的单链表初始化方式如下：

typedef struct LNode{
	ElemType data;        //数据域
	struct LNode *next;   //指针域
}LNode, *LinkList;

bool InitList(LinkList &L)
{
	L = NULL;      //空表
	return true;
}

void test()
{
	LinkList L;    //声明一个指向单链表的指针，注意此时并没有创建一个结点

	InitList(L);
}

//判空逻辑：
bool Empty(LinkList L)
{
	return (L == NULL);
}

头结点是在单链表的第一个结点之前附加一个结点，头结点不存储任何数据。

typedef struct LNode{
	ElemType data;        //数据域
	struct LNode *next;   //指针域
}LNode, *LinkList;

bool InitList(LinkList &L)
{
	L = (LNode*)malloc(sizeof(LNode));    //分配一个头结点
	if(L == NULL) return false;    //内存不足分配失败

	L->next = NULL;    //头结点之后暂时还没有结点
	return true;
}

void test()
{
	LinkList L;    //声明一个指向单链表的指针，注意此时并没有创建一个结点

	InitList(L);
}

//判空逻辑：
bool Empty(LinkList L)
{
	if(L->next == NULL)
		return true;
	else
		return false;
}

头指针和头结点的区别：

头指针始终指向链表中的第一个结点;
如果不带头结点，那头指针指向的就是存放数据的结点；如果带头结点，那么头指针指向的就是头结点，是不存放数据的；

之所以引入头结点，是为了写代码方便：

有头节点后，所有位置的操作算法统一，不再需要判断是否在第一个元素之前插入或删除第一个元素
不论链表是否为空，其头指针是指向头节点的非空指针，链表的头指针不变，因此空表和非空表的处理也就统一了

单链表基本操作

按位序插入

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

思路为找到待插入位置的前驱结点（第i-1），然后在其后面插入新结点。

带头结点的链表，不需要对第一个结点做特殊处理：

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e)
{
	if(i < 1) return false;   //先判断插入位置是否合法

	//第一步：找到第i-1个结点的位置
	LNode *p;        //指针p指向当前扫描到的结点
	int j = 0;		 //当前p指向的结点的位置
	p = L;           //L指向头结点，头结点是第0个结点(不存数据)
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	if(p == NULL)
		return false;   //i值不合法，超出了线性表长度

	//分配新结点，插入
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

这个算法的时间开销在于找到前驱结点的耗时，平均时间复杂度为

如果链表没有头结点，那么需要单独处理插入第一个元素时候的情况，需要把头指针的位置变更。后续的结点操作都一样

//在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList &L, int i, ElemType e)
{
	if(i < 1) return false;   //先判断插入位置是否合法

	//单独处理第一个结点
	if(i == 1)
	{
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;       //头指针指向新插入的结点
		return true;
	}

	//第一步：找到第i-1个结点的位置
	LNode *p;        //指针p指向当前扫描到的结点
	int j = 1;		 //当前p指向的结点的位置,此时从1开始
	p = L;           //p指向第一个结点，注意不是头结点
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	if(p == NULL)
		return false;   //i值不合法，超出了线性表长度

	//分配新结点，插入
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

按照结点插入

链表的插入操作分为前插操作和后插操作，即给定结点p，在其之后或者之前插入一个结点。单链表的插入算法中，一般都选择后插操作：

//在p结点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e)
{
	if(p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if(s == NULL)
		return false;  //分配失败，内存不足
	s->data = e;  //新创建的结点s保存数据元素e
	s->next = p->next;  
	p->next = s;     //将s连接到p之后
	return true;
}

正常来说，链表的每个结点都只能找到其后面的元素，那如何实现在某结点的前面插入元素呢？其实不需要考虑的那么复杂，链表插入后位置就固定了，我们依旧可以在p结点之后插入一个新结点s，然后交换p和s的数据域，达到偷天换日的效果：

//在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e)
{
	if(p == NULL)
		return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	if(s == NULL)
		return false;

	s->next = p->next; 
	p->next = s;       //依旧现在p结点之后插入s

	//交换s和p的数据域：
	s->data = p->data;
	p->data = e;
	return true;
}

//在p结点之前插入结点s
bool InsertPriorNode(LNode *p, LNode *s)
{
	if(p == NULL || s == NULL)
		return false;

	s->next = p->next; 
	p->next = s;       //依旧现在p结点之后插入s

	//交换s和p的数据域：
	ElemType temp = p->data;
	p->data = s->data;
	s->data=temp;
	return true;
}

按位序删除

只分析带头结点的链表的删除操作。删除第i个位置的结点p，只需要找到第i-1个结点，让其指向第i+1的位置即可：

bool ListDelete(LinkList &l, int i, ElemType &e)
{
	if(i < 1)
		return false;

	LNode* p;   //p指向当前扫描到的结点
	int j = 0;  //j是结点的位序，从0开始（头结点开始）
	p = L;   //L指向头结点

	while(p != NULL && j < i-1){  //找到第i-1个结点
		p = p->next;
		j++;
	}
	if(p == NULL)
		return false;   //i值不合法，超出线性表长度

	if(p->next == NULL)
		return false;    //第i-1个结点之后已经没有其他结点

	LNode* q = p->next;   //q指向被删除结点
	e = q->data;          //返回被删除元素的值
	p->next = q->next;    //将*q结点从链中断开
	free(q);              //释放存储空间
	return true;
}

时间消耗主要在寻找前驱结点上，平均时间复杂度是。

删除指定结点

删除指定的结点p，可以参考前插操作的偷天换日方法。赋值p的后继结点给自身，这样p和p的后继，同时指向了p的后继的后继，然后删除p的后继结点：

//删除指定的结点p
bool DeleteNode(LNode *p)
{
	if(p == NULL)
		return false;

	LNode* q = p->next;   //临时结点q指向p的后继
	p->data = p->next->data;  //p和后继结点交换数据域
	p->next = q->next;     //p的指针指向后继的后继
	free(q)；             //释放p的后继
	return true;
}

注意上面的代码是有缺陷的，不能删除最后的结点。因为最后的结点，他的后继是空，没有数据域了，会崩溃。如果要删除最后一个结点，那只能函数传递链表头指针，挨个遍历寻找p的前驱结点，时间复杂度是。这也体现出了单链表的局限性：无法实现逆向检索。

按位查找

只考虑带头结点的情况：

//按位查找，返回第i个元素,找不到返回NULL
LNode* GetElem(LinkList L, int i)
{
	if(i < 0)
		return NULL;

	LNode *p;     //指针p指向当前扫描到的结点
	int j = 0;    //从头结点开始
	p = L;        //p指向头结点
	while(p != NULL && j < i)
	{
		p = p->next;
		j++;
	}
	return p;
}

平均时间复杂度

按值查找

只考虑带头结点的情况

//按值查找，找到数据域==e的结点,没有返回NULL
LNode* LocateElem(LinkList L, ElemType e)
{
	LNode* p = L->Next; //L是头结点，p要从第一个结点开始
	//从第1个结点开始查找数据域为e的结点
	while(p != NULL && p->data != e){
		p = p->next;
	}
	return p;
}

求表长

int Length(LinkList L)
{
	int len = 0;
	LNode* p = L;
	while(p->next != NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}

上面是带头结点的单链表求表长。如果不带头结点，需要单独处理一下空表的情况。

单链表的建立

给定指定数量的数据元素，要把他们存到一个单链表里面，操作步骤：

初始化一个单链表
每次取一个数据元素，插入到链表中

根据插入到链表表头还是表尾，可以分为头插法和尾插法。

尾插法，即新结点插入到链表的表尾，插入顺序和结点次序相同。插入不要用前面的按位插入，每次插入都要进行一次遍历，整体的时间复杂度会变成。所以新增一个尾指针。始终指向当前链表的尾结点，每次插入只需要针对尾指针进行插入即可：

//尾插法
//用户循环输入int值，插入链表，直到输出9999结束
LinkList List_TailInsert(LinkList& L)
{
	int x;
	L = (LinkList)malloc(sizeof(LNode));   //初始化空表,建立头结点
	L->next = NULL; 
	LNode* s = L;
	LNode* r = L;   //r是尾指针
	scanf("%d", &x);
	while(x != 9999)
	{
		s = (LNode*)malloc(sizeof(LNode)); 
		s->data = x;
		r->next = s;
		r = s;   //尾指针指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL;   //尾结点指针置空
	return L;
}

头插法：每次输入元素的时候，都插入到单链表的表头。

LinkList List_HeadInsert(LinkList& L)
{
	LNode* s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));  //初始化空表，创建头结点
	L->next = NULL;     
	scanf("%d", &x);
	while(x != 9999)
	{
		s = (LNode*)malloc(sizeof(LNode));  //创建新结点
		s->data = x;
		s->next = L->next;  
		L->next = s;     //L为头指针，将新结点插入表头
		scanf("%d", &x);
	}
	return L;
}

双链表

单链表只能从前往后遍历。如果要访问某结点的前驱，只能再次从前往后遍历一次。所以引入双链表，内部两个指针，分别指向前驱结点和后继结点。

以下我们讨论双链表，默认带头结点。

typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;
}DNode, *DLinkNode;

//初始化
bool InitDLinkList(DLinkList &L)
{
	L = (DNode*)malloc(sizeof(DNode));  //分配一个头结点
	if(L == NULL)
		return false;
	L->prior = NULL;  //头结点的prior永远指向NULL
	L->next = NULL;   //初始化，头结点之后暂时还没有结点
	return true;
}


//双链表判空，只需要看头结点之后是否有结点
bool Empty(DLinkList L)
{
	if(L->next == NULL)
		return true;
	else
		return false;
}

双向链表的插入，一定要注意指针操作的顺序，还要特别处理一下如果插入到最后一个结点的情况。以后插操作为例子，所有的插入操作都可以转化为后插。

//在p结点之后插入结点s
bool InsertNextDNode(DNode *p, DNode *s)
{
	if(p == NULL || s == NULL)
		return false;

	//1、s后继指向p的后继
	s->next = p->next;

	//2、p的后继的前驱指向s，要注意p是否为尾结点
	if(p->next != NULL)
		p->next->prior = s;

	//3、s的前驱指向p
	s->prior = p;

	//4、p的后继指向s
	p->next = s;

	return true;
}

删除操作一样，要特别处理一下删除的结点就是最后一个结点的场景。

//删除p结点的后继结点
bool DeleteNextDNode(DNode* p)
{
	if(p == NULL)
		return false;

	DNode *q = p->next;  //q就是要删除的结点
	if(q == NULL)
		return false; //p没有后继结点，不用删除

	//1、p的后继指向q的下一个
	p->next = q->next;

	//2、q的前驱指向p，要判断q是不是已经是最后的结点了
	if(q->next != NULL)
		q->next->prior = p;

	free(q);  //释放结点空间
	return true;
}

销毁双链表，不断调用销毁结点的方法即可

void DestroyList(DLinkList &L)
{
	while(L->next != NULL)
		DeleteNextDNode(L);
	free(L);   //释放头结点
	L = NULL;  //头结点指向NULL
}

双链表不可随机存取，按位查找、按值查找都只能用遍历的方法实现，时间复杂度为

//后向遍历
while(p != NULL){
	p = p->next;
}

//前向遍历
while(p != NULL){
	p = p->prior;
}

//前向遍历跳过头结点
while(p->prior != NULL){
	p = p->prior;
}

循环链表

循环链表就是在单链表和双链表的基础上，做一点改变，变为循环单链表和循环双链表。

循环单链表

普通单链表最后一个结点指针指向NULL，而循环单链表最后一个结点的指针指向头结点。

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

//初始化循环单链表
bool InitList(LinkList &L){
	L = (LNode*)malloc(sizeof(LNode));  //分配一个头结点
	if(L == NULL)
		return false;
	L->next = L;        //头结点的next指向头结点
	return true;
}

//判断循环单链表是否为空（只有头结点）
bool Empty(LinkList L){
	if(L->next == L)
		return true;
	else
		return false;
}

//p判断结点p是否为表尾结点
bool IsTail(LinkList L, LNode *p){
	if(p->next == L)
		return true;
	else
		return false;
}

单链表从一个结点出发，只能找到后续的各个结点；
循环单链表从一个结点出发，可以找到其他任何一个结点；

链表的操作很多都是在头部或者尾部。循环单链表从头找到尾，时间复杂度为,但从尾找到头，时间复杂度仅为。所以很多时候循环单链表不设头指针，仅设尾指针，此时表头插入和表尾插入，时间复杂度都为。

循环双链表

双链表：表头结点的prior指向NULL，表尾结点的next指向NULL；
循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向表头结点；

typedef struct DNode{
	ElemType data;
	struct DNode *priot, *next;
}DNode, *DLinkList;

//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
	L = (DNode*)malloc(sizeof(DNode)); //分配一个头结点
	if(L == NULL)
		return false;
	L->prior = L;  //头结点的prior指向头结点
	L->next = L;   //头结点的next指向头结点
}

//循环双链表判空
bool Empty(DLinkList L){
	if(L->next == L)
		return true;
	else 	
		return false;
}

//判断结点p是否为表尾结点
bool IsTail(DLinkLisk L, DNode* p){
	if(p=>next == L)
		return true;
	else
		return false;
}

普通双链表的插入和删除，都需要考虑尾结点，因为尾结点后继是NULL，但循环双链表的插入和删除就比较简单

//在p后插入s
bool InsertNextDNode(DNode *p, DNode *s)
{
	s->next = p->next;
	p->next->prior = s;   //此处不需要再考虑是否为尾结点了，一定不为NULL
	s->prior = p;
	p->next = s;
}

//删除同理
//删除p结点的后继结点
bool DeleteNextDNode(DNode* p)
{
	if(p == NULL)
		return false;

	DNode *q = p->next;  //q就是要删除的结点

	p->next = q->next;
	q->next->prior = p;

	free(q);  //释放结点空间
	return true;
}

静态链表

对于普通单链表来说，各个结点在内存中星罗棋布，不连续；

静态链表：借助数组来描述链式存储结构，分配一整片连续的内存空间，各个节点集中安置。数组中分为数据域data和指针域next，这里的指针是指结点的数组下标--游标，next==-1时表示结束。

上图为例，假设每个结点共8B,数据元素占4B，游标占4B，则如果头结点的地址为addr，则存放e1的地址为addr+8*2.

//定义
#define MaxSize 10   //静态链表的最大长度
typedef struct{
	ElemType data;
	int next;
}SLinkList[MaxSize];

//上面的写法等价于
#define MaxSize 10   //静态链表的最大长度
struct Node{
	ElemType data;
	int next;
};
typedef struct Node SLinkList[MaxSize];

基本操作很少考察，代码实现相对动态链表来说，只需要修改指针，而不需要移动元素：

查找操作：

从头结点出发挨个往后遍历结点，时间复杂度;

插入位序为i的结点：

找到一个空结点，存入数据元素（初始化的时候，可以让next的值为一个特殊值，如-2，这样就知道哪个下标的值为空）；
从头结点出发找到位序为的结点；
修改新结点的next;
修改号结点的next;

删除某个结点：

从头结点出发找到前驱结点；
修改前驱结点的游标；
被删除结点的next设置为-2；

静态链表的优点：增删操作不需要大量移动元素

静态链表的缺点：不能随机存取，只能从头结点开始依次查询；容量固定不可变；

静态链表的适用场景：

不支持指针的低级语言；
数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

顺序表和链表

逻辑结构

在逻辑结构上都同属于线性表，都是线性结构

存储结构

顺序表：

优点：
1. 支持随机存取
2. 只需要存数据，存储密度高
缺点：
1. 需要分配大片连续空间；
2. 改变容量麻烦

链表：

优点：
1. 离散的小空间，分配方便
2. 改变容量方便
缺点：
1. 不可随机存取；
2. 需要额外存储地址，存储密度低；

基本操作

基本操作分为创建销毁、增删改查

顺序表的创建需要预分配大片连续地址空间，若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源。如果是静态分配，容量不可改；如果是动态分配，虽然可变容量，但需要移动大量元素，时间代价很高；

链表的创建只需要分配一个头结点，之后扩展很方便

顺序表的销毁操作只需要修改Length=0即可。对于静态分配的数据，等待系统自己回收空间；如果是动态分配的数组，那么需要手动free.

链表销毁时依次free结点

顺序表的插入和删除，需要将后续元素依次后移/前移，时间复杂度为，时间开销来自于移动元素。

链表的插入和删除只需要修改指针即可，时间复杂度也为,时间开销来自于查找目标元素。

虽然时间复杂度表示相同，但如果数据元素很大，则移动的时间代价很高，查找元素的时间代价更低。链表的效率要比顺序表高的多。

顺序表有随机存取特性，按位查找的时间复杂度是;链表只能一个一个遍历，时间复杂度为;

顺序表按值查找的时间复杂度为,如果元素有序，则可以利用一些算法在内找到；链表按值查找的时间复杂度为。

顺序表的查找效率更高。

取舍

表长难以预估，经常需要增删元素-------使用链表

表长可预估，查询操作较多--------使用顺序表

试卷中出现开放式题目，回答使用链表还是顺序表更好，可以通过框架来答题：

顺序表和链表的逻辑结构都是线性结构，都属于线性表。但二者存储结构不同，（分别说特点和优缺点），由于采用的存储方式不同，导致基本操作的效率也不一样，（分别说基本操作）

Fabian备忘录

二、线性表

逻辑结构--线性表的定义

运算--线性表的基本操作

存储结构

顺序表

顺序表的定义

静态分配

动态分配

基本操作

插入

删除

按位查找

按值查找

链式存储

单链表

单链表定义

单链表基本操作

按位序插入

按照结点插入

按位序删除

删除指定结点

按位查找

按值查找

求表长

单链表的建立

双链表

循环链表

循环单链表

循环双链表

静态链表

顺序表和链表

逻辑结构

存储结构

基本操作

取舍