目录
1.什么是链表。
2.链表的优点
3.单链表的实现
1.单链表的结构体
2.节点的创建
3.参数的调用
4.头插
5.尾插
7.头删
8.尾删
8.在pos节点前插入x
9.在pos节点前插入x
10.删除pos位置节点
对于顺序表我们发现,在此基础上仍存在了些许不足:
1.中间或头部的插入时间复杂度为O(n),有点浪费时间。
2.增容需要申请空间,拷贝数据,释放空间,会有不小的消耗。
3.增容一般是呈2倍增容的,势必会造成空间浪费。
如何解决以上问题,我们又了解到了一种新的数据结构-“链表”
1.什么是链表。
链表顾名思义,由一条链子连接表中各成员。实则链表是由每一块独立的空间组成,每一个空间里存放着数据和一个指针,每一个指针指向下一块空间的地址,依次指向,我们可以想象成为用链条串联起类,故叫链表,链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链次序实现的。
就像火车一样
我们一般将这一块空间称为一个节点,链表的末尾节点的指针是空指针。
2.链表的优点
相较于顺序表:
1.因为链表是由一块块空间构成,所以链表不存在容量不够要扩容的问题
2.根据需求申请释放空间
3.较好地解决了在头部或中间插入删除挪动数据的问题
3.单链表的实现
这里还是以存放整形数据为例:
1.单链表的结构体
如何来实现这样的结构呢?
typedef int SLdatatype;
typedef struct seqlist
{
SLdatatype data;
struct seqlist* next;
}SLnode;
可以看到这里的结构体里存放了本结构体的指针,每一个结构体里都有一个自身的指针,而这个自身的指针就代表下一个结构体的首地址,依次下去,直至到末尾next尾空。
用单链表的话来说,就是每一个节点存放着指向下一个节点地址的指针,故此我们可以创建所需的节点个数存放数据,用指针连接起来。
2.节点的创建
SLnode* SLcreatnode(SLdatatype x)
{
SLnode* newnode = (SLnode*)malloc(sizeof(SLnode));
if (newnode == NULL)
{
perror("开辟错误\n");
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
每创建一个节点,就是在堆区申请一块空间用来存放数据,利用malloc开辟该结构体大小的空间,之后返回该节点,也就是这片空间。
3.参数的调用
这里强调下参数,因为我们需要改变链表,定义链表变量的时候是指针,函数的参数应设计为二级指针。
对于一个函数我们在其中定义的变量生命周期只在该作用域中,出了作用域就会被销毁,而有的函数需要去改变实参,只是简单的改变形参,是不会影响实参的,但若为实参的地址,我们可通过解引用形参来改变实参,比如:
int swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int main()
{
int x = 10;
int y = 20;
swap(&x, &y);
printf("%d %d", x, y);
return 0;
}
因此,这里要想通过形参改变实参,参数设计为二级指针:这里以头插为例
4.头插
void SLpushfront(SLnode** p, SLdatatype x)//传参用二级指针
{
SLnode* newnode = SLcreatnode(x);
newnode->next = *p;
*p = newnode;
}
可以看到头插是先malloc一个节点赋值给newnode,之后在将该newnode 存放到目前的头节点的next中,然后赋值给头节点,即实现头部插入。
5.尾插
void SLpushback(SLnode** p, SLdatatype x)//尾插
{
SLnode* newnode = SLcreatnode(x);
//链表为空的话
if (*p == NULL)
{
*p = newnode;
(*p)->data = x;
}
else
{
//找尾巴(前提:链表不为空)
SLnode* tail = *p;
while (tail ->next!= NULL)
{
tail = tail -> next;
}
tail->next = newnode;
(*p)->data = x;
}
}
尾插需要我们找到最后一个节点,之后先改变末尾的next,(因为保证是连接的)然后再插入。
7.头删
void SLpopfront(SLnode** p)//头删
{
assert(*p);
if ((*p) ->next== NULL)
{
free(p);
*p = NULL;
}
else
{
SLnode* top = *p;
*p = (*p) -> next;//指向下一个
free(top);
top = NULL;
}
}
头删需要分情况
8.尾删
void SLpopback1(SLnode** p)//尾删
{
SLnode* pre = NULL;
SLnode* tail = *p;
while (tail->next != NULL)
{
pre = tail;//找到尾节点前一个
tail = tail->next;
}
free(tail);//释放最后的空间
pre->next = NULL;//同时前一个的next为空
}
或者
void SLpopback2(SLnode** p)
{
SLnode* tail = *p;
while(tail->next->next)//找倒数第二个节点
{
tail = tail->next;
}
free(tail->next);//释放
tail->next = NULL;//倒数第二个next置空
}
主要找到最后一个节点或者最后一个的前一个节点(这里的两种方法),在释放掉最后一个同时,前一个节点next为NULL。可以看到第二种直接释放掉前一个的next空间,即指向最后一个结点的空间,在置空。
8.在pos节点前插入x
void SLinsert(SLnode** p, SLnode* pos, SLdatatype x)//插在pos位置前
{
SLnode* newnode = SLcreatnode(x);
if (pos == *p)
{
SLpushfront(p, x);
}
SLnode* prev=*p;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
在这里需要注意在遍历找到pos位置前的一个节点时,我们都是prev->next==pos这样去寻找,但忽略了当头节点就是pos位置时的节点,故在开始我们还需要判断是否头节点等于pos节点,如何果实就直接调用头插文章来源:https://www.toymoban.com/news/detail-454597.html
9.在pos节点前插入x
//pos节点后插
void SLinsertafter(SLnode** p, SLnode* pos, SLdatatype x)
{
SLnode* newnode = SLcreatnode(x);
SLnode* prev = pos->next;
pos->next = newnode;
newnode->next = prev;
}
10.删除pos位置节点
void SLerase(SLnode** p, SLnode* pos)//删除pos位置的节点
{
SLnode* prev = *p;
if (*p == pos)
{
SLpopfront(p);
}
else
{
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
文章来源地址https://www.toymoban.com/news/detail-454597.html
到了这里,关于数据结构之单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!