杭电水题--排序关于strtok的一些问题

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1106

其实挺简单的，开始的时候使用了string，结果超时，然后查了一下，看有使用函数strtok和sscanf的，百度了一下，以前都不知道，学习了。

char *strtok(char s[], const char *delim);

功能是分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符串。

在这篇帖子：http://www.cnblogs.com/hoys/archive/2011/09/19/2180999.html有很详细的解释。

PS：总是感觉linux的string.h文件中的实现比较容易看，VS中是在strtok_s.inl文件中实现的，可以跟踪进去看看源码。

不过其中有些语句看不明白，拿出来大家讨论讨论：

下面这个是VS中的实现：

_FUNC_PROLOGUE
char * __cdecl _FUNC_NAME(char *_String, const char *_Control, char **_Context)
{
    unsigned char *str;
    const unsigned char *ctl = _Control;
    unsigned char map[32];
    int count;

    /* validation section */
    _VALIDATE_POINTER_ERROR_RETURN(_Context, EINVAL, NULL);
    _VALIDATE_POINTER_ERROR_RETURN(_Control, EINVAL, NULL);
    _VALIDATE_CONDITION_ERROR_RETURN(_String != NULL || *_Context != NULL, EINVAL, NULL);

    /* Clear control map */
    for (count = 0; count < 32; count++)
    {
        map[count] = 0;
    }

    /* Set bits in delimiter table */
    do {
        map[*ctl >> 3] |= (1 << (*ctl & 7));
    } while (*ctl++);

    /* If string is NULL, set str to the saved
    * pointer (i.e., continue breaking tokens out of the string
    * from the last strtok call) */
    if (_String != NULL)
    {
        str = _String;
    }
    else
    {
        str = *_Context;
    }

    /* Find beginning of token (skip over leading delimiters). Note that
    * there is no token iff this loop sets str to point to the terminal
    * null (*str == 0) */
    while ((map[*str >> 3] & (1 << (*str & 7))) && *str != 0)
    {
        str++;
    }

    _String = str;

    /* Find the end of the token. If it is not the end of the string,
    * put a null there. */
    for ( ; *str != 0 ; str++ )
    {
        if (map[*str >> 3] & (1 << (*str & 7)))
        {
            *str++ = 0;
            break;
        }
    }

    /* Update context */
    *_Context = str;

    /* Determine if a token has been found. */
    if (_String == str)
    {
        return NULL;
    }
    else
    {
        return _String;
    }
}

摘出一些语句（代码中好像不能直接放大字体：

do {
        map[*ctl >> 3] |= (1 << (*ctl & 7));
    } while (*ctl++);

这种实现的原理是什么，不理解？

刚发帖提问，有大神解释了，讨论帖：http://bbs.csdn.net/topics/390502089

我摘抄过来，果然实现的好巧妙哦：

map是个位集，每个字节存着8个标志位,一共32*8=256个标志位

map[*ctl >> 3] |= (1 << (*ctl & 7));

就是把map中第*ctl个标志位设为1

索引号除以8（>>3），算出是第几个字节

索引号模8（&0x07），算出是第几位

1 << 位数，得到一个相应位为1其它位为0的数值。

回到原题目，strtok函数会根据提供的分割字符修改原始字符串，其中使用了一个静态变量指针来记录下一个字符串的起始位置，查看strtok函数会看到：贴出来微软的实现，这里边涉及到了多线程的问题：

#ifdef _SECURE_VERSION
char * __cdecl strtok_s (
        char * string,
        const char * control,
        char ** context
        )
#else  /* _SECURE_VERSION */
char * __cdecl strtok (
        char * string,
        const char * control
        )
#endif  /* _SECURE_VERSION */
{
        unsigned char *str;
        const unsigned char *ctrl = control;

        unsigned char map[32];
        int count;

#ifdef _SECURE_VERSION

        /* validation section */
        _VALIDATE_RETURN(context != NULL, EINVAL, NULL);
        _VALIDATE_RETURN(string != NULL || *context != NULL, EINVAL, NULL);
        _VALIDATE_RETURN(control != NULL, EINVAL, NULL);

        /* no static storage is needed for the secure version */

#else  /* _SECURE_VERSION */

        _ptiddata ptd = _getptd();

#endif  /* _SECURE_VERSION */

        /* Clear control map */
        for (count = 0; count < 32; count++)
                map[count] = 0;

        /* Set bits in delimiter table */
        do {
                map[*ctrl >> 3] |= (1 << (*ctrl & 7));
        } while (*ctrl++);

        /* Initialize str */

        /* If string is NULL, set str to the saved
         * pointer (i.e., continue breaking tokens out of the string
         * from the last strtok call) */
        if (string)
                str = string;
        else
                str = _TOKEN;//这个是个宏定义，在前边有，是从当前线程的数据结构中取出来。

        /* Find beginning of token (skip over leading delimiters). Note that
         * there is no token iff this loop sets str to point to the terminal
         * null (*str == '\0') */
        while ( (map[*str >> 3] & (1 << (*str & 7))) && *str )
                str++;

        string = str;

        /* Find the end of the token. If it is not the end of the string,
         * put a null there. */
        for ( ; *str ; str++ )
                if ( map[*str >> 3] & (1 << (*str & 7)) ) {
                        *str++ = '\0';
                        break;
                }

        /* Update nextoken (or the corresponding field in the per-thread data
         * structure */
        _TOKEN = str;//存储

        /* Determine if a token has been found. */
        if ( string == str )
                return NULL;
        else
                return string;
}

if (string)
                str = string;
        else
                str = _TOKEN;

这段代码就是通过线程的数据结构存储，相当于linux实现中的static。

仔细看代码，（其他的跟strtok_s差不多）我只是分割字符串，整个_ptiddata ptd = _getptd()干什么，人家linux中是用静态指针来实现的，但是微软的实现中没有找到这个变量。其实不然，虽然没有明显的static，但是看他的注释发现是存储在线程的数据结构中的。

/* Update nextoken (or the corresponding field in the per-thread data
         * structure */
        _TOKEN = str;//存储

#ifdef _SECURE_VERSION
#define _TOKEN *context
#else  /* _SECURE_VERSION */
#define _TOKEN ptd->_token

通过_ptiddata ptd = _getptd()，它通过这个来获得当前的ptd。可是我们只有一个main，没有用_beginthread等API来创建ptd，那么一定是_getptd中做了一些事情，接着跟踪进去，（关于线程部分不是很了解，只是简单地说下自己的理解）。

_ptiddata ptd = _getptd_noexit();
        if (!ptd) {
            _amsg_exit(_RT_THREAD); /* write message and die */
        }
        return ptd;

单吧，就几句话，关键就在于_getptdgetptd_noexit()函数，（其他的代码就不贴了），首先通过TLS查找线程相关数据，如果没有找到，就分配一块内存，存放_tiddata结构，并将这块内存与__flsindex相关联。据说是使用了TLS技术，（Thread Local Storage），是用来存取线程相关数据的一种技术，在Win32中由操作系统的Tls*系列函数提供支持。【这里自己有限，也深入不下去了，不过对于题目来说已经了解的足够了】。

原题代码如下：配合着sscanf，就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1009;

char str[maxn];
int a[maxn];
char *p;
int n;
int i;

int main()
{
	while(cin >> str)
	{
		p=strtok(str,"5");
		n=0;

		while(p)
		{
			sscanf(p,"%d",&a[++n]);
			p=strtok(NULL,"5");
		}
		sort(a+1,a+1+n);
		for(i=1;i<=n;i++)
		{
			if(i!=1)
				cout << ' ';
			cout << a[i];
		}
		cout << endl;
	}
	return 0;
}

其实有时候一个很简单的不起眼的问题就能引发出很多问题出来，还是自己懂得太少，这么多问题都没有搞明白，继续努力吧。

杭电水题--排序关于strtok的一些问题

继续阅读

杭电ACM1031——Design T-Shirt

杭电 acm 1009 FatMouse' Trade FatMouse' Trade

【杭电】 1005 Number Sequence

杭电ACM刷题（2）：1005，Number Sequence

杭电oj数学题-1

杭电1098-数学题

杭电ACM课件学习简单数学题

[杭电]Number Sequence

杭电ACM1008电梯问题

杭电OJ 1007：Quoit Design

HDU's ACM 1008 Elevator

HDU1062:Text Reverse

HDU 1062 Text Reverse Text Reverse

杭电 acm 幸福列车（优先队列以及优先队列中的优先项如何排列）

hdu poj 1080 Human Gene Functions LCS 动态规划

杭电1280java实现

杭电水题--排序 关于strtok的一些问题

继续阅读

杭电水题--排序关于strtok的一些问题