一、什么是链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
逻辑结构：
物理结构：
- 链式结构在逻辑上是连续的，但在物理上不一定连续
- 节点是从堆上申请的空间，按策略分配的，可能连续也可能不连续
二、链表的分类
按照单双链表，是否有头，是否循环，可以将链表分为八种
1、单向或者双向
2、带头或不带头
3、循环或不循环
三、无头单向不循环链表的实现
代码结构设计：
- SList.h: 存放链表结构及需要用到的头文件，函数声明等
- SList.c: 各种操作函数的具体实现
SList.h
#pragma once #include <stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos);
SList.c
#include "SList.h"
动态申请一个节点
SListNode* BuySListNode(SLTDateType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } newNode->data = x; newNode->next = NULL; return newNode; }
单链表打印
void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) { //pplist不能为空 assert(pplist); //创建要插入的节点 SListNode* newNode = BuySListNode(x); //链表没有节点时 if (*pplist == NULL) { *pplist = newNode; } //链表有节点时 else { SListNode* cur = *pplist; //找到链表的最后一个节点 while (cur->next != NULL) { cur = cur->next; } cur->next = newNode; } }
单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x) { //pplist不能为空 assert(pplist); SListNode* newNode = BuySListNode(x); newNode->next = *pplist; *pplist = newNode; }
单链表的尾删
void SListPopBack(SListNode** pplist) { assert(pplist); //检查链表是否为空 assert(*pplist); //链表只有一个节点 if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* cur = *pplist; //找到倒数第二个节点 while (cur->next->next != NULL) { cur = cur->next; } free(cur->next); cur->next = NULL; } }
单链表头删
void SListPopFront(SListNode** pplist) { assert(pplist); //检查链表是否为空 assert(*pplist); SListNode* cur = *pplist; *pplist = cur->next; free(cur); }
单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return cur; }
在pos位置前插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x) { assert(pplist); assert(pos); if (pos == *pplist) { //在第一个节点前插入即头插 SLTPushFront(pplist, x); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } SListNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } } }
单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* newNode = BuySListNode(x); newNode->next = pos->next; pos->next = newNode; }
删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos) { assert(pplist); assert(pos); if (pos == *pplist) { //删除第一个节点即头删 SLTPopFront(pplist); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos) { assert(pos); assert(pos->next); SListNode* cur = pos->next->next; free(pos->next); pos->next = cur; }
