数据结构基础--线性表的链式存储（单链表）

链表概述

链表是一种很常见的数据结构，它的元素个数不受限制，当进行添加元素的时候存储的个数会随之改变，链表的优点：在运行时确定大小，能够快速的插入和删除数据，链表的缺点：不能随机访问，用户必须提供编程支持。
链表分为单链表，单向循环链表、双链表、双向循环链表，这篇文章主要讲述的是单链表。

在学习单链表之前我们先来了解几个概念性内容

头结点：头结点的数据域可以不存储任何信息，头结点的域存储指向第一个结点的指针（即第一个元素结点的存储位置）。头结点的作用是使所有非空，并使对的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。添加头结点能够更加方便的解决单链表的删除和插入操作，便于对首元结点进行处理，所以本篇文章在设置头结点的情况下进行的。
首指针：它是指向链表中的第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

单链表的常规操作(以下内容仅考虑常规条件下操作）

1.首先我们根据个人习惯，对一些类型进行重命名，和设置一些宏定义

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//指针域
}Node;
typedef struct Node * LinkList;

2.单链表的初始化

//初始化单链表
Status InitLinkList(LinkList *L)
{
//生成一个结点作为头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L ==NULL) {
        return ERROR;
    }
    (*L)->next = NULL;
    return OK;
}

3.单链表的插入：在指定位置插入数据

Status LinkListInsert(LinkList *L,int i , ElemType data){
  LinkList p,s;
  p  = *L;
  int  j  = 1;
//先找到插入的前一个位置
  while (p&&j<i) {
      p = p->next;
      ++j;
  }
//如果p为空或者j>i就不能再插入了
  if (!p||j>i) {
      return ERROR;
  }
//创建一个新的结点
  s = (LinkList)malloc(sizeof(Node));
//新节点赋值
  s->data = data;
//将新节点的next指向前一个结点p的next
  s->next = p->next;
//将p的next指向新的结点
  p->next = s;
  return OK;
}

4.单链表的删除，删除指定位置的数据，删除的思路，先找到首元结点，遍历找到要删除的前一个结点，记录下要删除的结点，将删除结点的前一个节点的next指向删除结点的下一个结点q->next，free删除节点的存储空间，这样完成了删除结点的操作。

Status ListDelete1(LinkList *L,int i,ElemType *e){
    LinkList p,q;
    int j=1;
//先找到首元结点
    p = (*L)->next;
//遍历找到要删除的前一个结点
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    //记录下要删除的结点
    q=p->next;
//将删除结点的前一个节点的next指向删除结点的下一个结点q->next
    p->next = q->next;
//free删除节点的存储空间
    free(q);
    return OK;
}

5.单链表的取值，取出指定位置i,上的数据，使用指针来让外界获取该数据。

Status GetElem(LinkList L,int i,ElemType *e){
    int j;
//获取首元结点
    LinkList p = L->next;
    j=1;
//先找到i 位置的前一个结点
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p || j >i) {
         return  ERROR;
    }
//获取数据
    *e = p->data;
    
    return OK;
}

6.单链表的遍历

void show(LinkList L){
//先找到首元结点
    LinkList p = L->next;
//遍历单链表
    while (p) {
//打印结点的数据
        printf("%d",p->data);
        p = p->next;
    }
    printf("\n");
}

下面讲一下单链表的另外两种插入结点方法：头插法、尾插法

头插法：每次插入结点都是从链表的头部插入，单链表L插入随机数
1.创建一个头结点
2.头结点的next为空
3.循环插入随机数据
4.创建新节点,赋值
5.将头结点的next指向p

void LinkListInsert(LinkList *L, int n){
    LinkList p;
//创建一个头结点
    (*L) = (LinkList)malloc(sizeof(Node));
//头结点的next为空
    (*L)->next = NULL;
 //循环插入随机数据
    for (int i= 0; i<n; i++) {
//创建新节点
        p = (LinkList)malloc(sizeof(Node));
//新节点的next为（*L）->next
        p->next =(*L)->next;
//赋值
        p->data = i;
//将头结点的next指向p
        (*L)->next = p;
    }
}

尾插法：每次插入的结点都是从链表的尾部插入
1.创建一个头结点
2.将尾指针指向链表*L
3.循环插入随机数据
4.创建新节点
5.尾指针的next指向新的结点
6.将新节点赋值给尾指针
7.将尾指针的next置为空

void LinkListInsert(LinkList *L, int n){
    LinkList p,r;
//创建一个头结点
    (*L) = (LinkList)malloc(sizeof(Node));
//将尾指针指向链表*L
    r=*L;
 //循环插入随机数据
    for (int i= 0; i<n; i++) {
//创建新节点
        p = (LinkList)malloc(sizeof(Node));
        p->data = i;
//尾指针的next指向新的结点
        r->next = p;
//将新节点赋值给尾指针
        r=p;
    }
//将尾指针的next置为空
r->next=NULL;
}