杭電水題--排序關于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的一些問題