东南大学数据结构课件第02章线性表.pptVIP

删除48 双向循环链表的删除算法 first first 非空表 31 48 15 current 31 15 current current-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; 双向循环链表的删除算法 template class T, class E bool DblListT, E::Remove( int i, E x, int d ) { //在双向循环链表中按d所指方向删除第i个结点。 DblNodeT, E *current = Locate (i, d); if (current == NULL) return false; //删除失败 current-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; //从lLink链和rLink链中摘下 x = current-data; delete current; //删除 return true; //删除成功 }; 静态链表 为数组中每一个元素附加一个链接指针，就形成静态链表结构。 处理时中可以不改变各元素的物理位置，只要重新链接就能改变这些元素的逻辑顺序。 它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。 静态链表每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。 所有结点形成一个结点数组， 静态链表的结构 0号是表头结点，link给出首元结点地址。 循环链表收尾时link = 0，回到表头结点。如果不是循环链表，收尾结点指针link = -1。 link指针是数组下标，因此是整数。 a1 a2 a3 a4 a5 Λ first 0 1 2 3 4 5 data a3 a4 a1 a5 a2 link 3 2 4 5 -1(0) 1 AH.first BH.first ? ? CH.first ? 1 0 1 0 -1 4 -1 4 -3 6 3 6 -9 10 -9 10 7 12 7 12 8 14 8 14 多项式链表的相加 AH = 1 - 3x6 + 7x12 BH = - x4 + 3x6 - 9x10 + 8x14 CH = 1 - x4 - 9x10 + 7x12 + 8x14 AH.first BH.first ? ? CH.first 1 0 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pc pb ? AH.first ? ? CH.first ? 1 0 1 0 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pb pc BH.first AH.first ? ? CH.first ? 1 0 1 0 -1 4 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pb pc BH.first AH.first ? ? CH.first ? 1 0 1 0 -1 4 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pb pc BH.first tmp = -3+3 = 0 AH.first ? ? CH.first 1 0 1 0 -1 4 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pc -9 10 pb BH.first ? AH.first ? ? CH.first 1 0 1 0 -1 4 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pc -9 10 pb BH.first 7 12 ? AH.first ? ? CH.first 1 0 1 0 -1 4 -1 4 -3 6 3 6 -9 10 7 12 8 14 pa pc -9 10 pb BH.first 7 12 8 14 ? p 循环链表 (Circular List) 循环链表是单链表的变形。 循环链表的最后一个结点的 link 指针不为 NULL，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。 循环链表的示例 带表头结点的循环链表 a0 a1 a2 an-1 first an-1 first a1 a0 first (空表) (非空表) template class T, class E struct CircLinkNode { //链表结点类定义 E da