当我们学完顺序表的时候,我们发现了好多问题如下:
- 中间/头部的插入删除,时间复杂度为O(N)
- 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们
再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
如何解决上面的问题呢??今天就跟着小张一起学习单链表吧!!
链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
注意:1.链式结构在逻辑上是连续的,但是在物理上不一定连续
2.结点一般都是在堆上申请出来的(malloc)
3.从堆上申请的空间,是按照一定策略来分配的,两次申请的空间可能连续,也可能不连续
单链表
单链表的接口实现
void printdata(info* phead)//打印单链表
info* BuySListNode(int x)//创建新结点
void pushback(info** pphead, int x)//尾插
void pushFront(info** pphead, int x)//头插
void popFront(info** pphead)//头删
void popBack(info** pphead)//尾删
info* SListFind(info* pphead, int x)//单链表查找
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
void SeqListErase(info** pphead, info* pos)//删除pos位置的值
void SListInsertAfter(info* pos, int x)//单链表在pos位置之后插入x
void SListEraseAfter(info* pos)//删除pos的后一个位置
0.结构体定义单个结点
typedef struct info {
int data;//data存数据
struct info* next;//info*next存放下一个结点的地址
}info;
1.创建新结点
info* BuySListNode(int x)
{
info* newnode = (info*)malloc(sizeof(info));//空间申请
assert(newnode);//断言,新结点是否申请到了
newnode->data = x;//数据赋值
newnode->next = NULL;//指向的地址赋值
return newnode;//将申请好的空间首地址返回回去
}
断言,如果没申请到空间,mallo返回空指针,断言newnode就会报错
为什么要用二级指针传参在尾插,头插,尾删,头删中
分析:
2.尾插
void pushback(info** pphead, int x)//尾插
{
info* newnode = BuySListNode(x);//将创建好的新结点的地址保存在newnode变量中
if (*pphead == NULL)//链表无结点
{
*pphead = newnode;// 将创建好的头节点的地址给给*pphead,作为新头节点的地址
}
else
{
info* tail = *pphead;//定义一个指针,先指向头结点的地址
while (tail->next != NULL)//循环遍历找尾结点
{
tail = tail->next;//指针指向下一个结点
}
tail->next = newnode;//找到尾结点,将尾结点的next存放新接结点的地址
}
}
分析:
文字解释:大体上就是直接将最后一个结点的next存入新结点的地址,然后将新结点的next存入空(NULL)。
申请新的结点,如果pphead为空地址,链表还没有结点,将新结点的地址传给pphead,新结点的地址就是头结点的地址,如果该链表中已经存在结点,定义一个指针先存放头节点的地址,然后遍历整个链表,循环寻找哪个结点的next为NULL,不是的话就将tail指向下一个结点,对应操作为tail = tail->next;结点的next为NULL,那个结点就是尾结点,找到尾结点之后将尾结点的next存入要插入新结点的地址,新结点的next已经在 BuySListNode(int x)置为空地址
3.打印链表
void printdata(info* phead)
{
info* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
}
分析
文字描述:定义一个指针cur指向头结点,使用这个指针循环遍历,这个指针指向的不为空的话就继续循环,在循环中打印cur->data,对应的操作是printf(“%d->”, cur->data);打印%d后面加->是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur = cur->next;,继续打印。
4.头插
void pushFront(info** pphead, int x)//头插
{
info* newnode = BuySListNode(x);//创建新结点,将新结点的地址存放在newnode指针变量中
newnode->next = *pphead;//新结点的下一个结点应该为旧头结点的地址
*pphead = newnode;//新头结点的地址更新为newnode指针所指向的地址
}
分析
文字描述:将创建的新结点的地址存放在newnode指针变量中,pphead为原先头结点的地址,头插一个新结点后,应该将新结点的next存放原先头结点的地址,对应操作为newnode->next = pphead;然后保存在pphead应该为新的头结点的地址,也就是newnode所指向的地址,对应操作为pphead = newnode;
5.头删
void popFront(info** pphead)
{
info* p =(*pphead)->next;//定义指针存放头结点的下一个结点的地址
free(*pphead);//释放头结点
*pphead = p;//头结点地址更新为原先头结点的下一个结点的地址
}
分析:
6.尾删
void popBack(info** pphead)
{
info* tailprev = NULL;
info* tail = *pphead;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{while (tail->next != NULL)
{
tailprev = tail;
tail = tail->next;
}
free(tail);
tailprev->next = NULL;
}
}
分析:
7.修改
info* SListFind(info* pphead, int x)
{
info* cur = pphead;//cur指针保存pphead指针接收的地址
while (cur)
{
if (cur->data == x)
{ //cur->data==y可以将查找出来的值修改为y,不用单独写修改函数,传参也要多一个y
return cur;//找到的话返回该结点的地址
}
cur = cur->next;//cur指向下一个结点的地址
}
return NULL;
}
分析:
8.pos指针指向结点的地址的前一个位置前插插入(随便插)
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{
assert(pphead);//头结点地址不能为空
if (pos == *pphead)//pos指针指向结点的地址为头结点,相当于头插
{
pushFront(*pphead, x);//调用头插函数
}
else
{
info* prev = *pphead;//定义一个prev指针,先让他保存头结点的地址
while (prev->next != pos)//循环遍历找pos指针指向结点的前一个结点
{
prev = prev->next;
}
info* newnode=BuySListNode(x);//申请新结点,将申请好的结点地址存放在newnode指针变量里面
prev->next = newnode;//使之前pos指针指向的结点的前一个结点的next存入插入新结点的地址,
newnode->next = pos;//然后新结点的next存入pos指向结点的地址
}
}
分析:
9.删除pos位置的值
void SeqListErase(info** pphead, info* pos)
{
if (pos == *pphead)//删除结点是否为头结点
{
popFront(*pphead);//头删
}
else
{
info* prev = *pphead;//定义一个prev指针,先让他存放头结点的地址
while (prev->next != pos)//循环遍历寻找哪个结点的next存放的是pos指针指向的结点的地址
{
prev = prev->next;//prev指针指向下一个结点
}
prev->next = pos->next;//pos指针指向的结点的上一个结点的next存放pos指针指向的结点的下一个结点的地址
free(pos);//释放掉pos指针指向的那块空间
}
}
分析:
10.单链表在pos位置之后插入x
void SListInsertAfter(info* pos, int x)
{
assert(pos);//防止在空指针
info* newnode=BuySListNode(x);//申请新结点
newnode->next = pos->next;
pos->next = newnode;
}
分析:
那么1,2是否可以反过来
pos->next = newnode;
newnode->next = pos->next;
不行,d3的地址会丢失
出现下图的情况:
11.删除pos的后一个位置
void SListEraseAfter(info* pos)
{
assert(pos);//防止pos指向空地址
if (pos->next == NULL)//如果pos指针指向最后一个结点
return;//直接退出,不往下执行
info* del = pos->next;//保存pos指针指向结点的下一个结点的地址
pos->next = del->next;//更新pos指针指向的结点的下一个结点为pos指针指向结点下下一个结点的地址
free(del);//释放掉保存pos指针指向结点的下一个结点的地址的空间。
}
分析:文章来源:https://www.toymoban.com/news/detail-700592.html
12.完整源码
#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct info {
int data;
struct info* next;
}info;
void printdata(info* phead)
{
info* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
}
info* BuySListNode(int x)
{
info* newnode = (info*)malloc(sizeof(info));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void pushback(info** pphead, int x)//尾插
{
info* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
info* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void pushFront(info** pphead, int x)//头插
{
info* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void popFront(info** pphead)//头删
{
info* p =(*pphead)->next;
free(*pphead);
*pphead = p;
}
void popBack(info** pphead)//尾删
{
info* tailprev = NULL;
info* tail = *pphead;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (tail->next != NULL)
{
tailprev = tail;
tail = tail->next;
}
free(tail);
tailprev->next = NULL;
}
}
info* SListFind(info* pphead, int x)//查找
{
info* cur = pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{
assert(*pphead);
if (pos == *pphead)
{
pushFront(*pphead, x);
}
else
{
info* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
info* newnode=BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void SeqListErase(info** pphead, info* pos)
{
if (pos == *pphead)
{
popFront(*pphead);
}
else
{
info* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void SListInsertAfter(info* pos, int x)
{
assert(pos);
info* newnode=BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListEraseAfter(info* pos)
{
assert(pos);
if (pos->next == NULL)
return;
info* del = pos->next;
pos->next = del->next;
free(del);
}
int main()
{
info* n1 = (info*)malloc(sizeof(info));
info* n2 = (info*)malloc(sizeof(info));
info* n3 = (info*)malloc(sizeof(info));
info* n4 = (info*)malloc(sizeof(info));
assert(n1 && n2 && n3 && n4);
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
printf("原链表:");
printdata(n1);
printf("\n");
printf("尾插:");
pushback(&n1, 5);
pushback(&n1, 6);
pushback(&n1, 7);
pushback(&n1, 8);
printdata(n1);
printf("\n");
printf("头插:");
pushFront(&n1, 10);
pushFront(&n1, 20);
printdata(n1);
printf("\n");
printf("头删:");
popFront(&n1);
printdata(n1);
printf("\n");
printf("尾删:");
popBack(&n1);
popBack(&n1);
printdata(n1);
printf("\n");
printf("查找到并修改:");
SListFind(n1, 3)->data = 80;
printdata(n1);
printf("\n");
printf("pos指针指向结点的地址的前一个位置前插插入:");
SeqListInsert(&n1, n4, 100);
printdata(n1);
printf("\n");
printf("删除pos位置的值:");
SeqListErase(&n1, n4);
printdata(n1);
printf("\n");
printf("单链表在pos位置之后插入x:");
SListInsertAfter(n2, 1000);
printdata(n1);
printf("\n");
printf("删除pos的后一个位置:");
SListEraseAfter(n1);
printdata(n1);
printf("\n");
}
13.代码编译运行
文章来源地址https://www.toymoban.com/news/detail-700592.html
到了这里,关于【数据结构】单链表详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!