前言
这是我学习数据结构的第三份笔记，有关单链表的知识。后期我会继续将数据结构知识的笔记补全。
上一期笔记有关顺序表，没看过的同学可以去看看：
有关顺序表的笔记
https://blog.csdn.net/hsy1603914691/article/details/142280812?spm=1001.2014.3001.5501
链表
链表的概念
1. 链表是⼀种物理存储结构上非连续、非顺序的存储结构。
2. 链表是顺序表的一种，所以它一定在逻辑结构上是线性的。
3. 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
4. 链表实际上由一个个节点组成。
结点的概念
1. 结点的组成主要有两个部分：当前结点要保存的数据和下⼀个结点的地址（指针变量）。
2. 链表中每个结点都是独立申请的，即需要插⼊数据时才去申请⼀块结点的空间。
3. 我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。
4. 两个节点之间的地址不一定是连续的。
单链表
定义单链表
typedef int LTDataType typedef struct SListNode { LTDataType data; //节点数据 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 }SLTN; //SListNode==Single List Node 单链表节点
创建新的节点
SLTN* Add_STLNode(SLTDataType x) { SLTN* node=(SLTN*)malloc(sizeof(SLTN)); node->data = x; node->next = NULL; return node; }
打印单链表
void Print_SLTNode(SLTN* phead)//不需要对原来的链表进行修改，所以只要传值。 { assert(phead); SLTN* purc = phead; while (purc != NULL) { printf("%d\n", purc->data); purc = purc->next; } printf("NULL\n"); }
尾插单链表
void Back_Push_STLNode(SLTN** pphead, SLTDataType x)//要对原来的链表进行操作，所以传地址。 { SLTN* newnode = Add_STLNode(x); SLTN* purc = *pphead; if (*pphead == NULL) { *pphead = newnode; } else { while (purc->next != NULL) { purc = purc->next; } purc->next = newnode; } }
头插单链表
void Front_Push_STLNode(SLTN** pphead, SLTDataType x) { SLTN* newnode = Add_STLNode(x); newnode->next = *pphead; *pphead = newnode; }
指定插入单链表
void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x) { assert(*pphead); assert(pos); SLTN* newnode=Add_STLNode(x); SLTN* prev = *pphead; while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; }
尾删单链表
void Back_Pop_STLNode(SLTN** pphead) { assert(*pphead); SLTN* ptail = *pphead; SLTN* prev = NULL; if (ptail->next == NULL) { free(ptail); ptail = NULL; } else { while (ptail->next != NULL) { prev = ptail; ptail = ptail->next; } prev->next = NULL; free(ptail); ptail = NULL; } }
头删单链表
void Front_Pop_STLNode(SLTN** pphead) { assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTN* second = (*pphead)->next; free(*pphead); *pphead = second; } }
指定删除单链表
void Delete_STLNode(SLTN** pphead, SLTN* pos) { assert(*pphead); assert(pos); SLTN* prev = *pphead; if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
销毁单链表
void Destroy_STLNode(SLTN** pphead) { assert(*pphead); SLTN* pcur = *pphead; while (pcur) { if (pcur!=NULL) { SLTN* next = pcur; free(pcur); pcur = next->next; } } *pphead = NULL; }
单链表实现代码
<test.h>文件
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SLTNode* next; }SLTN; void PrintSLTNode(SLTN* phead); void Back_Push_STLNode(SLTN** pphead, SLTDataType x); SLTN* Add_STLNode(SLTDataType x); void Front_Push_STLNode(SLTN** pphead, SLTDataType x); void Back_Pop_STLNode(SLTN** pphead); void Front_Pop_STLNode(SLTN** pphead); SLTN* Search_STLNode(SLTN* phead, SLTDataType x); void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x); void STLNode_Insert(SLTN** pphead, SLTN* pos, SLTDataType x); void Delete_STLNode(SLTN** pphead, SLTN* pos); void Destroy_STLNode(SLTN** pphead);
<test.c>文件
#include "test.h" void Print_SLTNode(SLTN* phead) { SLTN* purc = phead; while (purc) { printf("%d\n", purc->data); purc = purc->next; } printf("NULL"); } SLTN* Add_STLNode(SLTDataType x) { SLTN* node=(SLTN*)malloc(sizeof(SLTN)); node->data = x; node->next = NULL; return node; } void Back_Push_STLNode(SLTN** pphead, SLTDataType x) { SLTN* newnode = Add_STLNode(x); SLTN* purc = *pphead; if (*pphead == NULL) { *pphead = newnode; } else { while (purc->next != NULL) { purc = purc->next; } purc->next = newnode; } } void Front_Push_STLNode(SLTN** pphead, SLTDataType x) { SLTN* newnode = Add_STLNode(x); newnode->next = *pphead; *pphead = newnode; } void Back_Pop_STLNode(SLTN** pphead) { assert(*pphead); SLTN* ptail = *pphead; SLTN* prev = NULL; if (ptail->next == NULL) { free(ptail); ptail = NULL; } else { while (ptail->next != NULL) { prev = ptail; ptail = ptail->next; } prev->next = NULL; free(ptail); ptail = NULL; } } void Front_Pop_STLNode(SLTN** pphead) { assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTN* second = (*pphead)->next; free(*pphead); *pphead = second; } } SLTN* Search_STLNode(SLTN* phead, SLTDataType x) { assert(phead); SLTN* pcur = phead; while (pcur) { if (pcur->data == x) { printf("找到了。\n"); return pcur; } else { pcur = pcur->next; } } printf("没找到。\n"); } void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x) { assert(*pphead); assert(pos); SLTN* newnode=Add_STLNode(x); SLTN* prev = *pphead; while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } void STLNode_Insert( SLTN* pos, SLTDataType x) { assert(pos); SLTN* newnode = Add_STLNode(x); newnode->next = pos->next; pos->next = newnode; } void Delete_STLNode(SLTN** pphead, SLTN* pos) { assert(*pphead); assert(pos); SLTN* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } void Destroy_STLNode(SLTN** pphead) { assert(*pphead); SLTN* pcur = *pphead; while (pcur) { if (pcur!=NULL) { SLTN* next = pcur; free(pcur); pcur = next->next; } } *pphead = NULL; } int main() { SLTN* plist = NULL; Back_Push_STLNode(&plist,2); Back_Push_STLNode(&plist,3); Back_Push_STLNode(&plist,4); Front_Push_STLNode(&plist, 1); //Back_Pop_STLNode(&plist); //Front_Pop_STLNode(&plist); SLTN* pos1=Search_STLNode(plist,3); Insert_STLNode(&plist, pos1, 9); STLNode_Insert(pos1, 8); Delete_STLNode(&plist, pos1); //Destroy_STLNode(&plist); Print_SLTNode(plist); return 0; }
致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！
