1、假设变量x和n是两个正整数,我们知道x/n这个表达式的结果要取Floor,例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?例如x是17,n是4,则结果是5;x是16,n是4,则结果是4。
答: (x+n-1)/n (1). 设x=kn,k为整数,即x为n的整数倍。则(x+n-1)/n=(kn+n-1)/n=((k+1)n-1)/n,此时分子没有达到n的k+1倍,但大于等于n的k倍, 默认计算取下整则为k。符合要求。 (2).设x=kn+m,k为整数,m为整数且0<m<n。则(x+n-1)/n=(kn+m+n-1)/n=((k+1)n+m-1)/n。此时分子的大于等于(k+1)n,小于(k+2)n,按照默认计算应该为k+1。符合要求。
2、编写一个布尔函数int is_leap_year(int year),判断参数year是不是闰年。如果某年份能被4整除,但不能被100整除,那么这一年就是闰年,此外,能被400整除的年份也是闰年。
int is_leap_year(int year)
{
if (year % 4 == 0 && year % 400 != 0)
{
if (year % 100 != 0)
return 1;
else return 0;
}
else if (year % 400 == 0)
return 1;
else
return 0;
}
3、编写一个函数double myround(double x),输入一个小数,将它四舍五入。例如myround(-3.51)的值是-4.0,myround(4.49)的值是4.0。可以调用math.h中的库函数ceil和floor实现这个函数。
double myround(double x)
{
int sa = 0, si = 0;
if (x == 0.0)
return 0.0;
else if (x > 0.0)
{
sa = (int)x;
si = x + 0.5;
if (sa == floor(si))
return sa;
else return sa + 1;
}
else
{
sa = (int)x;
si = x - 0.5;
if (sa == ceil(si))
return sa;
else
return sa - 1;
}
}
4、编写递归函数求两个正整数a和b的最大公约数,编写递归函数求Fibonacci数列的第n项
int gcd(int greater, int less)
{
if (greater % less == 0)
return less;
else
return gcd(less, (greater % less));
}
long int fibonacci(int n)
{
if (n == 0 || n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
5、编写程序数一下1到100的所有整数中出现多少次数字9。
int count_9 (void)
{
int i, n = 0;
for (i = 1; i <= 100; i++)
{
if (i / 10 == 9)
{
if (i % 10 == 9)
n = n + 2;
else
n = n + 1;
}
else if (i % 10 == 9)
n = n + 1;
}
return n;
}
6、编写程序打印一个不重复的九九乘法表,编写函数diamond打印一个菱形。diamond(int , char);
void printf_99 (void)
{
int i, j;
for (i = 1; i <= 9; i++)
{
for ( j = 1; j <= 9; j++)
if (i >= j)
printf("%d\t", i * j);
printf("\n");
}
}
void diamond(int num, char pattern)
{
int row, col;
if (num % 2 == 0)
{
printf("num must be even!\n");
return;
}
for (row = -num; row <= num; row++)
{
for ( col = -num; col <= num; col++)
{
if (fabs(row) + fabs(col) <= num)
printf("%c", pattern);
else printf(" ");
}
printf("\n");
}
}
7、实现一个用分子分母的格式来表示有理数的结构体rational以及相关的函数,rational结构体之间可以做加减乘除运算,运算的结果仍然是rational。
#include<stdio.h>
#include <math.h>
#define MAX 20000
struct rational
{
int x, y;
};
int fenzi(struct rational z)
{
return z.x;
}
int fenmu(struct rational z)
{
return z.y;
}
struct rational make_from_fenzi_fenmu(int x, int y)
{
struct rational z;
z.x = x;
z.y = y;
return z;
}
int gcd(int max, int min)
{
int temp = 0;
int fabs_max = fabs(max);
int fabs_min = fabs(min);
if (fabs_max < fabs_min)
{
temp = fabs_max;
fabs_max = fabs_min;
fabs_min = temp;
}
if ((fabs_max % fabs_min) == 0)
return (fabs_min);
else
return gcd(fabs_min, fabs_max % fabs_min);
}
int lcm_(int max, int min)
{
int temp = 0;
int fabs_max = fabs(max);
int fabs_min = fabs(min);
if (fabs_max < fabs_min)
{
temp = fabs_max;
fabs_max = fabs_min;
fabs_min = temp;
}
int i;
for (i = fabs_max; i < MAX; i++)
if (i % fabs_max == 0 && i % fabs_min == 0)
break;
return i;
}
struct rational add(struct rational z1, struct rational z2)
{
struct rational z3;
int lcm = lcm_(fenmu(z1), fenmu(z2));
z3 = make_from_fenzi_fenmu(lcm / fenmu(z1) * fenzi(z1) + lcm / fenmu(z2) * fenzi(z2),
lcm );
int euclid = gcd(z3.y, z3.x);
return make_from_fenzi_fenmu(z3.x / euclid, z3.y / euclid);
}
struct rational sub(struct rational z1, struct rational z2)
{
struct rational z3;
int lcm = lcm_(fenmu(z1), fenmu(z2));
z3 = make_from_fenzi_fenmu(lcm / fenmu(z1) * fenzi(z1) - lcm / fenmu(z2) * fenzi(z2),
lcm );
int euclid = gcd(z3.y, z3.x);
return make_from_fenzi_fenmu(z3.x / euclid, z3.y / euclid);
}
struct rational mul(struct rational z1, struct rational z2)
{
struct rational z3;
z3 = make_from_fenzi_fenmu(fenzi(z1) * fenzi(z2), fenmu(z1) * fenmu(z2));
int euclid = gcd(z3.y, z3.x);
return make_from_fenzi_fenmu(z3.x / euclid, z3.y / euclid);
}
struct rational div(struct rational z1, struct rational z2)
{
struct rational z3;
z3 = make_from_fenzi_fenmu(fenzi(z1) * fenmu(z2), fenmu(z1) * fenzi(z2));
int euclid = gcd(z3.y, z3.x);
return make_from_fenzi_fenmu(z3.x / euclid, z3.y / euclid);
}
int print_rational(struct rational z)
{
if (fenzi(z) == 0)
printf ("0\n");
else if (fenmu(z) == 0)
{
printf("it's error!\n");
return 1;
}
else
printf ("%d/%d\n", fenzi(z), fenmu(z));
return 0 ;
}
int main(void)
{
struct rational z3, z4, z5, z6;
struct rational z1 = { -3, 4 };
struct rational z2 = { 1, 7 };
z3 = add(z1, z2);
print_rational(z3);
z4 = sub(z1, z2);
print_rational(z4);
z5 = mul(z1, z2);
print_rational(z5);
z6 = div(z1, z2);
print_rational(z6);
return 0;
}
8、补完本节直方图程序的main函数,以可视化的形式打印直方图,如统计20个0~9的随机数的结果
/*************************************************************************
> File Name: getrandom.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 27 Oct 2012 06:55:35 PM CST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//#define N 10000
#define N 20
int a[N];
void random(int uppernum)
{
int i;
srand(time(NULL));
for (i = 0; i < N; i++)
a[i] = rand() % uppernum;
}
int howmany(int value)
{
int count = 0, i;
for (i = 0; i < N; i++)
if (a[i] == value)
count++;
return count;
}
void print(void)
{
int i;
printf("value\thow many\n");
for (i = 0; i < 10; i++)
printf("%d\t%d\n", i, howmany(i));
printf("\n");
}
int main(void)
{
int i, j, k, histogram[10] = {0};
random(10);
print();
// for (i = 0; i < 10; i++)
// histogram[i] = howmany(i);
for (i = 0; i < N; i++)
histogram[a[i]]++;
for (i = 0; i < 10; i++)
printf("%d\t", i);
printf("\n");
for (j = 0; j < N; j++) {
for (k = 0; k < 10; k++) {
if (histogram[k] > 0) {
printf("*\t");
histogram[k]--;
}
else
printf("\t");
}
printf("\n");
}
return 0;
}
9、定义一个数组,编程打印它的全排列以及组合。
/*************************************************************************
> File Name: perm_comb.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sun 28 Oct 2012 09:08:06 AM CST
************************************************************************/
#include<stdio.h>
#define N 4
#define MAX_NUM 5
int a[MAX_NUM];
void swap(char *a, char *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int isswap(char ptr[], int begin, int end)
{
int i;
for (i = begin; i < end; i++)
if (ptr[i] == ptr[end])
return 0;
return 1;
}
void perm(char ptr[], int n, int curr)
{
if (curr == n - 1)
printf("%s\n", ptr);
else
{
int i;
for (i = curr; i < n; i++)
{
if (isswap(ptr, curr, i))
{
swap(ptr + i, ptr + curr);
perm(ptr, n, curr + 1);
swap(ptr + i, ptr + curr);
}
}
}
}
void comb(int m, int k)
{
int i;
for (i = m; i >= k; i--)
{
a[k] = i;
if (k > 1)
comb(m - 1, k - 1);
else
{
int j;
for(j = a[0]; j > 0; j--)
printf("%d", a[j]);
printf("\n");
}
}
}
int main(void)
{
int i;
char ptr[N] = {'0'};
for (i = 0; i < N; i++)
ptr[i] = (i + 1) + '0';
perm(ptr, N, 0);
a[0] = 3;
comb(MAX_NUM, a[0]);
}
10、编写一个程序,测试运行它的平台是大端还是小端字节序。
#include <stdio.h>
int main(int argc, char **argv)
{
union data
{
char sysbol;
int num;
} test;
test.num = 0x02000001;
printf("%d\n", (int)test.sysbol);
return 0;
}
11、定义以下变量: char a[4][3][2] = {{{'a', 'b'}, {'c', 'd'}, {'e', 'f'}},
{{'g', 'h'}, {'i', 'j'}, {'k', 'l'}},
{{'m', 'n'}, {'o', 'p'}, {'q', 'r'}},
{{'s', 't'}, {'u', 'v'}, {'w', 'x'}}};
char (*pa)[2] = &a[1][0];
char (*ppa)[3][2] = &a[1]; 要想通过pa或ppa访问数组a中的'r'元素,分别应该怎么写?
答:char r2 = pa[5][1]; // (*(pa+5)) 即 pa[5]
char r4 = ppa[1][2][1];
/*************************************************************************
> File Name: pointer_array.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: 2012年12月25日 星期二 14时12分13秒
************************************************************************/
#include<stdio.h>
/* 数组类型做右值使用时,自动转换成指向数组首元素的指针, 这也解释了为什么数组类型不能相互赋值或初始化,
* 编译器报的错是error: incompatible types in assignment
* 但做左值仍然表示整个数组的存储空间,而不是首元素的存储空间,数组名做左值还有一点特殊之处,
* 不支持++、赋值这些运算符,但支持取地址运算符&,所以&a是合法的.
*
*/
int main(void)
{
char a[4][3][2] = {{{'a', 'b'}, {'c', 'd'}, {'e', 'f'}},
{{'g', 'h'}, {'i', 'j'}, {'k', 'l'}},
{{'m', 'n'}, {'o', 'p'}, {'q', 'r'}},
{{'s', 't'}, {'u', 'v'}, {'w', 'x'}}
};
char (*pa)[2] = &a[1][0];
char (*ppa)[3][2] = &a[1];
/* a[1][0]是一个数组,有两个元素,在&a[1][0]这个表达式中,数组名做左值,取整个数组
* 的首地址赋给指针pa.注意,&a[1][0][0] 表示数组a[1][0]的首元素的首地址,而&a[1][0]表示数组a[1][0]的首地址,
* 显然这两个地址的数值相同,但这两个表达式的类型是两种不同的指针类型,
* 前者的类型是char *,而后者的类型是char (*)[2] ,指针的本质都只是一个内存地址,但指针的类型决定了如pa++此类的表达式跨越的内存字节数
* 以及通过pa可以访问到的内存大小
*/
char r1 = (*(pa + 5))[1];
/* pa+5 跳过10个字节指向a[2][2],即{'q','r'},(*(pa+5))就表示数组a[2][2]
* 所以a[2][2][1]可以用(*(pa+5))[1]来表示
*/
char r2 = pa[5][1]; // (*(pa+5)) 即 pa[5]
char r3 = (*(ppa + 1))[2][1];
char r4 = ppa[1][2][1];
printf("%c %c\n", pa[0][0], ppa[0][0][1]);
/* *pa 就表示pa 所指向的数组a[1][0],所以取数组的a[1][0][0] 元素可以用表达式(*pa)[0] 。
* 注意到*pa 可以写成pa[0] ,所以(*pa)[0] 这个表达式也可以改写成pa[0][0]
*/
printf("%c %c %c %c\n", r1, r2, r3, r4);
return 0;
}
/* 指针数组
* int *a[10];
* int **pa = &a[0];
* 则pa[0] 和a[0] 指向的是同一个int元素
*
* 数组指针
* int a[10];
* int (*pa)[10] = &a;
* a是一个数组,在&a 这个表达式中,数组名做左值,取整个数组的首地址赋给指针pa 。注
* 意,&a[0] 表示数组a的首元素的首地址,而&a表示数组a的首地址,显然这两个地址的数值相同,
* 但这两个表达式的类型是两种不同的指针类型,前者的类型是int *,而后者的类型是int
* (*)[10] 。*pa 就表示pa 所指向的数组a,所以取数组的a[0] 元素可以用表达式(*pa)[0] 。注意
* 到*pa 可以写成pa[0] ,所以(*pa)[0] 这个表达式也可以改写成pa[0][0] ,pa就像一个二维数组的名
* 字,它表示什么含义呢?下面把pa和二维数组放在一起做个分析。
* int a[5][10];
* int (*pa)[10] = &a[0];
* 则pa[0] 和a[0] 取的是同一个元素,唯一比原来复杂的地方在于这个元素是由10个int 组成的数组,
* 而不是基本类型。这样,我们可以把pa当成二维数组名来使用,pa[1][2] 和a[1][2]取的也是同一
* 个元素,而且pa比a用起来更灵活,数组名不支持赋值、自增等运算,而指针可以支
* 持,pa++ 使pa跳过二维数组的一行(40个字节),指向a[1] 的首地址。
*/
12、自己实现一个strcpy函数,尽可能简洁,按照本书的编码风格你能用三行代码写出函数体吗?
char *strcpy(char *dest, const char *src)
{
size_t i;
for (i = 0; src[i] != '\0'; i++)
dest[i] = src[i];
dest[i] = '\0';
return dest;
}
char *strncpy(char *dest, const char *src, size_t n)
{
size_t i;
for (i = 0; i < n && src[i] != '\0'; i++)
dest[i] = src[i];
for (; i < n; i++)
dest[i] = '\0';
return dest;
}
13、编一个函数,输入一个字符串,要求做一个新字符串,把其中所有的一个或多个连续的空白字符都压缩为一个空格。这里所说的空白包括空格、'\t'、'\n'、'\r'。
char *shrink_space(char *dest, const char *src, size_t n)
{
size_t i, j;
dest[0] = src[0];
for (i = 1, j = 1; src[i] != '\0'; i++, j++)
{
if (src[i] == '\t' || src[i] == '\n'
|| src[i] == '\r' || src[i] == ' ')
if (src[i - 1] != '\t' && src[i - 1] != '\n'
&& src[i - 1] != '\r' && src[i - 1] != ' ')
dest[j] = ' ';
else
j--;
else
dest[j] = src[i];
}
dest[j] = '\0';
return dest;
}
14、[K&R]的5.6节有一个qsort函数的实现,可以对一组任意类型的对象做快速排序。请读者仿照那个例子,写一个插入排序的函数和一个折半查找的函数。
void insertion_sort(int a[], int n)
{
int i, j, tmp;
for (i = 1; i < n; i++)
{
tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
assert(is_sorted()); /* Precondition */
while (start <= end)
{
assert(mustbe(start, end, number)); /* Maintenance */
mid = (start + end) / 2; // 改成 mid = start + (end - start) * (number - a[start])/(a[end] - a[start])
//即变成插值查找
if (a[mid] < number)
start = mid + 1;
else if (a[mid] > number)
end = mid - 1;
else
{
assert(mid >= start && mid <= end && a[mid] == number); /* Postcondition 1 */
return mid;
}
}
assert(!contains(number)); /* Postcondition 2 */
return -1;
}
15、解析URL中的路径和查询字符串。动态网页的URL末尾通常带有查询,例如:
http://www.google.cn/search?complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=http://www.baidu.com/s?wd=linux&cl=3
比如上面第一个例子,http://www.google.cn/search是路径部分,?号后面的complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=是查询字符串,由五个“key=value”形式的键值对(Key-valuePair)组成,以&隔开,有些键对应的值可能是空字符串,比如这个例子中的键meta。
现在要求实现一个函数,传入一个带查询字符串的URL,首先检查输入格式的合法性,然后对URL进行切分,将路径部分和各键值对分别传出,请仔细设计函数接口以便传出这些字符串。如果函数中有动态分配内存的操作,还要另外实现一个释放内存的函数
/*************************************************************************
> File Name: find_url_token.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 26 Jan 2013 04:05:32 PM CST
************************************************************************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 10
typedef struct
{
char *tokens[N];
int count;
} unit_t;
void find_url_token(char str[], const char tok[], unit_t *ptr)
{
int i;
char *token = NULL;
char *saveptr = NULL;
ptr->count = 0;
const char *needle = "://";
if (strstr(str, needle))
{
for (i = 0; ; str = NULL, i++)
{
token = strtok_r(str, tok, &saveptr);
if (token == NULL)
break;
else
{
ptr->tokens[i] = token;
ptr->count++;
}
}
}
// for (i = 0; i < ptr->count; i++)
// printf("%s\n", ptr->tokens[i]);
// return ptr;
}
int main(void)
{
/* 不能定义为char *url = "..."; 因为此时是定义一个指向字符串字面值(位于.rodata段)的指针,而
调用strtok_r函数会修改这个字符串,运行时会产生段错误 */
char url[] = "http://www.google.cn/search?complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=";
/* 给url初始化用的这个字符串并没有分配在.rodata段,而是直接写在指令里了,
* 运行程序时通过三条movl 指令把12个字节写到栈上,这就是url的存储空间*/
unit_t *ptr = malloc(sizeof(unit_t));
find_url_token(url, "?&", ptr);
int i;
for (i = 0; i < ptr->count; i++)
printf("%s\n", ptr->tokens[i]);
free(ptr);
return 0;
}
16、实现函数void reverse(void);将单链表反转。
typedef struct node *link;
struct node {
unsigned char item;
link next;
};
void reverse(void)
{
link pnode = head;
link pprev = NULL;
while (pnode != NULL)
{
// get the next node, and save it at pNext
link pnext = pnode->next;
// reverse the linkage between nodes
pnode->next = pprev;
// move forward on the the list
pprev = pnode;
pnode = pnext;
}
head = pprev;
}
17、在本节的例子中,生产者和消费者访问链表的顺序是LIFO的,请修改程序,把访问顺序改成FIFO。
/*************************************************************************
> File Name: consumer.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: 2012年12月19日 星期三 00时15分47秒
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>
/* 程序演示了一个生产者-消费者的例子,生产者生产一个结构体串在链表的表头上,消费者
从表尾取走结构体。注意: 不一定产生一次就取走一次,虽然产生一次就唤醒一次消费者
,但有可能此时并未调度消费者线程运行,但取走的一定是表尾的结构体,即最快生产剩下未被取走的即FIFO */
struct msg
{
struct msg *next;
int num;
};
struct msg *head;
pthread_cond_t has_product = PTHREAD_COND_INITIALIZER;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
void *consumer(void *p)
{
struct msg *mp;
for (;;)
{
pthread_mutex_lock(&lock);
while (head == NULL)
pthread_cond_wait(&has_product, &lock);
if (head->next != NULL)
{
mp = head->next;
head->next = mp->next;
}
else
{
mp = head;
head = mp->next;
}
pthread_mutex_unlock(&lock);
printf("Consume %d\n", mp->num);
free(mp);
sleep(rand() % 5);
}
}
void *producer(void *p)
{
struct msg *mp;
for (;;)
{
mp = malloc(sizeof(struct msg));
mp->num = rand() % 1000 + 1;
printf("Produce %d \n", mp->num);
pthread_mutex_lock(&lock);
mp->next = head;
head = mp;
pthread_mutex_unlock(&lock);
pthread_cond_signal(&has_product);
sleep(rand() % 5);
}
}
int main(int argc, char *argv[])
{
pthread_t pid, cid;
srand(time(NULL));
pthread_create(&pid, NULL, producer, NULL);
pthread_create(&cid, NULL, consumer, NULL);
pthread_join(pid, NULL);
pthread_join(cid, NULL);
return 0;
}
18、请编写一个程序完成以下功能:父进程fork出子进程,子进程调用exit(2)终止,父进程自定义SIGCHLD信号的处理函数,在其中调用wait获得子进程的退出状态并打印。
#include <unistd.h>
#include <stdlib.h>
#include <signal.h>
#include <stdio.h>
#include<sys/types.h>
#include<sys/wait.h>
pid_t pid; //信号处理函数也要访问,故设置成全局变量
void sig_chld(int signo)
{
int stat_val;
/* pid_t waitpid(pid_t pid, int *status, int options); */
waitpid(pid, &stat_val, 0);
if (WIFEXITED(stat_val))
printf("child exited with code %d\n", WEXITSTATUS(stat_val));
else if (WIFSIGNALED(stat_val))
printf("Child terminated abnormally, signal %d\n", WTERMSIG(stat_val));
}
int main(void)
{
struct sigaction newact, oldact;
newact.sa_handler = sig_chld;
sigemptyset(&newact.sa_mask);
newact.sa_flags = 0;
sigaction(SIGCHLD, &newact, &oldact);
pid = fork();
if (pid < 0)
{
perror("fork");
exit(1);
}
if (pid > 0) /* parent */
{
while (1);
}
else /* child */
exit(3);
sigaction(SIGCHLD, &oldact, NULL);
return 0;
}
/* 父进程fork 出子进程,子进程调用exit(2)终止,父进程自定
* 义SIGCHLD信号的处理函数,在其中调用waitpid 获得子进程的退出状态并打印。*/