一、单链表
1.1 概念与结构
顺序表存在空间申请过多过少或者增容导致空间浪费的问题。链表是线性表的一种，链表是一种物理存储结构上非连续、非顺序的存储结构，数据结构的逻辑顺序是通过链表中的指针链接次序实现的。
1.2 结点
链表由一个个结点连接而成，类似于火车车厢的连接。每个结点的地址不一定是连续的，但每个结点的结构包含指向下一个结点的地址。链表中每个结点都是独立申请的，需要插入数据时才去申请一块结点的空间。我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。所以在链表中没有增容的概念。结点是一个结构体，由数据 + 指向下一个结点的指针组成。
struct ListNode { int data; struct ListNode* next; }
1.3 链表的性质
1、链式机构在逻辑上是连续的，在物理结构上不一定连续 2、结点一般是从堆上申请的 3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续
假设当我们想要保存一个整型数据的时候，实际上是从操作系统申请一个内存空间，而这个内存空间不仅要保存当前的整型数据，还要保存下一个结点的地址。当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。而且对于链表来说没有增容的概念，是我们需要的时候再去申请一块空间，这就很好的处理了在顺序表中些许浪费的情况。
1.4 链表的打印
清楚了链表的结构，了解了结点的结构，现在我们可以简单的来打印一个链表。在以后的代码中，尽量养成三个文件的写法（头文件、实现文件、测试文件），这样会使代码更清晰可见，思路也会更清晰明了。首先我们在头文件中创建我们所需要的函数声明，在实现文件和测试文件中编写函数。
我们先用结点创建一个链表，在打印之前对它进行调试，发现在每一个结点中存放在我们事先输入的数据，并且通过前一个结点可以找到后一个结点。之后开始写打印的代码：
该打印函数将链表的第一个结点传入，头结点赋值给一个新的指针变量 pcur。while 循环的条件是 pcur 不为空指针，先让 pcur->data 就是第一个数据，打印完之后将 pcur 赋值给 pcur->next，然而 next 的地址又是下一个结点的地址，所以就会打印出下一个数据。
完整代码：
// SList.h
#pragma once
#include <stdlib.h>
#include <stdio.h>
typedef int SLDatatype;
typedef struct SLNode {
SLDatatype data;
struct SLNode* next;
} SL;
void SLprintf;
{
SL* pcur = phead;
(pcur) {
(, pcur->data);
pcur = pcur->next;
}
();
}
{
SL* node1 = (SL*)((SL));
node1->data = ;
SL* node2 = (SL*)((SL));
node2->data = ;
SL* node3 = (SL*)((SL));
node3->data = ;
SL* node4 = (SL*)((SL));
node4->data = ;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = ;
SLprintf(node1);
}
{
CreatSList();
;
}
