数据结构与算法 3. 列表 2021-07-05 浏览量 1307 暂无评论 ## 3.1 接口与实现 向量与列表都属于线性序列。 ### 3.1.1 从静态到动态 从静态(向量)到动态(列表) 静态的数据结构在进行一些动态操作,比如插入、删除时,过程较为繁琐。 ### 3.1.2 从向量到列表 列表采用动态储存策略,其中的元素称为节点,各节点通过指针或引用彼此连接,在逻辑上构成一个线性序列。相邻节点:前驱后继。 ### 3.1.3 从秩到位置 向量支持循秩访问,可在O(1)时间内直接确定其物理位置。 那列表能否沿用这一特性? **循位置访问:** ### 3.1.4 实现 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210702104025941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210702104100493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 定义ADT接口 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210702104114999.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 3.2 无序列表 ### 3.2.1 循秩访问 重载[]运算符。 ```cpp template T List::operator[](Rank r) const { Posi(T) p = first(); while (0 < r--) p = p->succ; return p->data; } ``` ### 3.2.2 查找 在节点p的n个前驱中, 找到等于e的最后者。 ```cpp Posi(T) List::find(T const &e, int n, Posi(T) p) const { while (0 < n--) if (e == (p = p->pred)->data) return p; return NULL; } ``` 如果将n与p交换,则表示在p的n个后继中找到等于e的最后者。 ### 3.2.3 插入和复制 ```cpp Posi(T) List::insertBefore(Posi(T) p, T const& e) { _size++; return p->insertAsPred(e); } Posi(T) ListNode::insertAsPred(T const& e) { Posi(T) x = new ListNode(e, pred, this); pred->succ = x; pred = x; return x; } void List::copyNodes(Posi(T) p, int n) { init(); while (n--) { insertAsLast(p->data); p = p->succ; } } void List::insertAsLast(T const& e) { insertBefore(trailer); } ``` ### 3.2.4 删除与析构 ```cpp T LIst::remove(Posi(T) p) { T e = p->data; p->pred->succ = p->succ; p->succ->pred = p->pred; delete p; _size--; return e; } List::~List() { clear(); delete header; delete trailer; } int List::clear() { int oldSize = _size; while (0 < _size) remove(header->succ); return oldSize; } ``` ### 3.2.5 唯一化 ```cpp template int List::deduplicate() { if (_size < 2) return 0; int oldSize = _size; Posi(T) p = first(); Rank r = 1; while ( trailer != (p = p->succ) ) { Posi(T) q = find(p->data, r, p); q ? remove(q) : r++; } return oldSize - _size; } ``` ## 3.3 有序列表 ### 3.3.1 唯一化 ```cpp int List::uniquify() { if (_size < 2) return 0; int oldSize = _size; ListNodePosi(T) p = first(); ListNodePosi(T) q; while (trailer != (q = p->succ)) if (p->data != q->data) p = q; else remove(q); return oldSize - _size; } ``` ### 3.3.2 查找 与无序列表相比并没有什么不同,根本原因在于列表的循位置访问,只能一个接一个,而不能像向量一般循秩访问,可以跳着访问。 ```cpp Posi(T) List::search(T const & e, int n, Posi(T) p) const { while ( 0 <= n--) if (((p = p->data) <= e)) break; return p; } ``` ## 3.4 选择排序 每次选个最大的,很像冒泡啊。 但是冒泡排序的效率很低,有改进的地方。 > 两两交换,小步慢跑 可以直接把最大的移到最后,而不是一步一步地交换。 列表可以这么操作,因为列表的插入不影响别的元素。如果是向量的话,冒泡排序和以下思路的选择排序就没有多大区别了。 ```cpp void List::selectionSort(Posi(T) p, int n) { Posi(T) head = p->pred; Posi tail = p; for (int i = 0; i < n; i++) tail = tail->succ; while (1 < n) { insertBefore(tail, remove(selectMax(head->succ, n))); tail = tail->pred; n--; } } ``` 反思: > insertBefore和remove都需要用到动态内存管理,new, delete,它们的操作时间约为普通操作时间的100倍,可以直接交换数据域。 `selectMax` ```cpp Posi(T) List::selectMax(Posi(T) p, int n) { Posi(T) max = p; for (Posi(T) cur = p; 1 < n; n--) if (!lt((cur = cur->succ)->data, max->data)) // painter覆盖,保证算法的稳定性 max = cur; return max; } ``` 性能: 总体复杂度仍然为$O(n^2)$,但元素移动操作和**比较(暂时还没)**操作比冒泡更少。 ## 3.5 插入排序 打牌理牌。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210705094651132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp void List::insertionSort(Posi(T) p, int n) { for (int i = 0; r < n; r++) { insertAfter(search(p->data, r, p), p->data); p = p->succ; remove(p->pred); } } ``` **性能分析** 最好情况$O(n)$,最坏情况$O(n^2)$ ## 3.6 逆序对 将逆序对的个数计算后逆序对的后一个元素上,那么每次插入需要比较的次数就是该元素上逆序对的个数。 假设列表中逆序对的个数为$I$,则插入排序的复杂度为$O(I+n)$,**输入敏感**。 可以把逆序对数量作为无序程度的衡量。 赞赏 微信支付 支付宝支付