数据结构之“Ordered List and Sorted List”（七）

2023-10-25 09:48
文章标签 数据结构 list sorted ordered

本文主要是介绍数据结构之“Ordered List and Sorted List”（七），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        本文主要学习“Sorted List”的应用—— 多项式相加（the addition of two polynomials，点击打开链接）。


一、多项式相加的计算机表示

        前面学习“Ordered List”的应用的时候，我们学到用“a sequence of ordered pairs”来表示一个多项式。如下：


        然后，用“Ordered List”来表示这个多项式，并编写了一个算法来求该多项式的微分。（点击打开链接）

        在计算多项式的微分的算法中，多项式中的每一项在序列中的具体位置并不影响该算法的效率。但是，如果我们考虑两个多项式相加的算法：它需要找出指数（exponent）相同的项，即分组（group），然将指数相同的项的系数（coefficient）相加。如果多项式中的项的位置是任意的，这个分组的过程需要多次遍历“Ordered List”，效率非常低。反之，如果多项式的项是从小到大（按指数）排列的，那么这个分组仅需一次遍历。


二、实现

接口声明：

#pragma once
#include "SortedListAsLinkedList.h"// the oredered pair
class TermB : public Object
{
public:TermB(double, unsigned int);void Put(std::ostream &)const;void Differentiate();double Coefficient() const;unsigned int Exponent() const;friend TermB operator+(const TermB&, const TermB&);protected:int CompareTo(Object const &) const;private:double coefficient;unsigned int exponent;
};class SortedPolynomial : public SortedListAsLinkedList
{
public:SortedPolynomial();~SortedPolynomial();SortedPolynomial(SortedPolynomial&);friend SortedPolynomial operator+(const SortedPolynomial &, const SortedPolynomial &);
};

实现 

#include "stdafx.h"
#include "SortedPolynomial.h"TermB::TermB(double _coefficient, unsigned int _exponent): coefficient(_coefficient), exponent(_exponent)
{
}void TermB::Put(std::ostream & s) const
{s << typeid(*this).name() << " {";s << coefficient << "," << exponent;s << " }";
}void TermB::Differentiate()
{if (exponent > 0){coefficient *= exponent;--exponent;}elsecoefficient = 0;
}double TermB::Coefficient() const
{return coefficient;
}unsigned int TermB::Exponent() const
{return exponent;
}TermB operator+(const TermB& arg1, const TermB& arg2)
{if (arg1.exponent != arg2.exponent)throw std::domain_error("unequal exponent");return TermB(arg1.coefficient + arg2.coefficient, arg1.exponent);
}int TermB::CompareTo(Object const & object) const
{TermB const & term = dynamic_cast<TermB const &> (object);if (exponent == term.exponent)return ::Compare(coefficient, term.coefficient);elsereturn exponent - term.exponent;
}SortedPolynomial::SortedPolynomial()
{
}SortedPolynomial::~SortedPolynomial()
{
}SortedPolynomial::SortedPolynomial(SortedPolynomial& arg)
{Purge();Pos & pos = *new Pos(arg, arg.linkedList.Head());//Iterator & pos = arg.NewIterator();while (!pos.IsDone()){const TermB & term = dynamic_cast<const TermB &> (*pos);Insert(*new TermB(term));++pos;}
}SortedPolynomial operator+(const SortedPolynomial & arg1, const SortedPolynomial & arg2)
{SortedPolynomial result;ListAsLinkedList::Pos & pos1 = *new ListAsLinkedList::Pos(arg1, arg1.linkedList.Head());ListAsLinkedList::Pos & pos2 = *new ListAsLinkedList::Pos(arg2, arg2.linkedList.Head());//Iterator & pos1 = arg1.NewIterator();//Iterator & pos2 = arg2.NewIterator();while (!pos1.IsDone() && !pos2.IsDone()){const TermB & term1 = dynamic_cast<const TermB &> (*pos1);const TermB & term2 = dynamic_cast<const TermB &> (*pos2);if (term1.Exponent() < term2.Exponent()){result.Insert(*new TermB(term1));++pos1;}else if (term1.Exponent() > term2.Exponent()){result.Insert(*new TermB(term2));++pos2;}else{TermB sum = term1 + term2;if (sum.Coefficient())result.Insert(*new TermB(sum));++pos1;++pos2;}}while (!pos1.IsDone()){const TermB & term1 = dynamic_cast<const TermB &> (*pos1);result.Insert(*new TermB(term1));++pos1;}while (!pos2.IsDone()){const TermB & term2 = dynamic_cast<const TermB &> (*pos2);result.Insert(*new TermB(term2));++pos2;}delete& pos1;delete& pos2;return result;
}


三、测试

测试代码

    // test for Polynomial Addition{SortedPolynomial polynomial;TermB pArray[] = { TermB(5,0), TermB(32,5), TermB(4,2), TermB(56,3), TermB(16,4), TermB(45,1) };for (unsigned int i = 0; i < 6; ++i)polynomial.Insert(pArray[i]);polynomial.Put(std::cout);cout << endl;SortedPolynomial polynomial2;TermB pArray2[] = { TermB(5, 0), TermB(32, 5), TermB(4, 2), TermB(56, 3), TermB(16, 4), TermB(45, 6) };for (unsigned int i = 0; i < 6; ++i)polynomial2.Insert(pArray2[i]);polynomial2.Put(std::cout);cout << endl;SortedPolynomial polynomial3 = polynomial + polynomial2;polynomial3.Put(std::cout);polynomial.RescindOwnership();polynomial2.RescindOwnership();polynomial3.RescindOwnership();}


四、分析和优化

1，“互补多项式”求和

        假设计算两个“互补多项式”（a addition of a polynomial and its arithmetic complement）的和。这两个多项式对应项相加为0，最终结果也为零，即在求和函数中无需执行“Insert”。那么它的总消耗时间就是主循环的次数，即O(n)。

        注：先考虑特殊情况，再考虑一般情况，这是一种解决问题的思路。

2，一般多项求和

        假设两个项数不相等的多项式，p(x) < q(x)。主循环执行L次，次循环执行M次。“Insert”函数为O(k)，则求和函数的效率为：



最坏的情况是O(n*n）。主要是因为，我们在分析时假设“Insert”函数不知道每次的具体插入位置。事实上，在循环中，每次都是“在尾部插入”，参照“Insert”函数的实现：

void SortedListAsLinkedList::Insert(Object & object)
{const Node<Object*>* prevPtr = NULL;const Node<Object*>* ptr = linkedList.Head();while (ptr != NULL && *ptr->Datum() < object){prevPtr = ptr;ptr = ptr->Next();}if (!prevPtr)linkedList.Prepend(&object);elselinkedList.InsertAfter(prevPtr, &object);++count;
}

      我们可以进行以下优化，取代Insert。 

SortedPolynomial operator+(const SortedPolynomial & arg1, const SortedPolynomial & arg2)
{SortedPolynomial result;ListAsLinkedList::Pos & pos1 = *new ListAsLinkedList::Pos(arg1, arg1.linkedList.Head());ListAsLinkedList::Pos & pos2 = *new ListAsLinkedList::Pos(arg2, arg2.linkedList.Head());//Iterator & pos1 = arg1.NewIterator();//Iterator & pos2 = arg2.NewIterator();while (!pos1.IsDone() && !pos2.IsDone()){const TermB & term1 = dynamic_cast<const TermB &> (*pos1);const TermB & term2 = dynamic_cast<const TermB &> (*pos2);if (term1.Exponent() < term2.Exponent()){result.linkedList.Append(new TermB(term1));// result.Insert(*new TermB(term1));++pos1;}else if (term1.Exponent() > term2.Exponent()){result.linkedList.Append(new TermB(term2)); //result.Insert(*new TermB(term2));++pos2;}else{TermB sum = term1 + term2;if (sum.Coefficient())result.linkedList.Append(new TermB(sum)); // result.Insert(*new TermB(sum));++pos1;++pos2;}}while (!pos1.IsDone()){const TermB & term1 = dynamic_cast<const TermB &> (*pos1);result.linkedList.Append(new TermB(term1)); // result.Insert(*new TermB(term1));++pos1;}while (!pos2.IsDone()){const TermB & term2 = dynamic_cast<const TermB &> (*pos2);result.linkedList.Append(new TermB(term2)); // result.Insert(*new TermB(term2));++pos2;}delete& pos1;delete& pos2;return result;
}

        优化后，运行时间降为O(n)。


这篇关于数据结构之“Ordered List and Sorted List”（七）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/281730。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
Collection List Set Map的区别和联系

Collection List Set Map的区别和联系

Collection List Set Map的区别和联系 这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。 有序否 允许元素重复否 Collection 否 是 List 是 是 Set AbstractSet 否
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
【Python报错已解决】AttributeError: ‘list‘ object has no attribute ‘text‘

【Python报错已解决】AttributeError: ‘list‘ object has no attribute ‘text‘

🎬 鸽芷咕：个人主页  🔥 个人专栏: 《C++干货基地》《粉丝福利》 ⛺️生活的理想，就是为了理想的生活! 文章目录 前言一、问题描述1.1 报错示例1.2 报错分析1.3 解决思路 二、解决方法2.1 方法一：检查属性名2.2 步骤二：访问列表元素的属性 三、其他解决方法四、总结 前言 在Python编程中，属性错误（At
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2