一、什么是单链表？
单链表是一种链式存取的数据结构，，链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。简单来说单链表就是一个一个的节点链接起来的链式结构，每个节点里面存储着一个数据和与它链接的下一个节点的（指针）地址。（注意，每一个节点都是同一种结构体类型）
二、单链表的增删查改
2.1 结构体变量的声明
typedef int SLTDataType; typedef struct SLTNode { SLTDataType data; struct SLTNode* next; }SLTNode;
2.2 申请新结点
SLTNode* BuySListNode(SLTDataType x) { SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode)); if (newNode == NULL) { perror("malloc fail"); return NULL; } else { newNode->data = x; newNode->next = NULL; return newNode; } }
2.2 链表的头插
void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newNode = BuySListNode(x); newNode->next = *pphead; *pphead = newNode; }
2.3 链表的尾插
void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newNode = BuySListNode(x); if (*pphead == NULL) { *pphead = newNode; } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newNode; } }
2.4 链表的头删
void SListPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; }
2.5 链表的尾删
void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tailPrev = NULL; SLTNode* tail = *pphead; while (tail->next) { tailPrev = tail; tail = tail->next; } tailPrev->next = NULL; free(tail); tail = NULL; } }
2.6 链表的查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x) { SLTNode* cur = pphead; while (cur) { if (cur->data == x) { return cur; } else { cur = cur->next; } } printf("找不到%d\n",x); return NULL; }
2.7 链表的任意位置后面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newNode = BuySListNode(x); SLTNode* posNext = pos->next; pos->next = newNode; newNode->next = posNext; }
2.8 链表的任意位置后面删除
void SListEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; }
2.9 链表的销毁
//建议传二级指针，因为销毁的话需要把这个指向链表的指针置空 //传一级指针无法把指向链表的指针置空 void SListDestroy(SLTNode** pphead) { SLTNode* cur = *pphead; while (cur) { SLTNode* del = cur; cur = cur->next; free(del); del = NULL; } *pphead = NULL; }
2.10 链表的打印
void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
三、代码汇总
3.1 SLish.h
#pragma once //SList.h #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int SLTDataType; typedef struct SLTNode { SLTDataType data; struct SLTNode* next; }SLTNode; // 动态申请一个节点 extern SLTNode* BuySListNode(SLTDataType x); // 单链表打印 extern void SListPrint(SLTNode* phead); // 单链表尾插 extern void SListPushBack(SLTNode** pphead, SLTDataType x); // 单链表的头插 extern void SListPushFront(SLTNode** pphead, SLTDataType x); // 单链表的尾删 extern void SListPopBack(SLTNode** pphead); // 单链表头删 extern void SListPopFront(SLTNode** pphead); // 单链表查找 extern SLTNode* SListFind(SLTNode* pphead, SLTDataType x); // 单链表在pos位置之后插入x // 分析思考为什么不在pos位置之前插入？ extern void SListInsertAfter(SLTNode* pos, SLTDataType x); // 单链表删除pos位置之后的值 // 分析思考为什么不删除pos位置？ extern void SListEraseAfter(SLTNode* pos); // 单链表的销毁 extern void SListDestroy(SLTNode** pphead);
3.2 SLish.c
#define _CRT_SECURE_NO_WARNINGS 1 //Slist.c #include "SList.h" SLTNode* BuySListNode(SLTDataType x) { SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode)); if (newNode == NULL) { perror("malloc fail"); return NULL; } else { newNode->data = x; newNode->next = NULL; return newNode; } } void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newNode = BuySListNode(x); if (*pphead == NULL) { *pphead = newNode; } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newNode; } } void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newNode = BuySListNode(x); newNode->next = *pphead; *pphead = newNode; } void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tailPrev = NULL; SLTNode* tail = *pphead; while (tail->next) { tailPrev = tail; tail = tail->next; } tailPrev->next = NULL; free(tail); tail = NULL; } } void SListPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; } SLTNode* SListFind(SLTNode* pphead, SLTDataType x) { SLTNode* cur = pphead; while (cur) { if (cur->data == x) { return cur; } else { cur = cur->next; } } printf("找不到%d\n",x); return NULL; } void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newNode = BuySListNode(x); SLTNode* posNext = pos->next; pos->next = newNode; newNode->next = posNext; } void SListEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; } void SListDestroy(SLTNode** pphead) { SLTNode* cur = *pphead; while (cur) { SLTNode* del = cur; cur = cur->next; free(del); del = NULL; } *pphead = NULL; }
3.3 test.c
#define _CRT_SECURE_NO_WARNINGS 1 //test.c #include "SList.h" void test_SListPushBack(void) { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPrint(plist); SLTNode* ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListInsertAfter(ret, 6); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListInsertAfter(ret, 7); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListInsertAfter(ret, 8); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListInsertAfter(ret, 9); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListInsertAfter(ret, 10); SListPrint(plist); } /*SLTNode* ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListEraseAfter(ret); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListEraseAfter(ret); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListEraseAfter(ret); SListPrint(plist); } ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListEraseAfter(ret); SListPrint(plist); }*/ /*ret = SListFind(plist, 1); if (ret != NULL) { printf("找到了，地址为：%p\n", ret); SListEraseAfter(ret); SListPrint(plist); }*/ //SListInsertAfter(ret, 8); /*SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist);*/ } void test_SListPushFront(void) { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); /*SListPopFront(&plist); SListPrint(plist);*/ //SListDestroy(plist); //SListPrint(plist); /*SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist);*/ } int main() { //test_SListPushBack(); test_SListPushFront(); return 0; }
