8.0、C语言数据结构——线性表 (4)

8.0、C语言数据结构——线性表 (4)

单链表的整表创建 ->

        1. 对于顺序存储结构的线性表的整表创建，我们可以用数组的初始化来直观理解；
        2.而单链表和顺序存储结构就不一样了，它不像顺序存储结构数据这么集中，他的数据可以使分散在内存各个角落的，他的增长是动态的；
        3. 对于每个链表来说，他占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求及时生成；
        

单链表的创建 -> 

        1. 创建单链表的过程是一个动态生成链表的过程，从空表的初始状态起，依次创建各元素结点并逐个插入链表；
        2. 所以单链表整表创建的算法思路如下：
        - 声明一结点 p 和计数器变量 i;
        - 初始化一个空表 L ；
        - 让 L 的头结点的指针指向 NULL ，即建立一个带头结点的单链表；
        - 循环实现后继结点的赋值和插入；
 

1. 头插法建立表单

        1. 头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，知道结束为止；
        2. 简单来说，就是把新加进的元素放在表头后的第一个位置；
        - 先让新结点的 next 指向头结点之后；
        - 然后让表头的 next 指向新结点；
        3. 用现实环境模拟的话就是插队的方法，始终让新结点插在第一的位置；

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;
        p->next = (*L)->next;
        (*L) -> next = p;
    }
}

2. 类比头插法 来看看 尾插法：

头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入和顺序相反；

那我们把思维逆转 -> 把新结点都插入到最后，这种算法称为 尾插法；

void CreateListTail(LinkList* L , int n) {
    LinkList p , r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    for(i = 0;i < n;i++) {
        p = (Node *)malloc(sizeof(Node));
        p -> data = rand()%100 + 1;
        r->next = p;
        r = p;
    }
    r -> next = NULL;
}

        1. 规定：变量 r 永远指向末尾元素；
        2. 比如在数据 ai-1 后面插入一个ai 那么未插入前 r 指向 ai-1 ，当 ai 插入后将 变量 p 指向 ai，最后让 r 指向 p 然后将 r 指向 ai （因为此时 ai 是末尾元素）；
        3. 再插入 ai + 1 同理此时 r 一定是指向 ai 的，然后将变量 p 指向 ai + 1，最后将 r 指向 p 然后将 r 指向 ai + 1（因为此时 ai + 1 是末尾元素）;

      我们分别从存储分配方式、时间性能、空间性能 三个方面来做对比；

存储分配方式 ->

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

时间性能 ：

查找->
        - 顺序存储结构 O(1);

        - 单链表 O(n)；

插入和删除->

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

空间性能：

        - 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出；

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

 综上所述对比：
        - 我们可以得出 -> 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；

        - 若需要频繁插入和删除时，宜采用单链表结构；