前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各个元素结点，并逐个插入链表

单链表整表创建的算法思路：

1.声明一结点p和计数器变量i；

2.初始化一空链表L

3.让L的头结点的指针指向null，即建立一个带头结点的单链表

4.循环：

生成一新结点赋值给p

随机生成一数字赋值给p的数据域p-》data；

将p插入到头结点与前一新结点之间

随机产生n个元素的值，建立带表头结点的单链线性表L(头插法)

void CreateListHead(LinkList *L,int n)
{
  LinkList p;
  int i;
  srand (time(0)) ; /*初始化随机数种子*/
  *L = (LinkList) malloc (sizeof (Node));
  (*L) -> next = NULL;  /*先建立一个带头结点的单链表*/
  for(i=0; i<n; i++ )
    {
        P = (LinkList) malloc(sizeof (Node) );  /*生成新结点*/
    p->data = rand()%100+1; /*随机生成100以内的数字*/
    p->next = (*L)->next;
    (*L)->next = p; /*插入到表头*/
    }
}

在算法代码里，最长用的是插队的办法，就是始终让新结点在第一的位置。这种算法简称为头插法

为什么新来的到第一的位置，每次把新结点都插在终端结点的后面，这种算法称之为尾插法

代码如下：

void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int i;
    srand(time(0));
    *L = (LinkList) malloc (sizeof(Node));  //L为整个线性表
    r = *L;     //*r 为指向尾部的结点;
    for (i = 0; i < n; i++)
    {
        p = (Node *)malloc(sizeof(Node));   //生成新结点
        p->data = rand() % 100 +1;
        r->next = p;
        r = p;  //将当前结点的新结点定义为终端节点
    }
    r->next = NULL;
}

注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量, r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

注意啊，r是一个变量！！！

值得注意的是r->next = p；的含义，其实就算将刚才的表尾终端结点r的指针指向新结点p

那么r = p是什么意思？？？

它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai，所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾节点了

单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下: 1.声明一结点p和q; 2.将第一个结点赋值给p; 3.循环

将下一结点赋值给q; 释放p; 将q赋值给p。

初始条件:顺序线性表L已存在，操作结果:将L重置为空表

Status ClearList ( LinkList *L)
{
    LinkList p,q;
  p= (*L)->next;  /*p指向第一个结点(将第一个结点赋值给p)*/
  while (p) /*没到表尾*/
    {
        q=p->next;  //将下一节点赋值给q
    free(p);  //释放p
    p=q;  //将q赋值给p
    }
  (*L)->next=NULL; /*头结点指针域为空*/
  return OK;
}

这个蛮好理解的！

其中q的作用，就是一个记录作用，p被释放了，但是谁得到了记录，以便于等当前结点释放后，把下一节点拿回来补充

单链表结构与顺序存储结构优缺点

1. 存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

2.时间性能

●查找

●顺序存储结构0(1)
●单链表0(n)

●插入和删除

●顺序存储结构需要平均移动表长半的元素，时间为0(n)
●单链表在线出某位置的指针后，插入和删除时间仅为0(1)

3.空间性能

●顺序存储结构需要预分配存储空间，分大了，浪费,分小了易发生上溢

●单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

**若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。**若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。

当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天,这种用顺序存储结构效率会高很多。

各有优缺点~