C和指针 第12章 使用结构和指针 12.8 编程练习

1. 编写一个函数，用于计数一个单链表的节点个数。它的唯一参数就是一个指向链表第1个节点的指针。编写这个函数时，必须知道哪些信息？这个函数还能用于执行其他任务吗？
解析：
这个函数很简单，虽然它只能用于所声明的那种类型的节点---你必须知道节点的内部结构。第13章将讨论这个问题的技巧。 
如果这个函数被调用时传递给它的是一个指向链表中间位置某个结点的指针，那么它将对链表中这个节点以后的节点进行计数。 
/*
**singly_linked_list_node.h 
*/
#ifndef SINGLY_LINKED_LIST_NODE_H
#define SINGLY_LINKED_LIST_NODE_H

typedef struct NODE{
    struct NODE *link;
    int value;
} Node;

extern int sll_count_nodes( struct NODE *first );
extern void sll_free( Node *current );
#endif

/*
** 在单链表中计数节点的个数。 
** program_1_sll_count_nodes.cpp。 
*/
#include <stdio.h>
#include <stdlib.h>
#include "singly_linked_list_node.h" 

int sll_count_nodes( struct NODE *first ){
    int count;
    
    for( count = 0; first != NULL; first = first->link ){
        count += 1;
    }
    
    return count;

}

void sll_free( Node *current ){
    Node *pt;
    Node *temp;
     
    pt = current;
    /*
    ** A very important thing: store the next node address beforehand.
    ** Otherwise after free function, the next node address stored previous node will be destroyed.
    */
    while( pt ){
        temp = pt->link;
        printf( "after temp = pt->link, pt = %p, temp = %p\n", pt, temp );
        free( pt );
        printf( "after free( pt ), pt = %p, pt->link = %p\n", pt, pt->link );
        pt = temp;
        printf( "after pt = temp, pt = %p\n", pt );
    }
}

/*
** program_1_main.cpp。 
*/ 
#include <stdio.h>
#include <stdlib.h>
#include "singly_linked_list_node.h" 

int main( void ){
    Node *head;
    Node *p;
    Node *pnode, *pnode2, *pnode3, *pnode4;
    int count; 
    
    pnode = (Node *)malloc( sizeof(Node) );
    pnode2 = (Node *)malloc( sizeof(Node) );
    pnode3 = (Node *)malloc( sizeof(Node) );
    pnode4 = (Node *)malloc( sizeof(Node) ); 
    if( pnode && pnode2 && pnode3 && pnode4 ){
        head = pnode;
        pnode->value = 20;
        pnode->link = pnode2;
        pnode2->value = 10;
        pnode2->link = pnode3;
        pnode3->value = 15;
        pnode3->link = pnode4;
        pnode4->value = 13;
        pnode4->link = NULL;
    }
    p = head;
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }
    printf( "\n" );
    count = sll_count_nodes( head );
    printf( "There are %d nodes in linked list.\n", count );
    /*
    ** free dynamic memory.
    */ 
    sll_free( head );
    return EXIT_SUCCESS;
}

/* 输出：

 */
2. 编写一个函数，在一个无序的单链表中寻找一个特定的值，并返回一个指向该节点的指针。可以假设节点数据结构在头文件singly_linked_list_node.h中定义。 
如果想让这个函数适用于有序的单链表，需不需要对它做些修改？
解析：
不需要修改。 
/*
**singly_linked_list_node.h 
*/
#ifndef SINGLY_LINKED_LIST_NODE_H
#define SINGLY_LINKED_LIST_NODE_H

typedef struct NODE{
    struct NODE *link;
    int value;
} Node;

extern int sll_count_nodes( struct NODE *first );
extern void sll_free( Node *current );
#endif

/*
** search_value_in_linked_list.cpp。 
*/
#include <stdio.h>
#include <stdlib.h>
#include "singly_linked_list_node.h"

Node *search_value( Node *first, int value ){
    for( ; first != NULL; first = first->link ){
        if( first->value == value ){
            return first;
            break;
        }
    }
    return NULL;

}

void sll_free( Node *current ){
    Node *pt;
    Node *temp;
     
    pt = current;
    /*
    ** A very important thing: store the next node address beforehand.
    ** Otherwise after free function, the next node address stored previous node will be destroyed.
    */
    while( pt ){
        temp = pt->link;
        printf( "after temp = pt->link, pt = %p, temp = %p\n", pt, temp );
        free( pt );
        printf( "after free( pt ), pt = %p, pt->link = %p\n", pt, pt->link );
        pt = temp;
        printf( "after pt = temp, pt = %p\n", pt );
    }
}

/*
** main.cpp。 
*/ 
#include <stdio.h>
#include <stdlib.h>
#include "singly_linked_list_node.h" 

int main( void ){
    Node *head;
    Node *p;
    Node *pnode, *pnode2, *pnode3, *pnode4;
    Node *result;
    
    pnode = (Node *)malloc( sizeof(Node) );
    pnode2 = (Node *)malloc( sizeof(Node) );
    pnode3 = (Node *)malloc( sizeof(Node) );
    pnode4 = (Node *)malloc( sizeof(Node) ); 
    if( pnode && pnode2 && pnode3 && pnode4 ){
        head = pnode;
        pnode->value = 20;
        pnode->link = pnode2;
        pnode2->value = 10;
        pnode2->link = pnode3;
        pnode3->value = 15;
        pnode3->link = pnode4;
        pnode4->value = 13;
        pnode4->link = NULL;
    }
    p = head;
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }
    printf( "\n" );
    int value = 13;
    result = search_value( head, value );
    if( result ){
        printf( "%d is in the elements of linked list.\n", value );    
    } else{
        printf( "%d is not in the elements of linked list.\n", value );    
    }
    value = 30;
    result = search_value( head, value );
    if( result ){
        printf( "%d is in the elements of linked list.\n", value );    
    } else{
        printf( "%d is not in the elements of linked list.\n", value );    
    }
    /*
    ** free dynamic memory.
    */ 
    sll_free( head );
    
    return EXIT_SUCCESS;
}

/* 输出：

 */ 
3. 重写编写程序12.7的dll_insert函数，使头指针和尾指针分别以一个单独的指针传递给函数，而不是作为一个节点的一部分。从函数的逻辑而言，这个改动有何效果？ 
/*
**doubly_linked_list_node.h。 
*/
#ifndef DOUBLY_LINKED_LIST_NODE_H
#define DOUBLY_LINKED_LIST_NODE_H
#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
    struct NODE *fwd;
    struct NODE *bwd; 
    int value;
} Node;

extern int dll_insert( Node **headPtr, Node **tailPtr, int value );
extern void dll_free( Node *rootp );

#endif

/*
** doubly_linked_list.node.cpp。 
*/
#include "doubly_linked_list_node.h"

#define TRUE 1
#define FALSE 0
 
/*传入指向 头部和尾部节点的指针 的指针，四种情况
 * 插入到表头，
 * 插入到表尾，
 * 插入到空表中，
 * 插入到表中，前三个都需要修改headPtr或tailPtr指针
 */
int dll_insert(Node **headPtr, Node **tailPtr, int value)
{
    Node *this2 = *headPtr;
    Node *newNode;
     
    while( this2 != NULL && this2 -> value < value){
        if( this2->value == 0 ){
            return FALSE;
        }
        this2 = this2->fwd;
    }
 
    newNode = (Node *)malloc(sizeof(Node));
    newNode->value = value;
 
    if(this2 == NULL){
    /*插入到表尾，或者空表中*/
        if(this2 == *headPtr){
        /*插入到空表*/
            *headPtr = newNode;
            *tailPtr = newNode;
            newNode->fwd = NULL;
            newNode->bwd = NULL;
        }else{
        /*插入到表尾*/
            newNode->fwd = NULL;
            /*原来的表尾元素为当前节点的前节点*/
            newNode->bwd = *tailPtr;
            (*tailPtr)->fwd = newNode;
            /*更新尾节点指针*/
            *tailPtr = newNode;
        }
    }else{
    /*插入到表头，或者表中*/
        if(this2 == *headPtr){
            /*插入到表头*/ 
            newNode->bwd = NULL;
            /*原来的表头变成第二个节点*/
            newNode->fwd = *headPtr;
            (*headPtr)->bwd = newNode;
            /*更新表头*/
            *headPtr = newNode;
        }else{
            /*插入到非空表中this2位置的前面*/
            newNode->fwd = this2;
            newNode->bwd = this2->bwd;
            this2->bwd->fwd = newNode;
            this2->bwd = newNode;
        }
    }
    return TRUE;

}

void dll_free( Node *rootp ){
    Node *current;
    Node *temp;

    current = rootp;
    while( current ){
        temp = current->fwd;
        free( current );
        current = temp;
    }
}
/*
** 转载于:https://www.cnblogs.com/yangxunwu1992/p/5851394.html
*/

#include "doubly_linked_list_node.h"

int main( void )
{
    Node *third;
    Node *second;
    Node *first;
     
    third = (Node*)malloc( sizeof(Node) );
    second = (Node*)malloc( sizeof(Node) );
    first = (Node*)malloc( sizeof(Node) );
    if( third && second && first ){
        third->fwd = NULL;
        third->bwd = second;
        third->value = 4;
        second->fwd = third;
        second->bwd = first;
        second->value = 2;
        first->fwd = second;
        first->bwd = NULL;
        first->value = 1;
    }
 
    Node *head = first;
    Node *tail = third;
 
    dll_insert(&head, &tail, 35);
    dll_insert(&head, &tail, 3);
    dll_insert(&head, &tail, -10);
 
    Node *rootPtr = head;
    while(rootPtr != NULL){
        printf("%d\t", rootPtr->value);
        rootPtr = rootPtr->fwd;
    }
    /*
    ** free dynamic memory.
    */
    rootPtr = head;
    dll_free( rootPtr );
    
    return  EXIT_SUCCESS;
}
/*
** 转载于:https://www.cnblogs.com/yangxunwu1992/p/5851394.html
*/

/* 输出：

 */ 
4. 编写一个函数，反序排列一个单链表的所有结点。函数具有下面的原型：
    struct NODE *sll_reverse( struct NODE *first );
在头文件singly_linked_list_node.h中声明节点数据结构。 
函数的参数指向链表的第1个节点。当链表被重排之后，函数返回一个指向链表新节点的指针。
链表最后一个节点的link字段的值应设置为NULL，在空链表（first==NULL）上执行这个函数
将返回NULL。 
/*
**singly_linked_list_node.h。 
*/
#ifndef SINGLY_LINKED_LIST_NODE_H
#define SINGLY_LINKED_LIST_NODE_H

typedef struct NODE{
    struct NODE *link;
    int value;
} Node;

extern struct NODE *sll_reverse( struct NODE *first );

#endif

/*
**singly_linked_list_node.cpp。 
*/
#include "singly_linked_list_node.h"
#include <stdlib.h>

struct NODE *sll_reverse( struct NODE *first ){
    if( !first ) {
        return NULL;
    }
    Node *pre;
    Node *next;
    Node *temp;
    
    /*
    ** set the link of the first node to NULL.
    */
    pre = first;
    next = pre->link;
    pre->link = NULL;
    while( next ){
        temp = next->link;
        next->link = pre;
        pre = next;
        next = temp;
    }
    
    return pre;
}

/*
** main.cpp。 
*/
#include <stdio.h>
#include <stdlib.h>
#include "singly_linked_list_node.h" 

int main( void ){
    Node *p;
    Node third = { NULL, 3 };
    Node second = { &third, 2 };
    Node first = { &second, 1 };
    
    printf( "print original elements in single linked list:\n" );
    p = &first;
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }    
    printf( "\n" );
    p = sll_reverse( &first );
    printf( "after p = sll_reverse( &first ), print elements in single linked list:\n" ); 
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }
    printf( "\n" );
    
    return EXIT_SUCCESS;
}
/* 输出：

*/

/*
5. 编写一个程序，从一个单链表中移除一个节点。函数的原型如下：
    int sll_remove( struct NODE **rootp, struct Node *node );
可以假设节点数据结构在头文件singly_linked_list_node.h中定义。函数的第1个参数是一个指向链表根指针的之前，第2个参数参数是一个指向待移除节点的指针。如果链表并不包含移除的节点，函数就返回假，否则它就移除这个节点并返回真。把一个指向待移除节点的指针（而不是待移除节点的值）作为参数传递给函数有那些优点？
解析：
首先，这个问题的答案是：接受一个指向希望删除的节点的指针可以使函数和存储在链表中的数据类型无关。所以通过对不同的链表包含不同的头文件，相同的代码可以作用于任何类型的值。其次，如果我们并不知道哪个节点包含了需要被删除的值，那么首先必须对它进行查找。 
*/
/*
**singly_linked_list_node.h。 
*/
#ifndef SINGLY_LINKED_LIST_NODE_H
#define SINGLY_LINKED_LIST_NODE_H

typedef struct NODE{
    struct NODE *link;
    int value;
} Node;

extern int sll_remove( struct NODE **linkp, struct NODE *delete2 );
extern void sll_free( Node *current );

#endif

/*
**从一个单链表删除一个指定的节点。第1个参数指向链表的根指针，第2个参数
**指向需要被删除的节点。如果它可以被删除，函数返回TRUE，否则返回FALSE。 
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "singly_linked_list_node.h"

#define FALSE 0
#define TRUE 1

int sll_remove( struct NODE **linkp, struct NODE *delete2 ){
    register Node *current;
    
    assert( delete2 != NULL );
    
    /*
    ** 寻找要求删除的节点。 
    */
    while( (current = *linkp) != NULL && current != delete2 ){
        linkp = &current->link;
    }
    
    if( current == delete2 ){
        *linkp = current->link;
        free( current );
        return TRUE;
    } else{
        return FALSE;
    }
}
/*
注意，让这个函数用free函数删除节点将是得它只适用于动态分配节点的链表。另一种方案
是如果函数返回真，由调用函数负责删除节点。当然，如果调用函数没有删除动态分配的节点，
将导致内存泄漏。
一个讨论问题：为什么这个函数需要使用assert？
因为在这个程序中地址为NULL的地方不需要删除。

*/ 

void sll_free( Node *current ){
    Node *pt;
    Node *temp;
     
    pt = current;
    /*
    ** A very important thing: store the next node address beforehand.
    ** Otherwise after free function, the next node address stored previous node will be destroyed.
    */
    while( pt ){
        temp = pt->link;
        printf( "after temp = pt->link, pt = %p, temp = %p\n", pt, temp );
        free( pt );
        printf( "after free( pt ), pt = %p, pt->link = %p\n", pt, pt->link );
        pt = temp;
        printf( "after pt = temp, pt = %p\n", pt );
    }
}

/*
**main.cpp。 
*/
#include <stdio.h>
#include <stdlib.h>
#include "singly_linked_list_node.h"

#define FALSE 0
#define TRUE 1

int main( void ){
    Node *p;
    Node *third = (Node *)malloc( sizeof(Node) );
    Node *second = (Node *)malloc( sizeof(Node) );
    Node *first = (Node *)malloc( sizeof(Node) );
    int result;
    
    if( first && second && third ){
        first->link = second;
        first->value = 1;
        second->link = third;
        second->value = 2;
        third->link = NULL;
        third->value = 3;
    }
    printf( "print original elements in single linked list:\n" );
    p = first;
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }    
    printf( "\n" );
    p = first;
    printf( "p = %p\n", p ); 
    result = sll_remove( &p, third );
    printf( "after result = sll_remove( &p, third ), p = %p\n", p );
    if( result == TRUE ){
        printf( "Node deletes successfully.\n" );
    } else{
        printf( "Don't have the node in this singly linked list.\n" );
    }
    printf( "after result = sll_remove( &p, third ), print elements in single linked list:\n" );
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }    
    printf( "\n" );
    p = first;
    printf( "p = %p\n", p ); 
    result = sll_remove( &p, first );
    printf( "after result = sll_remove( &p, first ), p = %p\n", p );
    if( result == TRUE ){
        printf( "Node deletes successfully.\n" );
    } else{
        printf( "Don't have the node in this singly linked list.\n" );
    }
    printf( "after result = sll_remove( &p, first ), print elements in single linked list:\n" );
    Node *begin;
    begin = p;
    while( p ){
        printf( "%d ", p->value );
        p = p->link;
    }    
    printf( "\n" );
    /*
    ** free dynamic memory.
    */ 
    sll_free( begin );
    
    return EXIT_SUCCESS;
}

/* 输出：

 */ 
6. 编写一个程序，从一个双链表中移除一个节点。函数的原型如下：
    int dll_remove( struct NODE **rootp, struct NODE *node );
可以假设节点数据结构在头文件doubly_linked_list_node.h中定义。函数的第1个参数是一个指向包含链表根指针的节点的指针（和程序12.7相同），第2个参数是个指向移除节点的指针。如果链表并不包含待移除的节点，函数就返回假，否则函数移除该节点并返回真。 
/* 这道题自己的做法是错误的，但是就是不知道自己那里错了，有没有大神帮帮忙，告知我该怎么修改。
/*
** doubly_linked_list_node.h
*/ 
#ifndef DOUBLY_LINKED_LIST_NODE_H
#define DOUBLY_LINKED_LIST_NODE_H 
typedef struct NODE {
    struct NODE *fwd;
    struct NODE *bwd;
    int         value; 
} Node; 

extern int dll_remove( struct NODE *rootp, struct NODE *node );
extern void dll_free( struct NODE *rootp );

#endif

/*
**从一个单链表删除一个指定的节点。第1个参数指向链表的根指针，第2个参数
**指向需要被删除的节点。如果它可以被删除，函数返回TRUE，否则返回FALSE。 
*/
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include "doubly_linked_list_node.h"

#define FALSE 0
#define TRUE 1

/*
** 删除的节点情况如下：
** 删除的节点在表头；(1) 
** 删除的节点在表中；(2)
** 删除的节点在表尾；(3)
** 删除的节点既在表头也在表尾。(4)
** 讨论情况(1)：
** 删除表头，表头后面的第一个节点作为新表头。新表头的bwd设置为NULL。
** 讨论情况(2):
** 删除的节点前面的第一个节点的fwd应该设置为删除节点后面的第一个节点，
** 删除的节点后面的第一个节点的bwd应该设置为删除节点前面的第一个节点。
** 讨论情况(3):
** 删除表尾，表尾前面的第一个节点作为新表尾。新表尾的fwd设置为NULL。
** 讨论情况(4):
** 表头和表尾均设置为空，使这个表为空表。 
*/
int dll_remove( struct NODE *rootp, struct NODE *node ){
    register Node *this2;
    register Node *next;
    
    assert( node != NULL );
    
    /*
    ** 寻找要求删除的节点。 
    */
    for( this2 = rootp; this2 != node; this2 = this2->fwd )
        ;
    /*
    ** 找到删除的节点。 
    */
    if( this2 == node ){
        /*
        ** 删除的节点在表头。 
        */ 
        if( this2 == rootp ){
            next = this2->fwd;
            /*
            ** 删除的节点只在表头，不在表尾。 
            */ 
            if( next != NULL ){
                free( rootp );
                *rootp = *next;
                rootp->bwd = NULL; 
                printf( "Delete the header node of double linked list successfully.\n" );
                return TRUE;
            } else{ /* 删除的节点既在表头，又在表尾。*/ 
                free( rootp );
                printf( "Don't have any node in double linked list.\n" );
                return TRUE;
            }
        } else{ /* 删除的节点不在表头 */ 
            next = this2->fwd;
            /* 删除的节点只在表中，不在表尾 */
            if( next != NULL ){
                free( this2 );
                /*this2->fwd = next->fwd;*/
                this2->bwd->fwd = next;
                next->bwd = this2->bwd;
                *(this2) = *(next); 
                printf( "Delete the middle node of double linked list successfully.\n" );
                return TRUE;
            } else{ /* 删除的节点在表尾 */ 
                this2->bwd->fwd = NULL;
                free( this2 );
                printf( "Delete the tail node of double linked list successfully.\n" );
                return TRUE;
            } 
        } 
    } else{
        printf( "Don't have the node in double linked list.\n" );
        return FALSE;
    }
}
/*
注意，让这个函数用free函数删除节点将是得它只适用于动态分配节点的链表。另一种方案
是如果函数返回真，由调用函数负责删除节点。当然，如果调用函数没有删除动态分配的节点，
将导致内存泄漏。
一个讨论问题：为什么这个函数需要使用assert？
因为地址为NULL的地方不需要删除其节点。

*/ 

void dll_free( Node *rootp ){
    Node *current;
    Node *temp;

    current = rootp;
    while( current ){
        temp = current->fwd;
        printf( "after temp = current->fwd, current = %p, temp = %p\n", current, temp );
        free( current );
        printf( "after free( current ), current = %p, current->fwd = %p\n", current, current->fwd );
        current = temp;
        printf( "after current = temp, current = %p\n", current );
    }
}

/*
** main.cpp。 
*/ 
#include <stdio.h>
#include <stdlib.h>
#include "doubly_linked_list_node.h"

#define FALSE 0
#define TRUE 1

int main( void )
{
    Node *forth;
    Node *third;
    Node *second;
    Node *first;
 
     forth = (Node*)malloc( sizeof(Node) ); 
    third = (Node*)malloc( sizeof(Node) );
    second = (Node*)malloc( sizeof(Node) );
    first = (Node*)malloc( sizeof(Node) );
    if( first && second && third && forth ){
        first->bwd = NULL;
        first->fwd = second;
        first->value = 1;
        second->fwd = third;
        second->bwd = first;
        second->value = 2;
        third->fwd = forth;
        third->bwd = second;
        third->value = 3;
        forth->fwd = NULL;
        forth->bwd = third;
        forth->value = 4; 
    }
     printf( "print original elements of double linked list:\n" );
    Node *rootPtr = first;
    while( rootPtr != NULL ){
        printf( "%d\t", rootPtr->value );
        rootPtr = rootPtr->fwd;
    }
    printf( "\n" ); 
    int result = dll_remove( first, first );
    printf( "after result = dll_remove( first, first ):\n" );
    if( result == TRUE ){
        printf( "Delete the node of double linked list successfully.\n" );
    } else{
        printf( "Don't have the node in double linked list. Deletion fails.\n" );
    }
    printf( "print elements of double linked list:\n" );
    rootPtr = first;
    while( rootPtr != NULL ){
        printf( "%d\t", rootPtr->value );
        rootPtr = rootPtr->fwd;
    }
    printf( "\n" );
    result = dll_remove( first, third );
    printf( "after result = dll_remove( first, third ):\n" );
    if( result == TRUE ){
        printf( "Delete the node of double linked list successfully.\n" );
    } else{
        printf( "Don't have the node in double linked list. Deletion fails.\n" );
    }
    printf( "print elements of double linked list:\n" );
    rootPtr = first;
    while( rootPtr != NULL ){
        printf( "%d\t", rootPtr->value );
        rootPtr = rootPtr->fwd;
    }
    printf( "\n" );
    /*
    ** free dynamic memory.
    */
    rootPtr = first;
    dll_free( rootPtr );
    
    return  EXIT_SUCCESS;
}

/* 输出：

 */

/* 如果你有兴趣，可以试着写写这道题的简化版本。 */ 
7. 编写一个程序，把一个新单词插入到问题7所描述的索引表中。函数接受两个参数：一个指向list指针的指针和一个字符串。该字符串假定包含单个单词。如果这个单词原先并未存在于索引表中，它应该复制到一块动态分配的节点并插入到索引表中。如果该字符串不是以一个字母开头，或者出现其他错误，函数就返回假。
函数应该维护一个一级链表，节点的排列以字母为序。其余的二级链表则以单词为序排列。

#ifndef CONCORDANCE_LIST_H
#define CONCORDANCE_LIST_H

typedef struct WORD_NODE{
    char *str;
    struct WORD_NODE *link;
} Word_node;

typedef struct LETTER_NODE{
    char ch;
    struct WORD_NODE *word;
    struct LETTER_NODE *letter_link;
} Letter_node;

/*
** 检查字符的正确性。 
*/
int check_alpha( char *ch );

/*
** 单词链表存在的情况下，插入节点到单词链表中。 
*/
int insert_word( struct WORD_NODE **pword_link, const char *word ); 

/*
** 单词链表不存在的情况下，插入节点到单词链表中。 
*/
int insert_word_2( struct WORD_NODE **pword_link, const char *word ); 

/*
** 第一级链表节点该字符存在的情况下插入单词。 
*/ 
int insert( struct LETTER_NODE **pletter_link, const char *word );

/*
** 第一级链表节点该字符不存在的情况下插入单词。 
*/ 
int insert_2( struct LETTER_NODE **pletter_link, const char *word );

/*
** 搜索指定的单词。 
*/ 
int search_word( struct LETTER_NODE **pletter_link, const char *word );

/*
** 打印所有的节点。 
*/
void print_all_nodes( struct LETTER_NODE *proot );

/*
** 释放所有的动态内存。 
*/
void free_all_nodes( struct LETTER_NODE *proot ); 
#endif

#include "concordance_list.h"
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>

#define TRUE 1
#define FALSE 0

/*
** 检查字符的正确性。 
*/
int check_alpha( char *ch ){
    if( isalpha( *ch ) ){
        return TRUE;
    }
    return FALSE;
}

/*
** 单词链表存在的情况下，插入节点到单词链表中。 
*/
int insert_word( struct WORD_NODE **pword_link, const char *word ){
    struct WORD_NODE *current;
    struct WORD_NODE *new_word;
    
    while( current = *pword_link ){
        if( strcmp( current->str, word ) == 0 ){
            return FALSE;
        } 
        /*
        ** 找到插入的位置。 
        */ 
        if( strcmp( current->str, word ) > 0 ){
            break;
        }
        pword_link = &current->link;
    }
    new_word = (struct WORD_NODE *)malloc( sizeof(struct WORD_NODE) );
    /*
    ** 内存分配失败，返回FALSE。 
    */
    if( !new_word ){
        return FALSE;
    }
    new_word->str = (char*)malloc( strlen(word) + 1 );
    /*
    ** 内存分配失败，返回FALSE。 
    */
    if( !new_word->str ){
        return FALSE;
    }
    strcpy( new_word->str, word ); 
    new_word->link = current;
    *pword_link = new_word;    
    return TRUE; 
}

/*
** 单词链表不存在的情况下，插入节点到单词链表中。 
*/
int insert_word_2( struct WORD_NODE **pword_link, const char *word ){
    /*
    ** 创建单词链表。 
    */ 
    (*pword_link) = (struct WORD_NODE *)malloc( sizeof(struct WORD_NODE) );
    if( !(*pword_link) ){
        return FALSE;
    }
    (*pword_link)->str = (char *)malloc( strlen(word) + 1 );
    if( !(*pword_link)->str ){
        return FALSE;
    }
    strcpy( (*pword_link)->str, word );
    (*pword_link)->link = NULL;
    return TRUE; 
}

/*
** 第一级链表节点该字符存在的情况下插入单词。 
*/ 
int insert( struct LETTER_NODE **pletter_link, const char *word ){
    struct LETTER_NODE *current;
    char ch;
    int result;
    
    ch = *word;
    ch = tolower( ch );
    while( current = *pletter_link ){
        if( ch == current->ch ){
            if( current->word ){
                printf( "1\n" );
                result = insert_word( &current->word, word );
                if( result == FALSE ){
                    return FALSE;
                }
            } else{
                printf( "2\n" );
                result = insert_word_2( &current->word, word );
                if( result == FALSE ){
                    return FALSE;    
                }
            }
            return TRUE;
        }
        pletter_link = &current->letter_link;
    }
    return TRUE; 
}

/*
** 第一级链表节点该字符不存在的情况下插入单词。 
*/ 
int insert_2( struct LETTER_NODE **pletter_link, const char *word ){
    struct LETTER_NODE *current;
    char ch;
    /* 
    ** 第一级链表中不存在该节点，创建第一级链表的后续的节点，并进行插入。
    */ 
    struct LETTER_NODE *new_letter_node;
    ch = *word;
    ch = tolower( ch );
    /*
    ** 如果出现跟insert函数中相同的字母，直接返回TRUE，不进行添加第一级新节点操作。 
    */ 
    while( current = *pletter_link ){
        if( ch == current->ch ){
            return TRUE;
        }
        /*
        ** 找到插入的位置。 
        */
        if( ch < current->ch ){
            break;
        }
        pletter_link = &current->letter_link;
    }
    new_letter_node = (struct LETTER_NODE *)malloc( sizeof(struct LETTER_NODE) );
    /*
    ** 内存分配失败，返回FALSE。 
    */
    if( !new_letter_node ){
        return FALSE;
    }
    new_letter_node->ch = ch;
    new_letter_node->word = (struct WORD_NODE *)malloc( sizeof(struct WORD_NODE) );
    /*
    ** 内存分配失败，返回FALSE。 
    */
    if( !new_letter_node->word ){
        return FALSE;
    }
    new_letter_node->word->str = (char *)malloc( strlen( word ) + 1 );
    /*
    ** 内存分配失败，返回FALSE; 
    */
    if( !new_letter_node->word->str ){
        return FALSE;
    }
    strcpy( new_letter_node->word->str, word );
    new_letter_node->word->link = NULL;
    new_letter_node->letter_link = current;
    *pletter_link = new_letter_node;
    return TRUE;
}

/*
** 搜索指定的单词。 
*/ 
int search_word( struct LETTER_NODE **pletter_link, const char *word ){
    int result;
    char ch;
    
    ch = *word;
    result = check_alpha( &ch );
    if( result == FALSE ){
        return FALSE;
    }
    result = insert( pletter_link, word );
    if( result == FALSE ){
        printf( "3\n" );
        return FALSE;
    }
    result = insert_2( pletter_link, word );
    if( result == FALSE ){
        printf( "4\n" );
        return FALSE;
    } 
    return TRUE;
}

/*
** 打印所有的节点。 
*/
void print_all_nodes( struct LETTER_NODE *proot ){
    while( proot ){
        printf( "ch = %c\n", proot->ch );
        Word_node *node;
        node = proot->word;
        while( node && node->str ){
            printf( "%s ", node->str );
            node = node->link;
        }
        printf( "\n" );
        proot = proot->letter_link;
    }
}

/*
** 释放所有的动态内存。 
*/
void free_all_nodes( struct LETTER_NODE *proot ){
    while( proot ){
        struct WORD_NODE *word_node;
        word_node = proot->word;
        while( word_node ){
            if( word_node->str ){
                free( word_node->str );
            }
            struct WORD_NODE *word_temp;
            word_temp = word_node->link;
            free( word_node );
            word_node = word_temp;
        }
        struct LETTER_NODE *letter_temp;
        letter_temp = proot->letter_link;
        free( proot );
        proot = letter_temp;
    } 
}

#include "concordance_list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 

#define TRUE 1
#define FALSE 0

int main( void ){
    struct LETTER_NODE *letter_node, *letter_node_2, *letter_node_3;
    struct WORD_NODE *word_node, *word_node_2, *word_node_3;
    int result;
    char word[10] = "ZAI";
    char word_2[10] = "an";
    
    word_node = (struct WORD_NODE *)malloc( sizeof(struct WORD_NODE) );
    word_node_2 = (struct WORD_NODE *)malloc( sizeof(struct WORD_NODE) );
    word_node_3 = (struct WORD_NODE *)malloc( sizeof(struct WORD_NODE) );
    if( word_node && word_node_2 && word_node_3 ){
        word_node->str = (char *)malloc( strlen( "an" ) + 1 );
        if( word_node->str ){
            strcpy( word_node->str, "an" );    
        }
        word_node->link = word_node_2;
        word_node_2->str = (char *)malloc( strlen( "and" ) + 1 );
        if( word_node_2->str ){
            strcpy( word_node_2->str, "and" );
        }
        word_node_2->link = NULL;
        word_node_3->str = (char *)malloc( strlen( "standard" ) + 1 );
        if( word_node_3->str ){
            strcpy( word_node_3->str, "standard" );
        } 
        word_node_3->link = NULL; 
    }
    letter_node = (struct LETTER_NODE *)malloc( sizeof(struct LETTER_NODE) );
    letter_node_2 = (struct LETTER_NODE *)malloc( sizeof(struct LETTER_NODE) );
    letter_node_3 = (struct LETTER_NODE *)malloc( sizeof(struct LETTER_NODE) );
    if( letter_node && letter_node_2 && letter_node_3 ){
        letter_node->ch = 'a';
        letter_node->letter_link = letter_node_2;
        letter_node->word = word_node;
        letter_node_2->ch = 'b';
        letter_node_2->letter_link = letter_node_3;
        letter_node_2->word = NULL;
        letter_node_3->ch = 's';
        letter_node_3->letter_link = NULL;
        letter_node_3->word = word_node_3;
    }
    printf( "print all nodes in singly linked list:\n" );
    printf( "letter_node = %p\n", letter_node );
    print_all_nodes( letter_node );
    result = search_word( &letter_node, word );
    if( result == TRUE ){
        printf( "\"%s\" is in linked list or is inserted into linked_list.\n", word );
    } else{
        printf( "\"%s\" has been existed in linked list or the word is illegal.\n", word );
    }
    printf( "after result = seach_word( &letter_node, \"%s\" ):\n", word );
    printf( "print all nodes in singly linked list again:\n" );
    printf( "letter_node = %p\n", letter_node );
    print_all_nodes( letter_node );
    word[0] = 'a';
    result = search_word( &letter_node, word );
    if( result == TRUE ){
        printf( "\"%s\" is in linked list or is inserted into linked_list.\n", word );
    } else{
        printf( "\"%s\" has been existed in linked list or the word is illegal.\n", word );
    }
    printf( "after result = seach_word( &letter_node, \"%s\" ):\n", word );
    printf( "print all nodes in singly linked list again:\n" );
    printf( "letter_node = %p\n", letter_node );
    print_all_nodes( letter_node );
    word[0] = 'b';
    result = search_word( &letter_node, word );
    if( result == TRUE ){
        printf( "\"%s\" is in linked list or is inserted into linked_list.\n", word );
    } else{
        printf( "\"%s\" has been existed in linked list or the word is illegal.\n", word );
    }
    printf( "after result = seach_word( &letter_node, \"%s\" ):\n", word );
    printf( "print all nodes in singly linked list again:\n" );
    printf( "letter_node = %p\n", letter_node );
    print_all_nodes( letter_node );
    result = search_word( &letter_node, word_2 );
    if( result == TRUE ){
        printf( "\"%s\" is in linked list or is inserted into linked_list.\n", word_2 );
    } else{
        printf( "\"%s\" has been existed in linked list or the word is illegal.\n", word_2 );
    }
    printf( "after result = seach_word( &letter_node, \"%s\" ):\n", word );
    printf( "print all nodes in singly linked list again:\n" );
    printf( "letter_node = %p\n", letter_node );
    print_all_nodes( letter_node );
    /*
    ** 释放动态内存。 
    */
    free_all_nodes( letter_node );
    return EXIT_SUCCESS;
}

/* 输出：

Microsoft Windows [版本 10.0.22000.739]
(c) Microsoft Corporation。保留所有权利。

C:\Users\22152>cd D:\BaiduNetdiskDownload\C和指针\第12章 使用结构和指针\编程练习\program_7

C:\Users\22152>d:

D:\BaiduNetdiskDownload\C和指针\第12章 使用结构和指针\编程练习\program_7>gcc concordance_list.cpp main.cpp -o main.exe

D:\BaiduNetdiskDownload\C和指针\第12章 使用结构和指针\编程练习\program_7>main.exe
print all nodes in singly linked list:
letter_node = 0000000000C11490
ch = a
an and
ch = b

ch = s
standard
"ZAI" is in linked list or is inserted into linked_list.
after result = seach_word( &letter_node, "ZAI" ):
print all nodes in singly linked list again:
letter_node = 0000000000C11490
ch = a
an and
ch = b

ch = s
standard
ch = z
ZAI
1
"aAI" is in linked list or is inserted into linked_list.
after result = seach_word( &letter_node, "aAI" ):
print all nodes in singly linked list again:
letter_node = 0000000000C11490
ch = a
aAI an and
ch = b

ch = s
standard
ch = z
ZAI
2
"bAI" is in linked list or is inserted into linked_list.
after result = seach_word( &letter_node, "bAI" ):
print all nodes in singly linked list again:
letter_node = 0000000000C11490
ch = a
aAI an and
ch = b
bAI
ch = s
standard
ch = z
ZAI
1
3
"an" has been existed in linked list or the word is illegal.
after result = seach_word( &letter_node, "bAI" ):
print all nodes in singly linked list again:
letter_node = 0000000000C11490
ch = a
aAI an and
ch = b
bAI
ch = s
standard
ch = z
ZAI

*/

/* 做出来这道题太不容易了呀！*/

还有一个疑问：为什么下面的打印函数只能打印出第一级节点的值而不能打印出单词链表的值呢？有没有大神解答下呢？欢迎评论思考。

/*
** 打印所有的节点。 
*/
void print_all_nodes( struct LETTER_NODE *proot ){
    while( proot ){
        printf( "ch = %c\n", proot->ch );
        while( proot->word && proot->word->str ){
            printf( "%s ", proot->word->str );
            proot->word = proot->word->link;
        }
        printf( "\n" );
        proot = proot->letter_link;
    }
}