数据结构]用 C 语言实现双链表的基本操作
双链表
导言
大家好,很高兴又和大家见面啦!!!
经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起来看看吧!
一、单链表与双链表
线性表的链式存储称为链表,链表是由数据域和指针域组成。
由一个数据域和一个指针域组成的链表我们称为单链表,单链表的指针域指向后继结点,所以我们在访问单链表时只能从前往后访问。这就导致了一个问题:我们在访问后继结点时的时间复杂度为O(1),但是在访问前驱结点时的时间复杂度却是O(n)。
为了克服单链表的这种单一访问的缺点,于是我们在单链表的结点上新增了一个指针域,使得链表上的每个结点都由一个数据域和两个指针域组成,双链表的结点结构如下所示:
这两个指针域一个指向后继结点(next),一个指向前驱结点(prior),我们将由这种结构的结点构成的链表称为双链表。
双链表和单链表一样,双链表也有带头结点的双链表与不带头结点的双链表,在没有特殊说明的情况下,我们都是以带头结点的双链表进行说明。接下来我们就来看一下与双链表相关的基本操作;
二、双链表类型的创建
我们首先来看一下双链表的类型创建的基本格式:
//双链表类型创建的基本格式
typedef struct DNode {
ElemType data;//数据域
struct DNode* prior, * next;//指针域
}DNode, * DLinkList;//数据类型重命名
//DNode——Double Node——强调的是双链表的结点
//DLinkList——强调的是指向双链表的指针,也就是整个双链表
//prior——在先的,在前的,先前的——指向前驱结点的指针
//next——下一个的,紧接着的,接下来的——指向后继结点的指针
//ElemType——数据元素的数据类型
//data——存储链表数据元素的变量
从格式中可以看到,其实双链表与单链表的类型创建格式是一致的,它们之间的差别有以下几点:
- 为了对这两种类型的链表有所区分,单链表的结点类型我们将其定义为
LNode
,双链表则是DNode
; - 单链表的类型我们将其定义为
LinkList
,双链表则是DLinkList
; - 在双链表中,我们定义了一个额外的指针
prior
用于指向前驱结点;
有了这个基本格式,我们同样还是以整型类型的数据元素为例来定义一个双链表,如下所示:
//双链表类型创建
typedef struct DNode {
int data;
struct DNode* prior, * next;
}DNode, * DLinkList;
int main()
{
DLinkList L;//定义指向双链表的头指针
return 0;
}
有了双链表的头指针,接下来我们就可以来创建双链表的头结点并将其初始化了;
三、双链表的初始化
我们先来看一下双链表初始化的基本格式:
//双链表初始化的基本格式
bool InitDLinkList(DLinkList* L)
{
*L = (DNode*)calloc(1, sizeof(DNode));//创建头结点
assert(*L);//如果头结点创建失败,则报错
(*L)->prior = NULL;//初始化前驱指针
(*L)->next = NULL;//初始化后继指针
return true;
}
可以看到,对于双链表来说,我们在初始化头结点时不仅要将后继指针进行初始化,还要将前驱指针进行初始化,这样是为了防止这两个指针变成野指针。
- 在单链表中有一点我们没有提到,就是我们在通过
malloc
和calloc
申请空间后一定要及时的对接收空间的指针进行检测,看是否为空指针。 - 当空间申请失败后,这两个函数返回的就是一个空指针,所以为了避免出现问题,我们可以通过assert来进行断言,也可以通过条件语句来进行判断。
- 对指针这一块的知识掌握的不牢固的朋友可以通过【C语言总集篇】指针篇这篇博客来复习一下指针的相关知识点
我们在对双链表初始化之后就可以来通过头插法或者尾插法来创建一个双链表了;
四、双链表的创建
由于双链表的结点结构与单链表的结点结构不同,因此我们在创建双链表时的逻辑也是稍有区别的,如下图所示:
由于多了一个前驱结点,这就导致我们在创建链表时通过头插法在创建第一个表头元素与创建其他的表头元素的步骤稍有不同,如下所示;
用头插法创建第一个表头结点的步骤:
- 新结点的后继指针指向头结点的后继指针指向的对象,即NULL;
- 新结点的前驱指针指向头结点;
- 头结点的后继指针指向新结点;
用C语言来描述的话则是:
//头插法创建第一个表头结点的插入步骤
New_Node->next = Head->next;//新结点的后继指针指向头结点后继指针指向的对象,即NULL
New_Node->prior = Head;//新结点的前驱指针指向头结点
Head->next = New_Node;//头结点的后继指针指向新结点
- 注:这个插入顺序要确保第3步的操作一定在第1步操作完后再执行;第2步的操作顺序可以随意放置;
用头插法创建第二个及以上的表头结点的步骤:
- 新结点的后继指针指向头结点的后继指针指向的对象,即表头结点;
- 头结点后继指针指向对象的前驱结点指向新结点;
- 新结点的前驱指针指向头结点;
- 头结点的后继指针指向新结点;
用C语言描述的话则是:
//头插法创建第二个及以上的头结点的插入步骤
New_Node->next = Head->next;//新结点的后继指针指向头结点后继指针指向的对象,即NULL
Head->next->prior = New_Node;//头指针的后继指针指向对象的前驱指针指向新结点
New_Node->prior = Head;//新结点的前驱指针指向头结点
Head->next = New_Node;//头结点的后继指针指向新结点
- 注:这个插入顺序要确保第4步的操作一定在第1步与第2步操作完之后执行;第3步操作的顺序可以随意放置;
接下来我们来看一下在这个逻辑下的双链表的头插法的基本格式:
//头插法创建双链表的基本格式
DLinkList DList_HeadInsert(DLinkList* L)
{
DNode* p;//指向新结点的指针
ElemType x = 0;//接收数据元素的变量
……;//获取需要存储的数据元素
while (x != EOF)//通过给循环设置结束条件来控制创建的结束
{
p = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(p);//当创建新结点失败时,assert会对指针p进行报错
if (!(*L)->next)//当头结点的后继指针指向空指针时
{
p->data = x;//将数据元素存储到新结点的数据域中
p->next = (*L)->next;//新结点的后继指针指向头结点后继指针指向的对象
p->prior = *L;//新结点的前驱指针指向头结点
(*L)->next = p;//头结点的后继指针指向新结点
}
else
{
p->data = x;//将数据元素存储到新结点的指针域中
p->next = (*L)->next;//新结点的后继指针指向头结点后继指针指向的对象
(*L)->next->prior = p;//头结点的后继指针指向的对象的前驱指针指向新结点
p->prior = *L;//新结点的前驱指针指向头结点
(*L)->next = p;//头结点的后继指针指向新结点
}
……;//获取需要存储的数据元素
}
return (*L);//创建好链表后返回头指针
}
但是对于尾插法而言,不管是第一个结点还是最后一个结点的创建,在插入步骤上都是不影响的,因为表尾结点的后继指针肯定是指向NULL的,因此通过尾插法创建的双链表则不需要分情况讨论,对应的尾插法创建格式如下所示:
//尾插法创建双链表的基本格式
DLinkList DList_TailInsert(DLinkList* L)
{
DNode* r = *L;//指向表尾的指针
DNode* s;//指向新结点的指针
ElemType x = 0;//接收数据元素的变量
……;//获取需要存储的数据元素
while (x != EOF)//通过给循环设置结束条件来控制创建的结束
{
s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(s);
s->data = x;//将数据元素存储到新结点的数据域中
s->next = r->next;//新结点的后继指针指向表尾结点的后继指针,即NULL
s->prior = r;//新结点的前驱指针指向表尾结点
r->next = s;//表尾结点的后继指针指向新结点
r = s;//表尾指针指向新结点
……;//获取新的数据元素
}
return(*L);//当链表创建结束,返回头指针
}
在创建好双链表后,我们又该如何遍历双链表来访问某个结点呢?
五、双链表的遍历
在给定一个结点后要想对单链表进行遍历的话,我们只能从该结点往后遍历,但是在双链表中,我们既可以从给定结点开始往后遍历,又可以从给定结点开始往前遍历。遍历的方式也很简单,我们只需要将指向双链表的指针往我们需要遍历的方向进行移动就行,如下所示:
//给定结点指针p遍历双链表
while (p->next)//p的后继结点不为空指针
{
p = p->next;//从结点p往后遍历
}
while (p->prior)//p的前驱结点不为空指针
{
p = p->prior;//从结点p往前遍历
}
想要对某一个结点进行想过操作时,我们就可以通过这个遍历的方式来找到对应结点并执行相关操作。
六、双链表的查找
由于双链表是与前驱结点以及后继结点进行双向链接的,因此我们在给定双链表的一个结点后,不管是查找该结点的后继结点还是前驱结点,对应的时间复杂度都为O(1);
在未给定结点的情况下,我们要想查找对应的结点,我们同样可以通过按值查找与按位查找两种查找方式来执行,下面我们来看一下在双链表中,这两种查找方式的基本格式又是如何:
//双链表的按位查找
DNode* GetElem(DLinkList L, int i)
{
if (i < 1)
return NULL;//当查找的位序不合理时返回空指针
DNode* p = L->next;//指向表头结点的指针
int j = 1;//表头结点的位序
while (p && j < i)//当查找结点为空指针时结束循环;当查找结点的位序与目标位序相等时结束循环
{
p = p->next;//继续往后遍历
j++;
}
return p;//查找结束后返回指针p
}
如果是已知某一个结点的位序,需要查找另一个结点的位序,我们可以将函数的参数换成已知的结点以及需要查找的结点位序就行,这里就不再展开。下面我们来看一下按值查找的基本格式:
//双链表的按位查找
DNode* LocateElem(DLinkList L, ElemType e)
{
DNode* p = L->next;//指向表头结点的指针
while (p && p->data != e)//当查找结点为空指针时结束循环
//当查找结点的数据域存储的元素与目标元素相等时结束循环
{
p = p->next;//继续往后遍历
}
return p;//查找结束后返回指针p
}
对于双链表而言,在进行查找操作时对应的时间复杂度就有以下几种情况:
- 如果是从表头结点或者表尾结点开始进行查找的话,那对应的时间复杂度就是O(n);
- 如果是已知结点要查找对应的前驱结点或者后继结点的话,那对应的时间复杂度就是O(1);
- 如果是已知某一结点,需要查找位序在该结点前面或者后面的结点的话,那对应的时间复杂度就是O(n);
七、双链表的插入
双链表的插入操作也是有前插与后插操作,前插操作的逻辑与单链表一致,都是通过在指点结点的后面插入一个新的结点,再对数据域中存储的数据进行移动从而完成前插操作,下面我们先来看一下双链表前插操作的基本格式:
//双链表的前插操作
bool InsertPriorDNode(DNode* p, ElemType e)
{
assert(p);//指针p为空指针时报错
DNode* q = p->prior;//指针p的前驱结点
assert(q);//指针q为空指针时报错
DNode* s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(s);//指针s为空指针时报错
s->data = e;//将要插入的元素e放入新结点的数据域中
s->next = p;//将新结点的后继指针指向进行前插操作的结点p
p->prior = s;//将结点p的前驱指针指向新结点s
q->next = s;//将前驱结点的后继指针指向新结点s
s->prior = q;//将新结点的前驱指针执行前驱结点q
return true;//完成前插操作后返回true
}
在双链表中进行前插操作时,我们有几点需要注意:
- 首先要确定该结点不是头结点,也就是该结点的前驱结点不为空指:
- 当该结点为头结点时,不能进行前插操作,此时给予一定的信息进行提示;
- 当该结点不为头结点时,则可以正常进行前插操作;
- 因为双链表结点的前驱指针直接指向的是前驱结点,因此我们不需要像单链表一样调用函数来查找前驱结点;
- 在进行插入操作时,前驱结点的后继指针执行新结点的操作最好放在最后一步执行;
下面我们来看一下双链表的后插操作:
//双链表的后插操作
bool InsertNextDNode(DNode* p, ElemType e)
{
assert(p);//指针p为空指针时报错
DNode* s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(s);//指针s为空指针时报错
s->data = e;//将要插入的数据放入新结点的数据域中
if (p->next)//结点p的后继结点不为空指针
{
s->next = p->next;//将新结点的后继指针指向结点p的后继结点
p->next->prior = s;//结点p的后继结点的前驱指针执行新结点
s->prior = p;//新结点的前驱指针指向结点p
p->next = s;//结点p的后继指针指向新结点
}
else//结点p的后继结点为空指针
{
s->next = p->next;//将新结点的后继指针指向结点p的后继结点
s->prior = p;//新结点的前驱指针指向结点p
p->next = s;//结点p的后继指针指向新结点
}
return true;//完成后插操作后返回true
}
在双链表中我们要执行后插操作,我们也需要注意几点:
- 要判断当前结点的后继结点是否为空指针,从而选择插入操作的执行步骤:
- 当前结点的后继结点不为空指针时,需要将后继结点的前驱指针的指向对象换成新结点;
- 当前结点的后继结点为空指针时,只需要将新结点的后继指针指向空指针就行
- 不管当前结点的后继结点是否为空指针,我们最好都是将当前结点的后继指针指向新结点的操作放在最后执行;
对于双链表而言,不管是前插操作还是后插操作,其对应的时间复杂度都是O(1),相比于单链表,双链表的执行效率会更高;
八、双链表的删除
如果我想删除双链表中的某个结点时,我们只需要按照以下步骤就能完成删除操作:
- 将当前结点的前驱结点的后继指针指向当前结点的后继结点;
- 将当前结点的后继结点的前驱指针指向当前结点的前驱结点;
- 释放当前结点的空间;
将其转换成C语言则是:
//双链表的删除操作
DNode->prior->next = DNode->next;//将前驱结点的后继指针指向后继结点
DNode->next->prior = DNode->prior;//将后继结点的前驱指针指向前驱结点
free(DNode);//释放当前结点的内存空间
如果是删除的结点为表尾结点,则我们只需要将表尾结点的前驱结点指向空指针,然后直接释放表尾结点的空间就行,转换成C语言则是如下所示:
//删除表尾结点
DNode->prior->next = NULL;//表尾结点的前驱结点的后继指针指向空指针
DNode->prior->next = DNode->next;//前驱结点的后继指针,指向后继结点,即空指针
free(DNode);//释放表尾结点的内存空间
删除表尾结点时,第一句代码与第二句代码都是可以使用的,效果都一样,二者选其一就行。下面我们将删除操作封装成一个函数的话,则对应的格式如下所示:
//双链表的删除操作
bool DeleteDNode(DNode* p)
{
assert(p);//指针p为空指针时报错
DNode* q = p->prior;//p的前驱结点
assert(q);//当q为空指针时报错
DNode* r = p->next;//p的后继结点
if (r)//后继结点不为空指针时
{
q->next = r;//前驱结点指向后继结点
r->prior = q;//后继结点指向前驱结点
free(p);//释放结点p的内存
}
else
{
q->next = r;//前驱结点指向后继结点,即空指针
free(p);//释放结点p的内存
}
return true;//完成删除操作后返回true
}
当对结点进行前删或者后删时,也是相同的逻辑,这不过在这个基础上做一点小小的变动,这里我就不展开介绍了。当我们相对整个双链表进行删除时,我们只需要重复删除表尾结点的操作即可,大家有兴趣的话可以自己尝试着编写一下;
结语
双链表的内容到这里咱们就全部介绍完了,在今天的篇章中,咱们详细介绍了双链表的创建、初始化、查找、插入、删除等基本操作,并给大家附上了对应操作的代码。希望今天的内容能够帮助大家更好的理解双链表及其基本操作。
在下一篇内容中,咱们将介绍循环链表以及静态链表的相关内容,大家记得关注哦!!!最后感谢各位的翻阅,咱们下一篇再见!
推荐阅读
-
用C语言详解图的拓扑排序算法实现与栈操作深度解析
-
用C语言实现GB2312与UTF-8编码间的相互转换操作
-
SSM三大框架基础面试题-一、Spring篇 什么是Spring框架? Spring是一种轻量级框架,提高开发人员的开发效率以及系统的可维护性。 我们一般说的Spring框架就是Spring Framework,它是很多模块的集合,使用这些模块可以很方便地协助我们进行开发。这些模块是核心容器、数据访问/集成、Web、AOP(面向切面编程)、工具、消息和测试模块。比如Core Container中的Core组件是Spring所有组件的核心,Beans组件和Context组件是实现IOC和DI的基础,AOP组件用来实现面向切面编程。 Spring的6个特征: 核心技术:依赖注入(DI),AOP,事件(Events),资源,i18n,验证,数据绑定,类型转换,SpEL。 测试:模拟对象,TestContext框架,Spring MVC测试,WebTestClient。 数据访问:事务,DAO支持,JDBC,ORM,编组XML。 Web支持:Spring MVC和Spring WebFlux Web框架。 集成:远程处理,JMS,JCA,JMX,电子邮件,任务,调度,缓存。 语言:Kotlin,Groovy,动态语言。 列举一些重要的Spring模块? Spring Core:核心,可以说Spring其他所有的功能都依赖于该类库。主要提供IOC和DI功能。 Spring Aspects:该模块为与AspectJ的集成提供支持。 Spring AOP:提供面向切面的编程实现。 Spring JDBC:Java数据库连接。 Spring JMS:Java消息服务。 Spring ORM:用于支持Hibernate等ORM工具。 Spring Web:为创建Web应用程序提供支持。 Spring Test:提供了对JUnit和TestNG测试的支持。 谈谈自己对于Spring IOC和AOP的理解 IOC(Inversion Of Controll,控制反转)是一种设计思想: 在程序中手动创建对象的控制权,交由给Spring框架来管理。IOC在其他语言中也有应用,并非Spring特有。IOC容器实际上就是一个Map(key, value),Map中存放的是各种对象。 将对象之间的相互依赖关系交给IOC容器来管理,并由IOC容器完成对象的注入。这样可以很大程度上简化应用的开发,把应用从复杂的依赖关系中解放出来。IOC容器就像是一个工厂一样,当我们需要创建一个对象的时候,只需要配置好配置文件/注解即可,完全不用考虑对象是如何被创建出来的。在实际项目中一个Service类可能由几百甚至上千个类作为它的底层,假如我们需要实例化这个Service,可能要每次都搞清楚这个Service所有底层类的构造函数,这可能会把人逼疯。如果利用IOC的话,你只需要配置好,然后在需要的地方引用就行了,大大增加了项目的可维护性且降低了开发难度。 Spring中的bean的作用域有哪些? 1.singleton:该bean实例为单例 2.prototype:每次请求都会创建一个新的bean实例(多例)。 3.request:每一次HTTP请求都会产生一个新的bean,该bean仅在当前HTTP request内有效。 4.session:每一次HTTP请求都会产生一个新的bean,该bean仅在当前HTTP session内有效。 5.global-session:全局session作用域,仅仅在基于Portlet的Web应用中才有意义,Spring5中已经没有了。Portlet是能够生成语义代码(例如HTML)片段的小型Java Web插件。它们基于Portlet容器,可以像Servlet一样处理HTTP请求。但是与Servlet不同,每个Portlet都有不同的会话。 Spring中的单例bean的线程安全问题了解吗? 概念用于理解:大部分时候我们并没有在系统中使用多线程,所以很少有人会关注这个问题。单例bean存在线程问题,主要是因为当多个线程操作同一个对象的时候,对这个对象的非静态成员变量的写操作会存在线程安全问题。 有两种常见的解决方案(用于回答的点): 1.在bean对象中尽量避免定义可变的成员变量(不太现实)。 2.在类中定义一个ThreadLocal成员变量,将需要的可变成员变量保存在ThreadLocal(线程本地化对象)中(推荐的一种方式)。 ThreadLocal解决多线程变量共享问题(参考博客):https://segmentfault.com/a/1190000009236777 Spring中Bean的生命周期: 1.Bean容器找到配置文件中Spring Bean的定义。 2.Bean容器利用Java Reflection API创建一个Bean的实例。 3.如果涉及到一些属性值,利用set方法设置一些属性值。 4.如果Bean实现了BeanNameAware接口,调用setBeanName方法,传入Bean的名字。 5.如果Bean实现了BeanClassLoaderAware接口,调用setBeanClassLoader方法,传入ClassLoader对象的实例。 6.如果Bean实现了BeanFactoryAware接口,调用setBeanClassFacotory方法,传入ClassLoader对象的实例。 7.与上面的类似,如果实现了其他*Aware接口,就调用相应的方法。 8.如果有和加载这个Bean的Spring容器相关的BeanPostProcessor对象,执postProcessBeforeInitialization方法。 9.如果Bean实现了InitializingBean接口,执行afeterPropertiesSet方法。 10.如果Bean在配置文件中的定义包含init-method属性,执行指定的方法。 11.如果有和加载这个Bean的Spring容器相关的BeanPostProcess对象,执行postProcessAfterInitialization方法。 12.当要销毁Bean的时候,如果Bean实现了DisposableBean接口,执行destroy方法。 13.当要销毁Bean的时候,如果Bean在配置文件中的定义包含destroy-method属性,执行指定的方法。 Spring框架中用到了哪些设计模式? 1.工厂设计模式:Spring使用工厂模式通过BeanFactory和ApplicationContext创建bean对象。 2.代理设计模式:Spring AOP功能的实现。 3.单例设计模式:Spring中的bean默认都是单例的。 4.模板方法模式:Spring中的jdbcTemplate、hibernateTemplate等以Template结尾的对数据库操作的类,它们就使用到了模板模式。 5.包装器设计模式:我们的项目需要连接多个数据库,而且不同的客户在每次访问中根据需要会去访问不同的数据库。这种模式让我们可以根据客户的需求能够动态切换不同的数据源。 6.观察者模式:Spring事件驱动模型就是观察者模式很经典的一个应用。 7.适配器模式:Spring AOP的增强或通知(Advice)使用到了适配器模式、Spring MVC中也是用到了适配器模式适配Controller。 还有很多。。。。。。。 @Component和@Bean的区别是什么 1.作用对象不同。@Component注解作用于类,而@Bean注解作用于方法。 2.@Component注解通常是通过类路径扫描来自动侦测以及自动装配到Spring容器中(我们可以使用@ComponentScan注解定义要扫描的路径)。@Bean注解通常是在标有该注解的方法中定义产生这个bean,告诉Spring这是某个类的实例,当我需要用它的时候还给我。 3.@Bean注解比@Component注解的自定义性更强,而且很多地方只能通过@Bean注解来注册bean。比如当引用第三方库的类需要装配到Spring容器的时候,就只能通过@Bean注解来实现。 @Configuration public class AppConfig { @Bean public TransferService transferService { return new TransferServiceImpl; } } <beans> <bean id="transferService" class="com.kk.TransferServiceImpl"/> </beans> @Bean public OneService getService(status) { case (status) { when 1: return new serviceImpl1; when 2: return new serviceImpl2; when 3: return new serviceImpl3; } } 将一个类声明为Spring的bean的注解有哪些? 声明bean的注解: @Component 组件,没有明确的角色 @Service 在业务逻辑层使用(service层) @Repository 在数据访问层使用(dao层) @Controller 在展现层使用,控制器的声明 注入bean的注解: @Autowired:由Spring提供 @Inject:由JSR-330提供 @Resource:由JSR-250提供 *扩:JSR 是 java 规范标准 Spring事务管理的方式有几种? 1.编程式事务:在代码中硬编码(不推荐使用)。 2.声明式事务:在配置文件中配置(推荐使用),分为基于XML的声明式事务和基于注解的声明式事务。 Spring事务中的隔离级别有哪几种? 在TransactionDefinition接口中定义了五个表示隔离级别的常量:ISOLATION_DEFAULT:使用后端数据库默认的隔离级别,Mysql默认采用的REPEATABLE_READ隔离级别;Oracle默认采用的READ_COMMITTED隔离级别。ISOLATION_READ_UNCOMMITTED:最低的隔离级别,允许读取尚未提交的数据变更,可能会导致脏读、幻读或不可重复读。ISOLATION_READ_COMMITTED:允许读取并发事务已经提交的数据,可以阻止脏读,但是幻读或不可重复读仍有可能发生ISOLATION_REPEATABLE_READ:对同一字段的多次读取结果都是一致的,除非数据是被本身事务自己所修改,可以阻止脏读和不可重复读,但幻读仍有可能发生。ISOLATION_SERIALIZABLE:最高的隔离级别,完全服从ACID的隔离级别。所有的事务依次逐个执行,这样事务之间就完全不可能产生干扰,也就是说,该级别可以防止脏读、不可重复读以及幻读。但是这将严重影响程序的性能。通常情况下也不会用到该级别。 Spring事务中有哪几种事务传播行为? 在TransactionDefinition接口中定义了八个表示事务传播行为的常量。 支持当前事务的情况:PROPAGATION_REQUIRED:如果当前存在事务,则加入该事务;如果当前没有事务,则创建一个新的事务。PROPAGATION_SUPPORTS: 如果当前存在事务,则加入该事务;如果当前没有事务,则以非事务的方式继续运行。PROPAGATION_MANDATORY: 如果当前存在事务,则加入该事务;如果当前没有事务,则抛出异常。(mandatory:强制性)。 不支持当前事务的情况:PROPAGATION_REQUIRES_NEW: 创建一个新的事务,如果当前存在事务,则把当前事务挂起。PROPAGATION_NOT_SUPPORTED: 以非事务方式运行,如果当前存在事务,则把当前事务挂起。PROPAGATION_NEVER: 以非事务方式运行,如果当前存在事务,则抛出异常。 其他情况:PROPAGATION_NESTED: 如果当前存在事务,则创建一个事务作为当前事务的嵌套事务来运行;如果当前没有事务,则该取值等价于PROPAGATION_REQUIRED。 二、SpringMVC篇 什么是Spring MVC ?简单介绍下你对springMVC的理解? Spring MVC是一个基于Java的实现了MVC设计模式的请求驱动类型的轻量级Web框架,通过把Model,View,Controller分离,将web层进行职责解耦,把复杂的web应用分成逻辑清晰的几部分,简化开发,减少出错,方便组内开发人员之间的配合。 Spring MVC的工作原理了解嘛? image.png Springmvc的优点: (1)可以支持各种视图技术,而不仅仅局限于JSP; (2)与Spring框架集成(如IoC容器、AOP等); (3)清晰的角色分配:前端控制器(dispatcherServlet) , 请求到处理器映射(handlerMapping), 处理器适配器(HandlerAdapter), 视图解析器(ViewResolver)。 (4) 支持各种请求资源的映射策略。 Spring MVC的主要组件? (1)前端控制器 DispatcherServlet(不需要程序员开发) 作用:接收请求、响应结果,相当于转发器,有了DispatcherServlet 就减少了其它组件之间的耦合度。 (2)处理器映射器HandlerMapping(不需要程序员开发) 作用:根据请求的URL来查找Handler (3)处理器适配器HandlerAdapter 注意:在编写Handler的时候要按照HandlerAdapter要求的规则去编写,这样适配器HandlerAdapter才可以正确的去执行Handler。 (4)处理器Handler(需要程序员开发) (5)视图解析器 ViewResolver(不需要程序员开发) 作用:进行视图的解析,根据视图逻辑名解析成真正的视图(view) (6)视图View(需要程序员开发jsp) View是一个接口, 它的实现类支持不同的视图类型(jsp,freemarker,pdf等等) springMVC和struts2的区别有哪些? (1)springmvc的入口是一个servlet即前端控制器(DispatchServlet),而struts2入口是一个filter过虑器(StrutsPrepareAndExecuteFilter)。 (2)springmvc是基于方法开发(一个url对应一个方法),请求参数传递到方法的形参,可以设计为单例或多例(建议单例),struts2是基于类开发,传递参数是通过类的属性,只能设计为多例。 (3)Struts采用值栈存储请求和响应的数据,通过OGNL存取数据,springmvc通过参数解析器是将request请求内容解析,并给方法形参赋值,将数据和视图封装成ModelAndView对象,最后又将ModelAndView中的模型数据通过reques域传输到页面。Jsp视图解析器默认使用jstl。 SpringMVC怎么样设定重定向和转发的? (1)转发:在返回值前面加"forward:",譬如"forward:user.do?name=method4" (2)重定向:在返回值前面加"redirect:",譬如"redirect:http://www.baidu.com" SpringMvc怎么和AJAX相互调用的? 通过Jackson框架就可以把Java里面的对象直接转化成Js可以识别的Json对象。具体步骤如下 : (1)加入Jackson.jar (2)在配置文件中配置json的映射 (3)在接受Ajax方法里面可以直接返回Object,List等,但方法前面要加上@ResponseBody注解。 如何解决POST请求中文乱码问题,GET的又如何处理呢? (1)解决post请求乱码问题: 在web.xml中配置一个CharacterEncodingFilter过滤器,设置成utf-8; <filter> <filter-name>CharacterEncodingFilter</filter-name> <filter-class>org.springframework.web.filter.CharacterEncodingFilter</filter-class> <init-param> <param-name>encoding</param-name> <param-value>utf-8</param-value> </init-param> </filter> <filter-mapping> <filter-name>CharacterEncodingFilter</filter-name> <url-pattern>/*</url-pattern> </filter-mapping> (2)get请求中文参数出现乱码解决方法有两个: ①修改tomcat配置文件添加编码与工程编码一致,如下: <ConnectorURIEncoding="utf-8" connectionTimeout="20000" port="8080" protocol="HTTP/1.1" redirectPort="8443"/> ②另外一种方法对参数进行重新编码: String userName = new String(request.getParamter("userName").getBytes("ISO8859-1"),"utf-8") ISO8859-1是tomcat默认编码,需要将tomcat编码后的内容按utf-8编码。 Spring MVC的异常处理 ? 统一异常处理: Spring MVC处理异常有3种方式: (1)使用Spring MVC提供的简单异常处理器SimpleMappingExceptionResolver; (2)实现Spring的异常处理接口HandlerExceptionResolver 自定义自己的异常处理器; (3)使用@ExceptionHandler注解实现异常处理; 统一异常处理的博客:https://blog.csdn.net/ctwy291314/article/details/81983103 SpringMVC的控制器是不是单例模式,如果是,有什么问题,怎么解决? 是单例模式,所以在多线程访问的时候有线程安全问题,不要用同步,会影响性能的,解决方案是在控制器里面不能写成员变量。(此题目类似于上面Spring 中 第5题 有两种解决方案) SpringMVC常用的注解有哪些? @RequestMapping:用于处理请求 url 映射的注解,可用于类或方法上。用于类上,则表示类中的所有响应请求的方法都是以该地址作为父路径。 @RequestBody:注解实现接收http请求的json数据,将json转换为java对象。 @ResponseBody:注解实现将conreoller方法返回对象转化为json对象响应给客户。 SpingMvc中的控制器的注解一般用那个,有没有别的注解可以替代? 一般用@Controller注解,也可以使用@RestController,@RestController注解相当于@ResponseBody + @Controller,表示是表现层,除此之外,一般不用别的注解代替。 如果在拦截请求中,我想拦截get方式提交的方法,怎么配置? 可以在@RequestMapping注解里面加上method=RequestMethod.GET。 怎样在方法里面得到Request,或者Session? 直接在方法的形参中声明request,SpringMVC就自动把request对象传入。 如果想在拦截的方法里面得到从前台传入的参数,怎么得到? 直接在形参里面声明这个参数就可以,但必须名字和传过来的参数一样。 如果前台有很多个参数传入,并且这些参数都是一个对象的,那么怎么样快速得到这个对象? 直接在方法中声明这个对象,SpringMVC就自动会把属性赋值到这个对象里面。 SpringMVC中函数的返回值是什么? 返回值可以有很多类型,有String, ModelAndView。ModelAndView类把视图和数据都合并的一起的。 SpringMVC用什么对象从后台向前台传递数据的? 通过ModelMap对象,可以在这个对象里面调用put方法,把对象加到里面,前台就可以拿到数据。 怎么样把ModelMap里面的数据放入Session里面? 可以在类上面加上@SessionAttributes注解,里面包含的字符串就是要放入session里面的key。 SpringMvc里面拦截器是怎么写的: 有两种写法,一种是实现HandlerInterceptor接口,另外一种是继承适配器类,接着在接口方法当中,实现处理逻辑;然后在SpringMvc的配置文件中配置拦截器即可: <!-- 配置SpringMvc的拦截器 --> <mvc:interceptors> <!-- 配置一个拦截器的Bean就可以了 默认是对所有请求都拦截 --> <bean id="myInterceptor" class="com.zwp.action.MyHandlerInterceptor"></bean> <!-- 只针对部分请求拦截 --> <mvc:interceptor> <mvc:mapping path="/modelMap.do" /> <bean class="com.zwp.action.MyHandlerInterceptorAdapter" /> </mvc:interceptor> </mvc:interceptors> 注解原理: 注解本质是一个继承了Annotation的特殊接口,其具体实现类是Java运行时生成的动态代理类。我们通过反射获取注解时,返回的是Java运行时生成的动态代理对象。通过代理对象调用自定义注解的方法,会最终调用AnnotationInvocationHandler的invoke方法。该方法会从memberValues这个Map中索引出对应的值。而memberValues的来源是Java常量池 三、Mybatis篇 什么是MyBatis? MyBatis是一个可以自定义SQL、存储过程和高级映射的持久层框架。 讲下MyBatis的缓存 MyBatis的缓存分为一级缓存和二级缓存,一级缓存放在session里面,默认就有, 二级缓存放在它的命名空间里,默认是不打开的,使用二级缓存属性类需要实现Serializable序列化接口, 可在它的映射文件中配置<cache/> Mybatis是如何进行分页的?分页插件的原理是什么? 1)Mybatis使用RowBounds对象进行分页,也可以直接编写sql实现分页,也可以使用Mybatis的分页插件。 2)分页插件的原理:实现Mybatis提供的接口,实现自定义插件,在插件的拦截方法内拦截待执行的sql,然后重写sql。 举例:select * from student,拦截sql后重写为:select t.* from (select * from student)t limit 0,10 简述Mybatis的插件运行原理,以及如何编写一个插件? 1)Mybatis仅可以编写针对ParameterHandler、ResultSetHandler、StatementHandler、 Executor这4种接口的插件,Mybatis通过动态代理, 为需要拦截的接口生成代理对象以实现接口方法拦截功能, 每当执行这4种接口对象的方法时,就会进入拦截方法, 具体就是InvocationHandler的invoke方法,当然, 只会拦截那些你指定需要拦截的方法。 2)实现Mybatis的Interceptor接口并复写intercept方法, 然后在给插件编写注解,指定要拦截哪一个接口的哪些方法即可, 记住,别忘了在配置文件中配置你编写的插件。 Mybatis动态sql是做什么的?都有哪些动态sql?能简述一下动态sql的执行原理不? 1)Mybatis动态sql可以让我们在Xml映射文件内, 以标签的形式编写动态sql,完成逻辑判断和动态拼接sql的功能。 2)Mybatis提供了9种动态sql标签:trim|where|set|foreach|if|choose|when|otherwise|bind。 3)其执行原理为,使用OGNL从sql参数对象中计算表达式的值, 根据表达式的值动态拼接sql,以此来完成动态sql的功能。 #{}和${}的区别是什么? 1)#{}是预编译处理,${}是字符串替换。 2)Mybatis在处理#{}时,会将sql中的#{}替换为?号,调用PreparedStatement的set方法来赋值(有效的防止SQL注入); 3)Mybatis在处理${}时,就是把${}替换成变量的值。 为什么说Mybatis是半自动ORM映射工具?它与全自动的区别在哪里? Hibernate属于全自动ORM映射工具, 使用Hibernate查询关联对象或者关联集合对象时, 可以根据对象关系模型直接获取,所以它是全自动的。 而Mybatis在查询关联对象或关联集合对象时, 需要手动编写sql来完成,所以,称之为半自动ORM映射工具。 Mybatis是否支持延迟加载?如果支持,它的实现原理是什么? 1)Mybatis仅支持association关联对象和collection关联集合对象的延迟加载, association指的就是一对一,collection指的就是一对多查询。 在Mybatis配置文件中, 可以配置是否启用延迟加载lazyLoadingEnabled=true|false。 2)它的原理是,使用CGLIB创建目标对象的代理对象, 当调用目标方法时,进入拦截器方法, 比如调用a.getB.getName, 拦截器invoke方法发现a.getB是null值, 那么就会单独发送事先保存好的查询关联B对象的sql, 把B查询上来,然后调用a.setB(b), 于是a的对象b属性就有值了, 接着完成a.getB.getName方法的调用。 这就是延迟加载的基本原理。 MyBatis与Hibernate有哪些不同? 1)Mybatis和hibernate不同,它不完全是一个ORM框架, 因为MyBatis需要程序员自己编写Sql语句, 不过mybatis可以通过XML或注解方式灵活配置要运行的sql语句, 并将java对象和sql语句映射生成最终执行的sql, 最后将sql执行的结果再映射生成java对象。 2)Mybatis学习门槛低,简单易学,程序员直接编写原生态sql, 可严格控制sql执行性能,灵活度高,非常适合对关系数据模型要求不高的软件开发, 例如互联网软件、企业运营类软件等,因为这类软件需求变化频繁, 一但需求变化要求成果输出迅速。但是灵活的前提是mybatis无法做到数据库无关性, 如果需要实现支持多种数据库的软件则需要自定义多套sql映射文件,工作量大。 3)Hibernate对象/关系映射能力强,数据库无关性好, 对于关系模型要求高的软件(例如需求固定的定制化软件) 如果用hibernate开发可以节省很多代码,提高效率。 但是Hibernate的缺点是学习门槛高,要精通门槛更高, 而且怎么设计O/R映射,在性能和对象模型之间如何权衡, 以及怎样用好Hibernate需要具有很强的经验和能力才行。 总之,按照用户的需求在有限的资源环境下只要能做出维护性、 扩展性良好的软件架构都是好架构,所以框架只有适合才是最好。 MyBatis的好处是什么? 1)MyBatis把sql语句从Java源程序中独立出来,放在单独的XML文件中编写, 给程序的维护带来了很大便利。 2)MyBatis封装了底层JDBC API的调用细节,并能自动将结果集转换成Java Bean对象, 大大简化了Java数据库编程的重复工作。 3)因为MyBatis需要程序员自己去编写sql语句, 程序员可以结合数据库自身的特点灵活控制sql语句, 因此能够实现比Hibernate等全自动orm框架更高的查询效率,能够完成复杂查询。 简述Mybatis的Xml映射文件和Mybatis内部数据结构之间的映射关系? Mybatis将所有Xml配置信息都封装到All-In-One重量级对象Configuration内部。 在Xml映射文件中,<parameterMap>标签会被解析为ParameterMap对象, 其每个子元素会被解析为ParameterMapping对象。 <resultMap>标签会被解析为ResultMap对象, 其每个子元素会被解析为ResultMapping对象。 每一个<select>、<insert>、<update>、<delete> 标签均会被解析为MappedStatement对象, 标签内的sql会被解析为BoundSql对象。 什么是MyBatis的接口绑定,有什么好处? 接口映射就是在MyBatis中任意定义接口,然后把接口里面的方法和SQL语句绑定, 我们直接调用接口方法就可以,这样比起原来了SqlSession提供的方法我们可以有更加灵活的选择和设置. 接口绑定有几种实现方式,分别是怎么实现的? 接口绑定有两种实现方式,一种是通过注解绑定,就是在接口的方法上面加 上@Select@Update等注解里面包含Sql语句来绑定, 另外一种就是通过xml里面写SQL来绑定,在这种情况下, 要指定xml映射文件里面的namespace必须为接口的全路径名. 什么情况下用注解绑定,什么情况下用xml绑定? 当Sql语句比较简单时候,用注解绑定;当SQL语句比较复杂时候,用xml绑定,一般用xml绑定的比较多 MyBatis实现一对一有几种方式?具体怎么操作的? 有联合查询和嵌套查询,联合查询是几个表联合查询,只查询一次, 通过在resultMap里面配置association节点配置一对一的类就可以完成; 嵌套查询是先查一个表,根据这个表里面的结果的外键id, 去再另外一个表里面查询数据,也是通过association配置, 但另外一个表的查询通过select属性配置。 Mybatis能执行一对一、一对多的关联查询吗?都有哪些实现方式,以及它们之间的区别? 能,Mybatis不仅可以执行一对一、一对多的关联查询, 还可以执行多对一,多对多的关联查询,多对一查询, 其实就是一对一查询,只需要把selectOne修改为selectList即可; 多对多查询,其实就是一对多查询,只需要把selectOne修改为selectList即可。 关联对象查询,有两种实现方式,一种是单独发送一个sql去查询关联对象, 赋给主对象,然后返回主对象。另一种是使用嵌套查询,嵌套查询的含义为使用join查询, 一部分列是A对象的属性值,另外一部分列是关联对象B的属性值, 好处是只发一个sql查询,就可以把主对象和其关联对象查出来。 MyBatis里面的动态Sql是怎么设定的?用什么语法? MyBatis里面的动态Sql一般是通过if节点来实现,通过OGNL语法来实现, 但是如果要写的完整,必须配合where,trim节点,where节点是判断包含节点有 内容就插入where,否则不插入,trim节点是用来判断如果动态语句是以and 或or 开始,那么会自动把这个and或者or取掉。 Mybatis是如何将sql执行结果封装为目标对象并返回的?都有哪些映射形式? 第一种是使用<resultMap>标签,逐一定义列名和对象属性名之间的映射关系。 第二种是使用sql列的别名功能,将列别名书写为对象属性名, 比如T_NAME AS NAME,对象属性名一般是name,小写, 但是列名不区分大小写,Mybatis会忽略列名大小写,
-
数据结构:双链表的 C 语言实现 - I. 链表的分类
-
go语言Socket编程-Socket编程 什么是Socket Socket,英文含义是插座、插孔,一般称之为套接字,用于描述IP地址和端口。可以实现不同程序间的数据通信。 Socket起源于Unix,而Unix基本哲学之一就是“一切皆文件”,都可以用“打开open –> 读写write/read –> 关闭close”模式来操作。Socket就是该模式的一个实现,网络的Socket数据传输是一种特殊的I/O,Socket也是一种文件描述符。Socket也具有一个类似于打开文件的函数调用:Socket,该函数返回一个整型的Socket描述符,随后的连接建立、数据传输等操作都是通过该Socket实现的。 套接字的内核实现较为复杂,不宜在学习初期深入学习,了解到如下结构足矣。 套接字通讯原理示意 在TCP/IP协议中,“IP地址+TCP或UDP端口号”唯一标识网络通讯中的一个进程。“IP地址+端口号”就对应一个socket。欲建立连接的两个进程各自有一个socket来标识,那么这两个socket组成的socket pair就唯一标识一个连接。因此可以用Socket来描述网络连接的一对一关系。 常用的Socket类型有两种:流式Socket(SOCK_STREAM)和数据报式Socket(SOCK_DGRAM)。流式是一种面向连接的Socket,针对于面向连接的TCP服务应用;数据报式Socket是一种无连接的Socket,对应于无连接的UDP服务应用。 网络应用程序设计模式 C/S模式 传统的网络应用设计模式,客户机(client)/服务器(server)模式。需要在通讯两端各自部署客户机和服务器来完成数据通信。 B/S模式 浏览器(Browser)/服务器(Server)模式。只需在一端部署服务器,而另外一端使用每台PC都默认配置的浏览器即可完成数据的传输。 优缺点 对于C/S模式来说,其优点明显。客户端位于目标主机上可以保证性能,将数据缓存至客户端本地,从而提高数据传输效率。且,一般来说客户端和服务器程序由一个开发团队创作,所以他们之间所采用的协议相对灵活。可以在标准协议的基础上根据需求裁剪及定制。例如,腾讯所采用的通信协议,即为ftp协议的修改剪裁版。 因此,传统的网络应用程序及较大型的网络应用程序都首选C/S模式进行开发。如,知名的网络游戏魔兽世界。3D画面,数据量庞大,使用C/S模式可以提前在本地进行大量数据的缓存处理,从而提高观感。 C/S模式的缺点也较突出。由于客户端和服务器都需要有一个开发团队来完成开发。工作量将成倍提升,开发周期较长。另外,从用户角度出发,需要将客户端安插至用户主机上,对用户主机的安全性构成威胁。这也是很多用户不愿使用C/S模式应用程序的重要原因。 B/S模式相比C/S模式而言,由于它没有独立的客户端,使用标准浏览器作为客户端,其工作开发量较小。只需开发服务器端即可。另外由于其采用浏览器显示数据,因此移植性非常好,不受平台限制。如早期的偷菜游戏,在各个平台上都可以完美运行。 B/S模式的缺点也较明显。由于使用第三方浏览器,因此网络应用支持受限。另外,没有客户端放到对方主机上,缓存数据不尽如人意,从而传输数据量受到限制。应用的观感大打折扣。第三,必须与浏览器一样,采用标准http协议进行通信,协议选择不灵活。 因此在开发过程中,模式的选择由上述各自的特点决定。根据实际需求选择应用程序设计模式。 简单的C/S模型通信 Server端:Listen函数 func Listen(network, address string) (Listener, error) network:选用的协议:TCP、UDP, 如:“tcp”或 “udp” address:IP地址+端口号, 如:“127.0.0.1:8000”或 “:8000” Listener 接口: type Listener interface { Accept (Conn, error) Close error Addr Addr } Conn 接口: type Conn interface { Read(b byte) (n int, err error) Write(b byte) (n int, err error) Close error LocalAddr Addr RemoteAddr Addr SetDeadline(t time.Time) error SetReadDeadline(t time.Time) error SetWriteDeadline(t time.Time) error } 参看 [<u>https://studygolang.com/pkgdoc</u>](https://studygolang.com/pkgdoc) 中文帮助文档中的demo: 示例代码:TCP服务器.go package main import ( "net" "fmt" ) func main { // 创建监听 listener, err:= net.Listen("tcp", ":8000") if err != nil { fmt.Println("listen err:", err) return } defer listener.Close // 主协程结束时,关闭listener fmt.Println("服务器等待客户端建立连接...") // 等待客户端连接请求 conn, err := listener.Accept if err != nil { fmt.Println("accept err:", err) return } defer conn.Close // 使用结束,断开与客户端链接 fmt.Println("客户端与服务器连接建立成功...") // 接收客户端数据 buf := make(byte, 1024) // 创建1024大小的缓冲区,用于read n, err := conn.Read(buf) if err != nil { fmt.Println("read err:", err) return } fmt.Println("服务器读到:", string(buf[:n])) // 读多少,打印多少。 }
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
数据结构]用 C 语言实现双链表的基本操作
-
数据结构]带头的双向循环链表的 C 语言实现
-
数据结构]单链表基本操作的 C 语言实现
-
C 语言中链表的基本操作(表头插入及其逆操作)