标签归档:C语言

最大公约数和最小公倍数

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数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

继续阅读

按文件名存储-哈希表

通过散列函数将数据值和它的存储位置联系起来。即通过精心地向表载入元素实现,从而提高访问速度。本例中采取的解决冲突的办法是建立一个链表,挂在这个位置的后面,所有散列函数值为这个位置的元素都添加到这个链表中,可以从头部插入也可以从尾部追加,甚至可以再这个位置后面再挂一个散列表。代码实现了将文件名按字母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;
}

继续阅读

二分法查找重复元素

二分法查找重复元素

条件:
随机生成若果个自然数
要求:
如果所查找的数值重复,返回第一个出现的数值下标。如果没有重复则返回对应的数值下表,如果没有查找到,则返回-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;
}

TCPL 2-3 编写十六进制字符串转换为整数函数

TCPL P37 htoi.c

TCPL p37 编写htoi(s), 把由十六进制数字组成的字符串(包含可选的前缀0x或0X)转换为与之等价的整数值。字符串中允许包括数字组成的:0~9,a~f 以及A~F.
难点为前缀的检测。程序回车退出,其他循环输入。

/*
 * htoi.c
 */
#include <stdio.h>

#define MAXLINE 1000

int m_getline(char line[], int maxline);
int htoi(char s[]);

int main(void)
{
        int hex;
        char ch[MAXLINE];

        while (m_getline(ch, MAXLINE) > 1) {
                hex = htoi(ch);
                if (hex != -1)
                        printf("%sHex -- %d\n", ch, hex);
                else
                        printf("%s\a is not a hex\n", ch);
        }

        return 0;
}

int m_getline(char s[], int n)
{
        int i, c;

        for (i = 0; i < n - 1 && (c = getchar()) != '\n' && c != EOF; i++)
                s[i] = c;
        if (c == '\n')
                s[i++] = c;
        s[i] = '\0';

        return i;
}

int htoi(char s[])
{
        int i;
        int n;
        i = 0;
        n = 0;
        while (s[i] == ' ' || s[i] == '\t')     /* blink space tab character */
                i++;
        if (s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
                for (i += 2; s[i] != '\n'; i++) {
                        if ((s[i] >= '0' && s[i] <= '9')
                                || (s[i] >= 'A' && s[i] <= 'F')
                                || (s[i] >= 'a' && s[i] <= 'f')) {
                                if (s[i] >= '0' && s[i] <= '9')
                                        n = 16 * n + s[i] - '0';
                                else if (s[i] >= 'A' && s[i] <= 'F')
                                        n = 16 * n + s[i] - 'A' + 10;
                                else if (s[i] >= 'a' && s[i] <= 'f')
                                        n = 16 * n + s[i] - 'a' + 10;
                        } else {
                                return -1;
                        }
                }
                return n;
        } else if ((s[i] >= '0' && s[i] <= '9')
                || (s[i] >= 'A' && s[i] <= 'F')
                || (s[i] >= 'a' && s[i] <= 'f')) {
                for (i = 0; s[i] != '\n'; i++) {
                        if (s[i] >= '0' && s[i] <= '9')
                                n = 16 * n + s[i] - '0';
                        else if (s[i] >= 'A' && s[i] <= 'F')
                                n = 16 * n + s[i] - 'A' + 10;
                        else if (s[i] >= 'a' && s[i] <= 'f')
                                n = 16 * n + s[i] - 'a' + 10;
                        else
                                break;
                }
                        return n;
        } else {
                return -1;
        }

//      return 0;
}

继续阅读

C语言用直方图统计单词长度

使用直方图打印输入单词的长度

C语言程序设计语言习题,打印输入中单词长度的直方图。翻遍互联网,没有一个称心的答案,好的程序无法编译,或者运行出错。
1-13习题: 编写一个程序,打印输入中单词长度的直方图。水平方向的直方图比较容易绘制,垂直方向的则要困难一些。

这是使用水平方向打印直方图的代码:

基本上,注释已经非常明确了。也比较简洁,以前写的代码,现在看还非常陌生,好歹完全理解了。代码不需要使用数组。

#include <stdio.h>

/*
 * 编写一个程序,打印输入中单词长度的直方图。水平方向的直方图比较容易
 * 绘制,垂直方向的直方图则要困难些。
 */
#define BEGIN 1
#define IN  1
#define OUT 0

int main(void)
{
        int i, c;
        int state;

        state = OUT;
        i = BEGIN;
        while ((c = getchar()) != EOF) {
                if (c == ' ' || c == '\t' || c == '\n') {
                        if (state == IN) {
                                putchar('\n');
                                ++i;
                                state = OUT;
                        }
                } else if (state == OUT) {
                        printf("%d: ", i);
                        putchar('*');
                        state = IN;
                } else {
                        putchar('*');
                }
        }

        return 0;
}

C语言下编译及执行结果:

回车后统计输入单词的直方图,结束程序使用, win系统下使用 回车结束程序。

[lhf@localhost 1.6]$ ./1-13
1 ab word ()4332
1: *
2: **
3: ****
4: ******
op faey zc---
5: **
6: ****
7: *****

继续阅读