トランプ 並べ替え問題 split関数

Question

前提・実現したいこと

C++で問題を解いています。
以下の関数が問題通り動いているかわかりません。

発生している問題・エラーメッセージ

ジョーカーを除いた52枚のトランプカードが上から順番に
s:スペード, C:クローバー,D:ダイヤ, H:ハートとして
SK SQ SJ S10 S9 S8 S7 S6 S5 S4 S3 S2 SA CK CQ CJ C10 C9 C8 C7 C6 C5 C4 C3 C2 CA DK DQ DJ D10 D9 D8 D7 D6 D5 D4 D3 D2 DA HK HQ HJ H10 H9 H8 H7 H6 H5 H4 H3 H2 HA
積まれています。
これを昇順にする問題です。
その際に使う関数として、一番上(head)から n 枚カードを残しその後に続くカードを切り取って 2 組に分割するsplit関数を作ります。実行後 head 自体は変化なく残った n 枚の組の一番上とします。切り取られた組の一番上のカードのポインタが return されるようにします。
今のところコンパイルは通るのですが、実行しても何も起きません。

該当のソースコード

#include <iostream>
using namespace std;

class Card {//トランプの一枚のカード
private:
int suit; //0-3 各々がH(Heart), D(Diamond), C(Clover), S(Spade)に対応
int number; //1-13
Card *next; //一枚下にあるカードを指すポインタ

public:
Card(int i, int j, Card current_next=NULL){suit = i; number = j; next = current_next;}
friend ostream& operator<<(ostream&, Card);
friend void printCards(Card head);
friend Card *split(Card *, int );
friend void pileup(Card *, Card *);
};

// Cardの出力オペレータ
ostream& operator<<(ostream &fout, Card c){
// suit = 0, 1, 2, 3 をH, D, C, Sに変換してsuitを表示
if(c.suit==0) fout << "H";
else if(c.suit==1) fout << "D";
else if(c.suit==2) fout << "C";
else fout << "S";
// number = 1 の時はA(Ace)を表示
// number = 2-10の時はそのまま数を表示
// number = 11, 12, 13 の時はJ(Jack), Q(Queen), K(King)を表示
if(c.number==1) fout << "A";
else if(c.number==11) fout << "J";
else if(c.number==12) fout << "Q";
else if(c.number==13) fout << "K";
else fout << c.number;
// 末尾にスペースを一つ表示
fout << ' ';

return fout;
}

//一番上のheadから順番に全てのカードをたどって表示する関数
void printCards(Card *head){

Card *current;

current = head;
int i = 0;
while(current != NULL){//次のカードがなくなるまで繰り返す
//currentの内容を表示し、次のカードに移動
cout << *current;
current = current->next;
// 13枚毎に改行する
i++;
if(i == 13){
cout << endl;
i = 0;
}
}
}

// 一番上(head)から n 枚カードを残しその後に続くカードを切り取って 2 組に分割する関数
// 実行後 head 自体は変化なく残った n 枚の組の一番上となる
// 切り取られた組の一番上のカードのポインタが return される
Card *split(Card *head, int n){
int i = 0;
while(head!=NULL){
head = head->next;
i++;
if(i==n)
break;
}
return head;
}

// head1 のカードの組を head2 の組の上にのせて 1 組にする関数
// 実行後 head1 は変化がなくまとめた組の一番上となる
void pileup(Card *head1, Card *head2){
while(head1!=NULL){
Card *tmp;
tmp = head2;
head2 = head1;
head1->next = tmp;
}
}

// 与えられたリストを逆順にしたリストを返す関数
Card *reverse(Card *head){
Card *new_head, *reverse_head;
reverse_head = NULL;
// カードを 1 枚ずつ head の上から取り去る
// そのカードを別の場所に 1 枚ずつ積んでいく
// 結果として逆順に積まれる
while(head != NULL){
new_head = split(head,1);
pileup(head,reverse_head);
reverse_head = head;
head = new_head;
}
return reverse_head;
}

int main() {

Card *head;//一番上のカードを指すポインタ

for(int i = 0; i < 4; i++){
for(int j = 1; j <= 13; j++){
// 最初のi=0,j=1の時のみ、next=NULLとしてカードを生成
// それ以降は現在のheadをnextとしてカードを生成し、新しいカードをheadとする
if(i==0 && j==1)
head = new Card(0, 1, NULL);
else
head = new Card(i, j, head);
}
}

// カードの表示
printCards(reverse(head));

return 0;
}

試したこと

split関数とpileup関数はすでに自分なり考えて書いてみました。

補足情報（FW/ツールのバージョンなど）

split関数とpileup関数以外は変えずに、2つの関数を追記することでプログラムを完成させます。

Comments

[episteme]

単方向リストを実装し、要素を反転させるのが目的ですか?
それとも「リストの実装とか、できればやりたくない(出来合いのがあればそのまま使いたい)」ですか?

[program777]

単方向リストを実装して、要素を反転させるのが目的です！
split関数とpileup関数以外はすでに与えられているので、追記するのは変えるとしたらsplit関数とpileup関数ですね。。。また、main 関数内では reverse 関数を利用してカードを昇順に並び替えてから表示しますが、reverse関数の入れる場所は変えても大丈夫です。

Answer 1

※ コレも多分望まれる回答ではありません

Deck(Cardの山)を用意し、append(末尾に挿入)/prepend(先頭に挿入)/draw(先頭を取り出す)を定義。
それらを使って反転してみた

#include <iostream>
#include <string>
#include <cassert>

enum class Suit { Heart=0, Diamond=1, Club=2, Spade=3 };

// Card : 単方向リストの要素
class Card {
private:
  Suit  suit_;
  int   rank_;
  Card* next_;
  void  set_next(Card* card) { next_ = card; }
public:
  Card(Suit suit, int rank) : suit_(suit), rank_(rank), next_(nullptr) {
    assert( rank_ > 0 && rank_ < 14);
  }

  Suit  suit() const { return suit_; }
  int   rank() const { return rank_; }
  Card* next() const { return next_; }
  std::string to_string() const;

  friend class Deck;
};

std::string Card::to_string() const {
  std::string result;
  result += "HDCS"[static_cast<int>(suit_)];
  if ( rank_ == 10 ) {
    result += "10";
  } else { 
    result += "_A23456789_JQK"[rank_];
    result += " ";
  }
  return result;
}

std::ostream& operator<<(std::ostream& stream, const Card& card) {
  return stream << card.to_string();
}

// Deck : Cardを要素とする単方向リスト
class Deck {
private:
  Card* head_;
public:
  Deck() : head_(nullptr) {}
  ~Deck() { while ( !empty() ) delete draw(); }

  // 内包するCardがなければtrue
  bool empty() const {
    return head_ == nullptr;
  }

  // 内包するCardの枚数
  int size() const {
    int result = 0;
    for ( const Card* p = head_; p; p=p->next() ) {
      ++result;
    }
    return result;
  }

  // 末尾にcardを挿入
  void append(Card* card) {
    assert(card != nullptr);
    assert(card->next() == nullptr);
    if ( head_ == nullptr ) {
      head_ = card;
    } else {
      Card* last = head_;
      for ( Card* p = head_; p; p=p->next() ) {
        last = p;
      }
      last->set_next(card);
    }
  }

  // 先頭にcardを挿入
  void prepend(Card* card) {
    assert(card != nullptr);
    assert(card->next() == nullptr);
    if ( head_ == nullptr ) {
      head_ = card;
    } else {
      card->set_next(head_);
      head_ = card;
    }
  }

  // 先頭のCardを取り出す
  Card* draw() {
    Card* card = head_;
    if ( card != nullptr ) {
      head_ = head_->next();
      card->set_next(nullptr);
    }
    return card;
  }

  // 内包するCardをプリントする
  void print_to(std::ostream& stream) const {
    int n = 0;
    for ( const Card* p = head_; p; p=p->next() ) {
      stream << *p << ' ';
      if ( ++n == 13 ) {
        stream << std::endl;
        n = 0;
      }
    }
  }

  //内包する全Cardをotherと交換する
  void swap(Deck& other) {
    Card* p = head_; 
    head_ = other.head_; 
    other.head_ = p;
  }
};

std::ostream& operator<<(std::ostream& stream, const Deck& d) {
  d.print_to(stream);
  return stream;
}

int main() {
  Deck deck;
  for ( Suit suit : { Suit::Heart, Suit::Diamond, Suit::Club, Suit::Spade} ) {
    for ( int rank = 1; rank < 14; ++rank ) {
      deck.append(new Card(suit,rank));
    }
  }
  std::cout << deck << std::endl;

  // deckの並びを反転する
  {
    Deck tmp;
    while ( !deck.empty() ) {
      // deckの先頭をtmpの先頭に移動
      tmp.prepend(deck.draw());
    }
    // deckとtmpを交換
    deck.swap(tmp);
  }
  std::cout << "after reverse...\n";
  std::cout << deck << std::endl;
}

Comments

[episteme]

Deck::draw が (一枚だけの)splitに相当しますね。

[program777]

ちなみにpileupに相当するするところはどこですか？

[episteme]

わかんないの?

[program777]

すみません。
swap関数ですかね...?

[episteme]

Deck::prepend/append でDeckにCardを追加しています。
# ってコメント付けてますし、Deckの基本操作はdraw/append/prependの3つだけです。

[program777]

解決しました！
ありがとうございました！

Answer 2

void pileup(Card* head1, Card* head2) {
	while (head1 != NULL) {
		Card* tmp;
		tmp = head2;
		head2 = head1;
		head1->next = tmp;
	}
}

while内でhead1が変わらないので無限ループになってるのが、いま止まらない理由でしょう。

// 一番上(head)から n 枚カードを残しその後に続くカードを切り取って 2 組に分割する関数 
// 実行後 head 自体は変化なく残った n 枚の組の一番上となる 
// 切り取られた組の一番上のカードのポインタが return される 
Card *split(Card *head, int n){
    int i = 0;
    while(head!=NULL){
        head = head->next;
        i++;
        if(i==n)
            break;
    }
    return head;
} 

もう一つここの動作も怪しいです。コメントで「実行後 head 自体は変化なく」と言っているように、この関数は実際には分割しません。いくらかのカード分進めたポインターを返すだけで、元も山は元の状態で残ったままです
（もう一つ小さなミスとしては引数のnが残ったカードの数ではなく、実際は進めるカードの数になっているということ）。ところがreverse内での実際の使用法を見ると、分割される前提で元の山に積み上げていっているので、どんどんカードの枚数が増えていきます(pileupの実装次第ではループした単方向リストになる)。
pileupとsplit以外は与えられてるということなので、実際にsplitするような実装に変えるべきなんでしょう。

---

split関数の理想的な動作としては[1-> 2-> 3-> 4-> 5-> Null]というようなリストが与えられたとき、[1-> Null]と[2-> 3-> 4-> 5-> Null]の二つのリストができる関数です。つまりどこかでnextにNullを代入するはずです。

コメントのsplit関数については最初のsplit関数と同じ動作です。もしかしたらポインターの働きを勘違いしてるんじゃないでしょうか。

Comments

[program777]

ではsplit関数はこのような感じでいいですか？
Card *split(Card *head, int n){
Card *current;
current = head;
int i = 0;
while(current!=NULL){
current = current->next;
i++;
if(i==n)
break;
}
return current;
}

[episteme]

「 つまりどこかでnextにNullを代入するはずです。」
なのですが、そのコードのどこでNULLを代入していますか?

[program777]

すみません、間違えました。
if文の中にreturn currentを入れると、n=1のときのcurrent->next、
つまり、切り取られた組の一番上のカードがリターンされているという感じになると思いますが、、、
Card *split(Card *head, int n){
Card *current;
current = head;
int i = 0;
while(current!=NULL){
current = current->next;
i++;
if(i==n)
return current;
break;
}
}
}

[program777]

これで、切り取られた組の一番上のカードがリターンされているという感じになりませんか？

[episteme]

nextの連鎖の途中にNULLを入れて前半と後半に"分断"せんならんのでは?

[program777]

なるほど。。。
Card *split(Card *head, int n){
Card *current;
current = head;
int i = 0;
while(current!=NULL){
current = current->next;
i++;
if(i==n){
current = NULL;
break;
}
}
return head->next;
}
これで分断できてますかね？

[episteme]

そんなんわざわざ訊かんでも、前半と後半をプリントすりゃわかるやん。

Answer 3

※ 望まれる回答ではありません

出来合いの std::list を使った例:

#include <iostream>
#include <list>

class Card {//トランプの一枚のカード
private:
    int suit_; //0-3 各々がH(Heart), D(Diamond), C(Clover), S(Spade)に対応
    int rank_; //1-13
public:
    Card(int suit, int rank) : suit_(suit), rank_(rank) {}
    friend std::ostream& operator<<(std::ostream&, const Card&);
};

// Cardの出力オペレータ
std::ostream& operator<<(std::ostream& fout, const Card& c) {
    return fout << "HDCS"[c.suit_] << "_A23456789TJQK"[c.rank_];
}

int main() {
    std::list<Card> deck;
    for (int suit = 0; suit < 4; ++suit ) {
        for (int rank = 1; rank <= 13; ++rank) {
            deck.emplace_back(suit, rank);
        }
    }

    // deck内のカードの表示
    auto printCard = [](const std::list<Card>& deck ) {
        int i = 0;
        for (const Card& card : deck) {
            std::cout << card << ' ';
            if (++i == 13) { i = 0; std::cout << std::endl; }
        }
    };

    // fromの先頭からn枚をtoの末尾に移動(splitに相当)
    auto draw = [](std::list<Card>& from, std::list<Card>& to, size_t n) {
        to.splice(to.end(), from, from.begin(), std::next(from.begin(), n));
    };

    std::cout <<"deck:\n";
    printCard(deck);
    std::cout << "\n";

    // 反転して表示
    deck.reverse();
    std::cout << "reversed:\n";
    printCard(deck);
    std::cout << "\n";

    // デッキトップから13枚を手札に
    std::cout << "draw 13 cards from deck...\n";
    std::list<Card> hands;
    draw(deck, hands, 13);

    std::cout << "deck:\n";
    printCard(deck);
    std::cout << "\nhand:\n";
    printCard(hands);


    return 0;
}