目录
实现单链表的基本 *** 作
想要把链表研究透彻 就需要对指针的深入了解
先引入一个概念 什么是指针?什么是变量?什么是指针变量?
我们创建的 int char double 都属于变量
变量有地址 指向这个地址就能改变这个变量
我们创建的指针也是变量
那指针变量也有自己的地址
指向这个地址就能改变这个变量
这个问题非常抽象
改变变量 就需要创建一个指针指向这个变量的地址
如果我们想要改变指针变量(注意这时就应该是指针变量)就要创建一个指针指向指针变量的地址
才能改变这个指针变量
本质上 指针变量和指针是有区别的
说法上 我们不会仔细区分指针变量和指针
看两段代码 能更加了解这段话
void test(int* b)
{
b = NULL;
}
int main()
{
int c = 10;
int* a = &c;
printf("%p\n", a);
test(a);
printf("%p\n",a);
return 0;
}
运行结果如下
那为甚 我传的已经是指针了 按理来说能改变a的值
我们要区分a是一个指针变量 里面存着c的地址
我们这么传参 只能改变c本身的值 而改不了a本身的值
void test(int **b)
{
*b = NULL;
}
int main()
{
int c = 10;
int* a = &c;
printf("%p\n", a);
test(&a);
printf("test之后\n%p\n", a);
return 0;
}
运行结果如下 我们想要改变a的量就要把a的地址传过来
因为此时的a就是一个指针变量
&a才是拿到了指针变量的地址 才能改变a本身
换而言之 我们总结 想要改变谁就要传谁的地址
只有理解上面这段话 才能理解链表
如果没理解请反复观看 不然下面就是劝退表!!!
链表结构用图来表示会容易理解
怕有和我一样英文不好的同志我统统给注释了 更能方便我们理解
一定要多画图哦!!!
实现单链表的基本 *** 作1.定义单链表结构体
typedef int SLDateType;方便我们修改链表数据类型
typedef struct SListNode
{
SLDateType date;
struct SListNode* next;
}SLNode;//重命名更加方便以后的调用
这样一来 我们就有了一个结构体 可以保存数据 并且支持指向下一个结点
是骡子是马 先牵出来溜溜 暴力初始化 先让我们对链表有一个概念
void test1()
{
SLNode* n1=(SLNode*)malloc(sizeof(SLNode));
assert(n1);
SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
assert(n2);
SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
assert(n3);
SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
assert(n4);
n1->date = 1;
n2->date = 2;
n3->date = 3;
n4->date = 4;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
SListprint(n1);
}
2.打印单链表中的数据
我们需要把数据全部打印出来 只需要判断目前节点的下一节点是否为NULL就可以
如果为NULL 说明目前节点 就是最后一个
void SListprint(SLNode* phead)//单链表的打印
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL\n");
}
打印一下刚才的暴力初始化内容
效果如下
3.链表的尾插
SLNode* BuySLNode(SLDateType x)//创建一个新的节点
{
SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
//创建一个节点NewNode
assert(NewNode);//判断是否创建成功
NewNode->date = x;//要插入的数据给此节点
NewNode->next = NULL;
//因为是尾插 所以他肯定是最后一个节点
//把此节点的下一节点设置为空指针
return NewNode;
}
void SLpushback(SLNode** phead, SLDateType x)//单链表的尾插
{
//注意的是 传进来的是**类型哦!!!
//因为我们不单单改变数据 也可能会改变节点的位置
SLNode* NewNode=BuySLNode(x);
if (*phead==NULL)//判断此链表是否有节点
{
//没有节点 把创建的节点当作头
*phead = NewNode;
}
else//有节点
{
//tail 结尾
//定义一个tail变量来遍历链表
SLNode* tail = *phead;//从头开始遍历
while (tail->next != NULL)//找到最后一个节点
{
tail = tail->next;
}
tail->next = NewNode;//连接新创建的节点
}
}
4.链表的尾删
void SLpopback(SLNode** phead)//单链表的尾删
{
assert(*phead);//如果是空 直接结束程序
//判断链表是单个节点 还是多个节点
//phead 是当作头传进来的
if ((*phead)->next == NULL)//如果下一节点为空 说明就是单节点
{
free(*phead);//一个节点 我们只需要free掉本身就可以
*phead = NULL;//置为空指针
}
//走到这里说明 为多节点
SLNode* tailPre = NULL;//保存尾节点的前一个节点
SLNode*tail = *phead;
while (tail->next != NULL)//找到尾节点
{
tailPre = tail;
tail = tail->next;
}
free(tail);//free 尾节点
tailPre->next = NULL;
}
tailpre 可能会有人不懂 我们画图解释
5.链表的头插
void SLpushFront(SLNode** phead, SLDateType x)//单链表的头插
{
SLNode* NewNode=BuySLNode(x);
NewNode->next = *phead;
*phead = NewNode;
}
不需要判断是否为空吗? 是的确实不需要
假设有节点的情况
假设没有节点的情况
都是ok的哦
6.链表的头删
void SLpopFront(SLNode** phead)//单链表的头删
{
assert(*phead);
SLNode* newnext = (*phead)->next;
free(*phead);
*phead = newnext;
}
头删是需要判断是否为空的 如果为空 那我们就删了个寂寞 free个bug出来
7查找链表中的数据
SLNode* SLfind(SLNode* phead, SLDateType x)
{
assert(phead);//如果为空=查了个寂寞
SLNode* cur = phead;
while (cur)
{
if (cur->date == x)//找到就返回
return cur;
cur = cur->next;
}
return NULL;//为空说明没有这个数据
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)