プログラマ専用SNS ミクプラ

はじめまして．
今，リスト構造を用いてマージソートのプログラムを作っています．
リストを分割する関数，分割したリストを再結合する関数，そしてマージソートを行う関数の3つで構成するのですが，
リストを分割，再結合する関数はおそらくですが出来ています。(それ単体での動作確認済み)
それぞれの関数を以下の様に作りました．

コード:

struct cell {
  int data;
  struct cell *next;
};

コード:

void mergeList ( struct cell *list1, struct cell *list2, struct cell *merged )
{
  if ( firstCell ( list1 ) != ( struct cell * ) NULL || firstCell ( list2 ) != ( struct cell * ) NULL )
    {

      if ( retrieveCell ( firstCell ( list1 ) ,  list2 ) < retrieveCell ( firstCell ( list2 ) ,  list2 ) 
	 || firstCell ( list2 ) == ( struct cell * ) NULL )
	{
	  insertCell ( retrieveCell ( firstCell ( list1 ) ,  list1 ) ,  ( struct cell * ) NULL ,  merged );
	  mergeList ( nextCell ( list1 ,  list1) ,  list2 ,  merged );
	}
      else if ( retrieveCell ( firstCell ( list1 ) , list2 ) > retrieveCell ( firstCell ( list2 ) ,  list2 ) 
	      || firstCell ( list1 ) == ( struct cell * ) NULL )
	{
	  insertCell ( retrieveCell ( firstCell ( list2 ) , list2 ) ,  ( struct cell * ) NULL ,  merged );
	  mergeList ( list1 , nextCell ( list2 , list2 ), merged );
	}
    }
}

コード:

void divideList ( struct cell *list , struct cell *list1, struct cell *list2 )
{

  if ( firstCell ( list ) != ( struct cell *) NULL )
    {

      insertCell ( retrieveCell ( firstCell ( list ) ,  list ) , ( struct cell *) NULL,  list1 );
      list = nextCell ( list ,  list );
      
      if ( firstCell ( list ) != ( struct cell *) NULL )
	{
	  
	  insertCell ( retrieveCell ( firstCell ( list ) , list ) , ( struct cell *) NULL , list2 );
	  list = nextCell (list , list );

	  divideList (list , list1, list2 );
	}
    }
}

コード:

void mergeSort ( struct cell *list ,  struct cell *sorted )
{

  struct cell *list1;
  list1 = makeNullList ();
  struct cell *list2;
  list2 = makeNullList ();

  struct cell *sorted1;
  sorted1 = makeNullList ();
  struct cell *sorted2;
  sorted2 = makeNullList();

  if( nextCell (firstCell ( list ) , list ) == ( struct cell *) NULL )
    {
      sorted = list;
      return;
    }
  
  divideList ( list ,  list1 ,  list2 );
  
  mergeSort ( list1 ,  sorted1 );

  mergeSort ( list2 ,  sorted2 );

  mergeList ( sorted1 ,  sorted2 ,  sorted );
}

コード:

/* 空リストを作成する関数 */
struct cell *makeNullList ()
{
  struct cell *list;

  /* 動的確保 */
  list = (struct cell *) malloc (sizeof (struct cell));
  if (list == (struct cell *) NULL)
    {
      printf("makeNullList: can not allocate memory for new list.\n");
      exit(1);
    }

  /* 初期化 */
  list->next = (struct cell *) NULL;

  return list;
}


/* 指定されたセルの次のセルへのポインタを返す関数 */
struct cell *nextCell (struct cell *target, struct cell *list)
{
  struct cell *ptr = (struct cell *) NULL;

  if (target != (struct cell *) NULL)
    {
      ptr = target -> next;
    }

  return ptr;
}


/* 連結リストの先頭のセルへのポインタを返す関数 */
struct cell *firstCell (struct cell *list)
{
  struct cell *first = (struct cell *) NULL;
  first = list -> next;

  return first;
}


/* 連端リストの終端のセルへのポインタを返す関数 */
struct cell *endCell (struct cell *list)
{
  struct cell *end = (struct cell *) NULL;

  if (list -> next != (struct cell *) NULL)
    {
      end = list -> next;

      while(end -> next != (struct cell *) NULL)
	{
	  end = end -> next;
	}
    }

  return end;
}


/* 指定されたセルの前のセルへのポインタを返す関数 */
struct cell *previousCell (struct cell *target, struct cell *list)
{
  struct cell *ptr = (struct cell *) NULL;
  ptr = list;
  
  while((ptr -> next) != target)
    {
      ptr = ptr -> next;
    }

  return ptr;
}


/* 新たにセルを作成し、指定された位置に挿入する関数 */
struct cell *insertCell (int data, struct cell *target, struct cell *list)
{
  struct cell *addData;
  addData = makeNullList();

  addData -> data = data;
  addData -> next = target;

  previousCell(target, list) -> next = addData;

  return addData;
}


/* 指定されたセルを指定されたリストから削除する関数 */
struct cell *deleteCell (struct cell *target, struct cell *list)
{
  struct cell *ptr = (struct cell *) NULL;

  if(list == (struct cell *)NULL);
  {
    return ptr;
  }
  
  previousCell(target, list) -> next = nextCell(target, list);
  ptr = nextCell(target, list);
  
  free(target);
  
  return ptr;
}


/* 指定されたセルのデータを返す関数 */
int retrieveCell (struct cell *target, struct cell *list)
{
  if (target != (struct cell *) NULL)
    {
      return (target -> data);
    }

    return 0;
}
 

/* 指定されたデータを値として持つセルへのポインタを返す関数 */
struct cell *locateCell (int data, struct cell *list)
{
  struct cell *ptr = (struct cell *) NULL;
  ptr = firstCell(list);

  while((ptr != (struct cell *) NULL)
	&& (retrieveCell(ptr, list) != data))
    {
      ptr = nextCell(ptr, list);
    }

  return ptr;
}


/* 指定された連結リスト中のすべてのセルを削除する関数 */
void deleteList (struct cell *list)
{
  while(list ->next != (struct cell*) NULL)
    {
      deleteCell(list->next, list);
    }

  free(list);

}


/* 指定されたリストの内容を表示させる関数 */
void printList (struct cell *list)
{
  struct cell *ptr = (struct cell *) NULL;
  ptr = list;


  if (list == (struct cell *) NULL)
    {
      printf("リストが定義されていません.\n");
    }

  else if (ptr -> next == (struct cell *) NULL)
    {
      printf("[ ]\n");
    }
  else 
    {
      printf("[");
      while(ptr -> next != (struct cell *) NULL)
	{
	  printf("%d", retrieveCell(ptr->next, list));
	  if(ptr -> next -> next  != (struct cell *) NULL)
	    {
	      printf(", ");
	    }
	  ptr = ptr -> next;
	}
      printf("]\n");
    }

mergesort関数内の16行目で，その関数内ではsortedにｌｉｓｔの値が束縛されるのですが，
returnで戻って，一つ前の再帰に戻ると引数として与えたはずのlist1，list2に値が入っていません．
retrieve関数でlistの最初の要素の値を読み取り，それをinsertCell関数でsortedに代入すれば可能なのですが，
前者の方法でダメな理由が分かりません．

また，後者の方法で試すと，mergeSort内の26行目でSegmentation faultが出てうまくいきません。
本来ならリストの要素の最後にNULLがあるはずなのですが，
その領域にアクセスしようとするとSegmentation faultが出ます．
ダミーセル→要素→要素→・・・→NULLが正しいはずなのですが，
ダミーセル→要素→要素→・・・→？となっているみたいです．

アルゴリズム自体が正しいのかどうか，Segmentation faultのせいで確認できていないので，
もしかしたら間違っていると思うので，アルゴリズムの訂正も含め，
上記の二項について分かる方，ご教授お願いします．

ちなみに，開発環境はubuntu10.04でgccを使っています．
知識は，初心者～中級者ぐらいだと思います．
ifの多い汚いプログラムだとは思いますが，よろしくお願いします．

mergesort関数内の16行目で，その関数内ではsortedにｌｉｓｔの値が束縛されるのですが，
returnで戻って，一つ前の再帰に戻ると引数として与えたはずのlist1，list2に値が入っていません．

sortedは、mergeSort関数内でのローカル変数なので、その値を関数内でいくら変更しても呼び出し元では変化しません。

コード:

mergeSort(list, sorted); // ポインタの値がコピーが渡されている。

ポインタの値の書き換えを呼び出し元に反映させるのなら、以下のようにしなければならないでしょう。

コード:

void mergeSort ( struct cell *list ,  struct cell **sorted )
{
  /*  前略 */
  *sorted = list;
  /* 後略 */
}

確かにそうでしたね．
ですが，mergeSort関数の仕様は，
リストへのポインタと，ソートしたリストへのポインタを引数にとるので，
引数の仕様は変更できないので，
この方法では実装できないです．
ということは，アルゴリズム全体を見直すか，
値を代入する方法をとる必要がありそうです．

プログラマ専用SNS ミクプラ

リスト構造を用いたマージソートについて

リスト構造を用いたマージソートについて

Re: リスト構造を用いたマージソートについて

Re: リスト構造を用いたマージソートについて