-
2020-07-13 21:07:03
方法
任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
例子
- { 01, 0000, 0001, 001, 1 } 是前缀码。
- { 0, 100, 110, 1110, 1100} 不是前缀码,原因是同时包含了 110 以及 1100,其中 110 是 1100 的前缀。
更多相关内容 -
c语言. 前缀码判断。
2021-12-26 17:15:05前缀码判断 输入n(n是不大于100的正整数)和n个电话号码,每个电话号码都是长度是1至10的数字串。请判断这个电话号码集是否符合编码要求,如果符合,输出“Yes”,否则输出“No”。 -
前缀码的判断(个人摸索的小技巧)
2021-03-02 17:04:06前缀码的判断 前缀码的判断小技巧 判断是否为前缀码,最重要是看队中的数的数的后尾加0或1是否会变为队中另外一个数,如果会变成,那么就是不是前缀码,如果会变成,那么就是前缀码 例如 { 0, 100, 110, 1110, 1100... -
数据结构题前缀码判定.cpp
2019-12-11 18:43:07数据结构前缀码判定,请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。 输入: 第1行为n(表示下面有n行编码) ... -
20. 前缀码判定
2021-11-03 15:08:16请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。 输入: 第1行为n(表示下面有n行编码) 第2~n+1行为n个由0或1组成...1 描述
前缀码:任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。
输入:
第1行为n(表示下面有n行编码)
第2~n+1行为n个由0或1组成的编码输出:判断结果
例如,如果输入:
5
00
01
10
110
111
每一个字符均不是其他字符编码的前缀,所以,输出:YES
再如,如果输入:
5
00
01
10
110
11
编码11与前面的编码110的前缀,所以,输出:11
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 以文本方式显示 - 5↵
- 00↵
- 01↵
- 10↵
- 110↵
- 111↵
以文本方式显示 - YES↵
1秒 64M 0 测试用例 2 以文本方式显示 - 5↵
- 00↵
- 01↵
- 10↵
- 110↵
- 11↵
以文本方式显示 - 11↵
1秒 64M 0 测试用例 3 以文本方式显示 - 5↵
- 00↵
- 01↵
- 10↵
- 11↵
- 111↵
以文本方式显示 - 111↵
1秒 64M 0 测试用例 4 以文本方式显示 - 5↵
- 111↵
- 110↵
- 10↵
- 01↵
- 00↵
以文本方式显示 - YES↵
1秒 64M 0 测试用例 5 以文本方式显示 - 8↵
- 00↵
- 010↵
- 0110↵
- 0111↵
- 10↵
- 110↵
- 1110↵
- 1111↵
以文本方式显示 - YES↵
1秒 64M 0 测试用例 6 以文本方式显示 - 8↵
- 00↵
- 010↵
- 0110↵
- 0111↵
- 10↵
- 11↵
- 1110↵
- 111↵
以文本方式显示 - 1110↵
1秒 64M 0 2 解题
- 分析:建立一棵二叉树来处理,如果遇到0就处理左边,遇到1就处理右边
- 例如:
根据用户的输入顺序来存储,先出现的编码先存到数组的前面位置,但是不影响唯一性,
比如上图,如果下一个编码是010,那么就要从数组的第5位开始存了,下标5这个信息存储在数组第一个节点的leftpoint中,这样就串起来了 - 代码:
/* 这颗树实际上就是一个一维数组,但是和完全二叉树存储方法不同,他并不能直接使用下标来遍历 准确的说这是一个存储在顺序表中的链表 节点的左右指针(就是int数字)指向下一个元素的下标 下一个元素的下标根据下一个数的取值来定,如果是0的话就是leftpoint指向的下标 如果是1的话就是rightpoint指向的下标 */ #include <cstdio> #include <cstdlib> #include <fstream> #include <iostream> #include <cstring> using namespace std; struct node { //读到的数字是1就处理右节点,如果是0的话就处理左节点 int flag = 0; int leftpoint = 0; int rightpoint = 0; }; typedef struct node hufftree; int main() { int n; // 这样申请的动态数组并不会自动赋值为节点中的0,只是申请了空间 // hufftree *ht; // ht = (hufftree*)malloc(sizeof(hufftree)*1000); hufftree ht[50000]; char *str; int len; //字符串(编码)的长度 int treecout = 1; //这个树的长度 int treeindex; //正在处理的这个字符对应在树中的位置 int i = 0; // freopen("file out.txt", "r", stdin); cin >> n; str = (char *)malloc(sizeof(char) * 100000); while (n--) { cin >> str; len = strlen(str); treeindex = 0; for (i = 0; i < len; i++) { if (ht[treeindex].flag == 1) { // flag为1,说明之前已经出现了一样的编码 cout << str << endl; return 0; //只需要输出第一次重复的前缀就行,直接返回 } if (i < len - 1) { //最后一个字符(结尾)需要单独处理,因为最后一位涉及flag,这里先讨论前面的字符 if (str[i] == '0') { //如果是0,我们就来看左指针 if (ht[treeindex].leftpoint == 0) { //如果还是初始值,说明没有出现过这个编码,直接建立就行了 ht[treeindex].leftpoint = treecout; treeindex = treecout++; // cout的值始终比index的值大1 continue; } else { //之前有相同的部分,直接按照leftpoint的指向得到下标 treeindex = ht[treeindex].leftpoint; continue; } } else {//如果是1,就看右指针 if (ht[treeindex].rightpoint == 0) { ht[treeindex].rightpoint = treecout; treeindex = treecout++; continue; } else { treeindex = ht[treeindex].rightpoint; continue; } } } else { //存最后一位 if (str[i] == '0') { //是0,针对左指针操作 if (ht[treeindex].leftpoint == 0) { //当前位的左指针没有使用,把他左边指针指向下一位,并且下一位的flag置为0 //记住:最后一位的相应指针是被使用了的,0:使用了leftpoint;1:使用了rightpoint ht[treeindex].leftpoint = treecout; ht[treecout].flag = 1;//是把下一位置的flag置为0 treecout++; continue; } else { //当前位的左指针被使用了,说明之前出现了相同的编码,而且程序运行到这说明是正在处理编码的最后一位,那么可以断定编码重复 cout << str << endl; return 0; } } else {//如果是1相同的道理 if (ht[treeindex].rightpoint == 0) { ht[treeindex].rightpoint = treecout; ht[treecout].flag = 1; treecout++; continue; } else { cout << str << endl; return 0; } } } } } cout << "YES" << endl; return 0; }
- 最先写的时候我把最后一位的flag置为1,而不是把下一位的flag置为1,这样就会有争议,无法确定是已经结束的这个字符串的最后一个字符是0还是1,对之后的判断产生困扰,之后我又增加了一个flag,但是还是无法完全AC,直到改成现在这个程序才过
-
二十一、前缀码判定
2020-11-13 21:44:30请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。 输入: 第1行为n(表示下面有n行编码) 第2~n+1行为n个由0或1组成...二十一、前缀码判定
题目描述
前缀码:任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。
输入:
第1行为n(表示下面有n行编码)
第2~n+1行为n个由0或1组成的编码**输出:**判断结果
例如,如果输入:
5
00
01
10
110
111
每一个字符均不是其他字符编码的前缀,所以,输出:YES
再如,如果输入:
5
00
01
10
110
11
编码11与前面的编码110的前缀,所以,输出:11
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 5
00
01
10
110
111YES 1秒 64M 0 测试用例 2 5
00
01
10
110
1111 1秒 64M 0 测试用例 3 5
00
01
10
11
111111 1秒 64M 0 测试用例 4 5
111
110
10
01
00YES 1秒 64M 0 测试用例 5 8
00
010
0110
0111
10
110
1110
1111YES 1秒 64M 0 测试用例 6 8
00
010
0110
0111
10
11
1110
1111110 1秒 64M 0 解题思路
所谓前缀码的判定,本质上是二叉树的建树问题。令二叉树的左子树都代表1,遇到 1 都向左走;右子树都代表0,遇到 0 都向右走。
对于全新的没有前缀的字符编码,则二叉树中建立对应分支,分支除了最后一个结点外的所有结点值都为0,仅最后一个结点值为1。
字符编码是前缀码的话,如果在分支的行进过程中碰到值为 1 的结点,则当前字符编码存在前缀码;如果编码遍历完成,但是最后一个字符没有新建结点,则当前字符编码是别人的前缀码。
对于前缀码,我们用一个 flag 进行标记。当 flag 为 1 时表示存在前缀码,输出第一个前缀码 prefix。如果全部判断完成,flag 仍为0,则没有前缀码。
上机代码
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<queue> #include<algorithm> using namespace std; typedef struct NODE { int data; struct NODE *lchild; struct NODE *rchild; }node,*Tree; int main() { int n = 0; char str[100010], prefix[100010]; int flag = 0; Tree bit, T; bit = (Tree)malloc(sizeof(node));//初始化 bit->data = 0; bit->lchild = NULL; bit->rchild = NULL; cin >> n; while(n--) { memset(str, 0, sizeof(str)); cin >> str; int len = strlen(str); if (flag == 1) //存在前缀码后面都不用判断了,读取编码后直接跳出循环 continue; strcpy(prefix, str);//保存第一个前缀码 T = bit;//每次变回根节点初始化状态 for (int i = 0; i < len; i++) { if (str[i] == '1') //1向左走 { if (T->lchild == NULL)//左子树新建结点 { T->lchild = (Tree)malloc(sizeof(node)); T = T->lchild; T->lchild = NULL; T->rchild = NULL; if (i == len - 1) T->data = 1; else T->data = 0; } else { if (T->lchild->data == 1 || i == len - 1)//存在前缀码 { flag = 1; break; } else T = T->lchild; } } else //0向右走 { if (T->rchild == NULL)//右子树新建结点 { T->rchild = (Tree)malloc(sizeof(node)); T = T->rchild; T->lchild = NULL; T->rchild = NULL; if (i == len - 1) T->data = 1; else T->data = 0; } else { if (T->rchild->data == 1 || i == len - 1) { flag = 1; break; } else T = T->rchild; } } } } if (flag == 0)//没有前缀码 cout << "YES" << endl; else cout << prefix << endl; //system("pause"); return 0; }
-
前缀码判定
2020-11-07 00:51:25请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。 输入 第1行为n(表示下面有n行编码) 第2~n+1行为n个由0或1组成的... -
通过IP地址前缀码判断ip地址类型
2013-09-25 10:36:27#include #include #include #include #include char assert_ip(unsigned long ip) { if(!(ip>>31^0x0)) return 'A'; if(!(ip>>30^0x2)) return 'B'; if(!(ip>>29^0x6)) -
MOOC 课后讨论5.2 判别是否是前缀码的算法
2022-04-20 21:16:21问题:如何判断一个字符集是否采用前缀码 【重要】前缀码:任何一个字符的编码都不是同一个字符集中另一个字符的编码的前缀 对于给出的一个字符集,请判断这个字符集是否是前缀码; InputSpecification: 输入... -
(数据结构)前缀码判定
2020-07-23 13:03:58请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。 输入: 第1行为n(表示下面有n行编码) 第2~n+1行为n个由0或1组成... -
17. 前缀码判定
2018-12-09 16:17:20请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出"YES”;否则输出第一个与前面编码发生矛盾的编码。 输入: 第1行为n(表示下面有n行编码) 第2~n+1行为n个由0或... -
算法分析与设计作业十一——最优二元前缀码
2021-05-24 16:24:25二元前缀码:任何字符的代码不能作为其他字符代码的前缀。 利用二元前级码译码:从第一个字符开始一次读入每个字符(0或1),如果发现读到的子串与某个码字相等,就将这个子串译作对应的码字;然后从下一个字符开始... -
哈夫曼编码最优前缀码的贪心算法
2021-03-10 12:58:17哈夫曼编码最优前缀码的贪心算法 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。 ... -
贪心算法与数据结构结合4——最优前缀码及哈夫曼算法
2020-04-27 09:21:49本篇主要介绍贪心算法与数据结构结合的最后一个内容:最优前缀码及哈夫曼算法 1、最优前缀码 什么是最优前缀码 我们先看一个二元前缀码: 二元前缀码:用0-1字符串作为代码表示字符,任何字符的代码不能作为其它... -
前缀码的本质(哈夫曼树)---数据结构
2020-05-11 22:12:37若要设计 不等长的编码,则必须保证一个字符的编码不是另一个字符的前缀,这种称为前缀码。 解决方法:通过构造哈夫曼树即可形成通行上使用的二进制不等长码。 (如下图) 这样便可以一举两得: 编码不会产生二义... -
11. 前缀码判定
2017-12-01 22:31:00请编写一个程序,判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码,则输出”YES”;否则输出第一个与前面编码发生矛盾的编码。 输入: 第1行为n(表示下面有n行编码) 第2~n+1行为n个由0或1... -
16. 前缀码判定
2014-12-10 23:33:2716. 前缀码判定 成绩 10 开启时间 2014年11月23日 Sunday 15:40 折扣 0.8 折扣时间 2014年12月7日 Sunday 23:55 允许迟交 否 关闭时间 2014年12月14日 Sunday ... -
Lua判断字符串前缀是否为指定字符的3种方法
2021-04-20 10:48:44在写 lua debugger 的时候,我需要判断一个字符串的前缀是不是 "@" 。有三个方案:1.比较直观的是 string.sub(str,1,1) == "@"2.感觉效率比较高的是 string.byte(str) == 643.或者是 string.find(str,"@") == 1我... -
信息与编码系列(二)最优码——Huffman码
2020-12-19 04:12:57目录序最优性(Optimality)二元Huffman码Huffman平均码长和最优性证明 元Huffman码与源的扩展序这篇文章主要是对教材第二个chapter的讨论。对于Huffman码来说,其实很熟悉了,只要涉及到编码的问题多少会涉及到这个... -
前缀判断
2013-10-10 14:06:01题目标题:前缀判断 如下的代码判断 needle_start指向的串是否为haystack_start指向的串的前缀,如不是,则返回NULL。 比如:"abcd1234" 就包含了 "abc" 为前缀 */ #include #include char* prefix(char* ... -
数据结构:判定编码方案是否为前缀编码
2020-04-15 00:57:22前缀编码定义: (字符集中)任一编码都不是其它字符的编码的前缀 (字符集中)任一编码都不是其它字符的编码的前缀 (字符集中)任一编码都不是其它字符的编码的前缀 重要的话说三遍! 例: (1)找出下面不是前缀... -
全球各个国家手机号码前缀 中英文国家名称对应的手机号码的前缀
2019-01-05 18:37:50对应的手机号码前缀(Country Code) String[] codes = { "+86", "+93", "+355", "+213", "+376", "+244", "+1264", "+247", "+1268", "+54", "+374", "+297", "+61", "+43", "+994", "+1242", "+973", ... -
哈夫曼编码(前缀编码)理解
2019-11-25 21:43:195,6,2,9,7 哈夫曼编码 比如文字内容”ABCDEF”,通过二进制数据表示 ...前缀编码:设计长短不等的编码,必须是任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码 因为每个... -
【数据结构】哈夫曼编码与前缀编码
2019-08-31 11:04:481.前缀编码 首先对于一个串可以用等长的二进制位表示,这样就叫做固定长度编码。如果可以用不等长的二进制位表示,则称之为可变长度编码。...对前缀编码的解码很简单,因为没有一个码是其他编码的前缀,所... -
霍夫码编码(一种不等长,非前缀编码方式)
2020-04-30 20:55:48霍夫曼编码是一种不等长非前缀编码方式,于1951年由MIT的霍夫曼提出。 用于对一串数字/符号编码获取最短的结果,获取最大的压缩效率。 特点:不等长、非前缀 等长式编码 等长编码,意思是对出现的元素采用相同位数的... -
判断网卡MAC地址前缀
2020-09-11 14:52:15我们的电脑上现在可是很多的网卡,因为存在虚拟网卡,Lan口和wifi网卡等等。 之前有人给出判断的前缀,但是不够完整。可以从这里下载完整的资料。 http://standards-oui.ieee.org/oui/oui.txt -
poj 1056 判断前缀
2012-02-09 15:21:05题意:输入一些二进制编码,判断是否有是其它编码前缀的编码,如果有则输出...not...。没有则可编码。每组输入数据以9为结束标志。 #include using namespace std; int main() { char str[15][15]; int i=0,h=1... -
1005-前缀判断
2016-03-19 20:14:57如下的代码判断 needle_start指向的串是否为haystack_start指向的串的前缀,如不是,则返回NULL。 比如:"abcd1234" 就包含了 "abc" 为前缀 char* prefix(char* haystack_start, char* needle_start) { char...