链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
现实中数据结构中
链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构:
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
单链表的实现
SList.h
#pragma once #include<stdio.h> #include<string.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDataType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDataType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDataType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDataType x); // 单链表在pos位置之后插入x // 分析思考为什么不在pos位置之前插入？ void SListInsertAfter(SListNode* pos, SLTDataType x); // 单链表删除pos位置之后的值 // 分析思考为什么不删除pos位置？ void SListEraseAfter(SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode* plist);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" // 动态申请一个节点 SListNode* BuySListNode(SLTDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("fail:malloc"); } newnode->data = x; newnode->next = NULL; return newnode; } //尾插 void SListPushBack(SListNode** pplist, SLTDataType x) { assert(pplist); SListNode * newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* tail = *pplist; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } //尾删 void SListPopBack(SListNode** pplist) { assert(pplist); assert(pplist); //两种情况 //1>一个节点时 if ((* pplist)->next == NULL) { free(*pplist); *pplist = NULL; } //2>多个节点时 else { SListNode* tail = *pplist; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //头插 void SListPushFront(SListNode** pplist, SLTDataType x) { assert(pplist); SListNode* phead = BuySListNode(x); phead->next = *pplist; *pplist = phead; } //头删 void SListPopFront(SListNode** pplist) { assert(pplist); assert(*pplist); SListNode* phead = (* pplist)->next; *pplist = phead; } //打印单链表 void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur) { printf("%d->",cur->data); cur = cur->next; } printf("NULL"); } SListNode* SListFind(SListNode* plist, SLTDataType x) { SListNode* cur = plist; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SListEraseAfter(SListNode* pos) { assert(pos); assert(pos->next); SListNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } // 单链表的销毁 void SListDestroy(SListNode** plist) { free(*plist); *plist = NULL; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" void TestSList() { SListNode* SList = NULL; SListPushBack(&SList, 1); SListPushBack(&SList, 2); SListPushBack(&SList, 3); SListPushBack(&SList, 4); SListPopBack(&SList); SListPushFront(&SList,5); SListPopFront(&SList); SListDestroy(&SList); SListPrint(SList); } int main() { TestSList(); return 0; }
画图思想：
