无聊中,于是写了一个冒泡排序的泛型算法。算法很简单,但是个人觉得从C标准库中学到的这种泛型的思想很有益处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
* 冒泡排序的泛型实现
*/

#include <stdio.h>
#include <string.h>

static void Swap(char *vp1, char *vp2, int width)
{
char tmp;

if ( vp1 != vp2 ) {
while ( width-- ) {
tmp = *vp1;
*vp1++ = *vp2;
*vp2++ = tmp;
}
}
}

void BubbleSort(void *base, int n, int elem_size,
int (*compare)( void *, void * ))
{
int i, last, end = n - 1;
char *elem_addr1, *elem_addr2;

while (end > 0) {
last = 0;
for (i = 0; i < end; i++) {
elem_addr1 = (char *)base + i * elem_size;
elem_addr2 = (char *)base + (i + 1) * elem_size;
if (compare( elem_addr1, elem_addr2 ) > 0) {
Swap(elem_addr1, elem_addr2, elem_size);
last = i;
}
}
end = last;
}
}

int compare_int(void *elem1, void *elem2)
{
return (*(int *)elem1 - *(int *)elem2);
}

int compare_double(void *elem1, void *elem2)
{
return (*(double *)elem1 > *(double *)elem2) ? 1 : 0;
}

int main(int argc, char *argv[])
{
int num_int[8] = {8,7,6,5,4,3,2,1};
double num_double[8] = {8.8,7.7,6.6,5.5,4.4,3.3,2.2,1.1};
int i;

BubbleSort(num_int, 8, sizeof(int), compare_int);

for (i = 0; i < 8; i++) {
printf("%d ", num_int[i]);
}

printf("\n");

BubbleSort(num_double, 8, sizeof(double), compare_double);

for (i = 0; i < 8; i++) {
printf("%.1f ", num_double[i]);
}

return 0;
}

最近频繁需要实现在windows控制台下输入星号密码的功能,Unix/Linux那种没有任何屏显的实现总感觉对用户不太友好。今天在自己的Linux代码库中发现了自己去年写图书馆管理系统的时候写的一个密码输入函数。索性拿来修改了接口并且重新优化了处理逻辑后移植到了windows下(其实也就是加上几句条件编译罢了)。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#ifndef _WIN32 // 如果不是WIN32环境,则要自定义getch()函数
#include <termio.h>

int getch(void)
{
struct termios tm, tm_old;
int fd = 0, ch;

if (tcgetattr(fd, &tm) < 0) {
return -1;
}

tm_old = tm;
cfmakeraw(&tm);
if (tcsetattr(fd, TCSANOW, &tm) < 0) {
return -1;
}

ch = fgetc(stdin);
if (tcsetattr(fd, TCSANOW, &tm_old) < 0) {
return -1;
}

return ch;
}
#else
#include <conio.h>
#endif // _WIN32

/*
* 密码输入函数,参数 passwd 为密码缓冲区,buff_len 为缓冲区长度
*/
char *passwd_input(char *passwd, int buff_len)
{
char str;
int i = 0;
int enter_num = 13;
int backspace_num;

#ifndef _WIN32
backspace_num = 127;
#else
backspace_num = 8;
#endif

if (passwd == NULL || buff_len <= 0) {
return passwd;
}
while (1)
{
// 如果没有按下退格键
if ((str = getch()) != (char)backspace_num) {
if (i < buff_len - 1) {
passwd[i++] = str;
printf("*");
}
} else {
if (i != 0) {
i--;
printf("\b \b");
}
}
// 如果按下了回车键
if (str == (char)enter_num) {
passwd[--i] = '\0';

if (i != buff_len - 1) {
printf("\b \b");
}
break;
} else if (str == -1) {
fprintf(stderr, "Error to set termio noecho.n");
}
}

return passwd;
}

/*
// 测试示例(请自行添加头文件)
int main(void)
{
char pass[7];

printf("亲,试试输入密码(长度限制 6):");
passwd_input(pass, 7);
printf("\n%s\n", pass);

return 0;
}
*/

前几天在写一个使用Huffman算法的文本压缩程序时被“段错误”折磨了好长时间。因为自己向来对内存的使用保持着“克勤克俭”的作风,所以总是被此类错误折磨的焦头难额。C语言的内存管理本来就是一个繁琐的工作,写代码时略有不慎便会出现诸如“段错误(吐核)”的运行时崩溃。

其实段错误是操作系统的一个内存保护机制,一般情况下某程序尝试访问其许可范围之外的内存空间时便会触发内核的“一般保护性异常”,内核便会向程序发送一个SIGSEGV(11)信号(无效的内存引用),而SIGSEGV信号默认handler的动作便是在终端上打印出名为“段错误”的出错信息,并产生Core(内核转储)文件,最后结束掉当前犯错的程序。

段错误的成因大致有以下几种:

  1. 程序访问了系统数据区,尤其是往系统保护的内存地址写数据。比如尝试对NULL指针进行解引用或者对其指向的内存写入数据(但是不见得所有的指针越界都会触发“段错误”);
  2. 内存访问越界(数组越界等);
  3. 无限的递归(导致栈溢出);
  4. 对malloc / calloc申请的堆内存二次释放(可能与glibc库版本有关);
  5. 由于操作系统的段保护机制,如果由于缓冲区溢出等错误导致对某段内存的非法访问也会触发;

另外还有一些大家平时不大注意的地方会导致段错误,例如使用标准库函数fclose对一个打开的文件关闭了多次也会导致段错误,同时终端可能会输出很多关于运行时库错误的信息。因为对使用malloc族函数申请的堆内存释放第二次的时候会触发段错误,所以我猜测fclose触发段错误的原因可能是对文件指针FILE *指向的内存二次释放时触发的段错误。而Valgrind检测的结果基本上证明了我的猜测,fclose引发了堆异常,错误被定位到了free函数。

Read More