6.0、C语言数据结构——链式存储结构 (1)

6.0、C语言数据结构——链式存储结构 (1)

链式存储定义如下：

        1. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元恶意存在内存中未被占用的任意位置；
        2. 比起顺序存储结构每个数据元素只需要存储一个位置就可以了；现在链式存储结构中，除了要存储数据元素信息外，还要存储他的后继元素的存储地址（指针）；

        3. 也就是说除了存储其本身的信息外，还需要存储一个指示其直接后继的存储位置的信息；

        1. 我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域；指针域中存储的信息称为指针或链；这两部分信息组成数据元素称为存储映像，称为结点（Node）;     
        2. n个结点链接成一个链表，即为线性表（a1,a2,a3,...,an）的链式存储结构；
        3. 因为此链表的每个结点中只包含一个指针域，所以叫做单链表；
        4. 对于线性表来说，总得有个头有个尾，链表也不例外；我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（NULL）；

        线性表中头结点中不存放数据，只存放指向下一个元素的指针；
那么这里需要区分一下 头结点 和 头指针 ->
        1. 头指针是指向 第一个结点 ( 头结点 ) 的指针，而不是存放在第一个结点里的指针；
        2. 头指针具有表示的作用，所以常用头指针冠以链表的名字（指针变量的名字）；
        3. 无论链表是否为空，头指针均不为空；
        4. 头指针是链表的必要元素；

头结点：

        1. 头结点是为了操作的统一和方便而设立的，放在第一个元素的节点之前，其数据域一般无意义，（但也可以用来存放链表的长度）；
        2. 有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其他结点的操作就统一了；
        3. 头结点不一定是链表的必要元素，头结点数据域中一般不存放数据，也可以存放链表的大小；

查找元素时：线性表与单链表的区别 ->

        1. 在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的；
        2. 但在单链表中，由于第 i 个元素到底在哪？我们压根儿没办法一开始就知道，必须得从第一个结点开始挨个儿找；

获得链表第 i 个数据的算法思路：

        1. 声明一个指针 p 指向链表第一个结点，初始化 j 从1开始；
        2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j + 1;
        3. 若到链表末尾 p 为空，则说明第 i 个元素不存在：
        4. 否则查找成功，返回结点 p 的数据；  

实现代码 ->

Status GetElem (LinkList L , ElemType* e) {
    int j;
    LinkList p;
    p = L -> next;
    j = 1;
    while() {
        p = p -> next;
        ++j;
    }
    if(!P || j > i) {
        return ERROR;
    }
    *e = p -> data;
    return OK;
}

1. 说白了，就是从头开始找，直到第 i 个元素为止；
2. 由于这个算法的时间复杂度取决于 i 的为止，当 i = 1 时，则不需要遍历，而 i = n 时则遍历 n -1 次才可以，因此最坏情况的时间复杂度为O ( n )；
3. 由于单链表的结构中没有定义表长，所以不能实现直到要循环多少次，因此也就不方便使用 for 来控制循环；
4. 其核心思想叫做 “ 工作指针后移 ” ， 这其实也是很多算法的常用技术；