単方向連結リストのインサート?ソート
すでにソートされている単方向連結リストに対して、ソートされている状態が崩れないように
新しい要素を挿入するプログラムを書きました
#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ポインタが必ずリストの先頭を指している状態にできるので、右端にポインタを移動させずともソートを開始でき、計算効率が上昇します。