精华内容
下载资源
问答
  • //使用数组链表实现map排序 public class Demo1 { //节点数组长度 private static int nodeLength = 1; public static void main(String[] args) { String data = "hello word if you have something wo public void...

    //使用数组链表实现map排序

    public class Demo1 {
        //节点数组长度
        private static int nodeLength = 1;
    
        public static void main(String[] args) {
            String data = "hello word if you have something wo  public void main, string args hello word hello word too data split his hash his split data too to word word word";
            Demo1 demo = new Demo1();
            Map<String, Integer> map = demo.map(data);
            demo.print(demo.toNode(map));
        }
    
        private void print(Node[] nodes){
            for(int i = nodes.length - 1; i >= 0; i--){
                if(null == nodes[i]) continue;
                Node node = nodes[i];
                do{
                    System.out.println(node.value + ":" + (i + 1));
                    node = node.next;
                }while (null != node);
            }
        }
    
    
        public Node[] toNode(Map<String,Integer> map){
            Node[] nodes = new Node[nodeLength];
            for(Map.Entry<String,Integer> entry : map.entrySet()){
                if(null == nodes[entry.getValue() - 1]){
                    nodes[entry.getValue() - 1] = new Node(entry.getKey());
                }else{
                    Node node = nodes[entry.getValue() - 1];
                    Node next = new Node(entry.getKey());
                    next.next = node.next;
                    node.next = next;
                }
            }
            return nodes;
        }
        public Map<String,Integer> map(String data){
            data = data.replaceAll(" +"," ").replaceAll("[,|.|?]"," ");
            String[] split = data.split("\\s");
            Map<String,Integer>  result = new HashMap<>();
            for(String word : split){
                if(word.trim().equals("")) continue;
                if(null == result.get(word)){
                    result.put(word,1);
                }else{
                    int num = result.get(word) + 1;
                    if(nodeLength < num){
                        nodeLength = num;
                    }
                    result.put(word,num);
                }
            }
            return result;
        }
        static class Node{
            String value;
            Node next;
            public Node(String value){
                this.value = value;
            }
        }
    
    }
    
    展开全文
  • 利用这个链表统计一篇文章的不同词,针对不同单词和同一单词的不同拼写形式进行排序 本文利用了C语言来实现了一通用的双向链表,其中双向链表的实现借鉴了 实现通用的双向链表(c语言实现) 读李先静《系统...

    使用C语言来实现一个通用的双向链表。利用这个链表来统计一篇文章的不同词数,针对不同单词和同一单词的不同拼写形式进行排序

    本文利用了C语言来实现了一个通用的双向链表,其中双向链表的实现借鉴了
    实现通用的双向链表(c语言实现)
    读李先静《系统程序员成长计划》内容总结
    这几篇文章。向其作者表示感谢。
    首先我们先放运行的截图吧(我所用的文件为哈利波特1-3册,有27W+个单词)

    测试文档字数

    运行主界面

    第一个功能

    第二个功能

    第三个功能

    1. 首先,我们要创建一个链表,然后对于链表中的一些操作(创建链表,插入数据,查找数据)等等基本的操作进行实现。在这里我主要是借鉴了之前的文章。然后我自己根据我的需要加入了一点方法。
    2. 我自己实现的方法主要有:
      1、一个检测此时的链表里面有没有我们的数据的方法,并且直接返回我们的数据位置,以及将我们的数据取出返回给我们的变量中
      2、几个比较函数,主要是用于对单词的数量进行排序(冒泡排序),以及在取单词并且加入链表的时候进行一个检测的操作
      3、对于统计单词的时候我自己设置的规则(区分大小写,不区分大小写,统计单词的拼写形式)**这段代码是付出了最多的心血的
      4、针对链表中的数据进行了排序的操作(最简单的冒泡排序,对于其他的排序太复杂了。。)
      5、其他细节,直接看代码吧
    3. 主要代码如下:针对一些特殊的地方我会进行具体的注释和讲解

    dlist.h 的代码:

    #include <stdlib.h>
    #ifndef DLIST_H_INCLUDED
    #define DLIST_H_INCLUDED
    
    
    //用c语言的方式编译
    #ifdef __cplusplus
    extern "C"{
    #endif /* _cplusplus */
    
    //枚举,函数的返回值类型
    typedef enum _DListRet
    {
        DLIST_RET_OK,
        DLIST_RET_OOM,
        DLIST_RET_STOP,
        DLIST_RET_PARAMS,
        DLIST_RET_FAIL
    }DListRet;
    
    //DList用于描述整个链表,定义在dlist.cpp中
    struct _DList;
    typedef struct _DList DList;
    
    //销毁节点的回调
    typedef void (*DListDataDestroyFunc)(void* ctx, void* data);
    //节点数据比较回调
    typedef int (*DListDataCompareFunc)(void* ctx, void* data);
    //遍历链表时的回调
    typedef DListRet (*DListDataVisitFunc)(void* ctx, void* data);
    
    //可供调用者使用的链表操作函数
    DList* dlist_create(DListDataDestroyFunc data_destroy, void* data_destroy_ctx);
    DListRet dlist_insert(DList* thiz, size_t index, void* data);
    DListRet dlist_prepend(DList* thiz, void* data);
    DListRet dlist_append(DList* thiz, void* data);
    DListRet dlist_delete(DList* thiz, size_t index);
    DListRet dlist_get_by_index(DList* thiz, size_t index, void** data);
    DListRet dlist_set_by_index(DList* thiz, size_t index, void* data);
    size_t dlist_length(DList* thiz);
    int dlist_hasnot(DList* thiz, DListDataCompareFunc cmp, void* ctx,void** data);
    int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx);
    DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx);
    DListRet dlist_forquantity(DList* thiz, DListDataVisitFunc visit, void* ctx,int num);
    void dlist_destroy(DList* thiz);
    DListRet BubbleSort(DList* thiz,DListDataCompareFunc cmp);
    
    
    #ifdef __cplusplus
    }
    #endif /* _cplusplus */
    
    
    #endif // DLIST_H_INCLUDED
    
    

    这个文件没什么可讲的,主要就是对于一些函数进行一个声明

    dlist.c

    #include "dlist.h"
    
    //链表节点描述
    typedef struct _DListNode
    {
        struct _DListNode* pre;
        struct _DListNode* next;
    
        void* data;
    }DListNode;
    
    //链表描述
    struct _DList
    {
        DListNode* first;
        DListDataDestroyFunc data_destroy;
        void* data_destroy_ctx;
    };
    
    /************************** 内部使用的函数 ****************************/
    //销毁一个节点的data成员,调用回调函数销毁
    static void _dlist_destroy_data(DList* thiz, void* data)
    {
        if (thiz->data_destroy != NULL)
        {
            thiz->data_destroy(thiz->data_destroy_ctx, data);
        }
    
        return;
    }
    
    //产生一个节点
    static DListNode* _dlist_create_node(DList* thiz, void* data)
    {
        DListNode* node = malloc(sizeof(DListNode));
    
        if (node != NULL)
        {
            node->pre = NULL;
            node->next = NULL;
            node->data = data;
        }
        return node;
    }
    
    //通过index获取一个节点
    static DListNode* _dlist_get_node(DList* thiz, size_t index, int fail_return_last)
    {
        DListNode* iter = thiz->first;
    
        while (iter != NULL && iter->next != NULL && index > 0)
        {
            iter = iter->next;
            index--;
        }
    
        if (!fail_return_last)
        {
            iter = index > 0 ? NULL : iter;
        }
    
        return iter;
    }
    
    //销毁一个节点
    static void _dlist_destroy_node(DList* thiz, DListNode* node)
    {
        if (node != NULL)
        {
            node->next = NULL;
            node->pre = NULL;
            _dlist_destroy_data(thiz, node->data);
            free(node);
        }
        return;
    }
    
    /************************** 调用者可使用的函数 ****************************/
    //链表生成,参数分别为销毁节点data的回调以及回调的参数
    DList* dlist_create(DListDataDestroyFunc data_destroy, void* data_destroy_ctx)
    {
        DList* thiz = malloc(sizeof(DList));
    
        if (thiz != NULL)
        {
            thiz->first = NULL;
            thiz->data_destroy = data_destroy;
            thiz->data_destroy_ctx = data_destroy_ctx;
        }
        return thiz;
    }
    
    DListRet dlist_insert(DList* thiz, size_t index, void* data)
    {
        DListNode* node = NULL;
        DListNode* cursor = NULL;
    
        //构造节点
        if ((node = _dlist_create_node(thiz, data)) == NULL)
        {
            return DLIST_RET_OOM;
        }
    
        //第一个节点
        if (thiz->first == NULL)
        {
            thiz->first = node;
    
            return DLIST_RET_OK;
        }
    
        //获取目标节点位置,1表示若超过链表长度length,则插在最后
        cursor = _dlist_get_node(thiz, index, 1);
    
        //插入链表中间位置
        if (index < dlist_length(thiz))
        {
            //头插
            if (thiz->first == cursor)
            {
                thiz->first = node;
            }
            //插入数据中间
            else
            {
                node->pre = cursor->pre;
                cursor->pre->next = node;
    
            }
            node->next = cursor;
            cursor->pre = node;
        }
        //尾插
        else
        {
            cursor->next = node;
            node->pre = cursor;
        }
    }
    
    //头插
    DListRet dlist_prepend(DList* thiz, void* data)
    {
        return dlist_insert(thiz, 0, data);
    }
    
    //尾插
    DListRet dlist_append(DList* thiz, void* data)
    {
        return dlist_insert(thiz, -1, data);
    }
    
    //删除一个节点
    DListRet dlist_delete(DList* thiz, size_t index)
    {
        //获取目标节点位置,0表示index超过length就返回NULL
        DListNode* cursor = _dlist_get_node(thiz, index, 0);
    
        if (cursor != NULL)
        {
            if (cursor == thiz->first)
            {
                thiz->first = cursor->next;
            }
    
            if (cursor->next != NULL)
            {
                cursor->pre->next = cursor->next;
            }
    
            if (cursor->pre != NULL)
            {
                cursor->next->pre = cursor->pre;
            }
    
            _dlist_destroy_node(thiz, cursor);
        }
        return DLIST_RET_OK;
    }
    
    //通过index获取一个节点的data
    DListRet dlist_get_by_index(DList* thiz, size_t index, void** data)
    {
        DListNode *cursor = _dlist_get_node(thiz, index, 0);
    
        if (cursor != NULL)
        {
            *data = cursor->data;
        }
    
        return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
    }
    
    //通过index设置一个节点的data
    DListRet dlist_set_by_index(DList* thiz, size_t index, void* data)
    {
        DListNode *cursor = _dlist_get_node(thiz, index, 0);
    
        if (cursor != NULL)
        {
            cursor->data = data;
        }
    
        return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
    }
    
    //获取链表的长度
    size_t dlist_length(DList* thiz)
    {
        size_t length = 0;
        DListNode* iter = thiz->first;
    
        while (iter != NULL)
        {
            length++;
            iter = iter->next;
        }
    
        return length;
    }
    
    //检测是否有这一个节点(可以直接返回节点吗)
    int dlist_hasnot(DList* thiz, DListDataCompareFunc cmp, void* ctx,void** data)
    {
        DListNode* iter = thiz->first;
        int i=0;
        while (iter != NULL)
        {
            int ans=cmp(ctx, iter->data);
            if (ans == 0)
            {
                *data = iter->data;
                return i;
            }
            i++;
            iter = iter->next;
        }
        return -1;//是一个全新的节点,没有在里面
    }
    
    //插摘目标数据所在的节点,比较函数采用回调的方法
    int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx)
    {
        int i = 0;
        DListNode* iter = thiz->first;
    
        while (iter != NULL)
        {
            int ans=cmp(ctx, iter->data);
            if (ans == 0)
            {
                break;
            }
            i++;
            iter = iter->next;
        }
    
        return i;
    }
    
    //遍历链表,并调用回调函数
    DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx)
    {
        DListRet ret = DLIST_RET_OK;
        DListNode* iter = thiz->first;
    
        while (iter != NULL && ret != DLIST_RET_STOP)
        {
            ret = visit(ctx, iter->data);
            iter = iter->next;
        }
    
        return ret;
    }
    
    DListRet dlist_forquantity(DList* thiz, DListDataVisitFunc visit, void* ctx,int num)
    {
        DListRet ret = DLIST_RET_OK;
        DListNode* iter = thiz->first;
        int i;
    
        for (i=0;i<num && iter != NULL && ret != DLIST_RET_STOP;i++)
        {
            ret = visit(ctx, iter->data);
            iter = iter->next;
        }
    
        return ret;
    }
    
    //销毁整个链表
    void dlist_destroy(DList* thiz)
    {
        DListNode* iter = thiz->first;
        DListNode* next = NULL;
    
        while (iter != NULL)
        {
            next = iter->next;
            _dlist_destroy_node(thiz, iter);
            iter = next;
        }
        thiz->first = NULL;
        free(thiz);
    
        return;
    }
    //交换的函数
    void swap(DListNode* q,DListNode* p)
    {
        void* t=q->data;
        q->data=p->data;
        p->data=t;
    }
    
    
    //冒泡排序
    DListRet BubbleSort(DList* thiz,DListDataCompareFunc cmp)
    {
        DListNode* p;
        DListNode* q;
        int length=(int)dlist_length(thiz);
    
        if((thiz->first->next) != NULL)
        {
            int i=0;
            while(i<length)
            {
                q = thiz->first;
                p = q->next;
            while(p != NULL)
            {
                if(cmp(q->data, p->data) == -1)//前面的比后面的小
                {
                   swap(q,p);
                }
    
                else
                {
                    q = q->next;
                    p = p->next;
                }
    
            }
            i++;
            }
        }
    
        return DLIST_RET_OK;
    }
    
    
    
    
    

    这片代码中的大部分都是在上面的链接中有的,大家可以看看上面的文章的思路(主要是第一篇)

    然后我个人实现的主要有dlist_hasnot 这个函数
    对于这个函数,我也是参考了之前的方法,认为没有一个合适的函数可以完成我的功能(主要是检测单词的时候我希望只遍历一遍链表就可以完成,返回单词在链表中的位置并且把值给取出来,这样子我们在修改链表中的值的时候就只需要再通过location就可以了,一共就是遍历两边链表。所以我自己又写了一个方法来检测我们的链表中有没有我们的单词(dlist_hasnot)这个方法。然后比较的方法也是使用回调函数来完成,只比较数据中的单词部分。

    还有我实现了BubbleSort 冒泡排序这个函数。主要也是将之前的冒泡排序中使用的数组给变成我们的链表,然后遍历链表来实现冒泡这个操作。
    至于冒泡排序中的swap(交换)的操作,我本来是打算用深拷贝(即把我们链表的节点交换,但是后面发现这个工作量太大而且会影响性能),索性我就直接用了浅拷贝,只是单纯的把data数据交换了,如果各位想用深拷贝的话也可以,就把我的swap函数给进行相应的修改就可以了。

    至于dlist_forquantity这个函数,因为我的测试数据非常大(一本哈利波特书籍)所以到时候进入链表的数据有几万个,所以如果我用遍历链表的函数输出的数据太多了。所以我自己写了一个dlist_forquantity函数,只输入链表中用户自定数量的数据。因为我们的冒泡排序将数量较多的数据给放到链表的前面了,所以正好符合我们的要求。

    main.c

    //main.c
    #include "dlist.h"
    #include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    
    struct Books
    {
       char  word[255];
       int   num;
       int   flag;
    } ;
    
    
    DListRet print(void* ctx, void* data)
    {
        printf("word's name: %s \n", ((*(struct Books*)data).word));
        printf("word's number: %d \n", ((*(struct Books*)data).num));
    
        return DLIST_RET_OK;
    }
    
    int ComparenumFunc(void* data1, void* data2)
    {
    
        if((*(struct Books*)data1).num == (*(struct Books*)data2).num)
            return 0;
        else if((*(struct Books*)data1).num> (*(struct Books*)data2).num)
           return 1;
        else
            return -1;
    }
    
    int CompareWordFunc(void* data1, void* data2)
    {
        return strcmp((*(struct Books*)data1).word,(*(struct Books*)data2).word);
    }
    
    static void dlist_temp(int choice)
    {
        FILE *fp = NULL;
        char buff[255];
    
        fp = fopen("C:\\Users\\liang.ding\\Desktop\\test2.txt", "r");
    
        DList* dlist = dlist_create(NULL, NULL);//专门用来放之前我们读取进来的单词(不区分大小写)
        DList* dlist1 = dlist_create(NULL, NULL);//专门来存放格式的表
        struct Books* tempbook;
        tempbook = (struct Books*)malloc(sizeof(struct Books)*5000000);
        int j=0;
        if(choice == 1)
        {
            while(fscanf(fp, "%s", buff)!=EOF)
        {
            struct Books* newbook;
            //printf("%s\n",buff);
            strcpy(tempbook[j].word,buff);
            tempbook[j].num=1;
            //这两个可以合成一步,从而提高效率
            int location=dlist_hasnot(dlist,CompareWordFunc,&tempbook[j],(void**)&newbook);
            if(location==-1)
            {
                dlist_append(dlist, &tempbook[j]);
                j++;
            }
            else
            {
                //int location=dlist_find(dlist, CompareWordFunc, &tempbook[j]);
                //printf("location = %d\n",location);
                //struct Books* newbook;
                //dlist_get_by_index(dlist, location, (void**)&newbook);
                newbook->num=newbook->num+1;
                //printf("newbook name: %s\n",newbook->word);
                //printf("newbook num: %d\n",newbook->num);
                dlist_set_by_index(dlist, location, newbook);
            }
        }
        dlist_forquantity(dlist, print, NULL,5);
        printf("\nAfter BubbleSort:\n");
        BubbleSort(dlist,ComparenumFunc);
        dlist_forquantity(dlist, print, NULL,5);
        printf("\n");
        }
    
        else if(choice == 2)
        {
            while(fscanf(fp, "%s", buff)!=EOF)
        {
            struct Books* newbook;
            int i;
            for(i=0;i<strlen(buff);i++)
            {
                if(buff[i]>'@'&&buff[i]<'[')
                    buff[i]=buff[i]+32;
            }
            strcpy(tempbook[j].word,buff);
            tempbook[j].num=1;
            //这两个可以合成一步,从而提高效率
            int location=dlist_hasnot(dlist,CompareWordFunc,&tempbook[j],(void**)&newbook);
            if(location==-1)
            {
                dlist_append(dlist, &tempbook[j]);
                j++;
            }
            else
            {
                //int location=dlist_find(dlist, CompareWordFunc, &tempbook[j]);
                //printf("location = %d\n",location);
                //struct Books* newbook;
                //dlist_get_by_index(dlist, location, (void**)&newbook);
                newbook->num=newbook->num+1;
                //printf("newbook name: %s\n",newbook->word);
                //printf("newbook num: %d\n",newbook->num);
                dlist_set_by_index(dlist, location, newbook);
            }
        }
            dlist_forquantity(dlist, print, NULL,5);
            printf("\nAfter BubbleSort:\n");
            BubbleSort(dlist,ComparenumFunc);
            dlist_forquantity(dlist, print, NULL,5);
            printf("\n");
        }
    
        else
        {
    
            //先用区分大小写的规则来把我们的单词给放入我们的链表中
            while(fscanf(fp, "%s", buff)!=EOF)
            {
                struct Books* newbook;
                strcpy(tempbook[j].word,buff);
                tempbook[j].num=1;
                int location=dlist_hasnot(dlist,CompareWordFunc,&tempbook[j],(void**)&newbook);
                if(location==-1)
                {
                    dlist_append(dlist, &tempbook[j]);
                    j++;
                }
            else
            {
                //int location=dlist_find(dlist, CompareWordFunc, &tempbook[j]);
                newbook->num=newbook->num+1;
                dlist_set_by_index(dlist, location, newbook);
            }
            }
            struct Books* form;
            struct Books* newbook;
            form = (struct Books*)malloc(sizeof(struct Books)*5000000);
            int z=0,i_,j_,z_=0;
            //z为tempbook的下标,作用为让tempbook赋值给每一个form
            //z_为form的下标,作用为接收tempbook的赋值
            //i_为form中word字符串的下标,作用为一个个取word中的字符以及对字符进行变成大写,小写的操作
            //j_为比较字符串的变量,我们把word的各种形式给取出来之后然后在tempbook里面进行比较,j_此时就为取每一个tempbook所使用的下标变量
            while(z<j)//我们的j变量是我们在之前一共添加进链表里面的tempbook的值,也就是说我们的链表里面一共有这么多个单词(没有重复的,区分了大小写)
            //然后我们的z变量作为一开始的值0,即我们要把tempbook给再遍历一遍,对于每个单词都要进行查找
            {
                int judge1=0,judge2=0,judge3=0,judge3_=0,judge4=0;//判断一开始我们读进字符串的格式
                //1:是否全为大写  2:是否全为小写  3:是否为首字母大写  4:是否里面有两个或者两个以上的大写字母
                strcpy(form[z_].word,tempbook[z].word);
                form[z_].num=1;
                form[z_].flag=0;
                int suppernum=0;
                //这是一开始的原始字符串
                if(isupper(form[z_].word[0]))	//测试原始单词是否为首字母大写的格式,因为到后面单词被转化为全大写了
                {
                    judge3_=1;
                }
                for(i_=0;i_<strlen(form[z_].word);i_++)//把它全部变为大写
                {
                    if((isupper(form[z_].word[i_])))
                        suppernum++;
                    if(islower(form[z_].word[i_]))
                        form[z_].word[i_]=form[z_].word[i_]-32;
                }
                //判断一开始读进字符串的格式,用judge变量来判断
                if(suppernum==strlen(form[z_].word))//全为大写
                    judge1=1;
                if(suppernum==0)//全为小写
                    judge2=1;
                if(suppernum==1 && judge3_==1)//只有首字符大写,注意这里是对原始单词进行检测,而不是对我们后面变为全大写的单词进行检测
                    judge3=1;
                if(suppernum>1 && suppernum<strlen(form[z_].word))//有两个或者两个以上的字符大写
                    judge4=1;
                //printf("%d\n",suppernum);
    
    
                for(j_=z+1;j_<j;j_++)
                {
                    if(tempbook[j_].num==0)
                        continue;
                    if(strcmp(form[z_].word,tempbook[j_].word)==0 && judge1==0)//检测到里面有相等的全为大写的字符串
                    {
                        form[z_].num++;
                        tempbook[j_].num=0;
                        break;
                    }
                }
    
                for(i_=0;i_<strlen(form[z_].word);i_++)//把它全部变为小写
                {
                    if(isupper(form[z_].word[i_]))
                        form[z_].word[i_]=form[z_].word[i_]+32;
                }
                for(j_=z+1;j_<j;j_++)
                {
                    if(tempbook[j_].num==0)
                        continue;
                    if(strcmp(form[z_].word,tempbook[j_].word)==0 && judge2==0)//检测到里面有相等的全为小写的字符串
                    {
                        form[z_].num++;
                        tempbook[j_].num=0;
                        break;
                    }
                }
    
                form[z_].word[0]=form[z_].word[0]-32 ;//把第一个字符变成大写
                for(j_=z+1;j_<j;j_++)
                {
                    if(tempbook[j_].num==0)
                        continue;
                    if(strcmp(form[z_].word,tempbook[j_].word)==0 && judge3==0)//检测到里面有相等的第一个字母为大写的字符串
                    {
                        form[z_].num++;
                        tempbook[j_].num=0;
                        break;
                    }
                }
                form[z_].word[0]=form[z_].word[0]+32; //再变回来,变成全部小写
    
                if(judge4 != 0)//字符串中出现了两个或者两个以上的大写字符
                {
                    //printf("4!\n");
                    int location ;
                    location=dlist_hasnot(dlist1,CompareWordFunc,&form[z_],(void**)&newbook);
                    if(location == -1)//表明之前没有节点,这是一个全新的节点
                    {
                        //printf("5!\n");
                        form[z_].flag=1;//加上标记,表示我们已经有这种类型了
                    }
                    else//之前有节点
                    {
                        //int location = dlist_find(dlist1,CompareWordFunc,&form[z_]);
                        if(newbook->flag == 0)//表示之前没有类似的字符串被统计过
                        {
                            newbook->num=newbook->num+1;
                            newbook->flag = 1;//添加了标记,表示被统计过
                            dlist_set_by_index(dlist1, location, newbook);
                        }
                    }
    
                }
    
                int flag=dlist_hasnot(dlist1,CompareWordFunc,&form[z_],(void**)&newbook);//找dlist1里面是否有这个单词的节点
                if(flag == -1) //里面没有这个单词的节点
                {
                    //printf("final word:%s\n",form[z_].word);
                    //printf("final num:%d\n",form[z_].num);
                    dlist_append(dlist1, &form[z_]);
                    z_++;
                }
    
                z++;
            }
            dlist_forquantity(dlist1, print, NULL,10);
            BubbleSort(dlist1,ComparenumFunc);
            printf("\nAfter BubbleSort:\n");
            dlist_forquantity(dlist1, print, NULL,2);
            //dlist_foreach(dlist, print, NULL);
        }
    
        /*
    
        int ans=dlist_find(dlist,CompareFunc,&test[4]);
        printf("answer=%d\n",ans);
        //printf("%d\n",dlist_hasnot(dlist,CompareWordFunc,&book4));
        dlist_foreach(dlist, print, NULL);
        printf("\n");
        //dlist_delete(dlist, 2);
        //printf("length=%d \n",(int)dlist_length(dlist));
    
        */
        //dlist_get_by_index(dlist, 4, (void**)&tmppc);
        //printf("**tmppc = %c\n", *(char*)tmppc);
        free(tempbook);
    }
    
    int main(int argc, char* argv[])
    {
        //dlist_temp(3);
        int choice;
        while(1)
        {
            printf("Please enter the statistical rule\n");
            printf("1:Do not ignore big and small            2:Ignore big and small          3:Count the spelling of words       0:Exit\n");
            scanf("%d",&choice);
            if(choice==0)
                return 0;
            dlist_temp(choice);
    
        }
        return 0;
    }
    
    

    这块是我付出最多心血的。。整了我差不多一周(太菜了

    首先我们看到我们的结构体struct Books
    里面的char word 表示的是每个单词(其实我认为char *会更好,直接保存单词的地址,但是后面的取词的操作可能会出问题。所以我为了方便和赶时间,就直接用char 数组了。直接利用我们的空间把每一个字符存起来)

    然后我们的num就是我们每个单词出现的数量(后面的是每种单词的拼写形式的数量)

    我们的flag只在最后的第三种方法(统计单词的拼写形式)有用。有一种形式就是单词里面有大于1但是又不是全部大写的格式(例如说McDonald’s 麦当劳)。我在统计这个单词的时候只是简单的用大写字母>1并且不等于单词长度来判断。但是这种方法会有许多重复的统计。例如说aAAAa 和 aaAAA 这两个单词用我的统计方法是会重复的。所以我就设置了一个flag变量,当我们统计到此类的单词的时候,我们就把flag的值给变成1,从而保证以后相同类型的单词不会被重复统计。

    针对print这个回调函数,我就是简单的输出每一个结构体的单词以及它的数量

    我实现了两个比较函数,一个是比较单词数量的ComparenumFunc。主要是在冒泡排序中使用
    另一个是CompareWordFunc,主要是在检测我们的链表中有没有重复的单词使用

    对于取词,我使用的是C语言的函数fscanf,直接把文本中的单词给读进buff变量中,这也是我为什么在结构体中不使用char* 而是使用char类型的数组的原因。这个函数把数据给输进buff中,,如果我们使用的是char *,那么虽然每一次buff的数据在改变,但是它的地址并不会变,所以我们的比较函数无法将读进来的数据与我们链表中的数据进行比较(因为都是地址,地址不会变的)
    但是我认为肯定有方法可以解决这个问题的。至于什么方法我还暂时没有想到,如果各位读者有新的见解可以评论交流。

    然后针对我们取到的词语,在链表中进行一个检测(dlist_hasnot函数),直接返回他在链表中的位置,并且把链表中的数据给取出来赋值给我们的临时变量。
    如果在链表中没有这个单词,就意味着这个单词是一个全新的单词。我们把它加入我们的链表中
    如果有这个单词,因为我们在之前已经用临时变量存了这个单词,所以我们可以直接把这个变量的数量给加一,然后再赋值给链表(此时还是要用dlist_set_by_index 方法来遍历一遍链表)
    但是这种方法还是要遍历两遍链表。我认为最好的方法是只遍历一遍链表。。如果有数据就把数量给加一即可,没有的话我们才重新加入一个新的节点。这样子我们的执行速度就可以提升一倍。
    但是还是受限于时间,我认为这也是一个比较大的工程(要编写特定的函数并且对链表中的数据进行修改)。我没有时间完成了。也欢迎各位读者来进行完成。

    最后我们再输出排序之前的链表,进行排序过后再输出一遍我们的链表(均为链表前5个数据)

    对于第二种操作(忽略单词的大小写)。实现方法和第一种差不多。只是我对一开始的buff变量进行了操作(遍历一遍,将所有的大写字符变成小写字符)。然后再进行后面的操作,其中加入链表,检测链表中是否有相同元素等等操作均和上面的一样

    对于第三种操作(统计单词的拼写形式)
    我们主要要统计单词的四种形式:
    1、全部小写
    2、全部大写
    3、首字大写
    4、部分大写(例如说McDonald’s这个词)
    所以我们可知道一个单词在这种规则下面最多也只有四种拼写形式。
    但是我们的问题有如下几个(这是我在实现过程中发现和遇到的问题,大家也可以讨论得出新的问题)
    1、当我们取到一个单词的时候,我们是先将这种单词变为四种形式(全大写,全小写,首字大写,部分大写),还是我们将每个词都变为小写,然后重复查找呢?
    2、如果我们将这个单词变为四种形式,那么部分大写应该如何解决呢?(比如说aAAA,aAAa,AAaa,aAaA这些单词形式都可以视为是部分大写),我们无法遍历所有的部分大写的拼写形式。这样子非常耗费时间和精力
    3、如果我们发现一个单词并且把这种形式给统计进我们的单词表里面,我们就可以把我们的这个单词给从我们原先的单词表中剔除。但是如何剔除呢,这个也是一个问题
    4、对于我们一开始取到的单词,我们进行转换的时候如何确认后面没有相同的单词导致我们的数量重复增加呢,例如说我们有一个BbBb,但是在文章里面有bBBB,bBbb等,均为我们的第四种形式我们如何进行一个去重的操作呢?

    下面我将会对每一个问题的解决方法进行我的讲解。
    先贴这一部分的代码:

     //先用区分大小写的规则来把我们的单词给放入我们的链表中
            while(fscanf(fp, "%s", buff)!=EOF)
            {
                struct Books* newbook;
                strcpy(tempbook[j].word,buff);
                tempbook[j].num=1;
                int location=dlist_hasnot(dlist,CompareWordFunc,&tempbook[j],(void**)&newbook);
                if(location==-1)
                {
                    dlist_append(dlist, &tempbook[j]);
                    j++;
                }
            else
            {
                //int location=dlist_find(dlist, CompareWordFunc, &tempbook[j]);
                newbook->num=newbook->num+1;
                dlist_set_by_index(dlist, location, newbook);
            }
            }
            struct Books* form;
            struct Books* newbook;
            form = (struct Books*)malloc(sizeof(struct Books)*5000000);
            int z=0,i_,j_,z_=0;
            //z为tempbook的下标,作用为让tempbook赋值给每一个form
            //z_为form的下标,作用为接收tempbook的赋值
            //i_为form中word字符串的下标,作用为一个个取word中的字符以及对字符进行变成大写,小写的操作
            //j_为比较字符串的变量,我们把word的各种形式给取出来之后然后在tempbook里面进行比较,j_此时就为取每一个tempbook所使用的下标变量
            while(z<j)//我们的j变量是我们在之前一共添加进链表里面的tempbook的值,也就是说我们的链表里面一共有这么多个单词(没有重复的,区分了大小写)
            //然后我们的z变量作为一开始的值0,即我们要把tempbook给再遍历一遍,对于每个单词都要进行查找
            {
                int judge1=0,judge2=0,judge3=0,judge3_=0,judge4=0;//判断一开始我们读进字符串的格式
                //1:是否全为大写  2:是否全为小写  3:是否为首字母大写  4:是否里面有两个或者两个以上的大写字母
                strcpy(form[z_].word,tempbook[z].word);
                form[z_].num=1;
                form[z_].flag=0;
                int suppernum=0;
                //这是一开始的原始字符串
                if(isupper(form[z_].word[0]))	//测试原始单词是否为首字母大写的格式,因为到后面单词被转化为全大写了
                {
                    judge3_=1;
                }
                for(i_=0;i_<strlen(form[z_].word);i_++)//把它全部变为大写
                {
                    if((isupper(form[z_].word[i_])))
                        suppernum++;
                    if(islower(form[z_].word[i_]))
                        form[z_].word[i_]=form[z_].word[i_]-32;
                }
                //判断一开始读进字符串的格式,用judge变量来判断
                if(suppernum==strlen(form[z_].word))//全为大写
                    judge1=1;
                if(suppernum==0)//全为小写
                    judge2=1;
                if(suppernum==1 && judge3_==1)//只有首字符大写,注意这里是对原始单词进行检测,而不是对我们后面变为全大写的单词进行检测
                    judge3=1;
                if(suppernum>1 && suppernum<strlen(form[z_].word))//有两个或者两个以上的字符大写
                    judge4=1;
                //printf("%d\n",suppernum);
    
    
                for(j_=z+1;j_<j;j_++)
                {
                    if(tempbook[j_].num==0)
                        continue;
                    if(strcmp(form[z_].word,tempbook[j_].word)==0 && judge1==0)//检测到里面有相等的全为大写的字符串
                    {
                        form[z_].num++;
                        tempbook[j_].num=0;
                        break;
                    }
                }
    
                for(i_=0;i_<strlen(form[z_].word);i_++)//把它全部变为小写
                {
                    if(isupper(form[z_].word[i_]))
                        form[z_].word[i_]=form[z_].word[i_]+32;
                }
                for(j_=z+1;j_<j;j_++)
                {
                    if(tempbook[j_].num==0)
                        continue;
                    if(strcmp(form[z_].word,tempbook[j_].word)==0 && judge2==0)//检测到里面有相等的全为小写的字符串
                    {
                        form[z_].num++;
                        tempbook[j_].num=0;
                        break;
                    }
                }
    
                form[z_].word[0]=form[z_].word[0]-32 ;//把第一个字符变成大写
                for(j_=z+1;j_<j;j_++)
                {
                    if(tempbook[j_].num==0)
                        continue;
                    if(strcmp(form[z_].word,tempbook[j_].word)==0 && judge3==0)//检测到里面有相等的第一个字母为大写的字符串
                    {
                        form[z_].num++;
                        tempbook[j_].num=0;
                        break;
                    }
                }
                form[z_].word[0]=form[z_].word[0]+32; //再变回来,变成全部小写
    
                if(judge4 != 0)//字符串中出现了两个或者两个以上的大写字符
                {
                    //printf("4!\n");
                    int location ;
                    location=dlist_hasnot(dlist1,CompareWordFunc,&form[z_],(void**)&newbook);
                    if(location == -1)//表明之前没有节点,这是一个全新的节点
                    {
                        //printf("5!\n");
                        form[z_].flag=1;//加上标记,表示我们已经有这种类型了
                    }
                    else//之前有节点
                    {
                        //int location = dlist_find(dlist1,CompareWordFunc,&form[z_]);
                        if(newbook->flag == 0)//表示之前没有类似的字符串被统计过
                        {
                            newbook->num=newbook->num+1;
                            newbook->flag = 1;//添加了标记,表示被统计过
                            dlist_set_by_index(dlist1, location, newbook);
                        }
                    }
    
                }
    
                int flag=dlist_hasnot(dlist1,CompareWordFunc,&form[z_],(void**)&newbook);//找dlist1里面是否有这个单词的节点
                if(flag == -1) //里面没有这个单词的节点
                {
                    //printf("final word:%s\n",form[z_].word);
                    //printf("final num:%d\n",form[z_].num);
                    dlist_append(dlist1, &form[z_]);
                    z_++;
                }
    
                z++;
            }
            dlist_forquantity(dlist1, print, NULL,10);
            BubbleSort(dlist1,ComparenumFunc);
            printf("\nAfter BubbleSort:\n");
            dlist_forquantity(dlist1, print, NULL,2);
            //dlist_foreach(dlist, print, NULL);
    

    我解决这个问题主要是利用了两个链表,一个是和之前的操作一样区分大小写的形式来把单词全部存进我们的链表中
    然后对这个链表进行遍历,将每个单词的拼写形式给存进我们的第二个链表中,最后对我们的第二个链表进行排序和输出

    其中我们的注释已经解释了大部分的内容。但是针对上面的几个问题我现在进行我的解答:
    1、我采用的是将读取到的单词转换为前三种形式(全大写,全小写,首字大写)然后在这个单词的后面进行查找(因为我们第一个链表就是区分大小写的来进行储存,所以直接在此个单词的后面进行查找,,可以提高效率)
    2、我们还要对我们当前读取进来的单词进行一个判断,判断它是四种形式中的哪一种,以防在后面读取到重复的单词(但是我认为只需要判断是否为第四种就行了。。因为之前的单词链表是不重复的。但是时间不够了。不能继续完善了)
    3、对于第四种形式,我之前定义的结构体中间有一个flag变量,就是来判断这个单词有没有部分大写的这个形式的。我们先判断我们读取进来的单词的形式,如果是第四种形式,我们就把相应的变量设置(judge4),然后在后面进行一个检测的操作。
    如果我们的链表中没有这个单词,我们就把这个单词给加进去
    如果有了这个单词,检测这个单词的flag值,如果为0,则表示这个单词的部分大写的形式并没有被统计到,我们就把这个单词的拼写数量加1,并且把flag给设置为1,表示这个单词被统计到了。
    4、最后对第二个链表进行一个检测,判断当前的链表有没有我们现在取到的单词的结构体,如果有,则放弃,没有,则把我们的单词给放进去。

    写在最后的总结

    这次的这个任务,让我对之前很久没有用过的C语言重新熟悉了一遍,并且对于双向链表有了一个更加深刻和直观的认识,知道自己应该如何去实现一个链表,一个链表应该有什么属性,什么操作。并且对于内存和地址的认识又更加加深了一步,知道了一些基本的函数。
    同时我对于通用数据类型(void*)有了更加深刻的认识。之前我是对于这块的知识几乎一窍不通。通过了这个任务让我更加了解了这个类型,在以后的工作中我也会运用到这方面的知识。
    同时因为我的程序主要是运行在Linux系统下面的,我对于Linux系统的认识也更加的深刻了。所以说我的收获是非常大的。
    在编程的过程中,,遇到的问题我也有了一个初步的解决思路,知道我们应该如何去定位问题的原因以及如何去解决发生的问题。
    最后感谢所有帮助过我的人。respect
    2020.12.24

    展开全文
  • 数据结构课程设计文档,使用的是数组链表的数据结构,编写的是一个统计文本某些单词个数和位置的程序。
  • 统计文件中的单词个数并输出(C语言) 分析:用单链表存储单词和单词的个数,从文件中读出一个单词,判断单词是否是第一次出现,如果是第一次出现就创建结点插入链表后,否则该单词数+1。 #include <stdio.h> ...

    统计文件中的单词个数并输出(C语言)

    分析:用单链表存储单词和单词的个数,从文件中读出一个单词,判断单词是否是第一次出现,如果是第一次出现就创建结点插入链表后,否则该单词数+1。

    #include <stdio.h>
    #include <ctype.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct node
    {
    	char c[30];
    	int count;
    	struct node *next;
    }node,*link;
    
    node *firstWord(node *head,char word[])//判断单词是不是第一次出现
    {
    	node *p=head;
    	while(p->next != NULL)
    	{
    		if(strcmp(p->next->c, word) == 0)
    			return p->next;
    		p=p->next;
    	}
    	return NULL;
    }
    
    void print(node *p)//输出单词和次数
    {
    	node *q=NULL;
    	while(p->next != NULL)
    	{
    		printf("%s %d\n", p->next->c,p->next->count);
    		q=p;
    		p=p->next;
    		free(q);
    	}
    	free(p);
    }
    int main()
    {
    	FILE *fp;
    	node *head,*p,*q,*t;
    	int i;
    	char ch,word[30]={0};
    	head=(link)malloc(sizeof(node));
    	head->next=NULL;
    	p=head;
    	if((fp=fopen("word.txt","r")) == NULL)
    	{
    		printf("cannot open the file\n");
    		exit(0);
    	}
    	while((ch=fgetc(fp)) != EOF)
    	{
    		if(!isalpha(ch))
    			continue;
    		i=0;
    		while(isalpha(ch))
    		{
    			word[i++]=ch;
    			ch=fgetc(fp);
    		}
    		word[i]='\0';//加入结束符
    		t=firstWord(head,word);
    		if(t == NULL)//第一次出现的单词
    		{
    			q=(link)malloc(sizeof(node));
    			q->next=NULL;
    			q->count=1;
    			strcpy(q->c,word);
    			p->next=q;
    			p=q;
    		}
    		else
    			t->count++;
    	}
    	fclose(fp);
    	print(head);
    	return 0;
    }
    
    展开全文
  •  问题:高效统计一篇英文文章里出现的所有单词,按照在文章中首次出现的顺序打印出该... 解决方式:利用Trie完成单词匹配,然后利用链表统计单词出现的个数。  源代码:   1 #include <stdio.h&g...

      问题出自blog:http://blog.csdn.net/v_july_v/article/details/6803368

      问题:高效统计一篇英文文章里出现的所有单词,按照在文章中首次出现的顺序打印出该单词和它出现的次数。

      解决方式:利用Trie完成单词匹配,然后利用链表来统计单词出现的个数。

      源代码:

      

      1 #include <stdio.h>
      2 #include <stdlib.h>     // for calloc(), free()
      3 #include <string.h>     // for strlen(), memset()
      4 
      5 enum { BranchSize = 26, StringSize = 40, NodeMax = 200 }; // 声明常量
      6 
      7 /* 链表信息以及相关操作函数 */
      8 struct ListNode
      9 {
     10     int     m_iCnt;             // 统计单词出现的次数
     11     char    m_szStr[StringSize];// 当前链表项中单词
     12     struct ListNode *m_pNxt;    // 指向下一个链表结点
     13 };
     14 
     15 struct ListHead
     16 {
     17     struct ListNode *m_pStart;  // 指向链表开始结点
     18     struct ListNode *m_pEnd;    // 指向链表末尾结点
     19 };
     20 
     21 typedef struct ListNode ListNode;
     22 typedef struct ListHead ListHead;
     23 
     24 // 分配头结点
     25 ListHead* AllocListHead()
     26 {
     27     ListHead *pNew = NULL;
     28 
     29     pNew = (ListHead *) calloc( 1, sizeof( ListHead ) );
     30     if ( NULL == pNew )
     31     {
     32         printf( "Out of Memory.\n" );
     33         return NULL;
     34     }
     35 
     36     pNew->m_pEnd        = NULL;
     37     pNew->m_pStart      = NULL;
     38 
     39     return pNew;
     40 }
     41 
     42 // 分配链表结点
     43 ListNode* AllocListNode( const char *szStr )
     44 {
     45     ListNode *pNew = NULL;
     46 
     47     pNew = (ListNode *)calloc( 1, sizeof(ListNode) );
     48     if ( NULL == pNew )
     49     {
     50         printf( "Out of Memory.\n" );
     51         return NULL;
     52     }
     53 
     54     // 初始化信息
     55     pNew->m_iCnt = 1;
     56     pNew->m_pNxt = NULL;
     57     strncpy( pNew->m_szStr, szStr, strlen( szStr ) );
     58     pNew->m_szStr[strlen(szStr)] = '\0';
     59 
     60     return pNew;
     61 }
     62 
     63 // 插入链表
     64 int InsertNodeIntoList( ListHead *pHead, const char *szStr )
     65 {
     66     ListNode *pStart = pHead->m_pStart,
     67               *pNew   = NULL;
     68 
     69     // 检查参数
     70     if ( NULL == szStr )
     71     {
     72         printf( "The string is null.\n" );
     73         return -1;
     74     }
     75 
     76     // 分配新节点
     77     pNew = AllocListNode( szStr );
     78     if ( NULL == pNew )
     79     {
     80         return -1;
     81     }
     82 
     83     // 将结点插入链表尾部
     84     if ( pStart != NULL )
     85     {
     86         pHead->m_pEnd->m_pNxt = pNew;
     87         pHead->m_pEnd = pNew;
     88     }
     89     else
     90     {
     91         pHead->m_pStart = pNew;
     92         pHead->m_pEnd = pNew;
     93     }
     94 
     95     return 1;
     96 }
     97 
     98 // 摧毁链表
     99 void DestoryList( ListHead **pHead )
    100 {
    101     ListNode *pStart = (*pHead)->m_pStart,
    102               *pFree  = NULL;
    103 
    104     if ( NULL == pHead )
    105         return;
    106 
    107     while ( pStart )
    108     {
    109         pFree = pStart;
    110         pStart= pStart->m_pNxt;
    111         free( pFree );
    112         pFree = NULL;
    113     }
    114 
    115     free( *pHead );
    116     *pHead = NULL;
    117 }
    118 
    119 // 输出链表中信息
    120 void OutputList( ListHead *pHead )
    121 {
    122     ListNode *pStart = pHead->m_pStart;
    123     int sum = 0;
    124 
    125     printf( "About statistic:\n");
    126     while ( pStart )
    127     {
    128         sum += pStart->m_iCnt;
    129         printf( "%s:\t\t%d\n", pStart->m_szStr, pStart->m_iCnt );
    130         pStart = pStart->m_pNxt;
    131     }
    132     printf( "The total words is %d.\n", sum );
    133     printf( "\n" );
    134 }
    135 
    136 /* Trie树结构体以及相关操作函数 */
    137 struct TrieNode
    138 {
    139     int     m_iIsStr;       // 记录此处是否构成一个字符串。
    140     struct TrieNode *m_pBranch[BranchSize]; // 指向各个子树的指针,小标0-25代表26个字符
    141     struct ListNode *m_pCountInfo;  // 指向该单词的统计信息结点
    142 };
    143 
    144 typedef struct TrieNode TrieNode;
    145 
    146 // 分配Trie树的新节点
    147 TrieNode* AllocTrieNode()
    148 {
    149     TrieNode *pNew = NULL;
    150     int idx = 0;
    151 
    152     pNew = (TrieNode *) calloc( 1, sizeof( TrieNode ) );
    153     if ( NULL == pNew )
    154     {
    155         printf( "Out of memory.\n" );
    156         return NULL;
    157     }
    158 
    159     // initialize information.
    160     for ( ; idx < BranchSize; ++idx )
    161         pNew->m_pBranch[idx] = NULL;
    162     pNew->m_pCountInfo  = NULL;
    163     pNew->m_iIsStr      = 0;
    164 
    165     return pNew;
    166 }
    167 
    168 // 在Trie树中查找单词
    169 int SearchNodeInTrie( TrieNode *pRoot,
    170                       const char *word )
    171 {
    172     TrieNode *pStart = pRoot;
    173 
    174     while ( *word && pStart )
    175     {
    176         pStart = pStart->m_pBranch[*word - 'a'];
    177         ++word;
    178     }
    179 
    180     // 在Trie树中找到szStr,则更新结点信息。
    181     if ( pStart != NULL && pStart->m_iIsStr )
    182     {
    183         pStart->m_pCountInfo->m_iCnt++;
    184         return 1;
    185     }
    186 
    187     return 0;
    188 }
    189 
    190 // 插入单词到Trie树中
    191 int InsertNodeIntoTrie( TrieNode *pRoot,
    192                         ListHead *pStart,
    193                         const char *szStr )
    194 {
    195     TrieNode *location  = pRoot;
    196     const char *word    = szStr;
    197 
    198     if ( SearchNodeInTrie( pRoot, szStr) == 1 )
    199         return 0;
    200 
    201     while ( *szStr )
    202     {
    203         if ( location->m_pBranch[*szStr - 'a'] == NULL ) // 不存在
    204         {
    205             TrieNode *pNew = AllocTrieNode();
    206             if ( NULL == pNew )
    207                 return -1;
    208             location->m_pBranch[*szStr - 'a'] = pNew;
    209         }
    210         // 每插入一步,相当于一个新串经过,指针要向下移动
    211         location = location->m_pBranch[*szStr - 'a'];
    212         ++szStr;
    213     }
    214     location->m_iIsStr = 1;
    215     if ( InsertNodeIntoList( pStart, word ) == 1 )
    216     {
    217         location->m_pCountInfo = pStart->m_pEnd;
    218         return 1;
    219     }
    220 
    221     return 0;
    222 }
    223 
    224 // 摧毁Trie树
    225 void DestoryTrie( TrieNode **pRoot )
    226 {
    227     TrieNode *TrieStack[NodeMax],
    228              *pNxt  = NULL,
    229              *root  = *pRoot;
    230     int top     = 0,
    231         idx     = 0;
    232 
    233     // Initialize stack
    234     for ( ; idx < NodeMax; ++idx )
    235         TrieStack[idx] = NULL;
    236 
    237     for ( idx = 0; idx < BranchSize; ++idx )
    238     {
    239         if ( root->m_pBranch[idx] != NULL )
    240             TrieStack[top++] = root->m_pBranch[idx];
    241     }
    242 
    243     // 遍历Trie树,并删除
    244     while ( top )
    245     {
    246         pNxt = TrieStack[--top];
    247 
    248         for ( idx = 0; idx < BranchSize; ++idx )
    249         {
    250             if ( pNxt->m_pBranch[idx] != NULL )
    251                 TrieStack[top++] = pNxt->m_pBranch[idx];
    252         }
    253 
    254         free( pNxt );
    255         pNxt = NULL;
    256     }
    257 
    258     free( *pRoot );
    259     *pRoot = NULL;
    260 }
    261 
    262 void TestFunction()
    263 {
    264     const char *pszStrs[9] =
    265         {
    266             "hello", "word", "hi",
    267             "hello", "hello","hi",
    268             "word", "word", "word"
    269         };
    270     int idx = 0;
    271     TrieNode *pTrie = NULL;
    272     ListHead *pList = NULL;
    273 
    274     pTrie = AllocTrieNode();
    275     if ( NULL == pTrie )
    276         return;
    277     pList = AllocListHead();
    278     if ( NULL == pList )
    279     {
    280         DestoryTrie( &pTrie );
    281         return;
    282     }
    283 
    284     for ( idx = 0; idx < 9; ++idx )
    285     {
    286         InsertNodeIntoTrie( pTrie, pList, pszStrs[idx] );
    287     }
    288 
    289     OutputList( pList );
    290 
    291     DestoryTrie( &pTrie );
    292     DestoryList( &pList );
    293 }
    294 
    295 int main()
    296 {
    297     TestFunction();
    298 
    299     return 0;
    300 }
    View Code

     

      Trie树源码参考blog:http://www.cnblogs.com/cherish_yimi/archive/2009/10/12/1581666.html

    转载于:https://www.cnblogs.com/life91/p/3272080.html

    展开全文
  • 要求:统计处一篇英文文章中的不同的单词,并得到单词个数。 用一个单向链表保存所出现的单词,注意几点:1)文件输入输出;2)字符串处理;3)链表数据结构 再看代码——算法实现如下: //=====================...
  • 在之前我自己写了一60行的链表版本的统计程序 相比这些strtok函数的程序要简洁明了的多 #include <stdio.h> #include <string.h> int main( void ) { int cnt = 0; char *blank = " "; //strtok...
  • 在看到这题目后,首先确定编写语言,用C语言编写。因为C语言中有很多关于字符串操作的函数可以利用。...这样单词就存储在了链表中。排序是比较困难的,因为排序的过程中还要时刻和对应的单词保持相对应,我采用...
  • 树中的每节点一般不是直接包含关键字,而是包含组成关键字的符号(当然叶子节点除外,叶子节点可能包含整个单词以及词频,非叶节点也可包含单词和词频)。根据存储结构的不同,又分为双链树和多重链表树。或者...
  • 六程序如下 hashtable.h#include "list.h" ...//以每个单词前面两字母叠加作为hashtable的key值 struct hash_node { struct list_head openlist;//开链法用来索引的链表 int sum; char* word; }; s
  • 用C语言写的统计英文文章单词的源程序,注释清楚,代码简洁,主要用链表结构实现,能够正确运行,里面统计时把数字和其他字母等也统计为一个单词,可以在统计的方法里面进行修改,方便学习参考
  • Linux下使用C语言调用C++编写的库...利用这个链表统计一篇文章的不同词,针对不同单词和同一单词的不同拼写形式进行排序 然后我根据这任务,需要用map来完成,其中map中的key为单词,value为单词出现的个数 ...
  • 所谓“单词”,是指由不超过80个单词字符组成的连续字符串,但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线,其它字符均认为是单词分隔符。 输入格式: 输入给出...
  • #include #include #include #include using namespace std; /* 问题:统计书中的单词及出现次数,实现一个... 一种做法是:根据给定的单词个数n,选取最接近n的质数k,然后对字符串进行散列, h = 31 * h + char
  • 比较两篇纯英文文本的相似度

    热门讨论 2013-04-14 10:29:48
    从文件中读出文本 比较相似度 以链表的形式存储 统计相同单词数 相同单词出现的次数 相同单词后面跟着的4个词中的相同单词个数……加权算出相似度
  • 1.加法2.减法3.乘法4.除法5.判断数字位数6.计算圆的面积7....统计单词个数20.静态创建链表21.动态创建链表(暂时没做)22.学生成绩排序23.学生成绩普涨10分 24.退出 (备注:仅供参考,有错可以私聊提出)
  • 200经典C程序【源码】

    千次下载 热门讨论 2013-08-08 10:48:40
    198 单词个数统计 199 方差运算 200 级数运算 201 输出素数 202 素数题 203 序列排序 204 整数各位数字排序 205 字符串字母移位 206 Fibonacc数列 第七部分 游戏篇 207 商人过河游戏 208 吃数游戏 ...
  • 198 单词个数统计 199 方差运算 200 级数运算 201 输出素数 202 素数题 203 序列排序 204 整数各位数字排序 205 字符串字母移位 206 Fibonacc数列 第七部分 游戏篇 207 商人过河游戏 ...
  • 198 单词个数统计 199 方差运算 200 级数运算 201 输出素数 202 素数题 203 序列排序 204 整数各位数字排序 205 字符串字母移位 206 Fibonacc数列 第七部分 游戏篇 207 商人过河游戏 208 吃数游戏 ...
  • 198 单词个数统计 199 方差运算 200 级数运算 201 输出素数 202 素数题 203 序列排序 204 整数各位数字排序 205 字符串字母移位 206 Fibonacc数列 第七部分 游戏篇 207 商人过河游戏 208 吃数游戏 ...
  • 面试8——手撕算法

    千次阅读 2020-06-16 20:24:19
    给一字符串判断单词数 开方算法 青蛙跳台阶 常用排序(快排和归并要写吐) 反转链表个链表,寻找公共节点 查找字符串中不重复的最长子串 LRU 手写求树的深度的代码 手写生产者消费者 编程实现string类 两数组A,...
  • 3.7 面试例题:链表中的倒数第m元素39 3.8 面试例题:链表的扁平化42 3.9 面试例题:空链表与循环链表48 第4章树和图53 4.1 树53 4.1.1 二元树54 4.1.2 二元搜索树55 4.1.3 堆57 4.1.4 常用的搜索方法58 ...
  • 3.7 面试例题:链表中的倒数第m元素39 3.8 面试例题:链表的扁平化42 3.9 面试例题:空链表与循环链表48 第4章树和图53 4.1 树53 4.1.1 二元树54 4.1.2 二元搜索树55 4.1.3 堆57 4.1.4 常用的搜索方法58 ...
  • 输入一行字符,统计其中有多少个单词,并将每个单词首字母大写(考虑空格,考虑单词的缩写) 译密码:按规律将字母变成其后的第四字母 输入一十六进制的字符串,输出其相应的十进制 提取两.
  • 编程之旅-Day40

    2019-04-27 23:39:22
    Day40-学习内容: 目录 Day40-学习内容: 1.剑指Offer 面试题52:求两个链表的第一个公共结点 面试题27:二叉树的镜像 ...例1:字符个数统计 例2:数字颠倒 例2:数字颠倒 1.剑指Offer 面试题52:...
  • q19_删除链表的倒数第N节点 q25_k一组翻转链表 q61_旋转链表 q138_复制带随机指针的链表 q206_反转链表 双指针遍历/滑动窗口 q3_无重复字符的最长子串 q11_盛最多水的容器 q15_三之和 q16_最接近的三之和...
  • 2021-03-22力扣刷题

    2021-03-22 15:18:11
    文章目录编号217存在重复元素HashMap解法,统计数组中每数字出现的次数直接用HashSet去重,速度更快编号705设计哈希集合编号215数组中第K最大元素利用最大堆的解法编号692前k高频单词利用大顶堆,自定义构造器...
  • 2)统计英文文本中,单词的出现次数,要求,输出按照出现次数的降序输出。 3)头文件里,定义全局变量和静态变量。会怎么样? 4)阻塞与非阻塞IO的区别,举例说明应用场景。 5)某个四位数的4倍等于它的反序,...
  • 八进制,阶乘,找位置,回文字符串,a+b,N阶楼梯上楼问题,大整数排序,二叉树排序,打印日期,A+B,对称矩阵,最小年龄的3个职工,矩阵最大值,守形数,遍历链表,成绩排序,最大的两个数,奇偶校验,二叉树遍历...

空空如也

空空如也

1 2 3 4
收藏数 70
精华内容 28
关键字:

统计链表单词个数