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

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

2.顺序表

定义

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

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

#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
	int data[MaxSize];	
	int length;			//当前长度
}SqList;
//	初始化顺序表
void InitList(SqList &L){
	for(int i=0; i<MaxSize ; i++)
		L.data[i] = 0 ; //设置默认值为0
	L.length = 0 ;
}

int main(){
	SqList L;	//声明顺序表
	InitList(L);
	return 0;
}

动态分配

C malloc 、frree 函数

C++ new 、delete 关键字

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10 //定义默认最大长度
typedef struct{
	int *data;		//指示动态分配数组的指针	
	int MaxSize;	//顺序表的最大容量
	int length;		//当前长度
}SqList;
//	初始化顺序表
void InitList(SqList &L){
	//申请存储空间
	L.data = (int*)malloc(InitSize*sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SqList &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;//顺序表最大长度增加len
	free(p);					//释放原来的内存空间
}

int main(){
	SqList L;	//声明顺序表
	InitList(L);//初始化顺序表
	printf("%d\n",L.MaxSize);
	IncreaseSize(L,5);//增加数组长度
	printf("after:%d\n",L.MaxSize);

	system("pause");
	return 0;
}

顺序表的特点

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

顺序表的插入和删除

插入

#include <stdio.h>
#define MaxSize 10

//定义顺序表
typedef struct{
	int data[MaxSize];	//数据
	int length;			//当前长度
}SqList;
//将e插入到顺序表L的第i处
bool ListInsert(SqList &L,int i,int e){
	if(i<1 || i<L.length+1)	//判断i的范围是否有效
		return false;
	if(L.length>= MaxSize) //当前存储空间已满，不能插入
		return false;
	for(int j=L.length; j>=i ; j--)//将第i个以及之后的元素后移
		L.data[j] = L.data[j-1];
	L.data[i-1] = e;
	L.length++;
	return true;
}

删除操作

//删除顺序表中的第i个元素
bool ListDelete(SqList &L,int i ,int &e){
	if(i<1 || i>L.length)	//判断i的范围是否合理
		return false;
	e = L.data[i-1];		//将被删除的值赋给e
	for(int j=i-1 ; j<L.length ;j++ ){					//元素前移
		L.data[j] = L.data[j+1];
	}
	L.length--;
	return true;
}

顺序表的查找

按位查找

//按位查找:获取表L中第i个位置的元素的值
int GetElem(SqList L,int i){
	return L.data[i-1];
}

按值查找

//按值查找：在表L中查找具有给定关键字值的元素,并返回对应位序
int LocateElem(SqList L,int e){
	for(int i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
		return 0;	//查找失败
}

3.单链表

定义

优点：不要求大片连续空间，改变容量方便。

缺点：不可随机存取，要耗费一定空间复杂度。

单链表的初始化

注意：如无特殊要求，一般视为带头结点的单链表来处理

不带头节点的单链表

#include <stdio.h>
#include <stdlib.h>
//不带头结点的单链表
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
	L = NULL;	//空表，无结点，防止脏数据
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
	if(L == NULL )
		return true;
	else
		return false;
}

void test(){
	LinkList L;
	InitList(L);
}

带头节点的单链表

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
	int 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;
}

int main(){
	LinkList L; //声明一个单链表指针
	InitList(L);

	system("pause");
	return 0;
}

比较

不带头结点，写代码更麻烦
对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
对空表和非空表的处理需要用不同的代码逻辑

插入按位序插入

带头结点

//在第i个位置插入元素e
bool ListInsert(LinkList &L ,int i, int e){
	if(i<1)
		return false;
	LNode *p;	//指针指向当前扫描到的结点
	int j=0;	//当前p指向的是第几个结点
	p = L;
	while (p!=NULL && j<i<1){	//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	//开始插入操作
	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, int 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;
	}

	LNode *p;	//指针指向当前扫描到的结点
	int j=0;	//当前p指向的是第几个结点
	p = L;
	while (p!=NULL && j<i<1){	//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	//开始插入操作
	LNode *s = (LNode *)malloc(sizeof(LNode));//申请空间
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

指定结点的后插操作

//后插操作:在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->next = p->next;
	p->next = s;		//将结点s保存数据元素e
	return true;
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	LNode *p;
	int j =0;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	InsertNextNode(p,e);
}

指定结点的前插操作

//前插操作：在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->data = p->data;  //将p中的元素复制到s中
	p->data = e;		//p中元素覆盖为e
	return true;
}

按位序删除

//按位序删除（带头结点）
bool ListDelete(LinkList &L,int i,ElemType &e){
	if(i<1)
		return false;
	LNode *p;
	int j=0;
	p = L;
	while(p!=NULL && j<i-1){//将p指针定位到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)//i值不合法
		return false;
	if(p->next == NULL)
		return false;
	LNode *q = p->next;	//令q指向被删除结点
	e = q->data;		//用e返回元素的值
	p->next=q->next;	//将*q结点从链中“断开”
	free(p);			//释放结点的存储空间
	return true;
}

指点结点的删除

即将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->next=q->next;		//将*q结点从链中“断开”
	free(q);				//释放后继结点的存储空间
	return true;
}

单链表的查找

按位查找

//按位查找，返回第i个元素(带头结点)
LNode * GetElem(LinkList L,int i){
	int j=1;
	LNode *p=p->next;
	if(i==0)//若获取的是第一个结点
		return L;
	if(i<1)//若链表L中没有结点
		return NULL;
	while(p!=NULL && j<i){
		p=p->next;
		j++;
	}
	return p;
}

按值查找

//按位查找，找到数据域==e的结点
LNode * LocateElem(LinkList L,ElemType e){
	LNode *p = L->next;
	//从第1个结点开始查找数据域为e的结点
	while(p!=NULL && p->data!=e)
		p=p->next;
	return p;		//若找到则返回结点指针，否则返回NULL
}

表的长度

//表的长度
int length(LinkList L){
	int len=0;
	LNode *p =L;
	while(p->next!=NULL){
		p = p->next;
		len++;
	}
	return len;
}

单链表的建立

尾插法

//尾插法
bool List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;						//r为表尾指针
	scanf("%d",&x);						//输入结点的值
	while(x!=9999){						//输入9999则结束输入
		//在r结点之后插入元素x
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r=s;							//确保r为表尾指针
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}

头插法

即每次插入一个元素都插入到单链表头结点后面。

LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	scanf("%d",&x);						//输入结点的值
	while(x!=9999){						//输入9999则结束输入
		//在头结点之后插入元素x
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d",&x);
	}
	return L;
}

4.双链表

与单链表相比，多了个前驱指针，可以逆向检索

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

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

//初始化双链表(带头结点)
bool InitDLinkList(DLinklist &L){
	L = (DNode *)malloc(sizeof(DNode));
	if(L==NULL)			//内存不足，分配失败
		return false;
	L->prior = NULL;	//头结点的prior永远指向NULL
	L->next = NULL;		
	return true;
}

int main(){
	//初始化双链表
	DLinklist L;
	InitDLinkList(L);

	return 0;
}

插入

//在p结点后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL)
		return false;
	s->next = p->next;
	if(p->next != NULL)	//如果p结点有后继结点
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
	if(p==NULL)
		return false;
	DNode *q = p->next;		//找到p的后继结点q
	if(q==NULL)				//p没有后继结点q
		return false;
	p->next = q->next;
	if(q->next!=NULL)		//q结点不是最后一个结点
		q->next->prior = p;
	free(q);				//释放结点空间
	return true;
}

5.循环链表

循环单链表

将表尾指针指向头结点

#include <stdio.h>
#include <stdlib.h>
#define ElemType int

typedef struct LNode{        //定义单链表结点类型
    ElemType data;           //每个节点存放一个数据元素
    struct LNode *next;      //指针指向下一个节点
}LNode,*LinkList;

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

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

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

循环双链表

双链表:
表头结点的prior指向NULL;

表尾结点的next指向NULL
循环双链表:
表头结点的prior指向表尾结点;

表尾结点的next指向头结点

初始化

#include <stdio.h>
#include <stdlib.h>
#define ElemType int


typedef struct DNode{
ElemType data;
struct DNode *prior ,*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指向头结点
	return true;
}
//判断循环双链表是否为空
bool Empty(DLinklist L) {
	if(L->next == L)
		return true;
	else
		return false;
}

//判断结点p是否为循环链表的表尾结点
bool isTail(DLinklist L,DNode *p){
	if( p->next==L)
		return true;
	else
		return false;
}

void testDLinkList() {
	//初始化循环双链表
	DLinklist L;
	InitDLinkList(L);
	// ...后续代码...
}

与双链表基本操作的不同

在p结点后插入新结点、删除p结点后面的结点时不用考虑p后继结点是否为空的问题

删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
	if(p==NULL)
		return false;
	DNode *q = p->next;		//找到p的后继结点q
	//注释的内容为双链表所需进行的条件判断
	//if(q==NULL)				//p没有后继结点q
	//	return false;
	p->next = q->next;
	//if(q->next!=NULL)		//q结点不是最后一个结点
	//	q->next->prior = p;
	free(q);				//释放结点空间
	return true;
}

插入

//在p结点后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL)
		return false;
	s->next = p->next;
	//注释的内容为双链表所需进行的条件判断
	// if(p->next != NULL)	//如果p结点有后继结点
	//	 p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

6.静态链表

单链表:各个结点在内存中随机存储。
静态链表:分配一整片连续的内存空间，各个结点集中存储。用数组的方式实现的链表。

#define MaxSize		//静态链表的最大长度
typedef struct {	//静态链表结构类型的定义
	int data;	//存储数据元素
	int next;		//下一个元素的数组下标
}SLinkList[MaxSize];

基本操作的实现逻辑

初始化静态链表:
把a[o] 的next 设为1
把其他结点的next设为一个特殊值用来表示结点空闲，如-2

查找:
从头结点出发挨个往后遍历结点

插入位序为i的结点:
①找到一个空的结点，存入数据元素

②从头结点出发找到位序为i-1的结点

③修改新结点的next
④修改i-1号结点的next

删除某个结点:
①从头结点出发找到前驱结点

②修改前驱结点的游标
③被删除结点next设置一个特殊值以表示已经被删除

7.顺序表和链表的异同

逻辑结构

都属于线性表，都是线性结构

存储结构

顺序表（顺序存储）：

优点:支持随机存取、存储密度高
缺点:大片连续空间分配不方便,改变容量不方便

链表（链式存储）：

优点:离散的小空间分配方便、改变容量方便
缺点:不支持随机存取、存储密度低

基本操作

创销、增删改查

创建

顺序表：

需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量;若分配空间过大，则浪费内存资源
链表：

只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

销毁

顺序表：

静态分配:静态数组 -->系统自动回收空间
动态分配:动态数组( malloc、 free) --> 需要手动free
链表：

依次删除各个结点（ free)

增删

顺序表：

插入/删除元素要将后续元素都后移/前移
链表：

插入/删除元素只需修改指针即可

查

顺序表：

按位查找:O(1)
按值查找:O(n)若表内元素有序，可在O( $\log_{2}n$ )时间内找到
链表：

按位查找:O(n)
按值查找:O(n)

综上所述

表长难以预估、经常要增加/删除元素—―链表
表长可预估、查询（搜索）操作较多――顺序表

开放式问题的答题思路:

问题:请描述顺序表和链表的bla bla bla....
交规线性表时,用顺序表还是链表好?(6分)
一一
顺序表和链表的逻辑结构都是线性结构，都属于线性表。
但是二者的存储结构不同，顺序表采用顺序存储...(特点，带来的优点缺点);链表采用链式存储...(特点、导致的优缺点）。
由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时...;当插入一个数据元素时...;当删除一个数据元素时...;当查找一个数需元素时...

代码：一种类似outlook资源树的CSS样式

.ztree{ padding

apache doris和StarRocks的区别

记录一下最新要用到2个新数据库的区别 Apache Doris是一个分布式的列式存储系统，它的设计目标是提供大规模数据处理的可靠性和高性能。Doris采用了集群方式，通过将数据分布在多个机器上进行处理来提高性能，并提供了SQL查询接口方便用户使用。 St

jquery find 找到frame select_《jQuery》

一、jQuery 如何获取元素 jQuery的基本设计思想和主要用法，就是"选择某个网页元素，然后对其进行某种操作"。这是它区别于其他Javascript库的根本特点。使用jQuery的第一步，往往就是将一个选择表达式，放

thymeleaf 静态资源公共模板找不到不存在

我想引入这两个文件

FCM服务器 admin-SDK接入指引

fabric-sdk-go代码启动报错：failed to create resmgmt client due to context error: user not found

在学习fabric的过程中，一步步走到了编写SDK的阶段，却被一个问题困扰了好久，在编写的fabric-sdk-go程序运行时一直报错：根据指定的资源管理客户端Context创建通道管理客户端失败: failed to create resmgmt cli

oracle查询备份记录,oracle 备份记录

cntrl_32_1_846932923 本机恢复步骤 1、做一次完整全备，确认备份成功。 2、手工删除一部分数据(运用在测试机上)。 3、查看数据控制文件 #su - oracle #rman

序列模型懒人简介（RNN、Seq2Seq、LSTM、GRU、Transformer）

点关注不迷路哦!点关注不迷路哦!点关注不迷路哦! RNN主要用于处理序列数据。RNN采用循环的结构，每个单元的输出与当前输入和之前的隐状态向量有关，每个单元输出一个预测值和传递到下一个单元的隐状态向量。很容易发现RNN有以下问题：1、输入与输出长度相

python 线程锁_python多线程锁的问题？

1，线程是指一个进程中的子任务，多线程就是指一个进程中同时运行多个子线程。比如有两个变量a,b，两个线程一和二，线程一的作用是改变a的值，线程二的作用是改变b的值，这样不管这两个线程怎么运行，a和b的值都不互相干扰。但是如果线程一和线程二的作用都是操作同一个变量c呢，我们为了要保证c的值得精

通用mapper集成，及代码成认识

spring的配置文件配置的是扫面生成的东西（配置在web端），generator.xml（配置在core依赖项目里，配合该core的pom.xml使用这个pom.xml中要配置注入的插件