質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

解決済

線形リスト(双方向)のソートの方法を教えてください。

don
don

総合スコア10

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

2回答

0評価

0クリップ

433閲覧

投稿2022/06/06 14:42

編集2022/06/11 05:26

双方向リストを用いて、キャラクター(名前、キャラクター番号)のリストを作成するコードを作っています。
登録したリストの、
①登録順ソート(キャラクター登録時に随時1から順に付加するキャラクター番号を利用)と、
②名前順リスト(アルファベット、漢字、ひらがな、全ての入力に対応)
を作りたいのですが、上手くいきません。

①についてはバブルソートで作りたいです。
バブルソートにこだわりはありません。自分がバブルソートしか使ったことがないため、初めにこう書きました。
以下に新たに作ってみた選択ソートでの並び替えをコードも載せておきます。
↓正直しっくり来ていません。

C++

// 登録順に並び替え CharaList *sortListOrderRegist( CharaList *pList ) { if( nullptr == pList ){ // 異常系 return nullptr; } CharaNode *pTargetNode; CharaNode *pUnsortNode; CharaNode *pMax; CharaNode *pPrevMax; CharaNode *pSortNode = NULL; pUnsortNode = pList->pHead; while( NULL != pUnsortNode ){ pMax = pUnsortNode; pPrevMax = NULL; pTargetNode = pUnsortNode; for( pTargetNode = pUnsortNode; NULL != pTargetNode->pNext; pTargetNode = pTargetNode->pNext ){ // 最大値要素と比較対象要素を比較する if( pTargetNode->pNext->nCharaNum > pMax->nCharaNum ){ // 最大値要素の更新 pMax = pTargetNode->pNext; pPrevMax = pTargetNode; } } // 最大値要素を未ソートリストから削除 if( NULL == pPrevMax ){ pUnsortNode = pMax->pNext; } else { pPrevMax->pNext = pMax->pNext; } // 最大値要素をソート済リストの先頭に追加 if( NULL == pSortNode ){ pSortNode = pMax; pMax->pNext = NULL; } else { pSortNode->pPrev = pMax; pMax->pNext = pSortNode; pSortNode = pMax; } } if( NULL != pSortNode ){ pSortNode->pPrev = NULL; } pList->pHead = pSortNode; } // 名前順に並び替え CharaList *sortListOrderName( CharaList *pList ) { if( nullptr == pList ){ //異常系 return nullptr; } CharaNode *pTargetNode; CharaNode *pUnsortNode; CharaNode *pMax; CharaNode *pPrevMax; CharaNode *pSortNode = NULL; pUnsortNode = pList->pHead; while( NULL != pUnsortNode ){ pMax = pUnsortNode; pPrevMax = NULL; pTargetNode = pUnsortNode; for( pTargetNode = pUnsortNode; NULL != pTargetNode->pNext; pTargetNode = pTargetNode->pNext ){ // 最大値要素と比較対象要素を比較する if( pTargetNode->pNext->strName > pMax->strName ){ /* 最大値要素の更新 */ pMax = pTargetNode->pNext; pPrevMax = pTargetNode; } } // 最大値要素を未ソートリストから削除 if( NULL == pPrevMax ){ pUnsortNode = pMax->pNext; } else { pPrevMax->pNext = pMax->pNext; } // 最大値要素をソート済リストの先頭に追加 if( NULL == pSortNode ){ pSortNode = pMax; pMax->pNext = NULL; pMax->pPrev = NULL; } else { pSortNode->pPrev = pMax; pMax->pNext = pSortNode; pSortNode = pMax; } } if( NULL != pSortNode ){ pSortNode->pPrev = NULL; } pList->pHead = pSortNode; }

以下、リスト構造の定義になります。

C++

typedef struct CharacterStatus{ string strName; int nCharaNum; // 登録順ソートのため    char chFurigana[256]; // 名前順ソートで利用する--- CharacterStatus *pPrev; CharacterStatus *pNext; } CharaNode; typedef struct CharacterNodeList{ CharaNode *pHead; // 先頭のノードを指すポインタ CharaNode *pTail; // 末尾のノードを指すポインタ } CharaList;

②について、ひらがなに限定した場合のコードを書いてみたので、これを利用して漢字、アルファベットにも対応させたいです。
以下、(単方向で書いてみた)コードになります。

C++

CharaList *sortListAscendingOrderByName( CharaList *pList ) { if( nullptr == pList ){//異常系 return nullptr; } int nNumberOfNodes = 0; //ノード数を数える for( CharaNode *pCurrent = pList->pHead; pCurrent != nullptr; pCurrent = pCurrent->pNext ){ nNumberOfNodes++; } //ノードが0個、1個の場合は処理せず終了 if( nNumberOfNodes < 2 ){ return pList; } //ノードが2個の場合 else if( 2 == nNumberOfNodes ){ //strcmp(s1, s2)の戻り値: s1 > s2 で正の値、s1 < s2 で負の値、s1 = s2で 0 を返す。 if( 0 < strcmp( pList->pHead->chFurigana, pList->pHead->pNext->chFurigana ) ){ //入れ替え用の仮ポインタpTentative CharaNode *pTemporary = pList->pHead->pNext; pList->pHead->pNext = nullptr; pTemporary->pNext = pList->pHead; pList->pHead = pTemporary; pList->pTail = pList->pHead->pNext; return pList; } } //ノードが3個以上の場合 else{ while( nNumberOfNodes > 1 ){ //(1)最初の2つのノードの入れ替え((2)では出来ないのでここで行う) if( 0 < strcmp( pList->pHead->chFurigana, pList->pHead->pNext->chFurigana ) ){ CharaNode *pTemporary = pList->pHead->pNext; pList->pHead->pNext = pTemporary->pNext; pTemporary->pNext = pList->pHead; pList->pHead = pTemporary; } //(2)pCurrentが指すノードの1つ先と2つ先のノードを比較し入れ替える CharaNode *pCurrent = pList->pHead; for( int i = 0; i < nNumberOfNodes - 2; i++ ){ if( 0 < strcmp( pCurrent->pNext->chFurigana, pCurrent->pNext->pNext->chFurigana ) ){ //(2-1)最後の2つのノードの入れ替え if( nullptr == pCurrent->pNext->pNext->pNext ){ CharaNode *pTemporary = pCurrent->pNext; pCurrent->pNext = pTemporary->pNext;// pTemporary->pNext = nullptr; pCurrent->pNext->pNext = pTemporary; pList->pTail = pTemporary; } //(2-2)中間の2つのノードの入れ替え else { CharaNode *pTemporary = pCurrent->pNext; pCurrent->pNext = pTemporary->pNext; pTemporary->pNext = pCurrent->pNext->pNext; pCurrent->pNext->pNext = pTemporary; } } pCurrent = pCurrent->pNext; }//end for nNumberOfNodes--; }//end while return pList; }//end if(nNodeNumber) }

アドバイス、改善点、見本となるコードなど教えていただきたいです。
よろしくお願いいたします。

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

kazuma-s

2022/06/06 16:15

pCurrent->pNext->chFurigana で、pCurrent は CharaList へのポインタ、 pCurrent->pNext は CharaNode へのポインタというのは分かるのですが、 chFurigana が何か分かりません。 strcmp で比較するということは char へのポインタのはずですが、 どこにも記述がありません。質問への追記をお願いします。 また、実際のテストデータでどういう結果になるのですか?
BeatStar

2022/06/06 23:01

どうしてもバブルソートですか? 割と厳しいですよ、それ。 というか、なぜ今回の質問が出てきたのでしょうか? 課題として? それとも自分の作品内での機能として?
episteme

2022/06/07 04:13

C++なら std::list 使えばコード書かずに済むんだが...課題もしくはトレーニングが目的ですか?
dodox86

2022/06/07 07:56

コードを見るに、string(std::string)以外はもうC言語ですね。 ワイド文字のstd::wstring をうまく使えるようにすれば「アルファベット、漢字、ひらがな」もほぼいけるようになる気がしますが。あえて苦難の道を選んでいるように思うので、与えられた課題なのか自分で選んだ問題なのか示すと、より回答もいただきやすいかもしれません。学校の課題のようなものだと、回答は避けられがちです。
don

2022/06/07 13:39

リスト構造体について学び始めたばかりのため、トレーニングが目的です。 バブルソートにこだわりはありませんが、バブルソート以外使ったことがなくて.... ほかに良い方法があれば、完全なコードがなくても構いませんので、導入部分だけでもご教授願いたいです。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。