前缀码的判断

前缀码的判断小技巧

判断是否为前缀码，最重要是看队中的数的数的后尾加0或1是否会变为队中另外一个数，如果会变成，那么就是不是前缀码，如果会变成，那么就是前缀码

例如

{ 0, 100, 110, 1110, 1100 } 因为110后面加上一个0就会变成1100，所以就不是前缀码。
当然这只是我通过一些题目摸索出来的一种方法，不一定准确，如果有问题还请各位大佬们纠正

1 描述

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，直到改成现在这个程序才过

参考来源

二十一、前缀码判定

题目描述

前缀码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

请编写一个程序，判断输入的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，遇到 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;
}