国家电力电网招聘考试计算机：数据结构知识必考复习知识点（重点）.pdf

一起求职（ ） 出品 ◎顺序表删除 一起求职（ ） 出品 算法思想：如果要删除序号5 元素，需要将6～8 依次向前移动一位 ▲移动次数为3 次，公式n-i ◎有序表合并 LA = (3,5,8,11) LB = (2,6,8,9,11,15,20) 则LC = (2,3,5,6,8,8,9,11,11,15,20) 算法思想（以非递减为例）：La 和Lb 非递减排列，La 与Lb 中元素逐个比较，较小的先插入Lc 中。 ▲注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。 ▲移动次数为（La.length + Lb.length） 2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。 ◎单链表 ▲每个节点有数据域和指针域 data next 头 a1 a2 a3 a4 a5 a6 带头节点L→ → → → → → → 一起求职（ ） 出品 P ↑ a1 a2 a3 a4 a5 a6 不带头节点L→ → → → → → P ↑ 单循环链表 ●在P （a3）节点前插入S 节点 (1)Q = P; //先让Q 指向a3 (2)P = L; //P指向第一个节点（带头结点指向头结点，不带头结点指向a1） (3)while(P-next != Q) P = P-next; //找到a3 的前驱a2，P 指向a2 (4)S-next = P-next; //P-next 为a3，让S-next 等于a3 (5)P-next = S; //a2 指针域指向节点S ●在P （a3）节点后插入S 节点 (1)S-next = P-next; (2)P-next = S; ●删除P （a3）前一个节点 (1)Q = P; (2)P = L; (3)while(P-next-next != Q) P = P-next; //找到a1 (4)P-next = P-next-next; //让a1 指针域指向a3，从而删除a2 ●删除P （a3）节点 (1)Q = P; (2)P = L; (3)while(P-next != Q) P = P-next; //找到a2 (4)P-next = P-next-next; //让a2 指针域指向a4，从而删除a3 ●删除P （a3）后一个节点 (1)P-next = P-next-next; //让a3 指针域指向a5，从而删除a4 ◎双链表 ▲每个节点有前驱指针、数据域、后继指针 prior data next 双循环链表 头 a1 a2 a3 a4 ●在P （a2）节点前插入S 节点 ▲技巧：先让S-prior 和S-next 与链表建立关系 注：步骤(4)必须在步骤(3)后面 (1)S-next = P; //先让S-next 指向a2 (2)S-prior = P-prior; //S-prior 指向a1 一起求职（ ） 出品 (3)P-prior-next = S; //再把a1-next 指向S (4)P-prior = S; // a2-prior 指向S ●在P （a2）节点后插入S 节点 注：步骤(4)必须在步骤(3)后面 (1)S-prior = P; (2)S-n