请问像这种题的思路是什么呀 - 编程论坛

#2

komorebi01102020-03-18 22:53

//感觉应该搞一个二维数组，但是不知道怎么跳过符号问题
//还不能重复，我刚学会桶排序，可是这是字符串啊qaq

#3

lin51616782020-03-18 23:35

写一个二十六叉树
百度字典树看看

[此贴子已经被作者于2020-3-18 23:40编辑过]

#4

komorebi01102020-03-18 23:44

回复 3楼 lin5161678

emmm数据结构刚刚才学到栈，这个算法对我来说太复杂了

#5

lin51616782020-03-19 00:19

程序代码：

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

typedef struct tree tree;

struct tree
{
    tree* pnext[26];
    int bend;
};

tree* init(char* str)
{
    tree* proot = calloc(1, sizeof *proot);
    for(tree* pcur = proot; *str; ++str)
    {
        if('a' <= *str && *str <= 'z')
        {
            int index = *str - 'a';
            if(pcur->pnext[index] == NULL)
                pcur->pnext[index] = calloc(1, sizeof *proot);
            pcur = pcur->pnext[index];
        }
        else
        {
            if(pcur == proot)
                continue;
            pcur->bend = 1;
            pcur = proot;
        }
    }
    return proot;
}

void printroot(tree* proot, char* str, int nlev)
{
    if(proot->bend != 0)
    {
        str[nlev] = 0;
        puts(str);
    }
    for(int i=0; i<sizeof proot->pnext / sizeof *proot->pnext; ++i)
    {
        if(proot->pnext[i] == NULL)
            continue;

        str[nlev] = 'a' + i;
        printroot(proot->pnext[i], str, nlev+1);
    }
}

void end(tree* proot)
{
    if(proot == NULL)
        return;

    for(int i=0; i<sizeof proot->pnext / sizeof *proot->pnext; ++i)
        end(proot->pnext[i]);
    free(proot);
}
void print(tree* proot)
{
    char str[512] = "";
    printroot(proot, str, 0);
}

int main(int argc, char *argv[])
{
    char* str = "aaa aaa aaaa aaaaa fesf ef e fe e fae e feaf  ffeefegag161argrg  efe";
    tree* ptree = init(str);
    print(ptree);
    end(ptree);
    return 0;
}

[此贴子已经被作者于2020-3-19 00:22编辑过]

#6

林月儿2020-03-19 05:49

去重，排序的任务为啥要树形结构？

#7

林月儿2020-03-19 06:40

普通的遍历插入排序还能顺带去重，但没有5楼的树形结构快
对每个字符串遍历字符，像是第一层放26个桶，然后每个桶下面再放26个
一层层下去像是棵树，比如ab，则相当于第一层的第一个桶和这个桶下面的第二个桶装满水
再遇到ac则在每一层只与相同前缀的字符串比较，提高效率

不过有个问题，相同的字符串前缀，不会新建树节点，只是遍历到叶子结点。
比如abc,ab这个abc放了三桶水，而ab,a在不在历史数据无法确定
这里用了pend做标记，表示结束。也可以每层放27个桶，对当前的分支加个结束符，少定义一个变量。

#8

吹水佬2020-03-19 07:36

只有本站会员才能查看附件，请登录

#include <stdio.h>
#include <string.h>

typedef struct _str
{
    char s[50];
} STR;

int cmp(const void *a , const void *b)
{
    return strcmp((*(STR*)a).s, (*(STR*)b).s);
}

void print(STR* s, int n, int b)
{
    char *p = s[0].s;
    printf("%s ", p);
    int i;
    for (i=1; i<n; ++i)
    {
        if (b)
        {
            if (strcmp(p,s[i].s) != 0)
            {
                printf( "%s ", s[i].s);
                p = s[i].s;
            }
        }
        else
            printf( "%s ", s[i].s);
    }
    printf("\n");
}

int main( void )
{
    char *s = "ask not what your country can do for you,ask what you can do for your country.";
    int n,m=0;
    STR str[100];
    char si[50];
    char *p=s;
    while (*p)
    {
        if (sscanf(p,"%[^ ,.!?]%n",si,&n) == 1)
        {
            strcpy(str[m++].s, si);
            p += n;
        }
        else
            ++p;
    }
    print(str, m, 0);
    qsort(str, m, sizeof(str[0]), cmp);
    print(str, m, 1);
}

#9

return_02020-03-19 08:50

去重，备一个桶，string数组，就行了

#10

return_02020-03-19 08:52

字典序后面再排就easy了

#11

komorebi01102020-03-19 12:45

回复 8楼吹水佬

emmm好像ac不了

#12

吹水佬2020-03-19 12:49

以下是引用komorebi0110在2020-3-19 12:45:32的发言：

emmm好像ac不了

照抄肯定不了

#13

komorebi01102020-03-19 13:18

回复 12楼吹水佬

哈哈哈谢谢，那我再看看

#14

maomao123452020-03-24 18:05

字典序a是直接大于b的，以此类推