VC98 とストラウストラップのプログラミング入門３（リスト）

2024年6月19日

柴犬は今日も熟睡しています。何の不安も感じていない幸せそうな顔しています。

概要

「ストラウストラップのプログラミング入門」を読み進めています。

12章から16章までとばして、今、第3部の「データとアルゴリズム」に入っています。

1000ページを超える厚い本ですが得るところが多い本です。

プログラミング関係の本の中で特にお気に入りの本です。

ベクタとフリーストア（リスト）

P547のアドレスの連鎖というリストの作り方が印象的で新鮮に思ったので記録します。

構造体のメンバーはデフォルトでは public なので次のようなコードになります。

copy

struct Link {
  string value;
  Link* prev;
  Link* succ;
  Link(const string& v, Link* p = 0, Link* s = 0)
	:value(v), prev(p), succ(s) {}
}

Link* insert(Link* p, Link* n) {
  n -> succ = p;                //①
  p -> prev -> succ = n;        //②
  n -> prev  = p -> prev;       //③
  p -> prev = n;                //④
  return n;
}

①～④までの関係を図示してみました。

②③は④の前に行わなければいけません。

ゼロ（pre = 0, succ = 0）から始めると、②はエラーとなるので修正します。

Link* insert(Link* p, Link* n) {
  n -> succ = p;                //①
  p -> prev -> succ = n;        //②
  n -> prev  = p -> prev;       //③
  p -> prev = n;                //④
  return n;
}

copy

#include <string>
#include "std_lib_facilities.h"

struct Link {
	string value;
	Link* prev;
	Link* succ;
	Link(const string& v, Link* p = 0, Link* s = 0)
		:value(v), prev(p), succ(s) {}
};

Link* insert(Link* p, Link* n) {
  if (n == 0) return p;
  if (p == 0) return n;
  n -> succ = p;    
  if (n -> prev) {p -> prev -> succ = n;}
  n -> prev  = p -> prev;
  p -> prev = n;
  return n;
}

int main() {
  
  Link* norse_gods = insert(0, new Link("Thor"));
  norse_gods = insert(norse_gods, new Link("Odin"));
  norse_gods = insert(norse_gods, new Link("Freia"));

  cout << "norse_gods :" <<  norse_gods -> value << " \n";
  keep_window_open();
  return 0;
}

上のコードは本では次のようになっていますが、

Link* norse_gods = new Link("Thor");

insert() のコードから次のように変更してみました。

ついつい本のコードを変えてみたくなるように、ストラウストラップ先生は書いています。こういうところがこのような厚い本を飽きさせず読み進めるところなのでしょう。

Link* norse_gods = insert(0, new Link("Thor"));

VC++ でビルド

エラーもなく無事ビルドできました。

実行ファイルも出来ています。

実行ファイルを実行してみました。

最後に挿入したのが「Freia」ですので、リストのトップは「Freia」です。期待通りの結果です。

ここまでとします。