分类目录归档:C语言

C,一种通用的、过程式的编程语言,广泛用于系统与应用软件的开发。于1969年至1973年间,为了移植与开发UNIX操作系统,由丹尼斯·里奇与肯·汤普逊,以B语言为基础,在贝尔实验室设计、开发出来。

最大公约数和最小公倍数

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

定理:gcd(a,b) = gcd(b,a mod b)

证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a, d|b,而r = a – kb,因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数,则
d | b , d |r ,但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

最小公倍数等于两个数的乘积除以最大公约数

/*
7-26 最大公约数和最小公倍数(15 分)

本题要求两个给定正整数的最大公约数和最小公倍数。
输入格式:

输入在一行中给出两个正整数M和N(≤1000)。
输出格式:

在一行中顺序输出M和N的最大公约数和最小公倍数,两数字间以1空格分隔。
输入样例:

511 292

输出样例:

73 2044

*/
#include <stdio.h>

int gcd(int, int);
int rec_gcd(int, int);
int lcm(int, int);
int main(void)
{
        int m, n;
        int g, l;
        scanf("%d%d", &m, &n);
        g = gcd(m, n);
        l = lcm(m, n);

        printf("%d %d\n", g, l);

        return 0;
}

int gcd(int u, int v)
{
        int r;
        while (v) {
                r = u % v;
                u = v;
                v = r;
        }

        return u;
}

int rec_gcd(int u, int v)
{
        if (!v)
                return u;
        else
                return rec_gcd(v, u % v);
}

int lcm(int u, int v)
{
        int r = gcd(u, v);
//      int l = u * (v / r);
//      int l = v * (u / r);
        int l = u * v / r;

        return l;
}


运行结果:

[lhf@lhf programming]$ ./26
511 292
73 2044

实现C语言的继承和多态

较经典的动物世界中的实例来举例:
假设动物们(包括人)都会吃(Eat),会走(Walk),会说(Talk),而派生类为 dog(汪星人) 和 cat(喵星人),当然还可以是更多,dog 和 cat 都有自己独特的 eat, walk 和 talk 方式,那么大致的代码如下:
代码无警告编译运行

基类头文件

// animal.h
#ifndef ANIMAL_H__
#define ANIMAL_H__

typedef struct animal_s_ animal_t;
typedef struct animal_ops_s_ animal_ops_t;

struct animal_s_ {
        char *name;
        animal_ops_t *animal_ops;
};

struct animal_ops_s_ {
        void (*eat)(char *);
        void (*walk)(int);
        void (*talk)(char *);
};

animal_t *animal_init(char *name);

void animal_eat(animal_t *, char *food);
void animal_walk(animal_t *, int steps);
void animal_talk(animal_t *, char *msg);

void animal_die(animal_t *);

#endif//ANIMAL_H__

基类实现

// animal.c
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "animal.h"

animal_t *animal_init(char *name)
{
        assert(name != NULL);
        size_t name_len = strlen(name);

        animal_t *animal = malloc(sizeof (*animal)
                + sizeof (animal_ops_t) + name_len + 1);
        memset(animal, 0, sizeof (*animal)
                + sizeof (animal_ops_t) + name_len + 1);
        animal->name = (char *)animal
                + sizeof (animal_t) + sizeof (animal_ops_t);
        memcpy(animal->name, name, name_len);
        animal->animal_ops = (animal_ops_t *)((char *)animal
                + sizeof (*animal));

        return animal;
}

void animal_eat(animal_t *animal, char *food)
{
        animal->animal_ops->eat(food);

        return;
}

void animal_walk(animal_t *animal, int steps)
{
        animal->animal_ops->walk(steps);

        return;
}

void animal_talk(animal_t *animal, char *msg)
{
        animal->animal_ops->talk(msg);

        return;
}

void animal_die(animal_t *animal)
{
        assert(animal != NULL);
        free(animal);

        return;
}

继续阅读

C语言输出菱形图像

使用C语言输出如下图像

思路:确定每行开始位置,和该行’*’的总个数。
代码文件,该图形可以整体右移,请调节 #define LEFT 1 参数

[lhf@localhost work]$ cat diamond.c
/**
 *     *
 *    * *
 *   * * *
 *    * *
 *     *
 */
#include <stdio.h>
#define LEFT 1  // right shift space

int main(void)
{
        int size = 0;
        printf("Input side number of diamond: ");
        scanf("%d", &size);
        int len = size * 2 - 1;
        int high = len;
        int width = len + LEFT;
        char diamond[high][width];

        const char dia = '*';
        const char pidd = ' ';

//      begin of start and number of diamond
        int begin = 0, n;
        for (int i = 0; i < high; i++) {
                if (i < size) {
                        begin = size - i - 1 + LEFT;
                        n = i + 1;
                } else {
                        begin = i - size + 1;
                        n = size - begin;
                        begin += LEFT;
                }
                for (int j = 0; j < width; j++) {
                        if ((j == begin) && (n--)) {
                                putchar(dia);
                                begin += 2;
                        } else
                                putchar(pidd);
                }
                putchar('\n');
        }

        return 0;
}

简单哈希表(hash table c)

hash表,有时候也被称为散列表。

引自wiki: 散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。
下面我们可以写一个简单的hash操作代码。

定义哈希表数据类型

/* hash.h */
#include <stdbool.h>

#ifndef HASH_H
#define HASH_H

typedef struct _NODE {
        int data;
        struct _NODE *next;
} NODE;

typedef struct _HASH_TABLE {
        NODE *value[10];
} HASH_TABLE;

HASH_TABLE *create_hash_table(void);
NODE *find_data_in_hash(HASH_TABLE *pHashTab, int data);
void print_hash_table(HASH_TABLE *pHashTab);
bool insert_data_into_hash(HASH_TABLE *pHashTab, int data);
bool delete_data_from_hash(HASH_TABLE *pHashTab, int data);
bool delete_idx_data_from_hash(HASH_TABLE *pHashTab, int idx);
bool delete_all_data_from_hash(HASH_TABLE *pHashTab);
bool reset_hash_table(HASH_TABLE *pHashTab);
bool destroy_hash_table(HASH_TABLE **ppHashTab);

#endif//HASH_H

继续阅读

C数据类型的DWORD

C数据类型的长度

类型  ILP32(位数)     LP64(位数)
char        8            8
short      16            16
int        32            32
long       32            64
long long  64            64
point      32            64

宏定义

    WORD       ->   unsigned   short 
    DWORD      ->   unsigned   int 
    LPVOID     ->   void   * 
    UINT       ->   unsigned   int 

按文件名存储-哈希表

通过散列函数将数据值和它的存储位置联系起来。即通过精心地向表载入元素实现,从而提高访问速度。本例中采取的解决冲突的办法是建立一个链表,挂在这个位置的后面,所有散列函数值为这个位置的元素都添加到这个链表中,可以从头部插入也可以从尾部追加,甚至可以再这个位置后面再挂一个散列表。代码实现了将文件名按字母a-z分类,不区分大小写。先以数组存储各节点,当发生冲突后即将节点加入链表中。然后遍历显示所有的文件名。

/* a2z.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define HASHSIZE 26
#define FILENAMELENGTH 20
#define TRUE 1
#define FALSE 0

struct file {
        char name[FILENAMELENGTH];
        struct file *next;
};

struct file * files[HASHSIZE];

char case_insensitive(char ch)
{
        if (isupper(ch))
                return ch - 'A' + 'a';
        return ch;
}

void init(void)
{
        int i;
        for (i = 0; i < HASHSIZE; i++)
                files[i] = NULL;
}

int hash(char *s)
{
        return case_insensitive(s[0]) - 'a';
}

int search(char *s)
{
        int num = hash(s);
        if (files[num] != NULL) {
                struct file *p = files[num];
                while (p != NULL) {
                        if (strcmp(p->name, s) == 0)
                                return TRUE;
                        p = p->next;
                }
        }

        return FALSE;
}

void insert(char *s)
{
        if (search(s) == FALSE) {
                int num = hash(s);
                struct file *new_node = malloc(sizeof (struct file));
                strcpy(new_node->name, s);
                if (files[num] == NULL) {
                        files[num] = new_node;
                        files[num]->next = NULL;
                } else {
                        new_node->next = files[num];
                        files[num] = new_node;
                }
        }

        return;
}

void free_node(struct file *p)
{
        free(p);

        return;
}


void del_node(char *s)
{
        if (search(s) == TRUE) {
                struct file *p = files[hash(s)], *q;
                if (strcmp(p->name, s) == 0) {
                        q = p;
                        files[hash(s)] = p->next;
                        free_node(q);
                } else {
                        while (p != NULL) {
                                q = p;
                                p = p->next;
                                if (strcmp(p->name, s) == 0)
                                        free_node(q);
                        }
                }
        }

        return;
}


void del(int num)
{
        struct file *p =files[num], *q;
        while (p != NULL) {
                q = p;
                p = p->next;
                free(q);
        }

        return;
}

void destroy(void)
{
        int i;

        for (i = 0; i < HASHSIZE; i++)
                del(i);

        return;
}

void show(int num)
{
        struct file *p = files[num];
        if (p != NULL) {
                printf("For file begins with '%c': \n", num + 'a');
                while (p != NULL) {
                        printf("%s\n", p->name);
                        p = p->next;
                }
                printf("\n");
        }



}

void show_all(void)
{
        int i;
        for (i = 0; i < HASHSIZE; i++)
                show(i);

        return;
}

int main(void)
{
        char * file_name[] = {
                "apple", "because", "song", "Dan", "discuz", "cartoon",
                "nobody", "android", "information", "love", "like", "No",
                "nothing", "like", "alone", "nothing", "sizeof", "Yes",
        };

        int len = sizeof file_name / sizeof (char *);
        int i;
        for (i = 0; i < len; i++)
                insert(file_name[i]);
        show_all();

        printf("---------------------------------\n");
        del_node("like");
        show_all();
        destroy();

        return 0;
}

继续阅读

printf 打印颜色

引言: 控制字符的通用格式如下:

Esc[{attr1};…;{attrn}m
其中: Esc 是转义字符, 其值为”\033″;
[ 是常量的左中括号;
{attr1};…{attrn} 是若干属性, 通常是由一个有特定意义的数字代替, 每个属性之间用分号分隔;
m 就是字面常量字符m, 结束标志

属性列表如下:
>>1. 通用格式控制:
0 重置所有属性
1 高亮/加粗
2 暗淡
4 下划线
5 闪烁
7 反转
8 隐藏

>>2. 前景色:
30 黑色
31 红色
32 绿色
33 黄色
34 蓝色
35 品红
36 青色
37 白色

>>3. 背景色:
40 黑色
41 红色
42 绿色
43 黄色
44 蓝色
45 品红
46 青色
47 白色
头文件1:

/* font color */
#define NONE            "\e[0m"         /* default */
#define BLACK           "\e[0;30m"      /* black */
#define L_BLACK         "\e[1;30m"      /* light black */
#define RED             "\e[0;31m"      /* red */
#define L_RED           "\e[1;31m"      /* light red */
#define GREEN           "\e[0;32m"      /* green */
#define L_GREEN         "\e[1;32m"      /* light green */
#define BROWN           "\e[0;33m"      /* brown */
#define YELLOW          "\e[1;33m"      /* yellow */
#define BLUE            "\e[0;34m"      /* blue */
#define L_BLUE          "\e[1;34m"      /* light blue */
#define PURPLE          "\e[0;35m"      /* purple */
#define L_PURPLE        "\e[1;35m"      /* light purple */
#define CYAN            "\e[0;36m"      /* cyan */
#define L_CYAN          "\e[1;36m"      /* light_cyan */
#define GRAY            "\e[0;37m"      /* gray */
#define WHITE           "\e[1;37m"      /* white */

/* background color*/
#define BG_BLACK        "\e[40m"        /* black background */
#define BG_RED          "\e[41m"        /* red background */
#define BG_GREEN        "\e[42m"        /* green background */
#define BG_YELLOW       "\e[43m"        /* yellow background */
#define BG_BLUE         "\e[44m"        /* blue background */
#define BG_CYAN         "\e[45"         /* cyan background */
#define BG_L_CYAN       "\e[46"         /* light cyan background */
#define BG_WHITE        "\e[47"         /* white background */

/* font attribure */
#define BOLD            "\e[1m"         /* blod/light */
#define UNDERLINE       "\e[4m"         /* underline */
#define BLINK           "\e[5m"         /* blink */
#define REVERSE         "\e[7m"         /* reverse */
#define HIDE            "\e[8m"         /* hide */
#define CLEAR           "\e[2J"         /* clear */
#define CLRLINE         "\r\e[K"        //or "\e[1K\r clear line "

头文件2:

/* cprint.h
 * color print
 */

/* font attribute */
#define NONE            "\e[0m"         /* defaults */
#define BOLD            "\e[1m"         /* blod */
#define H_BRIGHT        "\e[2m"         /* half-bright */
#define UNDERLINE       "\e[4m"         /* underscore */
#define BLINK           "\e[5m"         /* blink */
#define REVERSE         "\e[7m"         /* reverse video */
#define HIDE            "\e[8m"         /* hide */
#define DOUBLE_UNDERLINE "\e[21m"       /* doubly underline */
#define INTERSITY       "\e[22m"        /* intensity */
#define UNDERLINE_OFF   "\e[24m"        /* underline off */
#define BLINK_OFF       "\e[25m"        /* blink off */
#define REVERSE_OFF     "\e[27m"        /* reverse video off */
#define CLEAR           "\e[2j"         /* clear */
#define CLRLINE         "\r\e[k"        /* or "\e[1k[r clear line" */

/* foreground color */
#define BLACK           "\e[30m"        /* black foreground */
#define RED             "\e[31m"        /* red foreground */
#define GREEN           "\e[32m"        /* green foreground */
#define BROWN           "\e[33m"        /* brown foreground */
#define YELLOW          "\e[33m"
#define BLUE            "\e[34m"        /* blue foreground */
#define MAGENTA         "\e[35m"        /* magenta foreground */
#define CYAN            "\e[36m"        /* cyan foreground */
#define WHITE           "\e[37m"        /* white foreground */
#define COLOR           "\e[39m"        /* default foreground */

/* background color*/
#define BG_BLACK        "\e[40m"        /* black background */
#define BG_RED          "\e[41m"        /* red background */
#define BG_GREEN        "\e[42m"        /* green background */
#define BG_BROWN        "\e[43m"        /* brown background */
#define BG_YELLOW       "\e[43m"
#define BG_BLUE         "\e[44m"        /* blue background */
#define BG_MAGENTA      "\e[45m"        /* magenta background */
#define BG_CYAN         "\e[46m"        /* cyan background */
#define BG_WHITE        "\e[47m"        /* white background */
#define BG_COLOR        "\e[49m"        /* defaulte background */

正文, 如何使用printf函数在控制台彩色打印

转义序列以控制字符’ESC’开头。该字符的ASCII码十进制表示为27,十六进制表示为0x1B,八进制表示为033。多数转义序列超过两个字符,故通常以’ESC’和左括号'[‘开头。该起始序列称为控制序列引导符(CSI,Control Sequence Intro),通常由’\033[‘或’\e[‘代替。
继续阅读

二分法查找重复元素

二分法查找重复元素

条件:
随机生成若果个自然数
要求:
如果所查找的数值重复,返回第一个出现的数值下标。如果没有重复则返回对应的数值下表,如果没有查找到,则返回-1;
前提:
数组必须是排列好的从小到大的数组。程序中通过快排算法得到数组。
算法通过递归改进得出第一个出现的数组下标。我们知道,笼统上说二分法查找返回的是离中值下标最近的下标。
继续阅读

字符串转换浮点数函数

atof函数,支持科学计数法

/*
 * atof.c
 */
#include <stdio.h>
#include <ctype.h>

int m_getline(char line[], int max);
double atof(char s[]);
int atoi(char s[]);

#define MAX 100

int main(void)
{
        int n;
        double x;
        char str[MAX];

        while (m_getline(str, MAX) > 0) {
                x = atof(str);
                n = atoi(str);
                printf("\t%g %d\n", x, n);
        }

        return 0;
}

int m_getline(char s[], int lim)
{
        int i, c;
        i = 0;
        while (--lim > 0 && (c = getchar()) != '\n' && c != EOF)
                s[i++] = c;
        if (c == '\n')
                s[i++] = c;
        s[i] = '\0';

        return i;
}

double atof(char s[])
{
        int i, sign, n, esign, e;
        double val, power;

        for (i = 0; isspace(s[i]); i++)
                ;

        sign = (s[i] == '-') ? -1 : 1;

        if (s[i] == '-' || s[i] == '+')
                i++;

        for (val = 0.0; isdigit(s[i]); i++)
                val = 10.0 * val + (s[i] - '0');

        if (s[i] == '.')
                i++;
        for (power = 1.0; isdigit(s[i]); i++) {
                val = 10.0 * val + (s[i] - '0');
                power *= 10.0;
        }

        if (s[i] == 'e' || s[i] == 'E') {
                i++;
                esign = (s[i] == '-') ? -1 : 1;

                if (s[i] == '-' || s[i] == '+')
                        i++;
                for (n = 0; isdigit(s[i]); i++)
                        n = 10 * n + (s[i] - '0');

                e = 1;
                while (n-- > 0)
                        e *= 10;
                if (esign == 1)
                        return sign * val / power * e;
                else
                        return sign * val / power / e;
        } else {
                return sign * val / power;
        }
}

int atoi(char s[])
{
//      double atof(char s[]);
        return (int) atof(s);
}

大数阶乘C语言

算法1:

/*
 * factorial of large numbers
 */
#include <stdio.h>
#include <string.h>

#define MAX 100000

int main(void)
{
        int n, i, j, up, tmp;
        int res[MAX];
        while (scanf("%d", &n) > 0 && n >= 0) {
                memset(res, 0, sizeof res);     /* initialized to 0 */
                res[0] = 1;
                for (i = 2; i <= n; i++) {
                        up = 0;         /* carry initialized to 0 */
                        for (j = 0; j < MAX; j++) {
                                tmp = res[j] * i + up;  /* carry */
                                res[j] = tmp % 10;
                                up = tmp / 10;
                        }
                }
                for (i = MAX - 1; i >= 0; i--)  /* ignores the leading 0 */
                        if (res[i])
                                break;
                for (j = i; j >= 0; j--)
                        printf("%d", res[j]);
                printf("\n");
        }

        return 0;
}

算法2:

/*
 * factorial of large numbers
 */
#include <stdio.h>
#include <string.h>

#define CLR(arr, val) memset(arr, val, sizeof (arr))
#define MAX 10000

int main(void)
{
        int n, i, j;
        int res[MAX];

        while (scanf("%d", &n) > 0 && n >= 0) {
                CLR(res, 0);
                res[0] = 1;
                for (i = 1; i <= n; i++) {
                        for (j = 0; j < MAX; j++)
                                res[j] *= i;
                        for (j = 0; j < MAX; j++) {
                                if (res[j] > 9) {
                                        res[j + 1] += res[j] / 10;
                                        res[j] %= 10;
                                }
                        }
                }
                for (i = MAX - 1; i >= 0; i--)
                        if (res[i])
                                break;
                for (j = i; j >= 0; j--)
                        printf("%d", res[j]);
                printf("\n");
        }

        return 0;
}