posts - 2, comments - 0, trackbacks - 0, articles - 0

C库源代码实现: strtok

Posted on 2009-06-01 14:52 尹泉 阅读(8727) 评论(0)  编辑 收藏 引用 所属分类: C库源代码实现

NetBSD实现:

   1: char*  strtok_r(char* string_org,const char* demial,char** last)
   2: {
   3: const char* spanp; //span表示分隔,p表示指针
   4: char c, sc; //c表示char字符,sc表示 span char
   5: char* tok;  //token表示分隔的段
   6:  
   7: //当开始结尾都为NULL的时候,说明没有字符被查找,所以返回NULL
   8: if (string_org == NULL  && (string_org = *last) == NULL)
   9:     {
  10:     return (NULL);
  11:     }
  12:  
  13: //由goto组成的循环是在扫描字符串的时候,当遇到所需要匹配的字符时,略过这个字符。        
  14: cout:
  15: c = *string_org++;
  16:     
  17: for (spanp = demial; (sc = *spanp++) != 0; )
  18:     {
  19:     if (c == sc)
  20:         {
  21:         goto count;
  22:         }
  23:     }
  24:  
  25: //下一个字符为0,则表示到达了搜索结果,把last置为NULL,并返回NULL            
  26: if (c == 0)
  27:     {
  28:     *last = NULL;
  29:     return (NULL);
  30:     }
  31:  
  32: //把原始的字符串指针回退。            
  33: tok = string_org -1;
  34:  
  35: //开始扫描字符串中是否含有要匹配的字符,之后把这个匹配字符之前的部分返回。
  36: //这看似是个无限循环,但当源字符串和匹配字符串都走到结尾时,也就是string_org和sc都为NULL时,最外层循环最后会走到return(tok)结束循环。
  37: for (;;)
  38:     {
  39:     c = *string_org++;
  40:     spanp = demial;
  41:     
  42:     do 
  43:         {
  44:         if ((sc = *spanp++) == c) 
  45:             {
  46:             if (c == 0)
  47:                 {
  48:                 string_org = NULL;
  49:                 }
  50:             else
  51:                 {
  52:                 string_org[-1] = 0;
  53:                 }
  54:             *last = string_org;
  55:             return (tok);
  56:             }
  57:         } while (sc != 0);
  58:     }
  59:     
  60: }

在NetBSD中strtok的实现:

   1: //把last设置为一个静态局部变量来保存余下内容的地址。
   2: char *
   3: strtok(char *s, const char *delim)
   4:     {
   5:     static char *lasts;
   6:  
   7:     return strtok_r(s, delim, &lasts);
   8:     }

微软实现:

   1: char*  strtok_r(char* string_org,const char* demial)
   2: {
   3: static unsigned char* last; //保存分隔后剩余的部分
   4: unsigned char* str;         //返回的字符串
   5: const unsigned char* ctrl = (const unsigned char*)demial;//分隔字符
   6:  
   7: //把分隔字符放到一个索引表中。定义32是因为ASCII字符表最多是0~255个,也是说用最大的255右移3位,也就是除以8一定会是32中的一个数。
   8: unsigned char map[32]; 
   9: int count;
  10:  
  11: //把map全部清为0,之后相与的操作,与0的都为0
  12: for (count =0; count <32; count++)
  13:     {
  14:     map[count] = 0;
  15:     }
  16:  
  17: //把匹配字符放入表中
  18: //放入的算法是把匹配字符右移3位,相当于除以8,的数值 并上(加上)
  19: //匹配字符与7,得到低3位,得出的结果,是把1左移的位数。最大左移位数是7,也就是所表示的最大值是128,    
  20: do 
  21:     {
  22:     map[*ctrl >> 3] |= (1 << (*ctrl & 7));
  23:     } while (*ctrl++);
  24:     
  25: //原始字符串是否为空,如果为空表示第二次获取剩余字符的分隔部分。    
  26: if (string_org)
  27:     {
  28:     str = (unsigned char*)string_org;
  29:     } 
  30: else
  31:     {
  32:     str = last;
  33:     }
  34:  
  35: //在表中查找是否有匹配的字符,如果有略过    
  36: while ((map[*str >> 3] & (1 << (*str & 7)))  && *str)
  37:     {
  38:     str++;
  39:     }
  40:  
  41: //重置需要扫描的字符串    
  42: string_org = (char*)str;
  43:  
  44: //开始扫描
  45: for (;*str; str++)
  46:     {
  47:     if ( map[*str >> 3] & (1 << (*str & 7)))
  48:         {
  49:         *str++ = '\0';//当找到时,把匹配字符填为0,并且把str指向下一位。
  50:         break; //退出循环             
  51:         }
  52:             
  53:     }
  54:     
  55: last =str; // 把剩余字符串的指针保存到静态变量last中。
  56:     
  57: if (string_org == (char*)str)
  58:     {
  59:     return NULL; //没有找到,也就是没有移动指针的位置,返回NULL
  60:     }
  61: else
  62:     {
  63:     return string_org; //找到了,返回之前字符串的头指针
  64:     }
  65: }

 

对比:NetBSD的方法是节约了空间,牺牲了时间(它的时间复杂度为N2)
     而微软的方法是节约了时间(它的时间复杂度为N),牺牲了空间(开了一个32个8位的空间)


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理