1 复制

char* strcpy (char *s1, const char *s2);
将字符串s2复制到s1指定的地址

char* strncpy (char *s1, const char *s2, size_t len);
void*  memcpy (void *s1, const void *s2, size_t len);
将s2的前len个字符(字节)复制到s1中指定的地址, 不加'\0'

void* memmove (void *s1, const void *s2, size_t len);
当源单元和目的单元缓冲区交迭时使用

size_t strxfrm (char *s1, const char *s1, size_t len);
根据程序当前的区域选项, 将s2的前len个字符(字节)复制到s1中指定的地址, 不加'\0'

2 连接

char* strcat (char *s1, const char *s2);
将字符串s2连接到s1尾部

char* strncat (char *s1, const char *s2, size_t len);
将字符串s2的前len个字符连接到s1尾部, 不加'\0'

3 比较

int strcmp (const char *s1, const char *s2);
比较字符串s1和s2

int strncmp (const char *s1, const char *s2, size_t len);
int  memcmp (const void *s1, const void *s2, size_t len);
对s1和s2的前len个字符(字节)作比较

int strcoll (const char *s1, const char *s2);
根据程序当前的区域选项中的LC_COLLATE, 比较字符串s1和s2

4 查找

//获得prefix数组
int* GetPrefixValue(char* strPattern, int iPatternLen)
{
    int i, j; /* i runs through the string, j counts the hits*/
    int* prefix = (int*)malloc(iPatternLen*sizeof(int));
   
    i = 1; j = 0;
    prefix[0] = 0;
   
    while(i<iPatternLen)
    {
        if(strPattern[i] == strPattern[j])
        {
            prefix[i] = ++j;
        }
        else
        {
            j = 0;
            prefix[i] = j;
        }
       
        i++;
    }
   
    return prefix;          
}   

//返回target串在pattern串中第一次匹配的index
int KMPStringMatch(char* strPattern, int iPatternLen, char* strTarget, int iTargetLen, int* prefix)
{
    int i = 0;
    int j = 0;
   
    while(i<iPatternLen && j<iTargetLen)
    {
        if(j==0 || strPattern[i]==strTarget[j])
        {
            i++;  j++;
        }
        else
        {
            j = prefix[j];
        }
    }            
   
    free(prefix);
    
    if(j==iTargetLen)
    {
        return i-j;
    }
    else
    {
        return -1;
    }        
}        

int KMP(char* strPattern, char* strTarget)
{
    int* prefix = GetPrefixValue(strPattern, strlen(strPattern));
    int index = KMPStringMatch(strPattern, strlen(strPattern), strTarget, strlen(strTarget), prefix);
    return index;
}

//在文本文件中查找target串出现的行数
int SearchInTxtFile(char* fileName, char* strTarget)
{
    FILE* hFile = fopen(fileName, "r");
   
    char str[1024];
    int count = 0;
   
   
    while(fgets(str, 1024, hFile)) 
    {
        if(KMP(str, strTarget)!=-1)
        {
            count++;
        }   
    }     
   
    fclose(hFile);
    hFile=NULL;
   
    return count;
}    
            
int main()
{
    char ch;
    char str1[] = "abcabcabctasksb,abTo";
    char str2[] = "abc";
   
    double t=clock();
    printf("%d\n", KMP(str1,str2));
    printf("耗时：%f毫秒！\n", (clock()-t));
   
    t=clock();
    printf("find %d \n", SearchInTxtFile("c:\\txt.txt", "NULL"));
    printf("耗时：%f毫秒！\n", (clock()-t));
    scanf("%c", &ch);

    return 0;
} 

#include <iostream>
using namespace std;

template<class T>
class Chain;

template<class T>
class ChainNode
{
 friend class Chain<T>;
 friend ostream& operator<<(ostream& out, const Chain<T>& x);
private:
 T data;
 ChainNode<T> *link;
};

template<class T>
class Chain{

public:
 Chain(int p) {first = 0;};
 ~Chain();
 bool IsEmpty() const {return first == 0;}
 int Length() const;
 bool Find(int k, T& x) const;
 int Search(const T& x) const;
 //Chain<T>& Delete(int k, T& x);
 Chain<T>& Insert(int k, const T& x);
 void Output(ostream& out = cout) const;
private:
 ChainNode<T> *first; // 指向第一个节点的指针
};

template<class T>
ostream& operator<<(ostream& out, const Chain<T>& x);

#endif  // _CHAIN

  在Chain.cpp中对Chain.h中声明的函数进行了定义，具体内容如下：

#include "Chain.h"
#include <iostream>
using namespace std;

template<class T>
Chain<T>::~Chain()
{
 //链表的析构函数,用于删除链表中的所有节点
 ChainNode<T> *ptr = first;
 while (ptr)
 {
  first = ptr->link;
  delete ptr;
  ptr = first;
 }
}

template<class T>
int Chain<T>::Length() const
{
 //返回链表中的元素总数
 int count = 0;
 ChainNode<T> *ptr = first;
 while (ptr)
 {
  ++count;
  ptr = ptr->link;
 }
 return count;
}

template<class T>
bool Chain<T>::Find(int k, T& x) const
{
 //寻找链表中的第k个元素，并将其传送至x
 //如果不存在第k个元素，则返回false，否则返回true
 if (k < 1)
 {
  return false;
 }
 int count = k;
 ChainNode<T> *ptr = first;
 while (count && ptr)
 {
  --count;
  ptr = ptr->link
 }
 if (!ptr)
 {
  return false;
 }
 x = ptr->data;
 return true;
}

template<class T>
int Chain<T>::Search(const T& x) const
{
 //寻找x，如果发现x，则返回x的地址
 //如果x不在链表中，则返回0
 int count = 1;
 ChainNode<T> *ptr = first;
 while(ptr && (ptr->data!=x))
 {
  ++count;
  ptr = ptr->link;
 }
 if (ptr)
 {
  return count;
 }
 else
 {
  return 0;
 }
}

template<class T>
void Chain<T>::Output(ostream& out = cout) const
{
 ChainNode<T> *ptr = first;
 while (ptr)
 {
  out<<ptr->data<<"  ";
  ptr = ptr->link;
 }
}

//重载<<运算符
template<class T>
ostream& operator<<(ostream& out, const Chain<T>& x)
{
 x.Output(out);
 return out;
}

template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{
 ChainNode<T> *ptr = first;
 int count = 0;
 while (ptr && count < k)
 {
  ++count;
  ptr = ptr->link;
 }
 if (!ptr)  //如果没到第k个节点
 {
 
 }
 else
 {
  //要插入的新节点
  ChainNode<T>* cn = new ChainNode<T>;
  cn->data = x;
  cn->link = 0;
  if (ptr->link==0)  //到达了链表的结尾
  {
   ptr->link = cn;
  }
  else  //没到达结尾
  { 
   cn->link = ptr->link;
   ptr->link = cn;
  }
 }
 return *this
}

 在main.cpp中进行测试，测试的内容很少，但是刚开始就进行不了了。main.cpp内容如下：

#include "Chain.h"
using namespace std;

int main()
{
 Chain<int> c;
 cout<<c.Length();
 return 0;
}

编译的时候没有问题，但是在连接的时候就出现了问题，报错如下：
--------------------Configuration: Chain - Win32 Debug--------------------
Linking...
main.obj : error LNK2001: unresolved external symbol "public: __thiscall Chain<int>::~Chain<int>(void)" (??1?$Chain@H@@QAE@XZ)
main.obj : error LNK2001: unresolved external symbol "public: int __thiscall Chain<int>::Length(void)const " (?Length@?$Chain@H@@QBEHXZ)
Debug/Chain.exe : fatal error LNK1120: 2 unresolved externals
Error executing link.exe.

Chain.exe - 3 error(s), 0 warning(s)
但是从报错信息来看，应该是在main.cpp中没有找到所用到的函数 ~Chain<int>(void)和Length()的定义，在main.cpp中一共用到了三个函数，构造函数Chain()，但是构造函数是在Chain.h中定义的，所以编译器找到了其定义，但是另外两个函数是在Chain.cpp中定义的，而且目前报错没有找到，但是如果在main.cpp中引入#include "Chain.cpp"时，编译和连接就没有问题，这就证实了原来的估计是没有错的。我实在是不知道问题出现在哪里，所以希望哪位高手看出问题来的话，请告诉我，多谢了！

#ifndef _CHAIN
#define _CHAIN

template<class T>
class ChainNode
{
 friend class Chain<T>;
private:
 T data;
 ChainNode<T> *link;
};

template<class T>
class Chain{
public:
 Chain()
 {
  first = 0;
 };
 ~Chain();
 bool IsEmpty() const {return first == 0;}
 int Length() const;
 bool Find(int k, T& x) const;
 int Search(const T& x) const;
 //Chain<T>& Delete(int k, T& x);
 Chain<T>& Insert(int k, const T& x);
 void Output(ostream& out = cout) const;
private:
 ChainNode<T> *first; // 指向第一个节点的指针
};

#endif  // _CHAIN

结果报错：
--------------------Configuration: Chain - Win32 Debug--------------------
Compiling...
Chain.cpp
g:\work plan\c++ code practice\chain\chain.h(17) : error C2059: syntax error : '<'
        g:\work plan\c++ code practice\chain\chain.h(21) : see reference to class template instantiation 'ChainNode<T>' being compiled
g:\work plan\c++ code practice\chain\chain.h(17) : error C2238: unexpected token(s) preceding ';'
        g:\work plan\c++ code practice\chain\chain.h(21) : see reference to class template instantiation 'ChainNode<T>' being compiled
g:\work plan\c++ code practice\chain\chain.h(40) : error C2989: 'Chain' : template class has already been defined as a non-template class
        g:\work plan\c++ code practice\chain\chain.h(17) : see declaration of 'Chain'
g:\work plan\c++ code practice\chain\chain.cpp(6) : error C2059: syntax error : '<'
g:\work plan\c++ code practice\chain\chain.cpp(6) : error C2588: '::~Chain' : illegal global destructor
g:\work plan\c++ code practice\chain\chain.cpp(6) : fatal error C1903: unable to recover from previous error(s); stopping compilation
Error executing cl.exe.

Chain.obj - 6 error(s), 0 warning(s)

感觉从代码来看应该是没有问题的，如果哪个高手看出问题来了请一定告诉我啊，如果知道编译不通过的原因也请一定要告诉我啊。没办法，最后采用解决的办法就是修改ChainNode的定义了，定义为结构体:)
template<class T>
struct ChainNode
{
  T data;
  ChainNode<T> *link;
};
反正结构体中的数据成员都是public的，至于访问限制的实现就依靠迭代器来实现了，g++的STL中的树结点不也是结构体吗？:)