C语言文件操作

在C语言中,对文件的操作都通过标准库中的函数或宏来进行。标准库不是C语言本身的构成部分,但是支持标准C的实现都会提供该函数库中的函数声明、类型以及宏定义。比如,与文件操作相关的函数都定义在输入输出头文件<stdio.h>中。

流、缓存和文件

流(stream)不是缓存,也不等于文件。流是一种逻辑的、与设备无关的操纵多种外设方式,它把数据输入输出的操作对象(如磁盘文件或是物理设备的打印机、显示器、键盘等)都抽象化为一种“流”而不管其具体结构,这样涉及到流的操作函数都可用于各种对象,提高了编程的通用性。《C程序设计语言》中说“流是与磁盘或其他外围设备关联的数据的源或目的地,打开一个流,将把该流与一个文件或设备连接起来,关闭流将断开这种连接”。从代码的实现上来看,一个流可以由一个FILE结构来描述,而FILE结构里包含了指向缓冲区的指针和文件描述符,打开一个流时它通过指向缓冲区的指针和文件描述符来和缓存与文件(或设备)关联。更多的介绍还可以看这里这里

文件操作函数

FILE *fopen(const char *filename, const char *mode)
fopen函数打开filename指定的文件,并返回一个与之相关联的流。如果打开操作失败,则返回NULL。
继续阅读

KMP算法

KMP算法是字符串匹配的一种改进算法,在1977年由D. E. Knuth,J. H. Morris和V. R. Pratt一起提出,并以他们名字的首字母命名。和朴素的模式匹配算法相比,KMP算法最大的特点就是主串指针不回溯。它利用已经得到的“部分匹配”信息来减少不必要的比较而加快字符串的匹配速度。

KMP算法的本质

KMP算法本质上是实现了对自动机的模拟。它通过构造一个有限自动机来搜寻某给定的模式在正文中出现的位置。整个算法的核心就是对自动机的构建(或前缀函数的构建,KMP算法不用计算变迁函数,而是根据模式预先计算出一个辅助函数next来实现更快速的状态切换),当完成有限自动机的构建之后对主串的搜寻就显得很简单了。

前缀函数next的构建

模式的前缀函数包含有模式与其自身的位移进行匹配的信息。这些信息可用于避免在朴素的模式匹配算法中对无用位移的测试。比如主串和模式串在主串指针为Ti、模式串指针为Pj处匹配失败时,可以主串指针不回溯并直接取next函数的值next[j] = k将模式串向右滑动到第k个字符处重新开始比较,而不用去做无用位移的测试。只是这样的操作能成立k必须要满足一定的条件,如下所示:

首先,如果模式串能直接向右滑动到第k个字符处重新开始比较则说明模式串中的前k-1个字符必然已经和主串匹配了,也即必然已经有下面式子,且为了能最大化的向右移动则不能存在更大的k’满足下面式子:
继续阅读

朴素模式匹配算法

朴素模式匹配算法又称简单匹配算法或Brute-Force算法,它是字符串模式匹配中比较简单的一种算法。它从主串的第一个字符开始进行模式匹配,依次比较主串和模式串中的每个字符,若比较全部相等(模式匹配成功),则返回模式串中第一个字符在主串中的位置,否则主串指针从比较失败的字符处回溯到第二个字符开始重新和模式串进行匹配,这样依此下去,直到和模式串匹配成功或到主串的末尾(匹配不成功)为止。

朴素模式匹配算法的C/C++代码实现:

// 定义一个字符串结构体
typedef struct  {
    char data[MAX_SIZE];
    int length;
} string;

int BruteForce(string s, string t)
{
    int i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1; // 主串指针回溯
            j = 0;
        }
    }

    if (j > t.length)
        return i - t.length;
    else
        return -1;
}

继续阅读

字符串函数

几个常见字符串处理函数

/* *
 * str开头的函数部分
 * In the following functions,
 * variables s and t are of type char *;
 * cs and ct are of type const char *;
 * n is of type size_t;
 * and c is an int converted to char.
 */

/* strcpy - copy string ct to string s,
 including '\0'; return s. */
char *strcpy(char *s, const char *ct)
{
    char *tmp = s;

    while ((*tmp++ = *ct++) != '\0')
        /* nothing */;
    return s;
}

/* strcat - concatenate string ct to end of string s;
 return s. *
char *strcat(char * s, const char * ct)
{
    char *tmp = s;

    while (*tmp)
        tmp++;
    while ((*tmp++ = *ct++) != '\0')
        /* nothing */;

    return s;
}

/* strcmp - compare string cs to string ct,
 return <0 if cs<ct, 0 if cs==ct, or >0 if cs>ct. */
int strcmp(const char *cs,const char *ct)
{
    register signed char __res;

    while (1) {
        if ((__res = *cs - *ct++) != 0 || !*cs++)
            break;
    }

    return __res;
}

/* strlen - return length of cs. *
size_t strlen(const char *cs)
{
    const char *tmp;

    for (tmp = cs; *tmp != '\0'; ++tmp)
        /* nothing */;
    return tmp - cs;
}

/**
 * mem开头的函数部分
 * The mem... functions are meant for manipulating
 * objects as character arrays; the intent is an
 * interface to efficient routines.
 * In the following functions, s and t are of type void *;
 * cs and ct are of type const void *; n is of type size_t;
 * and c is an int converted to an unsigned char.
 */

/* memcpy - copy n characters from ct to s, and return s. */
void *memcpy(void *s, const void *ct, size_t n)
{
    char *dst = (char *)s, *src = (char *)ct;

    while (n--)
        *dst++ = *src++;

    return s;
}

/* memmove - same as memcpy except that it works even
 if the objects overlap. */
void *memmove(void *s, const void *ct, size_t n)
{
    char *dst, *src;

    if (s <= ct) {
        dst = (char *)s;
        src = (char *)ct;
        while (n--)
            *dst++ = *src++;
    } else {
        dst = (char *)s + n;
        src = (char *)ct + n;
        while (n--)
            *--dst = *--src;
    }

    return s;
}

/* memcmp - compare the first n characters of cs with ct;
 return as with strcmp. */
int memcmp(const void *cs, const void *ct, size_t n)
{
    const unsigned char *su1, *su2;
    signed char res = 0;

    for( su1 = cs, su2 = ct; 0 < n; ++su1, ++su2, n--)
        if ((res = *su1 - *su2) != 0)
            break;
    return res;
}

/* memset - place character c into first n
 characters of s, return s. */
void *memset(void *s, char c, size_t n)
{
    char *xs = (char *)s;

    while (n--)
        *xs++ = c;

    return s;
}

基数排序

基数排序和计数排序一样,是非基于比较的排序算法,它借助“分配”和“收集”两种操作对单逻辑关键字进行排序(基于/桶排序),它的排序速度很快,时间复杂度为线性,但由于需要的辅助空间太大(n(radix+1)),因此长期无法应用。直到1954年有人提出用“计数”代替“分配”才得以使它能在计算机上实现。此后,又有人提出用链表作为存储数据的结构,这样又能减少一些辅助空间,这也是一种比较好的实现方法(只是算法要较复杂)。

基数排序分为MSD(最高位优先)基数排序和LSD(最低位优先)基数排序,MSD从左到右处理关键字的位数,首先处理最重要的数字。它比较符合常规的思维,所需处理的信息量也较少。但按MSD进行排序,必须将序列逐层分割成若干个子序列,然后对各子序列分别进行排序;而LSD则从右到左先处理最不重要的数字,这样虽然可能花费了一些时间来处理不会影响结果的信息,但它不用分子序列,对每个关键字都是整个序列参加排序,而且对具体的应用还可以对其进行改进。因此在很多排序应用中都选择这种方法。

基数排序(LSD/用计数排序)的C/C++代码实现:

void radix_sort(int a[], int length)
{
    int i, j, digit;
    int c[16];
    int tmp[ARRAY_SIZE];
    for (i = 0; i < HEX; ++i) {
        for (j = 0; j < 16; ++j) c[j] = 0;
        for (j = 0; j < length; ++j) c[a[j]>>4*i&0xf]++;
        for (j = 1; j < 16; ++j) c[j] += c[j-1];
        for (j = length - 1; j >= 0; --j) {
            digit = a[j] >> 4 * i & 0xf;
            tmp[ c[digit]-1] = a[j];
            c[digit]--;
        }
        for (j = 0; j < length; ++j) a[j] = tmp[j];
    }
}

继续阅读