首次书写链表有关的知识，先来明确什么是链表？
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
举一个形象化的现实生活中的例子 :> 老式的绿皮火车，车厢由链条，钩子链接在了一起！！
而链表也类似，只不过，链表是通过指针的指向有次序的链接在了一起！！每一个链表可存储一个数据，并且存储着下一个链表节点的地址！！如下图所示 :>
由上图可以看出来，链表在逻辑上是连续的，但在物理结构上不一定连续！！
由于节点的空间，即每个数据单元是在堆上申请。而在堆上申请的空间有可能连续也有可能不连续！！
下面讲述链表的种类----->共有8种类型
如图所示 :>
而我们这里主要研究两种常用类型 :>
------------无头单向不循环-------------带头双向循环------------
1.无头单向不循环 :>
结构简单，一般作为其他数据结构的子结构，如，哈系桶，图的链接表等等。另外笔试面试中出现较多！！
2.带头双向循环 :>
结构复杂，常用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外，此种链表虽然结构复杂，但会带来很多的优势，实现反而简单了！！
好的！！下面让我们开始今天的无头单向不循环链表
头文件“SList.h”
初步创建
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
测试环节“Test.c”
#include "SList.h"
void test_01()
{
SLTNode* plist = NULL; //由于一个链表单元只存储一个数值，因此直接初始化即可
//而顺训表有多个变量，比如，sz, capcity需要进行初始化，因此需要分装一个初始化函数
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 5);
SLTPushBack(&plist, 7);
SLTPushBack(&plist, 9); //尾插数据
SLTPrint(plist);
}
int main()
{
test_01();
}
实现环节“SList.c”
#include "SList.h"
//打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while(cur)
{
printf("%d->", cur ->data);
cur = cur ->next;
}
printf("NULL\n");
}
//开辟空间
SLTNode* SLT_BUY(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if(newnode == NULL)
{
perror("malloc::fail");
return NULL;
}
newnode ->data = x;
newnode ->next = NULL; //防止野指针乱窜
return newnode;
}
//尾插数据
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//开辟空间
SLTNode* newnode = SLT_BUY(x);
if(*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while(tail != NULL)
{
tail = tail ->next;
}
tail = newnode;
}
}
//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = SLT_BUY(x);
newnode ->next = *pphead;
*pphead = newnode;
}
//尾删数据
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
//1.只有一个节点
//2.有两个及多个节点
if(*pphead == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while(tail ->next != NULL)
{
prev = tail;
tail = tail ->next;
}
free(tail);
tail = NULL;
prev ->next = NULL; //防止野指针乱窜
}
}
//头删数据
void SLTPopFront(SLTNode** pphead)
{
SLTNode* first = *pphead;
*pphead = first ->next; //运用了值覆盖原理
free(first);
first = NULL; //防止野指针乱窜
}
头文件“SList.h”
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
//开辟空间
SLTNode* SLT_BUY(SLTDataType x);
//尾插数据
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//尾删数据
void SLTPopBack(SLTNode** pphead);
//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//头删数据
void SLTPopFront(SLTNode** pphead);
测试环节“Test.c”
----->尾插尾删数据
#include "SList.h"
void test_01()
{
SLTNode* plist = NULL; //由于一个链表单元只存储一个数值，因此直接初始化即可
//而顺训表有多个变量，比如，sz, capcity需要进行初始化，因此需要分装一个初始化函数
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 5);
SLTPushFront(&plist, 7);
SLTPushFront(&plist, 9); //尾插数据
SLTPrint(plist);
SLTPopFront(&plist);
SLTPopFront(&plist); //尾删数据
SLTPrint(plist);
}
int main()
{
test_01();
}
下面是执行尾插尾删的运行结果 :>
测试环节“Test.c”
----->头插头删数据
#include "SList.h"
void test_02()
{
SLTNode* plist = NULL; //由于一个链表单元只存储一个数值，因此直接初始化即可
//而顺训表有多个变量，比如，sz, capcity需要进行初始化，因此需要分装一个初始化函数
SLTPushBack(&plist, 11);
SLTPushBack(&plist, 13);
SLTPushBack(&plist, 15);
SLTPushBack(&plist, 17);
SLTPushBack(&plist, 19); //头插数据
SLTPrint(plist);
SLTPopBack(&plist);
SLTPopBack(&plist); //头删数据
SLTPrint(plist);
}
int main()
{
test_02();
}
下面是执行头插头删的运行结果 :>
本期的链表就到这里了！！感谢阅读！！