面接問題:2 Dチェーンテーブル構造を展開する方法

トピックの説明:各ノードにも秩序チェーンテーブルがあることを示す秩序チェーンテーブルが与えられます.ノードには2種類のポインタがあります.

は、プライマリ・チェーン・テーブルの次のノードへのポインタです.

は、このノードのヘッダを指すチェーンテーブルである.すべてのチェーンテーブルがソートされます.例を参照:

  3 -> 11 -> 15 -> 30
  |     |     |     |
  6    21    22    39
  |           |     |
  8          50    40
  |                 |
  31               55

実装関数flatten()この関数は、チェーンテーブルを単一のチェーンテーブルにフラット化するために使用され、フラット化されたチェーンテーブルがソートされる.例えば上のチェーンテーブル、出力チェーンテーブルは

3 -> 6 -> 8 -> 11 -> 15 -> 21 -> 22 ->
30 -> 31 -> 39 -> 40 -> 45 -> 50

分析と解答
本題の主な考え方は,集計ソートにおける集計ソートを用い,集計方法を用いてこれらのチェーンテーブルを1つずつ集計することである.具体的には再帰アルゴリズムを用いることができる.集計された連結は、フラット化されたチェーンテーブルと現在のチェーンテーブルを結合します.まずこのチェーンの構造を定義します

typedef struct Node {
    int value;
    Node* right;
    Node* down;
}Node;

私たちは一応一番左上のノードをrootノードと呼んでいます.そして、構造全体を複数の列から構成されていると見なすことができます.そして問題を2つの秩序あるチェーンテーブルの統合と見なすことができます.

Node* Merge(Node* a, Node* b) {
    //          ，               
    if (a == NULL)
        return b;
    if (b == NULL)
         return a;
    Node* result = NULL;
    //     a      b        
    //     down      down             
    if (a->value < b->value) {
        result = a;
        result->down =  Merge(a->down, b);
    } else {
        result = b;
        result->down = Merge(a, b->down);
    }
    return result;
}

その後,複数のカラムに拡張するとflatten()が得られる.

Node* flatten(Node* root) {
    if (root == NULL || root->right == NULL)
          return root;
    //  root->right                ，           
   return Merge(root, flatten(root->right));
}

次に、次のテストを行います.

#include 
#include 

using namespace std;

//      ，       down             ，      
void Insert(Node **head_ref, int new_data) {                                             
  LinkList new_node = (LinkList)malloc(sizeof(Node));                                    
  new_node->right = NULL;                                                                
  new_node->value = new_data;    
  new_node->down = (*head_ref);    
  (*head_ref) = new_node;    
}  

int main() {

  Node* root = NULL;

  Insert(&root, 31);    
  Insert(&root, 8);    
  Insert(&root, 6);    
  Insert(&root, 3);    
    
  Insert(&(root->right), 21);    
  Insert(&(root->right), 11);    
    
  Insert(&(root->right->right), 50);    
  Insert(&(root->right->right), 22);    
  Insert(&(root->right->right), 15);    
    
  Insert(&(root->right->right->right), 55);    
  Insert(&(root->right->right->right), 40);                                              
  Insert(&(root->right->right->right), 39);                                              
  Insert(&(root->right->right->right), 30); 

  root = FlattenList(root);

  Node* tmp = root;

  while (tmp != NULL) {
    cout << tmp->value << "-> ";
    tmp = tmp->down;
  }

  FreeList(root);
  return 0;
}

結果:

[root@VM_16_3_centos data_struct]$ ./list/flatten_list
3-> 6-> 8-> 11-> 15-> 21-> 22-> 30-> 31-> 39-> 40-> 50-> 55->