リンクされた文字のリストが与えられた場合、母音と子音の両方が時系列になるように母音を最初に移動する必要があるという問題を解決していました。これは、元のリストに表示される順序です。
Input : S->T->A->C->K->O->V->E->R->F->L->O->W
Output : A->O->E->O->S->T->C->K->V->R->F->L->W
リストを1回トラバースして、母音と子音という2つのリストを作成し、後でそれらをマージしました。
追加のリストを作成せずに実行できますか？インプレースでポインタ操作を使用することを意味しますか？
リストの最初を覚えておいてください。母音に出会ったら、それをリストの最初に移動します。母音はあなたが覚えている新しい始まりになります。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
struct list {
struct list *next;
int ch;
};
#define IS_VOWEL(p) strchr("aeiouy", tolower(p->ch))
struct list *shuffle ( struct list *lst )
{
struct list *new=NULL, **dst, **src;
dst = &new;
for (src = &lst; *src; ) {
struct list *this;
this= *src;
if (!IS_VOWEL(this)) { src= &(*src)->next; continue; }
*src = this->next;
this->next = *dst;
*dst = this;
dst = & (*dst)->next;
}
*dst = lst;
return new;
}
int main (void)
{
struct list arr[] = { {arr+1, 'S'} , {arr+2, 'T'} , {arr+3, 'A'}
, {arr+4, 'C'} , {arr+5, 'K'} , {arr+6, 'O'}
, {arr+7, 'V'} , {arr+8, 'E'} , {arr+9, 'R'}
, {arr+10, 'F'} , {arr+11, 'L'} , {arr+12, 'O'} , {NULL, 'W'} };
struct list *result;
result = shuffle (arr);
for ( ; result; result = result->next ) {
printf( "-> %c" , result->ch );
}
printf( "\n" );
return 0;
}
出力：
-> A-> O-> E-> O-> S-> T-> C-> K-> V-> R-> F-> L-> W
1. Traverse the list
2. When you encounter a vowel, check with head if its smaller or greater
3. If smaller, re-place new vowel before head, else move head and check again
4. In the end relocate head to first
temp = head;
while(current.next != null) {
if(current.isVowel()) {
if(head.isVowel()) {
//check the precedence
//Re-place the current with temp
}
else {
//Re-place current in front of head
}
}
current = current.next;
}
これは抽象的な理解です。適切に実装してください。
ポインタを非常に簡単に変更して、ノードを実際に複製することなく2つの独立したリストを作成できます。これは、新しいリストの作成を避けたいと言うときの意味です。元のノードのポインタのみが変更されます。
まず、リストの構造を作成しましょう。
#include <stdio.h>
#include <stdlib.h>
// Structure for singly linked list.
typedef struct sNode {
char ch;
struct sNode *next;
} tNode;
次に、2つのユーティリティ関数を提供します。最初の関数はリストに文字を追加します。
// Append to list, not very efficient but debug code anyway.
static tNode *append (tNode *head, char ch) {
// Allocate new node and populate it.
tNode *next = malloc (sizeof (tNode));
if (next == NULL) {
puts ("Out of memory");
exit (1);
}
next->ch = ch;
next->next = NULL;
// First in list, just return it.
if (head == NULL)
return next;
// Else get last, adjust pointer and return head.
tNode *this = head;
while (this->next != NULL)
this = this->next;
this->next = next;
return head;
}
そして、デバッグ目的でリストをダンプする2番目：
// Debug code to dump a list.
static void dump (tNode *this) {
if (this == NULL)
return;
printf ("(%08x)%c", this, this->ch);
while ((this = this->next) != NULL)
printf (" -> (%08x)%c", this, this->ch);
putchar ('\n');
}
それを超えて、ノードが母音であるかどうかを判断する簡単な方法が必要です。ここでは、大文字のみを使用します。
// Check for vowel (uppercase only here).
static int isVowel (tNode *this) {
char ch = this->ch;
return (ch == 'A') || (ch == 'E') || (ch == 'I')
|| (ch == 'O') || (ch == 'U');
}
これが重要なビットであり、単一のリストを2つの別個のリスト（1つは母音、もう1つは子音）に変換するビットです。どのリストがどのタイプであるかは、リストの最初のエントリが何であるかによって異なります。
基本的には、リストの先頭にあるすべての共通ノード（この場合は「ST」）からサブリストを作成し、次の一致しないタイプ（「A」）の別のサブリストを作成し、次に、「C」から始めて、残りのノードを1つずつ処理し始めます。
後続の各ノードが調べられると、ポインターが調整されて、最初のリストまたは2番目のリストに追加されます（ここでも、実際に新しいノードを作成することはありません）。リストの最後でNULLに達したら、2番目のリストを最初のリストに追加するか、またはその逆を行うかを決定します（母音が最初に来る必要があります）。
このすべてのポインター操作のコードを以下に示します。
// Meat of the solution, reorganise the list.
static tNode *regroup (tNode *this) {
// No reorg on empty list.
if (this == NULL)
return this;
// Find first/last of type 1 (matches head), first of type 2.
tNode *firstTyp1 = this, *firstTyp2 = this, *lastTyp1 = this, *lastTyp2;
while ((firstTyp2 != NULL) && (isVowel (firstTyp1) == isVowel (firstTyp2 ))) {
lastTyp1 = firstTyp2;
firstTyp2 = firstTyp2->next;
}
// No type 2 means only one type, return list as is.
if (firstTyp2 == NULL)
return firstTyp1;
// Type 2 list has one entry, next node after that is for checking.
lastTyp2 = firstTyp2;
this = firstTyp2->next;
//dump (firstTyp1);
//dump (firstTyp2);
//putchar ('\n');
// Process nodes until list is exhausted.
while (this != NULL) {
// Adjust pointers to add to correct list.
if (isVowel (this) == isVowel (lastTyp1)) {
lastTyp2->next = this->next;
lastTyp1->next = this;
lastTyp1 = this;
} else {
lastTyp1->next = this->next;
lastTyp2->next = this;
lastTyp2 = this;
}
// Advance to next node.
this = this->next;
//dump (firstTyp1);
//dump (firstTyp2);
//putchar ('\n');
}
// Attach last of one list to first of the other,
// depending on which is the vowel list.
if (isVowel (firstTyp1)) {
lastTyp1->next = firstTyp2;
return firstTyp1;
}
lastTyp2->next = firstTyp1;
return firstTyp2;
}
そして最後に、何らかの説明のテストハーネスがなければ、複雑なプログラムは完成しません。したがって、ここでは、リストを初期形式で作成してダンプし、再編成して結果をダンプします。
int main (void) {
char *str = "STACKOVERFLOW";
tNode *list = NULL;
while (*str != '\0')
list = append (list, *(str++));
dump (list);
puts("");
list = regroup (list);
dump (list);
return 0;
}
すべてのコードを入力、コンパイル、および実行すると、期待どおりの結果が得られます。
(09c03008)S -> (09c03018)T -> (09c03028)A -> (09c03038)C ->
(09c03048)K -> (09c03058)O -> (09c03068)V -> (09c03078)E ->
(09c03088)R -> (09c03098)F -> (09c030a8)L -> (09c030b8)O ->
(09c030c8)W
(09c03028)A -> (09c03058)O -> (09c03078)E -> (09c030b8)O ->
(09c03008)S -> (09c03018)T -> (09c03038)C -> (09c03048)K ->
(09c03068)V -> (09c03088)R -> (09c03098)F -> (09c030a8)L ->
(09c030c8)W
読みにくい場合は、ポインタを削除して、文字を順番にリストします。
S -> T -> A -> C -> K -> O -> V -> E -> R -> F -> L -> O -> W
A -> O -> E -> O -> S -> T -> C -> K -> V -> R -> F -> L -> W