|
|
Home
> IT > Programming > 数据结构和算法 > 数据结构：线性表
ll.descendingIterator() 。但如上文所述，Java的迭代器（Iterator）只提供了hasNext() 和next() 两个方法，而且后者没有把移动和取值分开，这看似简化了其使用，但有时会造成很大麻烦。比如在上面的例子里，迭代器移动后有时会想再次取值，但用Java的这个迭代器，这就导致其进一步移动并取下一个值。List专用的ListIterator也没有这种功能，虽然可以插入、删除和修改了。当然，如果需要的话，我们可以自己实现一个这样的迭代器，或者用一些第三方提供的现成的（比如Guava里的PeekingIterator）。我是不喜欢过于用第三方的类库的，尤其是对Java中特别基本的类进行操作的那些，这些本来就该由Java自己提供的。对于Java来说，从Java 2就开始提供Collection了，到现在（Java 15！）还没有提供这么小的一个功能，个人感觉真的是不应该的。
在这一点上，基于运算符重载的C++意外地显示出巨大的优势，让代码更加简洁，尽管它没有一个简单的方法（复杂的还是有的）确定比如元素必须提供了比较操作符，但由于没有提供的话会导致编译错误，所以也不算个事。
对于前面提到的合并两个有序表的问题，如果用链表，且可以破坏输入的两个链表的话，则整个操作也是可以通过改一下指针完成。
还有一种链表的特殊实现方法：用顺序存储来实现，把结点的第二个域从指针变为索引。这主要是用于没提供指针的编程语言。但缺点也很多：失去了对存储空间要求的灵活；全部分配的空间用完后必须重新分配并拷贝所有元素（O(n)）；对于已删除的结点，为了重复利用这部分空间，往往是把它们加进一个备用链表（这样插入操作由O(1)变为O(2)）。反正我是不看好这种实现方法。
循环链表（Circular Linked List）：普通链表的尾端结点指向NULL，循环链表的尾端则指向头指针（假设链表提供一个头指针，用于指向头结点），从而形成一个闭环。这样，从每个结点都能到达任意一个结点。因而，判断到达表的尾端的方式也从其指针指向NULL变为指向头指针。一个变化型是不提供头指针而是提供尾指针。这种循环链表的好处是便于进行合并操作：只要以下步骤即可完成，时间为O(1)（以可破坏原来的两个链表为前提）：
对，并且只储存非零系数。对于这个例子，则只需储存两个结点：{<1, 0>, <2, 10000>}。
多项式加法：
假设有多项式P（n+1个系数）和Q（m+1个系数），而且m<n，那么其和为：
线性表
概述
线性表（Linear List）是n个数据元素的有限序列。- 数据对象：D = {a(i) | a(i) belongs to Set, i = 1, 2, ..., n, n >= 0}
- 数据关系：R = {
- 基本操作：构造空表，清空表，取得表长度，取得第i个元素，取得数据元素e的索引，取得数据元素e的前驱，取得数据元素e的后继，在索引i处插入数据元素e，在索引i处删除数据元素，遍历表的所有元素
public class ListUtils {
public static List<Integer> mergeSortedLists0(@NonNull List<Integer> sortedList1, @NonNull List<Integer> sortedList2) {
var resultList = new ArrayList(sortedList1.size() + sortedList2.size());
var i = 0;
var j = 0;
while (i < sortedList1.size() && j < sortedList2.size()) {
var elem1 = sortedList1.get(i);
var elem2 = sortedList2.get(j);
if (elem1 <= elem2) {
resultList.add(elem1);
++i;
} else {
resultList.add(elem2);
++j;
}
}
while (i < sortedList1.size()) {
resultList.add(sortedList1.get(i++));
}
while (j < sortedList2.size()) {
resultList.add(sortedList2.get(j++));
}
return resultList;
}
// more generic implementation:
// * not to assume input lists are ArrayLists (use index to get value from a linked list is slow)
// * use template to support different kinds of element types in lists
public static <T extends Comparable> List<T> mergeSortedLists(@NonNull List<T> sortedList1, @NonNull List<T> sortedList2) {
var resultList = new ArrayList<T>(sortedList1.size() + sortedList2.size());
var iter1 = sortedList1.iterator();
var iter2 = sortedList2.iterator();
T elem1 = null;
T elem2 = null;
while (true) {
if (elem1 == null && iter1.hasNext()) {
elem1 = iter1.next();
}
if (elem2 == null && iter2.hasNext()) {
elem2 = iter2.next();
}
if (elem1 == null && elem2 == null) {
break;
}
if (elem1 != null && (elem2 == null || elem1.compareTo(elem2) <= 0)) {
resultList.add(elem1);
elem1 = null;
} else {
resultList.add(elem2);
elem2 = null;
}
}
return resultList;
}
}
第二种实现方法中的条件分析：
#1: e1 == null && e2 == null: break #2: e1 == null && e2 != null: add e2 #3: e1 != null && e2 == null: add e1 #4: e1 != null && e2 != null && <e1, e2>: add e1 #5: e1 != null && e2 != null && <e2, e1>: add e2在程序中，#1是一个分支；#3和#4是一个分支；其余的（#2和#5）是一个分支。 这个算法的想法很简单，但程序编写起来意外地麻烦，感觉难以编写得简洁明快。第二种方法中之所以判断元素为null与否，主要是因为Java中的Iterator不像C++ STL中的那样把取值和移动分开（分别用*和++操作符），而是合为一体了（next()方法），所以使得该问题的实现有点麻烦。用C++来写的话，就好多了：
template <typename T>
std::vector<T> mergeSortedList(std::vector<T>& sortedList1, std::vector<T>& sortedList2)
{
typename std::vector<T>::iterator iter1 = sortedList1.begin();
typename std::vector<T>::iterator iter2 = sortedList2.begin();
typename std::vector<T> resultList;
while (iter1 != sortedList1.end() && iter2 != sortedList2.end()) {
if (*iter1 < *iter2) {
resultList.push_back(*iter1++);
}
else {
resultList.push_back(*iter2++);
}
}
while (iter1 != sortedList1.end()) {
resultList.push_back(*iter1++);
}
while (iter2 != sortedList2.end()) {
resultList.push_back(*iter2++);
}
return resultList;
}
第一种实现方法比较简洁，而且它也可以改写成用模板的通用程序，但是如果表是链表，随机存取是很慢的。如果一定要用这种写法，则宁可牺牲一点存储空间，把链表拷贝到ArrayList中再处理，会快得多。
存储
顺序存储
C++中实现为‘vector’，Java中为‘ArrayList’。就是如同数组那样存储在一整块连续的内存区间内。 优点是随机存取和在尾部追加元素的时间复杂度为O(1)。缺点是需要整块的内存空间，且存储区间不够用时，扩充操作是O(n)；一般的插入和删除也是O(n)，且有可能需要移动大量的结点。链式存储：链表
链表由一连串的结点（Node）构成，结点包括两个域：数据域（用于存储数据）和指针域（用于存储指向下一个结点的指针，或曰链）。 链表的优点是对空间存储的要求十分灵活，不需要整块的内存，零散的就可以；而且插入和删除操作很快，为O(1)（如果不需要找到前面的结点）或O(n)（如果需要找到前面的结点，但可以通过使用双链表来使之降为O(1)），因为只要修改几个指针即可完成操作。 Java中的LinkedList类提供了很多使用元素索引的方法，我也不知道这是个好事还是坏事，因为如果不假思索地就用的话，会使得程序效率很差。如果程序员自己实现这些方法的话，至少他会意识到其时间复杂度为O(n)。 另外，Java中该类的内部实现是一个双向链表，所以它也很贴心地提供了一个反向的迭代器：- 表B的尾结点从指向表B的头结点变为指向表A的头结点（通过表A的尾指针可轻松获得）
- 表A的尾结点从指向表A的头结点变为指向表B的头结点（通过表B的尾指针获得）
- 表A的尾指针的值改为表B的尾指针的值
P(x, n): {p(0), p(1), p(2), ..., p(n)}
P(x, n): {q(0), q(1), q(2), ..., q(m)}
m < n
R(x, n) = P + Q: {p(0) + q(0), p(1) + q(1), ..., p(m) + q(m), p(m+1), ..., p(n)}
显然，其时间为O(n)。
这种普通的多项式适合用顺序存储的表来表示。对于项比较“稀疏”的那种多项式，则适合用链表来表示。其相加的算法为：从两个表的表头开始各取一个元素，比较其指数：把小的那个放入新表。如果两个相等，则将其系数相加，结果不为０的话，放入新表。这跟前面的合并有序表的算法类似。
多项式乘法：可以转换为多个多项式加法。用一个多项式的每一项去乘另一个多项式，就得到一个新的多项式。最后把所有的多项式按上述“稀疏”多项式的要领相加即可。
