【开卷数据结构 】链表

作者简介:大家好,我是锡兰Ceylan_,可以叫我CC ❣️    
个人主页:锡兰Ceylan_的博客
博主信息:平凡的大一学生,有着不平凡的梦

        专栏

  • 【备战蓝桥,冲击省一】
  • 【开卷数据结构】

⚡希望大家多多支持一起进步~❤️
若有帮助,还请关注点赞收藏,不行的话我再努努力​

目录

链表的定义

链表的存储方式

单链表的初始化

头插法建立单链表

尾插法建立单链表

按序号寻找结点值

按值寻找结点

插入结点

删除结点


链表的定义

线性表的链式存储又称为单链表,其特点是用一组任意的存储单元来存储线性表的数据元素。

为了表示每个数据元素ai与其后续数据元素ai+1之间的逻辑关系,a1除了存储自身的信息之外,还需要存储一个指向其后续内容的信息(一般为后续内容的地址)。这两部分信息组成数据元素ai的存储映像,称为结点。

【开卷数据结构 】链表_第1张图片

单链表中结点类型的描述如下:

typedef struct LNode		//定义单链表结点类型 
{
	ElemType data;			//数据元素 
	struct LNode *next;		//指向下一地址 
}LNode, *LinkList;

链表的存储方式

整个链表的存取必须从头指针开始进行,头指针指向链表的第一个结点的存储位置。同时由于最后一个元素没有直接后继,则单链表的最后一个结点的指针为空(NULL)

我们来想一想,如果用链表来存储【Ceylan】,它的逻辑状态是什么样的呢?

首先应该需要一个头指针L,它指向第一个元素 'C',通过 'C' 所在结点的信息,可以访问下一节点 'e' 所在位置,以此类推,就可以完整找到整个【Ceylan

【开卷数据结构 】链表_第2张图片

单链表的初始化

单链表的初始化就是建立一个新的空的单链表

实现原理

1️⃣生成新结点作为头结点,用头指针L指向头结点

2️⃣头结点指向空

代码演示

Status InilList(LinkList &L)
{//构建一个空的链表L 
	L=new LNode;		//生成新结点作为头结点,用头指针L指向头结点 
	L->next=NULL;		//头结点指向空 
	return OK; 
}

头插法建立单链表

实现原理

1️⃣建立一个空表,生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的表头,也就是头结点之后

【开卷数据结构 】链表_第3张图片

  代码演示

void CreateList_H(LinkList &L,int n)
{
	L=new LNode;	
	L->next=NULL;			        //先建立一个带头结点的空链表 
	for(int i=0;i>p->data;				//输入p结点的数据 
		p->next=L->next;L->next=p;	//将新结点*p插入到头结点之后 	
	}
} 

❗️注意:

因为每次插入都是在链表头部,所以应该逆位序输入数据。输入顺序和线性表中的逻辑顺序是相反的

尾插法建立单链表

实现原理

1️⃣建立一个空表,生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的尾部

【开卷数据结构 】链表_第4张图片 代码演示

void CreateList_R(LinkList &L,int n)
{
	L=new LNode;	//先建立一个带头结点的空链表 
	r=L;			//尾指针指向头结点 
	for(int i=0;i>p->data;				//输入p结点的数据 
		p->next=NULL;r->next=p;		//将新结点*p插入尾结点*r之后 	
		r=p 
	}
} 

按序号寻找结点值

实现原理

1️⃣从第一个结点开始,顺指针next逐个向下搜索,直到找到第  i  个结点,

2️⃣若没有找到,返回最后一个指针域NULL

代码演示

LNode *GetElem(LinkList L,int i)
{
	int j=1;				//计数,初始为1 
	LNode *p=L->next;		//头结点指针赋值给p 
	if(i==0)
		return L;			//若i为 0,返回头指针 
	if(i<1)
		return NULL;		//若i无效,则返回 NULL 
	while(p&&jnext;
		j++;
	}
	return p;				//返回第 i 个结点的指针 
} 

按值寻找结点

实现原理

1️⃣从第一个结点开始,顺指针next逐个向下搜索数值,直到找到符合的数值

2️⃣若没有找到,返回最后一个指针域NULL

代码演示

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

插入结点

将值为 x 的新结点插到单链表的第 i 个位置。

实现原理

1️⃣调用按序号查找函数,查找第i-1个结点,假设返回结点为*p

2️⃣令新结点*s的指针域指向*p的后续结点

3️⃣令结点*p的指针域指向新的插入的结点*s

  代码演示

p=GetElem(L,i-1)		//查找插入位置的前驱结点 
s->next=p->next;		//新结点*s的指针域指向*p的后续结点
p->next=s;				//令结点*p的指针域指向新的插入的结点*s

删除结点

将单链表的第 i 个结点删除。

实现原理

1️⃣调用按序号查找函数,查找第 i 个结点,假设返回结点为*p

2️⃣将*p指针域next指向下下位结点

【开卷数据结构 】链表_第5张图片

p=GetElem(L,i-1)		//查找删除位置的前驱结点 
q=p->next;				//令q指向被删除结点 
p->next=q->next;		//将*q结点从链中断开 
free(q);				//释放结点的存储空间 

结束语

 本人不才,如有错误,欢迎各位大佬在评论区指正。有帮助的话还请【关注点赞收藏】,不行的话我再努努力

你可能感兴趣的