単方向連結リストのインサート？ソート

備忘録 プログラミング

すでにソートされている単方向連結リストに対して、ソートされている状態が崩れないように
新しい要素を挿入するプログラムを書きました

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define MAX 100
typedef struct link_tag{
  struct link_tag* next;
  int id;
}link_list;

void LeftInsert(link_list **head,link_list *p,link_list *obj)
{
  if(p == *head){
    obj->next = *head;
    *head = obj;
  }else{
  link_list *pp = *head;
  while(pp->next != p)
    pp = pp->next;
  pp->next = obj;
  obj->next = p;
  }
}

void RightInsert(link_list *p,link_list *obj)
{
    obj->next = p->next;
    p->next = obj;
}
void InsertList(link_list **head,link_list *obj)
{
  if(!(*head)){
    *head = obj;
    return;
  }
  link_list *p = *head;
  if((*head)->id > obj->id){
    LeftInsert(head,p,obj);
    return;
  }else{
    while(p->next)
      if(obj->id > p->next->id)
        p = p->next;
    else
      break;
  }
  RightInsert(p,obj);
}

link_list* CreateLink()
{
  link_list *obj;
  if(!(obj = (link_list*)malloc(sizeof(link_list)))){
    fprintf(stderr,"memory secure error\n");
    exit(1);
  }
  obj->id = rand() % MAX;
  obj->next = NULL;
  return obj;
}

int main()
{
  int i;
  srand((unsigned int)time(NULL));
  link_list *head=NULL,*p;
  for(i=0;i<MAX;i++)
    InsertList(&head,CreateLink());
  p = head;
  while(p){
    printf("%d\n",p->id);
    p = p->next;
  }
}

インサートソートというよりはリストに要素を追加する際にソート済みになるように要素を挿入しているって感じです
すでにあるリストをソートしてる訳ではないのでインサートソートといえるのかちょっと微妙です
双方向リストのインサートソートを書いたときと比べると、コードも簡潔で短くなっていて成長を感じます
headポインタのポインタを関数に持っていくと、先頭を指すポインタが呼び出し先で変更できるので、そこを活かしました。双方向リストのときは、先頭のポインタを呼び出し先で変更するアイデアがなかったので、とりあえずリストの末端に行って、そこから左に調べていくという方法をとっていました（そもそも単方向連結リストだとすぐに左にいくことができず、計算量が大変なことになる）。この方法を採用すれば、headポインタが必ずリストの先頭を指している状態にできるので、右端にポインタを移動させずともソートを開始でき、計算効率が上昇します。

大番長完結！

無茶苦茶モードをクリアして大番長コンプしました！
全キャラキャラクリして最大LVと最大BPも狙って上げてきていたので、
モード自体は楽に攻略できました
全クリしたので感想みたいなものを↓

アリスのゲームだけあってなかなかの中毒性
寝る時間とか土日を削ってPCにかじりついてやってました。
土日は昼飯を食う時間すら惜しかったですね...
主人公の斬真狼牙君、ゲーム中の顔は男前なんですけど、パッケージの顔は写りが悪いのかオネエっぽい...

14年前のゲームにしてはだいぶ良いものだとは思いますが、
えっちなCGが絵師によってばらつきが大きく、あまり統一性がないことにやや不満が残りました
ヒロインだと高羽のCGがやたら気合が入ってるんですが扇奈のCGはいまひとつ足りない感じがします
キャラがたくさんいるので製作の都合上仕方ないんですかね

OPのDash! To Truthいい曲だからきいて

Dash! To Truth

f:id:xxxasdfghjk999:20170710225653p:plain

大番長キャラクリ＆CGコンプ

大番長8周目おわりー
ついにCGとキャラクリが全部埋まりました！！！
長かった...
f:id:xxxasdfghjk999:20170710191335p:plainf:id:xxxasdfghjk999:20170710191338p:plainf:id:xxxasdfghjk999:20170710191348p:plain
↑ハードモードだとこんなリザルトが出てくるのね
次は無茶苦茶モードに挑戦して、それで大番長はおわりにしようかな