【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.21853

昇順リスト
投稿者---七瀬(2005/07/11 22:48:02)


WINDOWS2000 gcc cygwin
メモリ上に登録してあるデータを番号の昇順(バブルソートで)にソーティングするソースです。
怪しいところはfor文の条件と並び換え交換の退避の仕方です。(うまくlp2->prevを対比できない!)
注2.mem_headはメモリの先頭アドレス(mainではascend_data(&mem_head)として呼び出している)。 ちなみに宣言はlist_t mem_head;でありその後初期化している。

注:main_headはダミー(構造体本体)でmain_head->nextからデータが入っている。
void ascend_data(list_t *mem_head)
{
    list_t *last = NULL;        /* メモリの最後尾 */

    list_t *lp1=NULL;         /*  */
    list_t *lp2=NULL;         /*  */
    
    list_t *wk_p=NULL;      /* 一時退避作業用ポインタ */
    
    list_t wkdata;
     wk_p = &wkdata;
    
    /* 登録件数がある時 */
    if(gtotal_data_cnt !=0)
    {
        printf("<並び換え>\n");
        
        /* メモリ登録件数が1じゃないとき */
        if(gtotal_data_cnt != 1)
        {    
            
    
            for(lp1 = mem_head->next ; lp1->next != last ; lp1 = lp1->next )  /* 比較作業を止める位置 */
            {
                
                /* メモリの最後尾を探す */
                for(last = mem_head ; last->next!=NULL ; last = last->next);
                
                for(lp2 = last ; lp2->prev != lp1 ;lp2 = lp2->next  ) /* 比較対象となる要素の位置*/
                {
                    if( lp2->prev->num  > lp2->num) /*  */
                    {
                        /* 並び替えを行う */
                        wk_p = lp2->prev;
                        lp2->prev =lp2;
                        lp2 = wk_p;
                    }
                    
                }
            }
            printf("\n\n");
            printf("並び換え完了\n\n");
        }
        else
        {
            printf("データ1つの為、並び換えはありませんでした。\n\n");
        }
    }
    else
    {
        printf("メモリ登録データがありません。\n\n");
        return;
    }
    
}




この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:昇順リスト 21854 まきじ 2005/07/11 23:08:11


No.21854

Re:昇順リスト
投稿者---まきじ(2005/07/11 23:08:11)


>注2.mem_headはメモリの先頭アドレス(mainではascend_data(&mem_head)として呼び出している)。 ちなみに宣言はlist_t mem_head;

宣言は、list_t *mem_head ではないでしょうか?

>for(lp2 = last ; lp2->prev != lp1 ;lp2 = lp2->next)

後ろからソートしてる様なので、
lp2 = lp2->next ではなく、lp2 = lp2->prev ではないでしょうか?


この投稿にコメントする

削除パスワード

No.21856

Re:昇順リスト
投稿者---七瀬(2005/07/11 23:26:49)


>>注2.mem_headはメモリの先頭アドレス(mainではascend_data(&mem_head)として呼び出している)。 ちなみに宣言はlist_t mem_head;
>
>宣言は、list_t *mem_head ではないでしょうか?
既に書かれているもので他の関数も動作確認済みなので大丈夫なはずと思います。

>>for(lp2 = last ; lp2->prev != lp1 ;lp2 = lp2->next)
>
>後ろからソートしてる様なので、
>lp2 = lp2->next ではなく、lp2 = lp2->prev ではないでしょうか?
そうですね。いろいろ修正・デバッグをしているうちに間違えてしまいました。

振り出しに戻ってしまいました。

void ascend_data(list_t *mem_head)
{
    list_t *last = NULL;        /* メモリの最後尾 */

    list_t *lp1=NULL;         /*  */
    list_t *lp2=NULL;         /*  */
    
    list_t *wk_p=NULL;      /* 一時退避作業用ポインタ */
    
    list_t wkdata;
     wk_p = &wkdata;
    
    /* 登録件数がある時 */
    if(gtotal_data_cnt !=0)
    {
        printf("<並び換え>\n");
        
        /* メモリ登録件数が1じゃないとき */
        if(gtotal_data_cnt != 1)
        {    
            
    
            for(lp1 = mem_head->next ; lp1->next != last ; lp1 = lp1->next )  /* 比較作業を止める位置 */
            {
                
                /* メモリの最後尾を探す */
                for(last = mem_head ; last->next!=NULL ; last = last->next);
                
                for(lp2 = last ; lp2->prev != lp1 ;lp2 = lp2->prev  ) /* 比較対象となる要素の位置*/
                {
                    if( lp2->prev->num  > lp2->num) /*  */
                    {
                        /* 並び替えを行う */
                        wk_p = lp2->prev;
                        lp2->prev =lp2;
                        lp2 = wk_p;
                    }
                    
                }
            }
            printf("\n\n");
            printf("並び換え完了\n\n");
        }
        else
        {
            printf("データ1つの為、並び換えはありませんでした。\n\n");
        }
    }
    else
    {
        printf("メモリ登録データがありません。\n\n");
        return;
    }
    
}







この投稿にコメントする

削除パスワード

No.21857

Re:昇順リスト
投稿者---まきじ(2005/07/12 00:23:35)


>既に書かれているもので他の関数も動作確認済みなので大丈夫なはずと思います。

それなら良いですが・・・

#mem_head は、ダミーノードを指していて、そのダミーノードは
#malloc() などで、領域を確保してると思うので
#mem_head は ポインタ変数かと思ったんですけど・・・

>wk_p = lp2->prev;
>lp2->prev =lp2;
>lp2 = wk_p;

繋ぎ換えができていない。
紙に書いたりして、もう一度考えてみて下さい。


この投稿にコメントする

削除パスワード

No.21858

Re:昇順リスト
投稿者---七瀬(2005/07/12 00:55:25)


紙に書いて考えてみましたが、駄目(セグフォ)ですね。
紙上では、うまく退避できたと思うのですが・・・

void ascend_data(list_t *main_head)
{
    list_t *last = NULL;        /* メモリの最後尾 */
    //list_t *list_p;

    
    //list_t *lp1=NULL;   /*  */

    list_t *lp2=NULL;         /*  */
    
    list_t *wk_p=NULL;      /* 一時退避作業用ポインタ */
    list_t wkdata;
      
    int s_loop = 0;
    
     wk_p=&wkdata;
                
    
    /* 登録件数がある時 */
    if(gtotal_data_cnt !=0)
    {
        printf("<並び換え>\n");
        
        /* メモリ登録件数が1じゃないとき */
        if(gtotal_data_cnt != 1)
        {    
            //for(lp1 = main_head ; lp1->next != last ; lp1 = lp1->next )  /* 比較作業を止める位置 */

            for(s_loop = 0 ; s_loop < (gtotal_data_cnt - 1) ; s_loop++ ) 
            {
                
                /* メモリの最後尾を探す */
                for(last = main_head ; last->next!=NULL ; last = last->next);
                
                for(lp2 = last ; lp2->prev != NULL ;lp2 = lp2->prev  ) /* 比較対象となる要素の位置*/
                {
                    if( lp2->prev->num  > lp2->num) /*  */
                    {
                        
                        /* 並び替えを行う */
                        wkdata = *lp2->prev;
                        wk_p = lp2->prev;
                        lp2->prev =lp2;
                        
                        lp2 = wk_p;
                    }
                    
                }
            }
            printf("\n\n");
            printf("並び換え完了\n\n");
        }
        else
        {
            printf("データ1つの為、並び換えはありませんでした。\n\n");
        }
    }
    else
    {
        printf("メモリ登録データがありません。\n\n");
        return;
    }
    
}



この投稿にコメントする

削除パスワード

No.21859

Re:昇順リスト
投稿者---まきじ(2005/07/12 01:10:39)


>wkdata = *lp2->prev;
>wk_p = lp2->prev;
>lp2->prev =lp2;
>lp2 = wk_p;

他の部分は、正常に動作してる事が前提で
繋ぎ換え部分を。

wk_p = lp2 -> prev;
lp2 -> prev = wk_p -> prev;
lp2 -> next = wk_p;
wk_p -> prev = lp2;


この投稿にコメントする

削除パスワード

No.21862

Re:昇順リスト
投稿者---まきじ(2005/07/12 08:56:11)


訂正

>wk_p = lp2 -> prev;
>lp2 -> prev = wk_p -> prev;
wk_p -> prev -> next = lp2; <---------- 追加
>lp2 -> next = wk_p;
>wk_p -> prev = lp2;


この投稿にコメントする

削除パスワード

No.21887

Re:昇順リスト
投稿者---七瀬(2005/07/12 22:37:47)


朝早くからアドバイスありがとうございました。
ただまきじさんのつなぎ換えを紙に書いて考えても、今の私ではわかりませんでした。
(せっかくご提示してくださったのに申し訳ないです。)

そこでもう一度自分で以下のように考えてみました。セグフォは消えたものの無限ループに陥りうまく並び換えできません。

今回変更した点は最小値が左からひとつずつ決まっていくので、それに使う変数minと、退避の時リストから一時的にはずす変数wk_p(lp2->prev)です。

void ascend_data(list_t *main_head)
{
  list_t *last = NULL;    /* メモリの最後尾 */
  //list_t *list_p;

  
  //list_t *lp1=NULL;   /*  */

  list_t *lp2=NULL;   /*  */
  
  list_t *wk_p=NULL;      /* 一時退避作業用ポインタ */
  //list_t wkdata;

    
  list_t *min;          /* 最小値 */
  //int s_loop = 0;

  int s_flag = FLAG_OFF;
   //wk_p=&wkdata;

  min = main_head->next;
        
  
  /* 登録件数がある時 */
  if(gtotal_data_cnt !=0)
  {
    printf("<並び換え>\n");
    
    /* メモリ登録件数が1じゃないとき */
    if(gtotal_data_cnt != 1)
    {    
      /* メモリの最後尾を探す */
      for(last = main_head ; last->next!=NULL ; last = last->next);
      
      //for(lp1 = main_head ; lp1->next != last ; lp1 = lp1->next )  /* 比較作業を止める位置 */

      //for(s_loop = 0 ; s_loop < (gtotal_data_cnt - 1) ; s_loop++ ) 

      while(min != last)
      {
        //for(lp1 = main_head ; lp1->next != last->prev ; lp1 = lp1->next )  /* 比較作業を止める位置 */

        
        /* メモリの最後尾を探す */
        for(last = main_head ; last->next!=NULL ; last = last->next);
        
        for(lp2 = last ; lp2 != min ;lp2 = lp2->prev  ) /* 比較対象となる要素の位置*/
        {
          if( lp2->prev->num  > lp2->num) /*  */
          {
            
            /* 並び替えを行う */
            wk_p = lp2 -> prev;
            
            lp2->prev->prev = lp2;
            lp2->prev = lp2->prev->prev;
            
            lp2->next =wk_p;
            wk_p->prev =lp2;
            
            wk_p->next = lp2->next;
            lp2->next->prev = wk_p;
            
            s_flag = FLAG_ON;
            lp2 = lp2->next;
          }
          
        }
        min = lp2->prev;
      }
      if(s_flag == FLAG_OFF)
      {
        printf("並び替えがありませんでした。");
      }
      printf("\n\n");
      printf("並び換え完了\n\n");
    }
    else
    {
      printf("データ1つの為、並び換えはありませんでした。\n\n");
    }
  }
  else
  {
    printf("メモリ登録データがありません。\n\n");
    return;
  }
  
}




この投稿にコメントする

削除パスワード

No.21888

Re:昇順リスト
投稿者---まきじ(2005/07/12 23:05:09)


>今回変更した点は最小値が左からひとつずつ決まっていくので、それに使う変数minと、退避の時リストから一時的にはずす変数wk_p(lp2->prev)です。

最初に提示したソースで良い様な気がしますが?
繋ぎ換えの部分だけが、できてないみたいですけど。

繋ぎ換え部分は、私が提示したソースでは駄目でしょうか?
# 他が動かなかったら確認しようがないと思いますけど・・・


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧