• 线性表（Linear List)：指由 $n$ 个类型相同的数据元素 $A_1, A_2,..., A_n$ 组成的有限序列-

• 特点

  • 同一性：数据元素的类型必须相同
  • 有穷性：数据元素的个数是有限个的
  • 有序性：相邻数据元素间存在着序偶关系$<A_i, A_{i+1}>$或者$<A_{i-1}, A_i>$（即 $A_i$ 的直接前驱必然是$A_{i-1}$，$Ai$ 的直接后继必然是 $A_{i+1}$）

• 实现方式（存储结构）与查找、插入/删除

  • 1、顺序存储：即顺序表

    • 实际应用：数组、字符串、栈、队列等
    • 查找：随机访问（高效），由于存储地址是连续的，故可以通过计算快速定位到任意元素
    • 插入/删除：需要移动元素

  • 2、链式存储（重点）：即链表（单向/双向/循环）

  • //形如下述结构体：
    struct Node {
      	int data;//节点数据
      	Node *next;//后继指针，也写作Rlink
        Node *pre; //前驱指针，也写作Llink、prior
    };
    

  • 

  • //做出如下定义
     //head：头指针，指向第一个节点
     //p -> pre： 节点p的前驱节点
     //p -> data：节点p的数据元素
     //p -> next：节点p的后继节点
     //null：空节点，一般用于表示链表结尾
    

    • 查找：由于是采用链式存储，在存储空间中的布局是分散的，故只能从第一个元素开始，根据指针依次访问下一个节点，直到访问到想要的元素

  • //查找元素x的流程伪代码：
    
      int* p = head;//初始化p指向头节点
      while (p != null) {//重复执行直到p为null（链表结尾）
          if (p -> data == x) {//判断p所指节点的数据是否为元素x
              //找到元素x对应的操作
          } else {
              p = p -> next;//否则将p指向下一个节点
          }
      }
    

    • 插入/删除（重点）：由于是通过指针去“连接”每一个元素，故在插入/删除操作中只需要设定好指针即可完成（高效）

      • 

      • //如上图，删除节点p的流程伪代码：
        
         p -> pre -> next = p -> next;
         //将节点p的前驱节点（a）的后继指针，指向节点p的后继节点（c）
         p -> next -> pre = p -> pre;
         //将节点p的后继节点（c）的前驱指针，指向为节点p的前驱节点（a）
         delete p;
         //删除节点p
        

      • 

      • //如上图，在节点p后面插入节点s的流程伪代码：
        
         s -> pre = p;
         //1、将节点s的前驱指针，指向节点p
         s -> next = p -> next;
         //2、将节点s的后继指针，指向节点p的后继节点
         p -> next -> pre = s;
         //3、将节点p的后继节点的前驱指针，指向节点s
         p -> next = s;
         //4、将节点p的后继指针，指向节点s
        

      • 上述顺序不是固定的，但需注意：由于p的后继节点只能通过p -> next访问到，故在节点s与p的后继节点建立连接前，不能变更节点p的后继指针-

• 三、线性查找与哈希表

  • 线性查找：不管是顺序表还是链表，想要查找指定数据时，都需要从头开始遍历，这种查找称为线性查找；当数据内容较多时，比较耗时

  • 哈希函数：为解决线性查找的缺陷，可以借助某个函数，根据元素中的数据映射到表中的某个位置，这个函数就称为哈希函数（散列函数），对应的存储方式也称为散列存储，得到的数据结构称为哈希表

  • 示例：将数列$(1, 56, 9, 21, 5)$通过哈希函数H(K) = floor(sqrt(K)) % 10存储至数组arr中

  • arr[floor(sqrt(1)) % 10] = 1;//arr[1] = 1;
    
    arr[floor(sqrt(56)) % 10] = 56;//arr[7] = 56;
    
    arr[floor(sqrt(9)) % 10] = 9;//arr[3] = 9;
    
    arr[floor(sqrt(21)) % 10] = 21;//arr[4] = 21;
    
    arr[floor(sqrt(5)) % 10] = 5;//arr[2] = 5;
    
    //最终arr[]存储情况为{0, 1, 5, 9, 21, 0, 0, 56, 0, 0, 0}
    

  • 假设后面想 查找值为$5$ 的数据时，便可以通过哈希函数H(5) = floor(sqrt(5)) % 10 = 2直接定位到属于它的下标[2]，然后根据存储的数据来判断它是否存在

  • 冲突与解决方法

    • 但是，如果数列变更为$(1, 6, 9, 21, 5)$时，容易发现H(6) = 2与H(5) = 2，两者的映射位置是相同的，这就会造成冲突
    • 解决的方法是换一个哈希函数，例如H(K) = floor(sqrt(k * k + 3)) % 10，可得
      • $H(1) = 2$
      • $H(6) = 6$
      • $H(9) = 9$
      • $H(21) = 1$
      • $H(5) = 5$
    • 容易发现，现在各自都不会造成冲突

​