1

以下は、特定の問題を解決するために私が書いたコードです。しかし、2 つのエッジ ケースの解決に問題があります。最初の要素自体が母音の場合と、最後の要素が母音の場合です。最初のエッジ ケースについては、母音が見つかるまでリストを反復処理し、そのノードの前にヘッド ノードを挿入し、ヘッド ポインタを更新することで解決できると思います。しかし、最後の要素が母音である 2 番目のケースでは、その場合、私のコードは無限ループに陥っています。その特定のケースをどのように処理できますか？また、問題を解決するための別のアプローチを提案できる場合は、そうしてください。可能であれば、コードに適用できるあらゆる種類の改善を提案してください。

#include<iostream>

using namespace std;

struct node
{
    char ch;
    node *next;
};

void enqueue (node **head, node **tail, char val)
{
    node *newn = (node *)malloc(sizeof(node));
    newn->ch = val;
    newn->next = NULL;

    if (*head == NULL)
    {
        *head = newn;
        *tail = newn;
    }

    (*tail)->next = newn;
    (*tail) = newn;

}

void print (node *head)
{
    while (head!=NULL)
    {
        cout<<head->ch<<" ";
        head = head->next;
    }
    cout<<endl;
}

bool isVowel (char ch)
{
    ch = ch | 32;

    if (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u')
        return true;
    return false;

}



node* segregateVowels (node *head, node *tail)
{
    if (head == NULL)
        return head;

    node *temp = head;
    node *fin = tail;

    while (temp!=fin)
    {
        cout<<temp->ch<<" "<<fin->ch<<endl;
        getchar();
        if (isVowel(temp->next->ch))
        {
            node *shift = temp->next;
            temp->next = temp->next->next;
            tail->next = shift;
            shift->next = NULL;
            tail = shift;
        }
        else
            temp = temp->next;

    }
    return head;

}


int main()
{
    srand(time(NULL));

    node *head = NULL, *tail = NULL;

    int i = 20;

    while (i>=0)
    {
        enqueue (&head, &tail, rand()%26+65);
        i--;
    }

    print(head);


    head = segregateVowels (head, tail);


    print(head);
}
4

1 に答える 1

1

最後の要素が母音である 2 番目のエッジ ケースを処理するには:

while (temp!=fin)

と

while (temp->next!=fin)

実際には、 のデータをチェックする必要はありませんfin。母音であれば、すでに最後まで分離されています。子音であれば条件も満たします。いずれにせよ、結果には影響しません。もちろん、サイズが 1 の場合は、他のいくつかのケースを処理する必要があります。

最初のエッジ ケースの処理は簡単です。

ヘッド ノードの母音をチェックする小さな if 条件を記述し、それに応じてwhileループの開始前にポインターを更新します。これで完了です。

別の簡単なアプローチがあります。二重にリンクされたリストであると仮定します...

head(リストの先頭を指す) とtail(リストの末尾を指す) の2 つのポインターを取得します。次のコードを理解してみてください。

int head_count=1, tail_count=linked_list_size;
while(head_count<tail_count)
{
     while(!isvowel(head->data) && head_count<=linked_list_size)
     {
         head=head->next;
         head_count++;
     }
     while(isvowel(tail->data) && tail_count>0)
     {
          tail=tail->prev;
          tail_count--;
      }
     if(tail_count>head_count)
     {//swap the values..
          char tmpc = head->data;
          head->data = tail->data;
          tail->data = head->data;
     } 
 }

時間の複雑さ:O(N) 空間の複雑さ:O(1)

O(N)...の余分なスペースを使用する別のアプローチ

  • 2 つの配列を作成します..vowelsとconsonants配列.
  • リンクされたリストを最後まで解析し、すべての文字をそれぞれの配列に格納します。
  • リンクされたリストのデータを最初にvowels配列の文字で上書きし、次に子音配列で上書きします。

時間の複雑さ:O(N)

于 2013-07-15T18:40:46.400 に答える