我要评论目录
概念
单链表是一种在物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接顺序实现的。
放一张bit课件里的图,我觉得很形象：
链表的单个结点
typedef int sldatatype;//重定义一下在链表内存放的数据类型，方便后期对类型进行统一修改
//链表的单个结点
typedef struct slistnode {//single list node :链表结点
sldatatype data;//存放的数据
struct slistnode* next;//指向下一个结点的指针
}slnode;//重定义名字方便后期使用链表的打印操作
//链表的打印操作
void slprint(slnode* phead) {
assert(phead);//不能传入空指针
slnode* pcur = phead;
//pointer cursor:指针光标，不让头结点丢失(虽然不会改变头结点的指向)
while (pcur) {//等同于pcur!=null
printf("%d->", pcur->data);//打印此结点的数据
pcur = pcur->next;//使pcur指向下一个结点
}
printf("null\n");
}新结点的申请
后面会涉及到新结点的插入，申请新结点可以封装成一个函数，避免代码冗余
//新结点的申请
slnode* slbuynode(sldatatype x) {
slnode* node = (slnode*)malloc(sizeof(slnode));
if (!node) {//返回值为空,申请失败(一般是空间不足了)，直接退出
perror("malloc fail");
exit(1);
}
node->data = x;//将数据赋给data
node->next = null;//将下一个节点置为null;
return node;
}尾部插入
//尾部插入
void slpushback(slnode** pphead, sldatatype x) {
//注意在这里我们传参的是二级指针，因为我们需要在函数内部改变头结点的指向
assert(pphead);//不能传null
//新结点的申请
slnode* node=slbuynode(x);
if (*pphead == null) {
*pphead = node;
}
else {
slnode* pcur = *pphead;
while (pcur->next) {//找到next元素为null的结点，也就是为链表尾部
pcur = pcur->next;
}
pcur->next = node;
}
}测试运行一下：
头部插入
//头部插入
void slpushfront(slnode** pphead, sldatatype x) {
assert(pphead);
slnode* node = slbuynode(x);
//这里需要处理头结点为空的情况吗？不需要，因为没有涉及到解引用其元素
node->next = *pphead;
*pphead = node;
}
测试运行一下：
尾部删除
//尾部删除
void slpopback(slnode** pphead) {
assert(*pphead && pphead);//
if (!(*pphead)->next) {//处理只有一个元素的情况
free(*pphead);
*pphead = null;
}
else {
slnode* prev = null;
slnode* pcur = *pphead;
while (pcur->next) {//找到尾结点前一个结点
prev = pcur;
pcur = pcur->next;
}
free(pcur);//将尾结点释放
pcur = null;
prev->next = null;//将尾结点的前一个结点的next元素置为null
}
}测试运行一下：
头部删除
//头部删除
void slpopfront(slnode** pphead) {
assert(*pphead && pphead);
slnode* next = (*pphead)->next;//保存头结点的下一个结点地址
free(*pphead);//释放头结点
*pphead = next;//使头结点指向下一个结点
}测试运行一下：
查找
在链表中想要对指定位置进行操作不能使用下标，所以我们必须找到指定位置的地址才能对其进行操作。
//查找
slnode* slfind(slnode* phead, sldatatype x) {
assert(phead);
slnode* pcur = phead;
while (pcur) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return null;
}在指定位置之前插入数据
//在指定位置之前插入数据
void slinsert(slnode** pphead, slnode* pos, sldatatype x) {
assert(pphead && pos && *pphead);//pos和pphead不能为空,以及pphead指向空间不能为空
if (*pphead == pos) {//处理头插的情况
slpushfront(pphead,x);
}
else {
slnode* node = slbuynode(x);
slnode* pcur = *pphead;
while (pcur->next != pos) {//找到pos前一个结点
pcur = pcur->next;
}
node->next = pcur->next;
pcur->next = node;
}
}测试运行一下：
在任意位置之后插入数据
//在任意位置之后插入数据
void slinsertafter(slnode* pos, sldatatype x) {
assert(pos);//pos不能为空
slnode* node = slbuynode(x);
node->next = pos->next;
pos->next = node;
}测试运行一下：
删除pos结点
//删除pos结点
void slerase(slnode** pphead, slnode* pos) {
assert(*pphead && pphead && pos);
if (*pphead == pos) {//处理头删的情况
slpopfront(pphead);
}
else {
slnode* pcur = *pphead;
while (pcur->next!= pos) {
pcur = pcur->next;
}
pcur->next = pos->next;
free(pos);
pos = null;
}
}测试运行一下：
删除pos之后结点
//删除pos之后结点
void sleraseafter(slnode* pos) {
assert(pos && pos->next);//pos后面的结点也不能为空
slnode* next = pos->next;
pos->next = next->next;
free(next);
next = null;
}测试运行一下：
销毁链表
//销毁链表
void sldestory(slnode** pphead) {
assert(pphead && *pphead);
slnode* pcur = *pphead;
while (pcur) {
slnode* nextnode = pcur->next;//使用一个变量接受下一个结点地址
free(pcur);
pcur = nextnode;
}
*pphead = null;
}
发表评论