TAOCP3中一道关于对序列重排的题目的实现

原题参照TAOCP3习题Section 5, 24题

题目大约是，有一个有序的单向链表，每一个元素形如<a, b>，a和b分别是一个元素（在我的解法中用字符串表示）。输入是一个文件，文件中有N-1个形如上述的元祖（N为链表中实际元素的个数），顺序随机。要求输出元祖所指示的原先的序列。比如，输入是，<k4, k5> <k1, k2> <k3, k4> <k2, k3>，链表重建为<k1, k2> <k2, k3> <k3, k4> <k4, k5>，输出为k1 k2 k3 k4 k5。

代码：

/*************************
 copyright @watofall
 no guarantee for bugfree!
**************************/

#include <iostream>
#include <fstream>
#include "string.h"
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_CHAR 100
#define MAX_PAIR 100

typedef struct Pair
{
    char *val;
    char *next;
}Pair;

typedef struct NumVal
{
    int sequence;
    char *val;
}NumVal;

bool comp1(Pair a, Pair b)
{
    if(strcmp(a.val, b.val) < 0)
        return true;
    else
        return false;
}

bool comp2(Pair a, Pair b)
{
    if(strcmp(a.next, b.next) < 0)
        return true;
    else
        return false;
}

bool comp3(NumVal a, NumVal b)
{
    if(strcmp(a.val, b.val) < 0)
        return true;
    else
        return false;
}

bool comp4(NumVal a, NumVal b)
{
    return a.sequence < b.sequence;
}

int main() {
    ifstream fin ("sort_pair2.in");
    int i, j, k, count, t;
    char buf1[MAX_CHAR], buf2[MAX_CHAR];
    vector<Pair> pairs, pairs_b, pairs_;
    vector<NumVal> num_vals, num_vals_;

    for(i = 0; fin.good(); i ++)
    {
        fin >> buf1 >> buf2;

        Pair new_pair;

        new_pair.val = new char[strlen(buf1)];
        new_pair.next = new char[strlen(buf2)];
        strcpy(new_pair.val, buf1);
        strcpy(new_pair.next, buf2);
        pairs.push_back(new_pair);
    }
    count = i + 1;

    pairs_b = pairs;
    sort(pairs.begin(), pairs.end(), comp1);
    sort(pairs_b.begin(),pairs_b.end(), comp2);
    // find the last element
    for(i = 0, j = 0; j < count - 1;)
    {
        if(i >= count - 1) // find miss match
        {
            NumVal new_num_val;
            new_num_val.sequence = count;
            new_num_val.val = pairs_b[j].next;
            num_vals.push_back(new_num_val);
            j ++;
        }
        else if(strcmp(pairs_b[j].next, pairs[i].val) == 0) // find match
        {
            i ++;
            j ++;
        }
        else if(strcmp(pairs_b[j].next, pairs[i].val) > 0) // go on match to the next element
        {
            i ++;
        }
        else // find miss match
        {
            NumVal new_num_val;
            new_num_val.sequence = count;
            new_num_val.val = pairs_b[j].next;
            num_vals.push_back(new_num_val);
            j ++;
        }
    }

    // match and add
    for(t = 1; t <= count; t *= 2)
    {
        pairs_b = pairs;
        sort(pairs.begin(), pairs.end(), comp1);
        sort(pairs_b.begin(), pairs_b.end(), comp2);
        sort(num_vals.begin(), num_vals.end(), comp3);
        pairs_.clear();
        num_vals_ = num_vals;

        for(i = 0, j = 0, k = 0; i < count - t;)
        {
            if(j < count - t && strcmp(pairs_b[i].next, pairs[j].val) == 0) // pairs_b match pairs
            {
                Pair new_pair;
                new_pair.val = pairs_b[i].val;
                new_pair.next = pairs[j].next;
                pairs_.push_back(new_pair);
                i ++;
                j ++;
                continue;
            }

            if(k < num_vals.size() && strcmp(pairs_b[i].next, num_vals[k].val) == 0) // pairs_b match num_vals
            {
                NumVal new_num_val;
                new_num_val.sequence = num_vals[k].sequence - t;
                new_num_val.val = pairs_b[i].val;
                num_vals_.push_back(new_num_val);
                i ++;
                k ++;
                continue;
            }
            
            if(j < count - t && strcmp(pairs_b[i].next, pairs[j].val) > 0) // go on search pairs
            {
                j ++;
                continue;
            }
            
            if(k < num_vals.size() && strcmp(pairs_b[i].next, num_vals[k].val) > 0)
            {
                k ++;
                continue;
            }
        }

        pairs = pairs_;
        num_vals = num_vals_;
    }

    sort(num_vals.begin(), num_vals.end(), comp4);
    cout << "results :" << endl;
    for(i = 0; i < num_vals.size(); i ++)
    {
        cout << num_vals[i].val << " ";
    }
}

sample input :

e f
f j
h i
i u
b o
w x
x y
y z
z c
c d
u v
v w
s a
q r
r s
o p
p t
t g
g h
a b
d e
j k
k l
l m
m n

results :
q r s a b o p t g h i u v w x y z c d e f j k l m n

算法的主要思路是利用排序能够快速找出两个集合中相同元素的性质，维护三个数组F H G，F为剩下的元祖，H和F相同，F按元组的第二个元素升序（字典序，与输出的序列无关，方便查重）排列，H按元组的第一个元素升序排列，G是已经知道序列的最终序列中的末尾元素，以元素字典序的升序排列。H中元组的跨度t不断增加（即对<a, b>，t为在结果序列中a经过几次访问到达b），且不断乘2，因此外部循环为lg(n)次。而内部循环由于有排序，复杂度为O(nlg(n))，故总体时间复杂度为O(nlg²(n))。