实现链表的头插
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"slist.h" //链表的概念及结构 //链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑结构是通过链表中的指针来链接 void testslist() { slistnode*plist = NULL;//一开始定义一个指针，但啥都没有，所以先赋值空指针，作为头节点，存入第一个节点的地址 slistpushback(&plist, 1);//尾插//也要传地址才可以，实参传给形参，形参是实参的临时拷贝 slistpushback(&plist, 2); slistpushback(&plist, 3); slistpushback(&plist, 4); slistpushfront(&plist, 0);//头插 slistpopback(&plist); slistpopfront(&plist);//头删 slistprint(plist); } int main() { //需要定义一个指针指向头部 testslist(); return 0; }
slist.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"slist.h" void slistprint(slistnode*phead) { slistnode*cur = phead; while (cur != NULL)//遍历是cur不等于空就往下走，走到尾部还不等于空，走到下一个节点，是空的 { printf("%d->", cur->date); cur = cur->next;//cur指向下一个指针 } printf("NULL\n"); } //开辟节点做的事情很多次，所以直接用一个函数去做开辟节点的事情就可以了 slistnode*buynode(slistdate x) { slistnode*newnode = (slistnode*)malloc(sizeof(slistnode));// 要尾插就要动态开辟一个节点出来 newnode->date = x;//将newnode初始化 newnode->next = NULL;//把next赋值为空 return newnode; } void slistpushback(slistnode**pphead, slistdate x) { slistnode*newnode = buynode(x); //那么我们这个时候要找尾 //找到尾节点的指针 if (*pphead == NULL) { *pphead = newnode; } else { slistnode*tail = *pphead;//我们要让tail走到尾部去，而非走到空 while (tail->next != NULL) { tail = tail->next; }//找到了尾节点,链接新节点 tail->next=newnode; } } void slistpushfront(slistnode**pphead, slistdate x) { //头插 //也要malloc出来一个节点 slistnode*newnode = buynode(x); newnode->next = *pphead;//指向头节点，随后要让phead存第一个节点的地址 *pphead = newnode;//phead存入newnode地址，phead作为头节点，就把newnode当作了头节点 } //尾删要分3种情况分析 //1.没有节点 //2.一个节点 //3.多个节点 void slistpopback(slistnode**pphead)//尾删 { //1.想删除就找到那个节点，free掉就可以了，因为都是malloc出来的 //但是，如果将tail找到了那个尾节点，直接free掉，那么前一个节点的指针就会变成野指针，它的指针仍有存在值，但是没有指向的目标， //因此，我们要找到它的前一个节点，再定义一个prev，作为尾节点找到最后一个节点，他的前一个节点 //1.没有节点,即*pphead没有指向，就直接返回不用删除 if (*pphead == NULL) { return; } //只有一个节点 else if ((*pphead)->next == NULL)//由于*和->的优先级相同，所以为了不报错，就应该把*pphead用括号包含 { //直接free掉8 free(*pphead); *pphead = NULL;//再将*pphead置成空指针，防止它变成野指针 } //有多个节点 else { //先定义tail用来找尾，prev找尾前一个节点 slistnode*tail = *pphead; slistnode*prev = NULL;//prev置成空指针 //找尾节点 while (tail->next != NULL) { prev = tail; tail = tail->next; } //此时prev就是尾节点 free(tail); prev->next = NULL; } } void slistpopfront(slistnode**pphead)//头删 { //先保存它下一个指针，next slistnode*next = (*pphead)->next;//next保存第二个节点的地址，之后将其作为第一个节点 //删除头节点 free(*pphead); *pphead = next; }
slist.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> typedef int slistdate;//对int重命名，只会方便把int改成double或其他数据类型 struct slistnode { slistdate date;// struct slistnode*next;//指针地址，指向下一个节点 }; typedef struct slistnode slistnode;//方便写 //可能会改变链表的头指针就传二级指针 void slistpushback(slistnode**pphead, slistdate x);//尾插 void slistpushfront(slistnode**pphead, slistdate x);//头插 //不会改变链表的头指针，就传一级指针 void slistprint(slistnode*phead); void slistpopback(slistnode**pphead);//尾删 void slistpopfront(slistnode**pphead);//头删
1.头插实现
void slistpushfront(slistnode**pphead, slistdate x) { //头插 //也要malloc出来一个节点 slistnode*newnode = buynode(x); newnode->next = *pphead;//指向头节点，随后要让phead存第一个节点的地址 *pphead = newnode;//phead存入newnode地址，phead作为头节点，就把newnode当作了头节点 }
2.头删
void slistpopfront(slistnode**pphead)//头删 { //先保存它下一个指针，next slistnode*next = (*pphead)->next;//next保存第二个节点的地址，之后将其作为第一个节点 //删除头节点 free(*pphead); *pphead = next; }
4.尾删
//尾删要分3种情况分析 //1.没有节点 //2.一个节点 //3.多个节点 void slistpopback(slistnode**pphead)//尾删 { //1.想删除就找到那个节点，free掉就可以了，因为都是malloc出来的 //但是，如果将tail找到了那个尾节点，直接free掉，那么前一个节点的指针就会变成野指针，它的指针仍有存在值，但是没有指向的目标， //因此，我们要找到它的前一个节点，再定义一个prev，作为尾节点找到最后一个节点，他的前一个节点 //1.没有节点,即*pphead没有指向，就直接返回不用删除 if (*pphead == NULL) { return; } //只有一个节点 else if ((*pphead)->next == NULL)//由于*和->的优先级相同，所以为了不报错，就应该把*pphead用括号包含 { //直接free掉8 free(*pphead); *pphead = NULL;//再将*pphead置成空指针，防止它变成野指针 } //有多个节点 else { //先定义tail用来找尾，prev找尾前一个节点 slistnode*tail = *pphead; slistnode*prev = NULL;//prev置成空指针 //找尾节点 while (tail->next != NULL) { prev = tail; tail = tail->next; } //此时prev就是尾节点 free(tail); prev->next = NULL; } }
