0

我正在解决一个问题，其中给定一个链接的字符列表，我们必须将元音移动到开头，以便元音和辅音都按时间顺序排列。那是它们在原始列表中出现的顺序。

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

我通过遍历列表一次并创建了两个称为元音和辅音的列表来完成它，然后将它们合并。

可以在不创建额外列表的情况下完成吗？我的意思是就地可能使用指针操作？

4

4 回答 4

1

记住列表的开头。当你遇到一个元音时，把它移到列表的开头；元音成为你记忆中的新开始。

于 2012-09-05T22:15:34.323 回答
0 
#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

于 2012-09-05T23:19:31.843 回答
0 
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;
    }

这是一种抽象的理解。正确实施。

于 2012-09-05T22:24:28.703 回答
0

您可以很容易地修改指针以创建两个独立的列表，而无需实际复制任何节点，这就是我假设您说要避免创建新列表时的意思。仅修改原始节点中的指针。

首先让我们为列表创建结构：

#include <stdio.h>
#include <stdlib.h>

// Structure for singly linked list.

typedef struct sNode {
    char ch;
    struct sNode *next;
} tNode;

接下来我们提供两个实用函数，第一个将字符附加到列表中：

// 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;
}

第二个是为了调试目的转储列表：

// 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');
}

现在这是重要的一点，它将单个列表变成两个不同的列表（一个元音，一个辅音）。哪个列表是哪个类型取决于列表中的第一个条目是什么。

基本上所做的是从列表开头的所有公共节点（在本例中为“ST”）创建一个子列表，下一个不匹配类型的另一个子列表（“A”），以及然后开始一一处理剩余的节点，从“C”开始。

在检查每个后续节点时，会调整指针以将其添加到第一个或第二个列表中（同样，没有实际创建新节点）。一旦我们到达列表末尾的 NULL，我们就决定是否将第二个列表附加到第一个列表，反之亦然（元音必须先出现）。

所有这些指针操作的代码如下所示：

// 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
于 2015-07-31T12:49:27.703 回答