数据结构与算法电子0209链表节点的插入算法.ppt

链表的插入 链表的插入 单链表的插入操作好比是要在我们女同学脖 子上的戴的项链的某个位置加一个环，在这个过 程中需要拆掉待插入位置前后的两个环的链接关 系，并重新建立前后两个环与新加入的一个环的 链接关系。 假设要在链表两个数据元素 a 和 b 之间插入一 个新的数据元素 x ，已知 p 为其单链表存储结构中 指向结点 a 的指针，如下图所示。 例题 a b a b x (a) 插入前 (b) 插入后 p p s 例题 要插入数据元素 x, 首先要生成一个数据域为 x 的结点，然后再插入到单链表中。假设这个结点 已经生成，并且我们用教室编号表示指针具体值， 我们对上图做一个修改。 a 2104 1203 b …… 2104 1203 P 插入前 a 3309 1203 b …… 2104 1203 P 插入后 x 2104 3309 3309 S 从这两张图，我们可以看出，要将 x 结点插入 到 a 和 b 结点之间，需要修改两块内存区域，分别 是 a 结点的指针域和 x 结点的指针域，如图所示， 分别改成 3309 和 2204 。显然我们应该用两个赋值 语句来对两个指针域进行修改。这就带来两个问 题，赋值语句的左边和右边分别如何表示？ 由于 p 指针指向 a 结点，所以 a 结点的指针 域用 p-next 来表示； s 指针指向 x 结点，所以 x 结点的指针域用 s- next 来表示。 赋值表达式的左边 a 结点和 x 结点的指针域， 我们分别用什么符号来表示呢？ 其次，赋值表达式右边中的 3309 和 2104 分别来自哪里呢？ 我们知道 3309 就是 x 结点的首地址，它存 放在 s 指针变量中，而 2104 是 b 结点的首地址， 它原来是存放在 a 结点的指针域中 , 用 p-next 来 表示。 这样行吗？显然这样是不行的， p-next 表 示的内存内容原来是 3309 ，但是经过 p-next = s; 这条语句后，内容已经变成 3309 了，而我们需 要赋给 s-next 的值应该是 2104 。所以插入 x 结点 的主要两条赋值语句的顺序应该是： p-next = s; s-next = p-next; s-next = p-next; p-next = s; 单链表的插入 算法 Status ListInsert_L(LinkList L,int i,ElemType e) // 在带头结点的单链表 L 中第 i 个位置之前插入元素 e { p=L; j=0; while(pji?1){p=p -next;++j;} // 寻找第i?1个结 点 if(!p||ji?1)return ERROR;//i大于表长 + 1 或者小于 1 s=new LNode; // 生成新结点 s s-data=e; // 将结点 s 的数据域置为 e s-next=p-next; // 将结点 s 插入 L 中 p-next=s; return OK; }//ListInsert_L 可以看出，这个算法的时间 复杂度为 O(n) ，时间主要是消耗 在让 p 指针指向第 i-1 个结点上了。