双方向リストを用いて、キャラクター(名前、キャラクター番号)のリストを作成するコードを作っています。
登録したリストの、
①登録順ソート(キャラクター登録時に随時1から順に付加するキャラクター番号を利用)と、
②名前順リスト(アルファベット、漢字、ひらがな、全ての入力に対応)
を作りたいのですが、上手くいきません。
①についてはバブルソートで作りたいです。
バブルソートにこだわりはありません。自分がバブルソートしか使ったことがないため、初めにこう書きました。
以下に新たに作ってみた選択ソートでの並び替えをコードも載せておきます。
↓正直しっくり来ていません。
C++
1// 登録順に並び替え 2CharaList *sortListOrderRegist( CharaList *pList ) 3{ 4 if( nullptr == pList ){ // 異常系 5 return nullptr; 6 } 7 8 CharaNode *pTargetNode; 9 CharaNode *pUnsortNode; 10 CharaNode *pMax; 11 CharaNode *pPrevMax; 12 CharaNode *pSortNode = NULL; 13 14 pUnsortNode = pList->pHead; 15 while( NULL != pUnsortNode ){ 16 pMax = pUnsortNode; 17 pPrevMax = NULL; 18 pTargetNode = pUnsortNode; 19 for( pTargetNode = pUnsortNode; NULL != pTargetNode->pNext; pTargetNode = pTargetNode->pNext ){ 20 // 最大値要素と比較対象要素を比較する 21 if( pTargetNode->pNext->nCharaNum > pMax->nCharaNum ){ 22 // 最大値要素の更新 23 pMax = pTargetNode->pNext; 24 pPrevMax = pTargetNode; 25 } 26 } 27 28 // 最大値要素を未ソートリストから削除 29 if( NULL == pPrevMax ){ 30 pUnsortNode = pMax->pNext; 31 } 32 else { 33 pPrevMax->pNext = pMax->pNext; 34 } 35 36 // 最大値要素をソート済リストの先頭に追加 37 if( NULL == pSortNode ){ 38 pSortNode = pMax; 39 pMax->pNext = NULL; 40 } 41 else { 42 pSortNode->pPrev = pMax; 43 pMax->pNext = pSortNode; 44 pSortNode = pMax; 45 } 46 } 47 if( NULL != pSortNode ){ 48 pSortNode->pPrev = NULL; 49 } 50 pList->pHead = pSortNode; 51} 52 53 54// 名前順に並び替え 55CharaList *sortListOrderName( CharaList *pList ) 56{ 57 if( nullptr == pList ){ //異常系 58 return nullptr; 59 } 60 61 CharaNode *pTargetNode; 62 CharaNode *pUnsortNode; 63 CharaNode *pMax; 64 CharaNode *pPrevMax; 65 CharaNode *pSortNode = NULL; 66 67 pUnsortNode = pList->pHead; 68 while( NULL != pUnsortNode ){ 69 pMax = pUnsortNode; 70 pPrevMax = NULL; 71 pTargetNode = pUnsortNode; 72 for( pTargetNode = pUnsortNode; NULL != pTargetNode->pNext; pTargetNode = pTargetNode->pNext ){ 73 // 最大値要素と比較対象要素を比較する 74 if( pTargetNode->pNext->strName > pMax->strName ){ 75 /* 最大値要素の更新 */ 76 pMax = pTargetNode->pNext; 77 pPrevMax = pTargetNode; 78 } 79 } 80 81 // 最大値要素を未ソートリストから削除 82 if( NULL == pPrevMax ){ 83 pUnsortNode = pMax->pNext; 84 } 85 else { 86 pPrevMax->pNext = pMax->pNext; 87 } 88 89 // 最大値要素をソート済リストの先頭に追加 90 if( NULL == pSortNode ){ 91 pSortNode = pMax; 92 pMax->pNext = NULL; 93 pMax->pPrev = NULL; 94 } 95 else { 96 pSortNode->pPrev = pMax; 97 pMax->pNext = pSortNode; 98 pSortNode = pMax; 99 } 100 } 101 if( NULL != pSortNode ){ 102 pSortNode->pPrev = NULL; 103 } 104 pList->pHead = pSortNode; 105}
以下、リスト構造の定義になります。
C++
1typedef struct CharacterStatus{ 2 string strName; 3 int nCharaNum; // 登録順ソートのため 4 char chFurigana[256]; // 名前順ソートで利用する--- 5 CharacterStatus *pPrev; 6 CharacterStatus *pNext; 7} CharaNode; 8 9typedef struct CharacterNodeList{ 10 CharaNode *pHead; // 先頭のノードを指すポインタ 11 CharaNode *pTail; // 末尾のノードを指すポインタ 12} CharaList;
②について、ひらがなに限定した場合のコードを書いてみたので、これを利用して漢字、アルファベットにも対応させたいです。
以下、(単方向で書いてみた)コードになります。
C++
1CharaList *sortListAscendingOrderByName( CharaList *pList ) 2{ 3 if( nullptr == pList ){//異常系 4 return nullptr; 5 } 6 7 int nNumberOfNodes = 0; 8 //ノード数を数える 9 for( CharaNode *pCurrent = pList->pHead; pCurrent != nullptr; pCurrent = pCurrent->pNext ){ 10 nNumberOfNodes++; 11 } 12 //ノードが0個、1個の場合は処理せず終了 13 if( nNumberOfNodes < 2 ){ 14 return pList; 15 } 16 //ノードが2個の場合 17 else if( 2 == nNumberOfNodes ){ 18 //strcmp(s1, s2)の戻り値: s1 > s2 で正の値、s1 < s2 で負の値、s1 = s2で 0 を返す。 19 if( 0 < strcmp( pList->pHead->chFurigana, pList->pHead->pNext->chFurigana ) ){ 20 //入れ替え用の仮ポインタpTentative 21 CharaNode *pTemporary = pList->pHead->pNext; 22 pList->pHead->pNext = nullptr; 23 pTemporary->pNext = pList->pHead; 24 pList->pHead = pTemporary; 25 pList->pTail = pList->pHead->pNext; 26 return pList; 27 } 28 } 29 //ノードが3個以上の場合 30 else{ 31 while( nNumberOfNodes > 1 ){ 32 //(1)最初の2つのノードの入れ替え((2)では出来ないのでここで行う) 33 if( 0 < strcmp( pList->pHead->chFurigana, pList->pHead->pNext->chFurigana ) ){ 34 CharaNode *pTemporary = pList->pHead->pNext; 35 pList->pHead->pNext = pTemporary->pNext; 36 pTemporary->pNext = pList->pHead; 37 pList->pHead = pTemporary; 38 } 39 //(2)pCurrentが指すノードの1つ先と2つ先のノードを比較し入れ替える 40 CharaNode *pCurrent = pList->pHead; 41 for( int i = 0; i < nNumberOfNodes - 2; i++ ){ 42 if( 0 < strcmp( pCurrent->pNext->chFurigana, pCurrent->pNext->pNext->chFurigana ) ){ 43 //(2-1)最後の2つのノードの入れ替え 44 if( nullptr == pCurrent->pNext->pNext->pNext ){ 45 CharaNode *pTemporary = pCurrent->pNext; 46 pCurrent->pNext = pTemporary->pNext;// 47 pTemporary->pNext = nullptr; 48 pCurrent->pNext->pNext = pTemporary; 49 pList->pTail = pTemporary; 50 } 51 //(2-2)中間の2つのノードの入れ替え 52 else { 53 CharaNode *pTemporary = pCurrent->pNext; 54 pCurrent->pNext = pTemporary->pNext; 55 pTemporary->pNext = pCurrent->pNext->pNext; 56 pCurrent->pNext->pNext = pTemporary; 57 } 58 } 59 pCurrent = pCurrent->pNext; 60 }//end for 61 nNumberOfNodes--; 62 }//end while 63 return pList; 64 }//end if(nNodeNumber) 65}
アドバイス、改善点、見本となるコードなど教えていただきたいです。
よろしくお願いいたします。
pCurrent->pNext->chFurigana で、pCurrent は CharaList へのポインタ、
pCurrent->pNext は CharaNode へのポインタというのは分かるのですが、
chFurigana が何か分かりません。
strcmp で比較するということは char へのポインタのはずですが、
どこにも記述がありません。質問への追記をお願いします。
また、実際のテストデータでどういう結果になるのですか?
どうしてもバブルソートですか?
割と厳しいですよ、それ。
というか、なぜ今回の質問が出てきたのでしょうか?
課題として? それとも自分の作品内での機能として?
C++なら std::list 使えばコード書かずに済むんだが...課題もしくはトレーニングが目的ですか?
コードを見るに、string(std::string)以外はもうC言語ですね。 ワイド文字のstd::wstring をうまく使えるようにすれば「アルファベット、漢字、ひらがな」もほぼいけるようになる気がしますが。あえて苦難の道を選んでいるように思うので、与えられた課題なのか自分で選んだ問題なのか示すと、より回答もいただきやすいかもしれません。学校の課題のようなものだと、回答は避けられがちです。
リスト構造体について学び始めたばかりのため、トレーニングが目的です。
バブルソートにこだわりはありませんが、バブルソート以外使ったことがなくて....
ほかに良い方法があれば、完全なコードがなくても構いませんので、導入部分だけでもご教授願いたいです。
回答2件