我们不废话,直入正题。
引入
什么是链表?
来看看百度怎么说:
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
可以发现:
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
这些,就是链表的特性。
这就是链表的概念图。Blue、Yellow、Red 这 3 个字符串作为数据被存储于链表的数据域中。每个数据都有 1 个 “指针”,它指向下一个数据的内存地址,这被称为指针域。
了解完概念,我们就要来看看基本操作了。
一.创建
上面看到:
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
一个结点,可用一个结构体存储(此处表示为Lnode)。
数据域就很简单,我们通常用再搞一个结构体来存储。
而指针呢?
在链表的创建中,我们需要添加一个指向下一个节点的指针,这个指针保存的是下一个节点的地址。
那么指针的类型是什么呢?当然是Lnode了,因为指针指向的,是下一个结点。
下面引入一段话来帮助理解:
将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。
那么,就可以实现了。
struct Lnode{
ElemType data;//数据域
struct Node *next;//指针域
};
二.初始化
说是初始化,实际上是在创建结点。那么,只需开辟一个类型为Lnode的空间即可。
如何开辟空间?
我们需要一个new。
new是什么?
new其实就是计算机开辟一段新的空间,但是和一般的声明不同的是,new开辟的空间在堆上,而一般声明的变量存放在栈上。通常来说,当在局部函数中new出一段新的空间,该段空间在局部函数调用结束后仍然能够使用,可以用来向主函数传递参数。另外需要注意的是,new的使用格式,new出来的是一段空间的首地址。所以一般需要用指针来存放这段地址。
————————————————
版权声明:本内容为CSDN博主「柒笙歌」的原创
原文链接: C++之new的详解_new c++_柒笙歌的博客-CSDN博客
算了,不乱说了,自己搜搜看吧!然后,接着来。
真正的初始化
不过,这个结点后面还没有其它的结点,因此其指针域的指向应该是空的。
这里,我们用NULL表示。
NULL是什么?
Null是在计算中具有保留的值,用于指示 指针不引用有效对象。
这句话很显然的点明了。
在C++中,NULL可以直接赋值给指针。因此就很简单了!
代码实现
void InitList(Lnode* &L)//初始化
{
L=new Lnode;
L->next=NULL;
}
三.判断是否为空链表
首先,我们要知道,什么是空链表?
空链表:链表中无元素。(头指针和头结点仍在)
也就是说,头结点的指针域的指向为空
那么,就非常简单了。
bool check(Lnode* L)//判断是否为空
{
if(L->next==NULL) return 0;//空
return 1;
}
四.清空链表(不留头结点)
用一个L表示当前头结点,用p表示当前节点。
每次就将p转到L的下一个,然后释放L,在将L变为p。以此不断循环,直到p为空。
代码如下:
void xiaohui(linklist &L)//全部删掉 (不留头结点)
{
Lnode *p;//linklist L
while(p)
{
L=p;
p=p->next;
free(L);
}
}
五.变成空表(留头结点)
这与上面的只有一个区别。题目写得很清楚:留头结点。
那么我们只用q替代L,帮p探路。那么,在p为NULL时,我们还可知道原来的头结点的指针——就是L
好,上代码:
void qk(linklist &L)//变成空表(留头结点)
{
Lnode *p,*q;//linklist L
q=L->next;
while(p)
{
p=q;
q=q->next;
free(p);
}
L->next=NULL;
}
五.查找、访问
相对于数组,链表的数据是分散储存于数组的随机位置的。
因为数据都是分散存储的,所以如果想要访问 数据,只能从第1个数据开始,顺着指针的指 向一一往下访问(这便是顺序访问)。比如,想 要找到Red这一数据,就得从Blue开始访问。
这之后,还要经过 Yellow,我们才能找到 Red。
也比较基础,上代码!
int cz(linklist L,char mz[])//查找
{
Lnode *p=L->next;
while(p)
{
if(strcmp(mz,p->data.name)==0) break;
p=p->next;
}
if(!p)
{
return 0;
}
return 1;
}
六.添加
如果想要添加数据,只需要改变添加位置前后 的指针指向就可以,非常简单。比如,在Blue 和Yellow之间添加Green。
将 Blue 的指针指向的位置变成 Green,然后再 把Green的指针指向Yellow,数据的添加就大功告成了。
代码如下:
int cr(linklist &L,int x,ElemType e)//插入
{
int i=0;
Lnode *p=L;
while(p&&i<x-1)
{
p=p->next;
i++;
}
Lnode *s=new Lnode;
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
七.删除
数据的删除也一样,只要改变指针的指向就可 以,比如删除Yellow。
这时,只需要把 Green 指针指向的位置从 Yellow 变成 Red,删除就完成了。但是, Yellow 本身还存储在 内存中,需要把它释放掉(可以用free数组)
看代码:文章来源:https://www.toymoban.com/news/detail-418113.html
int cr(linklist &L,int x,ElemType &e)//删除第x个节点,并返回删除值
{
int i=1;
Lnode *p=L->next,*t;
while(p&&i<x-1)
{
p=p->next;
i++;
}
t=p->next;
p->next=p->next->next;
free(t);
return 1;
}
基本操作汇总
#include<bits/stdc++.h>
using namespace std;
typedef struct student{
char name[8];
int num;
int cj;
}ElemType;
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode,*linklist;
void InitList(linklist &L)//初始化
{
L=new Lnode;
L->next=NULL;
}
bool check(linklist L)//判断是否为空
{
if(L->next==NULL) return 0;//空
return 1;
}
void xiaohui(linklist &L)//全部删掉
{
Lnode *p;//linklist L
while(p)
{
L=p;
p=p->next;
free(L);
}
}
void qk(linklist &L)//变成空表(留头结点)
{
Lnode *p,*q;//linklist L
q=L->next;
while(p)
{
p=q;
q=q->next;
free(p);
}
L->next=NULL;
}
int bc(linklist &L)//链表的长度
{
int s=0;
Lnode *p;
p=L->next;
while(p)
{
s++;
p=p->next;
}
return s;
}
int qz(linklist &L,int x,ElemType &a)//取第x个的值
{
int i=1;
Lnode *p=L->next;
while(p&&i<x)
{
p=p->next;
i++;
}
if(!p)
{
return 0;
}
a=p->data;
return 1;
}
int cz(linklist L,char mz[])//查找
{
Lnode *p=L->next;
while(p)
{
if(strcmp(mz,p->data.name)==0) break;
p=p->next;
}
if(!p)
{
return 0;
}
return 1;
}
int cr(linklist &L,int x,ElemType e)//插入
{
int i=0;
Lnode *p=L;
while(p&&i<x-1)
{
p=p->next;
i++;
}
Lnode *s=new Lnode;
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
int cr(linklist &L,int x,ElemType &e)//删除第x个节点,并返回删除值
{
int i=1;
Lnode *p=L->next,*t;
while(p&&i<x-1)
{
p=p->next;
i++;
}
t=p->next;
p->next=p->next->next;
free(t);
return 1;
}
int tc(int n,linklist &L)//建立头插法
{
Lnode *p;
for(int i=1;i<=n;i++)
{
p=new Lnode;
//cin>>p->data;
p->next=L->next;
L->next=p;
}
}
int tc(int n,linklist &L)//建立尾插法
{
Lnode *p,*r=L;
for(int i=1;i<=n;i++)
{
p=new Lnode;
p->next=NULL;
//cin>>p->data;
r->next=p;
r=p;
}
}
int main()
{
}
最后
因为太懒了,就拖了很久,今天开网,终于发布了,麻烦来个三连,谢谢!文章来源地址https://www.toymoban.com/news/detail-418113.html
到了这里,关于【数据结构】链表 详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!