拆分 C 中的字符链表

Question

我应该编写一个名为“disAssemblyList”的函数来获取字符链表（没有虚拟元素）。该函数应该将具有大字母的节点移动到“bigLetter”链表（没有虚拟元素），将具有小字母的节点移动到“smallLetter”链表，将 nums 移动到“nums”链表，其他字符保留在原始列表中。

我需要通过引用传递 smallLetter、bigLetter 和 nums 链表以及 return 包含其他字符的列表。

我需要扫描原始列表。原始列表可以为空。

例如：

原始链表：

3-> a-> 7-> M-> K-> u-> 5-> #-> &-> P-> %-> A

bigLetter:

M-> K-> P-> A

smallLetter:

a-> u

nums:

3-> 7-> 5

其他字符（函数运行后的原始列表）：

#-> &-> %

我写了这段代码，但我似乎无法理解如何让它工作。 它不扫描字符到链表。

typedef struct chNode
{
    char data;
    struct chNode *next;
}chNode;


chNode * createCharList(char data)
{
    chNode *temp = (chNode*)malloc(sizeof(chNode));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

chNode * addCharToLast(chNode *head, char data)
{
    chNode *p = head;
    chNode *temp = createCharList(data);
    if (head == NULL)
        return temp;
    while (p->next != NULL)
        p = p->next;
    p->next = temp;
    return head;
}

void printf_CharList(chNode *head)
{
    chNode *p = head;
    while (p != NULL)
    {
        printf("%d, ", p->data);
        p = p->next;
    }
    printf("\n\n");
}


chNode* insert_Charlist() // A function that imports numbers into a linked list , till -1
{
    char ch;
    chNode *Head = NULL;
    printf("Enter chars For Linked-List Till 'Enter':\n");
    //5scanf_s("%c", &ch);
    ch = getchar();
    while (ch != "\n")
    {

        Head = addCharToLast(Head, ch); //Makes last number to be First
        //scanf_s("%c", &ch);
        ch = getchar();
    }
    return Head;
}

void add_to_other_list(chNode** head, chNode* p)
{
    static chNode* tail = NULL;

    p->next = NULL;
    if (tail == NULL)
    {
        *head = p;
    }
    else
    {
        tail->next = p;
    }
    tail = p;
}


chNode* disAssemblyList(chNode* p, chNode **bigLetter, chNode **smallLetter, chNode **nums)
{
    chNode* t = NULL;

    if (p == NULL) return p;          // 0 elements
    if (p->next == NULL) return p;    // 1 element
    if (p->next->next == NULL)          // 2 elements
    {

        if ((p->next->data >= 65) && (p->next->data) <= 90)
        {
            // Move p->next to other list
            add_to_other_list(&(*bigLetter), p->next);
            p->next = NULL;
            return p;
        }
    }

    // Repeat as long as the list has minimum 3 elements
    while (p->next)
    {
        if ((p->next->data >= 65) && (p->next->data) <= 90)
        {
            // Move p-next
            t = p->next;
            p->next = p->next->next;
            add_to_other_list(&(*bigLetter), t);
        }

        if ((p->next->data >= 97) && (p->next->data) <= 122)
        {
            t = p->next;
            p->next = p->next->next;
            add_to_other_list(&(*smallLetter), t);
        }

        if ((p->next->data >= 48) && (p->next->data) <= 57)
        {
            t = p->next;
            p->next = p->next->next;
            add_to_other_list(&(*nums), t);

        }
        p = p->next;
    }

    return p;

}


void main()
{

    chNode *Orignial_list = NULL;
    chNode *bigLetter = NULL;
    chNode *smallLetter = NULL;
    chNode *nums = NULL;
    Orignial_list = insert_Charlist(); // Function that imports a list
    printf("You Entered This linked-list:\n");
    printf_CharList(Orignial_list); //Printing the linked list
    Orignial_list = disAssemblyList(Orignial_list,&bigLetter,&smallLetter,&nums);
    printf("The BigLetter Linked-List is:\n");
    printf_CharList(bigLetter);
    printf_CharList(smallLetter);
    printf_CharList(nums);
    printf_CharList(Orignial_list);
    getch();

}

Answer 1

我没有查看您的所有代码，因为据我了解，问题是关于一个将原始列表拆分为其他列表的函数实现。

尽管我确信您的代码中存在缺陷，例如函数 print_CharList 输出字符的内部代码，而不是本身存储在列表中的字符。

void printf_CharList(chNode *head)
{
    chNode *p = head;
    while (p != NULL)
    {
        printf("%d, ", p->data);
        p = p->next;
    }
    printf("\n\n");
}

或者带有静态变量的函数add_to_other_list没有意义。

或者函数开头的这个条件disAssemblyList

if (p->next == NULL) return p;    // 1 elementNevertheless the function

同样没有意义。

不过，拆分列表的函数看起来就像下面的演示程序所示。

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

typedef struct chNode
{
    char data;
    struct chNode *next;
} chNode;

void clear( chNode **head )
{
    while ( *head != NULL )
    {
        chNode *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}

size_t assign( chNode **head, const char *s )
{
    if ( *head ) clear( head );
    
    size_t n = 0;
    
    while ( *s && ( *head = malloc( sizeof( chNode ) ) ) != NULL )
    {
        ( *head )->data = *s++;
        ( *head )->next = NULL;
        head = &( *head )->next;
        ++n;
    }
    
    return n;
}

FILE * display( const chNode *head, FILE *fp )
{
    for ( ; head != NULL; head = head->next )
    {
        fprintf( fp, "%c -> ", head->data );
    }
    
    fputs( "null", fp );
    
    return fp;
}

chNode * disAssemblyList( chNode *p, 
                          chNode **bigLetter, 
                          chNode **smallLetter, 
                          chNode **nums )
{
    while ( *bigLetter ) bigLetter = &( *bigLetter )->next;
    while ( *smallLetter ) smallLetter = &( *smallLetter )->next;
    while ( *nums ) nums = &( *nums )->next;

    chNode **head = &p;
    
    while ( *head != NULL )
    {
        if ( isdigit( ( unsigned char )( *head )->data ) )
        {
            *nums = *head;
            *head = ( *head )->next;
            ( *nums )->next = NULL;
            nums = &( *nums )->next;
        }
        else if ( isupper( ( unsigned char )( *head )->data ) )
        {
            *bigLetter = *head;
            *head = ( *head )->next;
            ( *bigLetter )->next = NULL;
            bigLetter = &( *bigLetter )->next;
        }
        else if ( islower( ( unsigned char )( *head )->data ) )
        {
            *smallLetter = *head;
            *head = ( *head )->next;
            ( *smallLetter )->next = NULL;
            smallLetter = &( *smallLetter )->next;
        }
        else
        {
            head = &( *head )->next;
        }
    }
    
    return p;
}   

int main(void) 
{
    chNode *head = NULL;
    
    assign( &head, "3a7MKu5#&P%A" );
    
    fputc( '\n', display( head, stdout ) );
    
    putchar( '\n' );
    
    chNode *bigLetter = NULL;
    chNode *smallLetter = NULL;
    chNode *nums = NULL;
    
    head = disAssemblyList( head, &bigLetter, &smallLetter, &nums );
    
    fputc( '\n', display( head, stdout ) );
    fputc( '\n', display( bigLetter, stdout ) );
    fputc( '\n', display( smallLetter, stdout ) );
    fputc( '\n', display( nums, stdout ) );
    
    clear( &head );
    clear( &bigLetter );
    clear( &smallLetter );
    clear( &nums );

    return 0;
}

程序输出为

3 -> a -> 7 -> M -> K -> u -> 5 -> # -> & -> P -> % -> A -> null

# -> & -> % -> null
M -> K -> P -> A -> null
a -> u -> null
3 -> 7 -> 5 -> null

如果不允许使用 header <ctype.h> 中的标准 C 函数，那么函数 disAssemblyList 中的 while 循环可能看起来像

    while ( *head != NULL )
    {
        char c = ( *head )->data;

        if ( '0' <= c && c <= '9' )
        {
            *nums = *head;
            *head = ( *head )->next;
            ( *nums )->next = NULL;
            nums = &( *nums )->next;
        }
        else if ( 'A' <= c && c <= 'Z' )
        {
            *bigLetter = *head;
            *head = ( *head )->next;
            ( *bigLetter )->next = NULL;
            bigLetter = &( *bigLetter )->next;
        }
        else if ( 'a' <= c && c <= 'z' )
        {
            *smallLetter = *head;
            *head = ( *head )->next;
            ( *smallLetter )->next = NULL;
            smallLetter = &( *smallLetter )->next;
        }
        else
        {
            head = &( *head )->next;
        }
    }

Answer 2

您的代码中有一些小问题和 2 个大问题。

首先是小问题：

该代码不包含所需的包含：
```
  #include <stdio.h>
  #include <stdlib.h>
```
好的，我假设它们存在于您的真实代码中（是，不是吗）
代码声明了一个 void main()。除了特殊情况（例如构建内核的独立环境），您必须使用 int main() 和 return 值
您正在 while (ch != "\n") 比较 insert_Charlist 中的 char 和 char *。应该是：
```
  while (ch != '\n')
```
您未能释放分配的内存。这不是什么大问题，因为它会在程序结束时被 return 编辑到环境中，但最佳实践建议始终 free 已经 malloc 编辑的内容。

现在是认真的。 add_to_other_list 和 disAssemblyList 这两个基本功能都被完全破坏了。现在是学习如何使用调试器单步执行代码并查看会发生什么的时候了。更糟糕的是，它们的一般逻辑被破坏了，我不得不重写它们：

void add_to_other_list(chNode** head, chNode* p)
{
    static chNode* tail;

    p->next = NULL;
    if (*head == NULL)
    {
        *head = p;
    }
    else
    {
        for (tail=*head; tail->next != NULL; tail = tail->next);  //skip to end of list
        tail->next = p;
    }
}

chNode* disAssemblyList(chNode* head, chNode **bigLetter, chNode **smallLetter, chNode **nums)
{
    chNode dummy = {0, head};  // build a dummy node to start one before current head
    chNode *p = &dummy;
    chNode* t;

    // Repeat as long as the list has minimum 1 element to process
    while (p->next)
    {
        if ((p->next->data >= 65) && (p->next->data) <= 90)
        {
            // Move p-next
            t = p->next;
            p->next = p->next->next;
            add_to_other_list(&(*bigLetter), t);
        }

        else if ((p->next->data >= 97) && (p->next->data) <= 122)
        {
            t = p->next;
            p->next = p->next->next;
            add_to_other_list(&(*smallLetter), t);
        }

        else if ((p->next->data >= 48) && (p->next->data) <= 57)
        {
            t = p->next;
            p->next = p->next->next;
            add_to_other_list(&(*nums), t);

        }
        else p = p->next;   // only advance p if p->next has not been moved
    }

    return dummy.next;

}

拆分 C 中的字符链表

split linked list of chars in C

c

split

linked-list

singly-linked-list

function-definition