第2章专题3线性表的链接存储.ppt

（1）若线性表频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用链表做存储结构。 （2）若线性表中元素个数变化较大或者未知，最好使用链表实现；如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。 template class DataType LinkListDataType :: LinkList(DataType a[ ], int n) { first = new Node; //生成头结点 r = first; //尾指针初始化 for (i = 0; i n; i++) { s = new Node; s-data = a[i]; r-next = s; r = s; } r-next = NULL; } 2.3 线性表的链接存储结构及实现 单链表的实现———构造函数 尾插法的C++描述： 单链表的实现———删除 操作接口： DataType Delete(int i); 2.3 线性表的链接存储结构及实现 p 如何实现结点ai-1和ai之间逻辑关系的变化？ first a1 ai-1 ai+1 ai 算法描述： q=p-next; x=q-data; p-next=q-next; delete q; q 单链表的实现———删除 2.3 线性表的链接存储结构及实现 算法描述： q=p-next; x=q-data; p-next=q-next; delete q; 注意分析边界情况——表头、表尾。 p q p q 表尾的特殊情况： 虽然被删结点不存在，但其前驱结点却存在。 p-next=NULL first a1 an a2 ∧ 算法描述——伪代码 1.工作指针p初始化； 2. 查找第i-1个结点并使工作指针p指向该结点； 3. 若p不存在或p不存在后继结点，则抛出位置异常； 否则， 3.1 暂存被删结点和被删元素值； 3.2 摘链，将结点p的后继结点从链表上摘下； 3.3 释放被删结点； 3.4 返回被删元素值； 2.3 线性表的链接存储结构及实现 单链表的实现———删除 template class DataType DataType LinkListDataType :: Delete(int i) { p = first ; count = 0; while (p != NULL count i - 1) { p = p-next; count++; } if (p == NULL || p-next == NULL) throw 位置; else { q = p-next; x = q-data; p-next = q-next; delete q; return x; } } 2.3 线性表的链接存储结构及实现 单链表的实现———删除 单链表的实现——析构函数 析构函数将单链表中所有结点的存储空间释放。 2.3 线性表的链接存储结构及实现 操作接口：~LinkList( ); first a1 a2 an ∧ ai q 算法描述： q = first; first = first-next; delete q; first 注意：保证链表未处理的部分不断开 单链表的实现——析构函数 template class DataType LinkListDataType :: ~LinkList( ) { while (first != NULL) { q = first; first = first-next; delete q; } } 2.3 线性表的链接存储结构及实现 算法描述： 启示：算法设计的一般过程 算法设计的一般步骤： 第一步：确定入口（已知条件）、出口（结果）； 第二步：根据一个小实例画出示意图； 第三步：① 正向思维：选定一个思考问题