计算机堆与栈的区别就不赘述了,本内容主要通过演练几个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
#include <stdio.h>
#include <malloc.h>
int main(void){
/*在栈上分配*/
int i1=0;
int i2=0;
int i3=0;
int i4=0;
printf("栈:向下\n");
printf("i1=0x%08x\n",&i1);
printf("i2=0x%08x\n",&i2);
printf("i3=0x%08x\n",&i3);
printf("i4=0x%08x\n\n",&i4);
printf("--------------------\n\n");
/*在堆上分配*/
char *p1 = (char *)malloc(4);
char *p2 = (char *)malloc(4);
char *p3 = (char *)malloc(4);
char *p4 = (char *)malloc(4);
printf("p1=0x%08x\n",p1);
printf("p2=0x%08x\n",p2);
printf("p3=0x%08x\n",p3);
printf("p4=0x%08x\n",p4);
printf("堆:向上\n\n");
/*释放堆内存*/
free(p1);
p1=NULL;
free(p2);
p2=NULL;
free(p3);
p3=NULL;
free(p4);
p4=NULL;
return 0;
}

/*运行结果:
栈:向下
i1=0xffd0041c
i2=0xffd00418
i3=0xffd00414
i4=0xffd00410

--------------------

p1=0x56f5c570
p2=0x56f5c580
p3=0x56f5c590
p4=0x56f5c5a0
堆:向上

*/

综上:
内存中的栈区主要用于分配局部变量空间,处于相对较高的地址,其栈地址是向下增长的;而堆区则主要用于分配程序员申请的内存空间,堆地址是向上增长的。

另一个关于堆栈地址分配的例子

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
/*
编译:gcc -m32 -o test test.c
*/
#include <stdio.h>
#include <malloc.h>

void main(void){

char * fmt = "ebp:%#x\n";
char * p = "AAA ";
char *p1 = (char *)malloc(4);

asm(
"pushl %%ebx\n\t"
"pushl %0\n\t"
"call printf\n\t"
:
:"m"(fmt)
:
);

printf("fmt:%#x\n", fmt);
printf(" p:%#x\n", p);
printf(" p1:%#x\n", p1);

}

/*运行结果:
ebp:0x5661f000
fmt:0x5661d008
p:0x5661d011
p1:0x56a30160

*/

可见,程序运行时候栈底位于0x5661f000,而fmt和p这两个字符串分别存放在栈上的0x5661d0080x5661d00f和0x5661d0110x5661d015。

堆空间的分配

malloc(int),如果分配成功则返回分配好的地址,所以用一个指针去接收这个地址。输入参数指定分配的大小,单位是字节。

例:

char *p=(char *)malloc(100);

分配100个字节,分配的时候指定类型为char *类型,所以可以存储100个字符。

堆内存泄漏

如果在堆内存申请之后未进行安全释放,则有可能会造成内存泄漏问题。

Linux系统中的堆管理

本次复习重点不在研究堆管理机制,此部分内容留待后续再复习。

此部分内容参考资料:
Linux堆内存管理深入分析(上)
Linux堆内存管理深入分析(下)
Understanding glibc malloc
Syscalls used by malloc

参考资料

C语言堆栈入门——堆和栈的区别
堆和栈的理解和区别,C语言堆和栈完全攻略

把这个部分作为单独的环节来复习,是因为内联汇编在安全工程师的C语言编程当中用处是比较广泛的。无论是开发shellcode,调试exp,或是对代码做免杀,做代码虚拟机(虽然我在这方面并不擅长,但是大概看过一些其实现方式)都需要用到内联汇编。

另外对于高手来说,巧妙运用C语言内联汇编,有时是提高程序运行效率的很好的方式,或是在开发程序时,对调试起到一定的帮助。

不过,要想熟悉内联汇编,首先要熟悉汇编。

内联汇编的基本格式

这里以Linux下,GCC作为编译器,AT&T汇编作为内联汇编格式:

简单内联汇编

1
__asm__("汇编语句")

拓展内联汇编

1
2
3
4
5
__asm__ ( 汇编语句
: 输出对象 (可选)
: 输入对象 (可选)
: 可能受影响的寄存器 (可选)
);

简单内联汇编和拓展内联汇编的区别是简单内联汇编只包括指令,而扩展内联汇编包括操作数。

如果希望确保编译器不会在asm内部优化指令,可以在asm后使用关键字volatile。如果程序需要与 ANSI C 兼容,则应该使用 __asm____volatile__,而不是 asm 和 volatile。

内联汇编的常见用法

通过内联汇编把a的值赋给b:

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

void main(){
int a=10, b;
asm ("movl %1, %%eax;"
"movl %%eax, %0;"
:"=r"(b) /* 输出 */
:"r"(a) /* 输入 */
:"%eax" /* 破坏的寄存器 */
);
printf("%d",b);
}
  • 在本例中,b是输出操作数,由%0引用,a是输入操作数,由%1引用。
  • “r”是操作数的约束,它指定将变量a和b存储在寄存器中。注意,输出操作数约束应该带有一个约束修饰符”=”,指定它是输出操作数。
  • 要在asm内使用寄存器%eax,%eax的前面应该再加一个%,因为asm使用%0、%1等来标识变量。任何带有一个%的数都看作是输入/输出操作数,而不认为是寄存器。
  • 第三个冒号后的修饰寄存器%eax告诉将在asm中修改GCC %eax的值,这样GCC 就不使用该寄存器存储任何其它的值。
  • movl %1, %%eax将a的值移到%eax中, movl %%eax, %0将%eax的内容移到b中。
  • 因为b被指定成输出操作数,因此当asm的执行完成后,它将反映出更新的值。换句话说,对asm内b所做的更改将在asm外反映出来。

需要注意几点第一就是所有寄存器都使用%%作为前缀,第二在这个部分新增了%0%9的占位符来表示用户填充的数据。那么占位符,占的是什么位呢,谁来填充,怎么填充?%0%9的占位符会用输出部分和输入部分指定的寄存器或变量按照出现的顺序依次填充。如果不够填充则会出现编译错误的情况。

invalid 'asm': operand number out of range

https://www.it610.com/article/3871091.htm

使用内联汇编输出HelloWorld

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//编译方式:gcc -m32 -o test test.c
void main(){
char * s="Hello World\n";

asm ( "movl $4, %%eax\n\t" //eax包含系统调用号,调用0x80中断来执行这个函数
"movl $1, %%ebx\n\t" //ebx包含要写入的文件描述符,1表示当前终端
"movl %0, %%ecx\n\t" //ecx表示字符串的开头地址
"movl $12, %%edx\n\t" //edx是要输出的字符长度
"int $0x80\n\t"
: //输出值,为空表示没有输入值
:"m"(s) //输入参数,从%0~%9
: //"%eax", "%ebx", "%ecx", "%edx"
);
}

注意
在编写内联汇编时如果遇到以下报错:

error: invalid 'asm': operand number out of range

很有可能是输入输出的操作数出了问题。说明输入输出操作数超出了范围。

在本例中,如果将输入参数从”m”类型的内存参数,改为”r”类型的寄存器参数,则会报此错。

具体原因尚在研究中。今后在使用时需要多留心参数类型的区别。

另外以上程序再编译时需要采用32位架构,否则会无法运行(因为使用的全都是32位寄存器)。

内联汇编中使用多个输入参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*编译:gcc -m32 -o test test.c */

void main(){
char * s1="Hello";
char * s2="World";
char * s3="\n";

asm volatile (
"pushl %0\n\t"
"call printf\n\t"

"pushl %1\n\t"
"call printf\n\t"

"pushl %2\n\t"
"call printf\n\t"
: //输出值,为空表示没有输入值
:"m"(s1), "m"(s2), "m"(s3)
:
);
}

总结

内联汇编还有很多的用法是需要琢磨的,也会随着对C语言理解的深入以及汇编的水平,探索出越来越高明的用法。

需要注意以下几点:

  1. asm内汇编代码分割符,参考资料[2]中提到说最好采用”\n\t”,不过我在使用”;”也没有遇到bug。
  2. asm的输入输出参数之间采用逗号分割,在汇编代码中调用是从%0开始编号的,从0%~9%
  3. 如果输出值为空,也需要用冒号占位

参考资料

1. Linux 中 x86 的内联汇编
2. 内联汇编基础学习

windows.h是Windows系统中的一个头文件,它包含了其他Windows头文件,这些头文件的某些也包含了其他头文件。这些头文件定义了Windows的所有资料型态、函数调用、资料结构和常数识别字,它们是Windows文件中的一个重要部分。C/C++ 程序在源文件前面写#include <windows.h>即可。

https://blog.csdn.net/qq_32350131/article/details/80343890

Windows系统C语言常用系统函数

FindWindow查找窗口句柄
SendMessage向窗口句柄发送指令

1
2
3
4
5
6
7
8
9
10
11
12
#include <windows.h>

int main(){
HWND window; //定义一个窗口句柄变量,用来储存窗口句柄
/* FindWindow("窗口类名","窗口标题名")
窗口类名和窗口标题名可以只填一个,不填的用NULL填充
*/

window = FindWindow(NULL,"新建文本文档.txt - 记事本"); //查找标题为"新建文本文档.txt - 记事本"的窗口
SendMessage(window,WM_CLOSE,0,0); //向窗口发送关闭指令
return 0;
}

WindowFromPoint通过鼠标点击获得被点击窗口的句柄
GetCursorPos函数获取鼠标指针位置

模拟键盘向窗口发送字符:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <windows.h>

int main() {
POINT mouse;
HWND window;
while (1) {
GetCursorPos(&mouse);
window = WindowFromPoint(mouse);
//SendMessage(窗口句柄,消息类型,消息附带内容,消息附带内容)
SendMessage(window,WM_CHAR,'a',0);
Sleep(100);
}
return 0;
}

SetCursorPos函数设置鼠标指针位置

改变鼠标位置(运行后鼠标会飘,不失为一个小恶作剧程序):

1
2
3
4
5
6
7
8
9
10
#include <windows.h>

int main(){
int i;
while(i < 100000){
SetCursorPos(100,100);
i += 1;
}
return 0;
}

ShowWindow函数改变窗口状态,包括隐藏窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <windows.h>
#include <stdio.h>
#include <time.h>

int main(){
HWND window;
window = FindWindow(NULL,"新建文本文档.txt - 记事本");
ShowWindow(window,SW_HIDE); //隐藏窗口
Sleep(5000);
ShowWindow(window,SW_MAXIMIZE); //最大化窗口
Sleep(5000);
ShowWindow(window,SW_MINIMIZE); //最小化窗口
Sleep(5000);
ShowWindow(window,SW_RESTORE); //还原窗口
Sleep(5000);
return 0;
}

GetClientRect函数获取窗口尺寸

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <windows.h>
#include <stdio.h>

int main(){
HWND windows;
while(1){
RECT rectangle; //矩形变量,用于记录矩形四个角的数据
windows=FindWindow(NULL,"新建文本文档.txt - 记事本");
GetClientRect(windows,&rectangle);
printf("%d,%d,%d,%d\n",rectangle.left,rectangle.top,rectangle.right,rectangle.bottom);
Sleep(1000);
}
}

EnumWindow函数枚举遍历可见窗口

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
#include <tchar.h>
#include <stdio.h>
#include <windows.h>
// typedef
typedef TCHAR tchar;

// 窗口枚举回调函数
BOOL CALLBACK EnumWinProc( HWND hWnd, LPARAM lParam ){
tchar class_name[64] = { 0 };
tchar window_text[128] = { 0 };

GetClassName(hWnd, class_name, 64);
GetWindowTextA(hWnd,window_text,128);

//如果是可见窗口并且没有父窗口
if( IsWindowVisible(hWnd) && GetParent(hWnd) == NULL ){
printf("hWnd: %u\tClassName: %s\tWindowText: %s\n", hWnd, class_name, window_text);
}

return TRUE;
}

int main(){
EnumWindows(EnumWinProc, NULL);
return 0;
}

创建目录、拷贝文件、删除文件、删除目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <windows.h>

void main(){
//创建目录
CreateDirectory("C:\\testdir",NULL);
Sleep(3000);

//拷贝文件
CopyFile("C:\\Windows\\System32\\cmd.exe","C:\\testdir\\c.exe",FALSE);
Sleep(3000);

//删除文件
DeleteFile("C:\\testdir\\c.exe");
Sleep(3000);

//删除目录
RemoveDirectory("C:\\testdir");
}

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
#include <tchar.h>
#include <stdio.h>
#include <windows.h>

typedef TCHAR tchar;

int main() {
POINT mouse;
HWND window;
HWND last_window;

tchar class_name[64] = { 0 };
tchar window_text[128] = { 0 };

while (1) {
GetCursorPos(&mouse);
window = WindowFromPoint(mouse);


GetClassName(window, class_name, 64);
GetWindowTextA(window,window_text,128);

if(window != last_window){
last_window = window;
printf("窗口句柄: %u\t窗口类: %s\t窗口标题: %s\n", window, class_name, window_text);
}

//SendMessage(窗口句柄,消息类型,消息附带内容,消息附带内容)
//SendMessage(window,WM_CHAR,'a',0);
Sleep(100);
}
return 0;
}

运行结果:

延伸阅读:Windows API实现截图

https://blog.csdn.net/greenapple_shan/article/details/39828313

参考资料

C语言windows.h库的常用函数(一)
C语言windows.h库的常用函数(二)
C语言windows.h库的常用函数(三)
C语言windows.h库的常用函数(四)
Win32 API Docs
Win32 API Docs / Winuser.h / EnumWindows function

本篇内容跳跃且杂乱,后续可能会再次对内容进行整理。

文件系统调用

遍历目录
目录是一种特殊的文件,对其进行操作是,需要用到opendir、readdir、closedir等函数。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h> //@/usr/include/dirent.h
#include <errno.h>

void list_dir( char * dir_name ){
DIR * dirp;
struct dirent *direntp;
if((dirp=opendir(dir_name)) == NULL ){
fprintf(stderr,"Error Message: %s\n", strerror(errno));
exit(0);
}
//printf("Dir Size:%d\n", dirp -> __size);//这里为什么访问不到dirp的__size?

while((direntp = readdir(dirp)) != NULL){
if( strcmp(".",direntp->d_name) && strcmp("..",direntp->d_name) ){
// d_type的enum见/usr/include/dirent.h
printf( "%d => %s\n", direntp->d_type, direntp -> d_name );
}
}

closedir(dirp);
}


void main(){
list_dir("/tmp");
}

获取文件信息

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h> //@/usr/include/dirent.h
#include <errno.h>
#include <sys/stat.h>

#define DIRECTORY "/tmp/"


void file_info(char * file){
printf("\t%s\n",file);
struct stat stat_buf;
if( stat(file,&stat_buf) == -1 ){
fprintf(stderr,"Error Message: %s\n", strerror(errno));
exit(0);
}
printf("\tDevice: %d\n", stat_buf.st_dev);
printf("\ti-Nnumber: %d\n", stat_buf.st_ino);
printf("\tSize: %d\n", stat_buf.st_size);
}

void list_dir( char * dir_name ){
DIR * dirp;
struct dirent *direntp;
if((dirp=opendir(dir_name)) == NULL ){
fprintf(stderr,"Error Message: %s\n", strerror(errno));
exit(0);
}
//printf("Dir Size:%d\n", dirp -> __size);//这里为什么访问不到dirp的__size?

while((direntp = readdir(dirp)) != NULL){
if( strcmp(".",direntp->d_name) && strcmp("..",direntp->d_name) ){
// d_type的enum见/usr/include/dirent.h
printf( "%d => %s\n", direntp->d_type, direntp -> d_name );
char file_path[256] = "";
strcat(file_path,DIRECTORY);
strcat(file_path,direntp->d_name);
file_info(file_path);
//使用过后要置空
strcpy(file_path,"");
}
}

closedir(dirp);
}


void main(){
list_dir(DIRECTORY);
}

解析文件描述符

Linux系统中,进程拥有各自打开文件的描述符。通常,文件描述符按生成顺序放在文件描述符表中。Linux内核将文件描述符表用一维数组描述,每个打开的文件占用一个单元,用于存放存取文件的必要信息。

信号系统调用

信号是内核与进程间通信的一种方式。内核为每个进程定义了多种信号和处理方式,用户也可以根据需要对信号的处理方式进行重新定义。

Linux内核共定义了31种非实时的信号,为没种信号定义了处理动作,包括结束进程、写入内核文件、停止进程和忽略等。

Linux系统中的信号 《GNU/Linux C编程》 7.2.1

信号默认处理方式

符号 含义
A 结束进程
B 忽略信号
C 结束进程并写入内核文件
D 停止进程
E 信号不能被捕获
F 信号不能被忽略
G 非POSIX信号

可靠信号与不可靠信号

因为早期历史原因,将信号值小于32的信号称为不可靠信号,32~63之间的信号称为可靠信号,也称为实时信号。

I/O操作模式

基本I/O操作模式

  1. 阻塞模式
  2. 非阻塞模式
  3. 同步方式
  4. 异步方式

文件I/O操作模式

  1. 同步阻塞I/O模式
  2. 同步非阻塞I/O模式
  3. I/O多路复用模式
  4. 信号驱动I/O模式
  5. 异步I/O模式

进程

Linux下C语言进程相关的函数主要有:

函数 说明
getpid() 获取当前进程ID
getppid() 获取父进程ID
getpgrp() 获取进程组ID
fork() 创建子进程
wait() 等待子进程结束

fork()函数是Linux系统下C语言用来创建子进程的函数。最简单的用法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <unistd.h>

int main(void){
pid_t pid;

pid=fork();
printf("%d->%d\n",getpid(),pid);

}

/*
执行结果:
14929->14930
14930->0
*/

可以看到,fork()函数后的printf函数,执行了两次,一次是在进程ID为14920的进程中,打印pid的值为14930。另一次是在进程ID为14930的进程中,打印了0。
这就是fork()函数的用法,它会在程序中返回两次,在父进程中的返回值是子进程的进程ID,子进程中返回0,如此便可区分父、子进程。可以利用这个原理设计一个双进程的程序:

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
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>

int glob = 1;

int main(void){
int var = 2;

pid_t pid;

printf("ProcessID(%d) ParentProcessID(%d)\n", getpid(),getppid());
printf("&var: %x\t&glob: %x\tvar(%d)\tglob(%d)\n", &var,&glob, glob, var);


if ((pid = fork()) < 0) {
// 进程创建失败
printf("Fock Error");
} else if (pid == 0) {
//位于子进程中
printf("\n");
printf("ProcessID(%d) ParentProcessID(%d)\n", getpid(),getppid());
sleep(2);
glob++;
var++;
printf("ProcessID(%d) ParentProcessID(%d)\n", getpid(),getppid());
printf("&var: %x\t&glob: %x\tvar(%d)\tglob(%d)\n", &var,&glob, glob, var);
printf("\n");
} else {
// 位于父进程中
sleep(1);
//wait(&pid);
printf("&var: %x\t&glob: %x\tvar(%d)\tglob(%d)\n", &var,&glob, glob, var);
}

}

/*
执行结果:
[email protected]:~$gcc -m32 -o test test.c && ./test
ProcessID(14581) ParentProcessID(3595)
&var: ff92f988 &glob: 56638030 var(1) glob(2)

ProcessID(14582) ParentProcessID(14581) // 父进程执行时,两个进程是父子关系。
&var: ff92f988 &glob: 56638030 var(1) glob(2)
[email protected]:~$ProcessID(14582) ParentProcessID(1099) //父进程退出后,子进程交由系统接管。
&var: ff92f988 &glob: 56638030 var(2) glob(3)


[email protected]:~$

*/

在此例中,程序是以双进程的方式在系统中执行的。并且父进程比子进程执行时间短,所以父进程先结束,子进程在父进程退出后,仍然在控制台打印出信息,是因为在父进程退出后,子进程会交由系统接管,此时子进程的父进程ID变成了一个系统进程(systemd或者init)。

多进程

C语言多进程Fork实例:

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
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void){
int i=0;
for(i=0;i<3;i++){
pid_t fpid = fork();
if(fpid==0)
printf("\tSon: %d (%d)\n",getpid(),getppid());
else
wait(0);
printf("Father: %d (%d)\n",getpid(),getppid());
}
return 0;
}

/*
执行结果:
Son: 16013 (16012)
Father: 16013 (16012)
Son: 16014 (16013)
Father: 16014 (16013)
Son: 16015 (16014)
Father: 16015 (16014)
Father: 16014 (16013)
Father: 16013 (16012)
Son: 16016 (16013)
Father: 16016 (16013)
Father: 16013 (16012)
Father: 16012 (3595)
Son: 16017 (16012)
Father: 16017 (16012)
Son: 16018 (16017)
Father: 16018 (16017)
Father: 16017 (16012)
Father: 16012 (3595)
Son: 16019 (16012)
Father: 16019 (16012)
Father: 16012 (3595)
*/

一个完整的多进程示例:

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
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int sub_func(int sec){
printf("\tProcess:%d, ParentProcess(%d), sec(%d)\n",getpid(),getppid(),sec);
sleep(sec);
return 0;
}

int main(void){
int i=0;
printf("Father: %d (%d)\n",getpid(),getppid());

for(i=0;i<3;i++){
pid_t fpid = fork();
if(fpid==0){
sub_func(i);
}else{
wait(&fpid);
}
}
return 0;
}

/*
编译:gcc -m32 -o test test.c && ./test
执行结果:
Father: 18081 (3595)
Process:18082, ParentProcess(18081), sec(0)
Process:18083, ParentProcess(18082), sec(1)
Process:18084, ParentProcess(18083), sec(2)
Process:18088, ParentProcess(18082), sec(2)
Process:18089, ParentProcess(18081), sec(1)
Process:18090, ParentProcess(18089), sec(2)
Process:18091, ParentProcess(18081), sec(2)
*/

昨日家中断网,除此类突发情况和周末外,原则上不中断。

线程

学计算机原理必须听到的一句话:线程是操作系统运算调度的最小单位。但个人觉得这句话说的不太严谨,严格意义上来说,操作系统运算调度的最小单位应该是指令。线程只能视为一系列运算指令构成的最小调度单元。

同一进程可以拥有多条线程,线程之间共享该进程中的全部系统资源,如虚拟地址空间,文件描述符和信号处理等等。但同一进程中的多个线程有各自的调用栈(call stack),自己的寄存器环境(register context),自己的线程本地存储(thread-local storage)。
多线程可以提高程序在多核机器上某些任务的处理性能。如果采用多进程的方式,进程间通信需要通过管道等方式,数据在用户空间和内核空间频繁切换,开销很大。而多线程因为可以使用共享的全局变量,所以通信(数据交换)非常高效。

Unix系统中,C语言线程相关主要函数定义在/usr/include/pthread.h头文件中。其中最常用的主要有以下函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//创建线程
extern int pthread_create (pthread_t *__restrict __newthread,
const pthread_attr_t *__restrict __attr,
void *(*__start_routine) (void *),
void *__restrict __arg) __THROWNL __nonnull ((1, 3));

/* Terminate calling thread.

The registered cleanup handlers are called via exception handling
so we cannot mark this function with __THROW.*/
//结束线程
extern void pthread_exit (void *__retval) __attribute__ ((__noreturn__));

/* Make calling thread wait for termination of the thread TH. The
exit status of the thread is stored in *THREAD_RETURN, if THREAD_RETURN
is not NULL.

This function is a cancellation point and therefore not marked with
__THROW. */
//线程等待
extern int pthread_join (pthread_t __th, void **__thread_return);

多线程

多线程样例:

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
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

/*
* test.c
* 编译:gcc -m32 -lpthread -o test test.c
* 运行: ./test
*/

void print_msg(int);


void main(){

pthread_t threads[8];

void * func = &print_msg;
int i=0;
for(i=0;i<4;i++){
printf("Init thread %d\n",i);
pthread_create(&threads[i],NULL,func,(void *)i);
}

for(i=0;i<4;i++){

pthread_join((long unsigned int)&threads[i],NULL);
}

pthread_exit(NULL);

}


void print_msg(int sec){
printf("Thread-%d Start.\n", sec);
sleep(sec);
printf("Thread-%d Done.\n", sec);
}


/*
运行结果:
Init thread 0
Init thread 1
Init thread 2
Init thread 3
Thread-3 Start.
Thread-1 Start.
Thread-0 Start.
Thread-2 Start.
Thread-0 Done.
Thread-1 Done.
Thread-2 Done.
Thread-3 Done.
*/

今晚记录的内容有点草率,一些详细的用法未能完全梳理,以后如果有机会再追加。

虽然是七夕,也还是要坚持学习呀!(老婆还没下班)

内存管理

C 语言为内存的分配和管理提供了几个函数,可以在 <stdlib.h> 头文件中找到。

  • void *calloc(int num, int size)
    • 在内存中动态地分配 num 个长度为 size 的连续空间(num*size个byte),并将每一个字节都初始化为 0。
  • void free(void *address)
    • 该函数释放 address 所指向的内存块,释放的是动态分配的内存空间。
  • void *malloc(int num)
    • 堆区分配一块指定大小的内存空间,用来存放数据。这块内存空间在函数执行完成后不会被初始化,它们的值是未知的。
  • void *realloc(void *address, int newsize)
    • 该函数重新分配内存,把内存扩展到 newsize。

Example:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
char name[100];
char *description;
strcpy(name, "Zara Ali");

/* 动态分配内存 */
description = (char *)malloc( 30 * sizeof(char) );
if( description == NULL ){
fprintf(stderr, "Error - unable to allocate required memory\n");
}else{
strcpy( description, "Zara ali a DPS student.");
}
/* 重新分配内存 */
description = (char *) realloc( description, 100 * sizeof(char) );
if( description == NULL ){
fprintf(stderr, "Error - unable to allocate required memory\n");
}else{
strcat( description, "She is in class 10th");
}

printf("Name = %s\n", name );
printf("Description: %s\n", description );

/* 使用 free() 函数释放内存 */
free(description);
}

读写文件

读文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

int main(){
FILE *fp = NULL;
char buff[255];

fp = fopen("/tmp/test.txt", "r");
/*
/tmp/test.txt
This is testing for fprintf...
This is testing for fputs...
*/
fscanf(fp, "%s", buff); //fscanf() 方法只读取This,因为它在后边遇到了一个空格
printf("1: %s\n", buff );

//fgets() 从 fp 所指向的输入流中读取 n - 1 个字符复制到缓冲区 buf,并追加一个 null 字符来终止字符串。
fgets(buff, 255, (FILE*)fp);
printf("2: %s\n", buff );

fgets(buff, 255, (FILE*)fp);
printf("3: %s\n", buff );
fclose(fp);
}

写文件

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(){
FILE *fp = NULL;

fp = fopen("/tmp/test.txt", "w+");
fprintf(fp, "This is testing for fprintf...\n");
fputs("This is testing for fputs...\n", fp);
fclose(fp);
}

C语言读写二进制文件(fread,fwrite)

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
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

#define MAXLEN 1024

int main(){

FILE *src, *dst;
dst = fopen("/tmp/ls-copied", "wb" );
src = fopen("/bin/ls", "rb");
unsigned char buf[MAXLEN];
if( dst == NULL || src == NULL ){
fprintf(stderr, "%d\n", errno);
exit(1);
}

int rc;
while( (rc = fread(buf,sizeof(unsigned char), MAXLEN, src)) != 0 ){
fwrite( buf, sizeof( unsigned char ), rc, dst );
}

fclose(src);
fclose(dst);
return 0;
}

管道

管道是在同一台计算机上两个进程之间进行数据交换的一种机制。具有单向、先进先出、无结构的字节流等特点。管道有两端,一端用于写入数据,另一端用于读出数据。

根据管道提供的接口不同,(Linux系统下)分为命名管道无名管道

无名管道

无名管道用于在内核中建立一条有两个端的管道,一端用于读,另一端用于写。从管道写入端写入的数据可以从读出端读出。它占用两个文件描述符,不能被非血缘关系的进程共享,一般应用在父子进程中。

1
2
3
#include <unistd.h>

int pipe(int fildes[2]);/*其中fildes[0]为读而开,fildes[1]为写而开,fildes[1]的输出是fildes[0]的输入*/

一条命令协助理解Linux下的管道:cat /tmp/test.txt | grep XXX | more

命名管道
管道如果被命名,就可以在整个系统中使用。FIFO管道即为命名管道,它以一种特殊的文件类型存储于文件系统中,以供其他进程访问。

1
2
3
4
5
#include <sys/types.h>

#include <sys/stat.h>

int mkfifo(char *path,mode_t mode);

path:管道文件的路径和名称
mode:管道文件的权限,类似open函数的第三个参数,并且自带了O_CREAT 和O_EXCL选项。
成功调用mkfifo返回0,错误返回-1。
本函数只能创建一个不存在的管道文件,或者返回”文件已存在”错误。

例:pipe_read.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <fcntl.h>
#include <stdio.h>
void main(){
FILE *fp;
char buf[255];
while ( 1 ){
if ( (fp = fopen( "myfifo", "r" ) ) == NULL )
return;
fgets( buf, sizeof(buf), fp );
printf( "gets:[%s]", buf );
if ( strncmp( buf, "quit", 4 ) == 0 || strncmp( buf, "exit", 4 ) == 0 )
break;
fclose( fp );
}
}

pipe_write.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
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/errno.h>

extern int errno;
void main(){
FILE *fp;
char buf[255];
/*创建管道,如果已存在则跳过*/
if ( mkfifo( "myfifo", S_IFIFO | 0666 ) < 0 && errno != EEXIST )
return;
while ( 1 ){
if ( (fp = fopen( "myfifo", "w" ) ) == NULL )
return; /*打开管道*/
printf( "please input:" );
gets( buf );
fputs( buf, fp );
fputs( "/n", fp );
if ( strncmp( buf, "quit", 4 ) == 0 || strncmp( buf, "exit", 4 ) == 0)
break;
fclose( fp );
}
}

Windows下的管道

Windows下的C语言管道示例link
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
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

int runcmd( char* lpCmd )
{
char buf[2048] = {0}; //缓冲区
DWORD len;
HANDLE hRead, hWrite; // 管道读写句柄
STARTUPINFO si;
PROCESS_INFORMATION pi;
SECURITY_ATTRIBUTES sa;

//ZeroMemory( buf, 2047 );
sa.nLength = sizeof( sa );
sa.bInheritHandle = TRUE; // 管道句柄是可被继承的
sa.lpSecurityDescriptor = NULL;

// 创建匿名管道,管道句柄是可被继承的
if( !CreatePipe( &hRead, &hWrite, &sa, 2048 ) )
{
printf( "管道创建失败!(%#X)\n", (unsigned int)GetLastError() );
return 1;
}

ZeroMemory( &si, sizeof( si ) );
si.cb = sizeof( si );
si.dwFlags = STARTF_USESTDHANDLES | STARTF_USESHOWWINDOW;
si.wShowWindow = SW_HIDE;
si.hStdError = hWrite;
si.hStdOutput = hWrite;

// 创建子进程,运行命令,子进程是可继承的
if ( !CreateProcess( NULL, lpCmd, NULL, NULL, TRUE, 0, NULL, NULL, &si, &pi ) )
{
printf( "创建进程失败!(%#x)\n", (unsigned int)GetLastError() );
CloseHandle( hRead );
CloseHandle( hWrite );
return 1;
}
// 写端句柄已被继承,本地需要关闭,不然读管道时将被阻塞
CloseHandle( hWrite );
// 读管道内容,并显示
while ( ReadFile( hRead, buf, 2047, &len, NULL ) )
{
printf( buf );
ZeroMemory( buf, 2047 );
}
CloseHandle( hRead );
return 0;
}

int main( int argc, char** argv )
{
char cmd[256];
printf( "输入命令行:" );
gets( cmd );
runcmd( cmd );
system( "pause" );
return 0;
}

C语言标准库

C语言是一种通用的、面向过程式的计算机程序设计语言。1972 年,为了移植与开发 UNIX 操作系统,丹尼斯·里奇在贝尔电话实验室设计开发了 C 语言。
C标准库是一组 C 内置函数、常量和头文件,比如 stdio.hstdlib.hmath.h 等等。这个标准库可以作为 C 程序员的参考手册。
C语言标准库有各种不同的实现,比如glibc, 用于嵌入式Linux的uClibc,还有ARM公司的C语言标准库及精简版的MicroLib等。不同标准库的实现并不相同,而且提供的函数也不完全相同,不过有一个它们都支持的最小子集,这也就是最典型的C语言标准库。
典型的C语言标准库(GNU C 标准库)官网:The GNU C Library

glibc和libc有什么区别呢?
libc是Linux下的ANSI C的函数库;
glibc是Linux下的GUN C函数库;
ANSI C和GNU C有什么区别呢?
ANSI C是基本的C语言函数库,包含了C语言最基本的库函数。这个库可以根据 头文件划分为 15 个部分,其中包括:字符类型 (<ctype.h>)、错误码 (<errno.h>)、 浮点常数 (<float.h>)、数学常数 (<math.h>)、标准定义 (<stddef.h>)、 标准 I/O (<stdio.h>)、工具函数 (<stdlib.h>)、字符串操作 (<string.h>)、 时间和日期 (<time.h>)、可变参数表 (<stdarg.h>)、信号 (<signal.h>)、 非局部跳转 (<setjmp.h>)、本地信息 (<local.h>)、程序断言 (<assert.h>) 等等。这在其他的C语言的IDE中都是有的。
而GNU C函数库是一种类似于第三方插件的东西,由于Linux是用C语言写的,所以Linux的一些操作是用C语言实现的,所以GNU组织开发了一个C语言的库 用于我们更好的利用C语言开发基于Linux操作系统的程序。其实我们可以把它理解为类似于Qt是一个C++的第三方函数库一样。

标准库 内容
<stdio.h> 输入和输出
<stdlib.h> 最常用的一些系统函数
<string.h> 字符串处理
<math.h> 定义了一系列数学函数
<ctype.h> 包含了一系列字符类测试函数
<time.h> 时间和日期
<stdarg.h> 可变参数列表
<signal.h> 信号
<assert.h> 声明断言
<setjmp.h> 非局部跳转
<errno.h> 定义错误代码和处理错误的函数
<stddef.h> 一些常数、类型和变量
<locale.h> 定义了特定地域的设置,比如日期格式和货币符号
<float.h> 包含了一组与浮点值相关的常量和运算
<limits.h> 定义整数数据类型的取值范围

C语言错误处理和调试

C 语言不提供对错误处理的直接支持,但是作为一种系统编程语言,它以返回值的形式提供底层数据。在发生错误时,大多数的 C 或 UNIX 函数调用返回 1 或 NULL,同时会设置一个错误代码 errno,该错误代码是全局变量,表示在函数调用期间发生了错误。可以在 errno.h 头文件中找到各种各样的错误代码。
所以,C 程序员可以通过检查返回值,然后根据返回值决定采取哪种适当的动作。开发人员应该在程序初始化时,把 errno 设置为 0,这是一种良好的编程习惯。0 值表示程序中没有错误。

C语言错误处理一例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <errno.h>
#include <string.h>

extern int errno ;

int main (){
FILE * pf;
int errnum;
pf = fopen ("unexist.txt", "rb");
if (pf == NULL){
errnum = errno;
fprintf(stderr, "错误号: %d\n", errno);
perror("通过 perror 输出错误");
fprintf(stderr, "打开文件错误: %s\n", strerror( errnum ));
}else{
fclose (pf);
}
return 0;
}

C语言调试

Linux下的C语言程序调试,可以使用GDB。这篇文章记录了GDB调试器基本使用,更多的调试技术,后续再研究。

C语言输入输出

getchar() & putchar()

一次只能输入输出一个字符。
Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

int main(){
int c;

printf( "Enter a value :");
c = getchar( );
printf( "\nYou entered: ");
putchar( c );
printf( "\n");

char *s = "abc";
int i =0;
for ( i=0;i<sizeof(s);i++){
putchar(s[i]);
putchar('\n');
}

return 0;
}

gets() & puts()
char *gets(char *s) 函数从 stdin 读取一行到 s 所指向的缓冲区,直到一个终止符或 EOF。
int puts(const char *s) 函数把字符串 s 和一个尾随的换行符写入到 stdout。

Example:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(){
char str[100];
printf( "Enter a value :");
gets( str );
printf( "\nYou entered: ");
puts( str );
return 0;
}

scanf() 和 printf()
int scanf(const char *format, …) 函数从标准输入流 stdin 读取输入,并根据提供的 format 来浏览输入。

int printf(const char *format, …) 函数把输出写入到标准输出流 stdout ,并根据提供的格式产生输出。

format 可以是一个简单的常量字符串,但是您可以分别指定 %s、%d、%c、%f 等来输出或读取字符串、整数、字符或浮点数。还有许多其他可用的格式选项,可以根据需要使用。

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main() {

char str[100];
int i;

printf( "Enter a value :");
scanf("%s %d", str, &i);

printf( "\nYou entered: %s %d ", str, i);
printf("\n");
return 0;
}

余生疯狂做产品!跟这个世界继续死磕!

今晚复习跟数据结构息息相关的几个知识点。

存储类型

C语言中有以下类型的存储方式:

  • auto
    • auto用于声明变量的生存期为自动,即将不在任何类、结构、枚举、联合和函数中定义的变量视为全局变量,而在函数中定义的变量视为局部变量。
    • 因为auto是C语言变量默认的存储类型,所以一般不写。
  • register
    • register要求编译器尽可能的将register类型的变量存在CPU内部寄存器中而不是通过内存寻址的RAM中,以便提高效率。
  • static
    • static指示编译器在程序的生命周期内保持局部变量的存在,而不需要在每次它进入和离开作用域时进行创建和销毁。使用 static修饰局部变量可以在函数调用之间保持局部变量的值。
    • static修饰符也可以应用于全局变量,当 static修饰全局变量时,会使变量的作用域限制在声明它的文件内。
    • static是全局变量的默认存储类。
  • extern
    • extern存储类用于提供一个全局变量的引用,全局变量对所有的程序文件都是可见的。当使用extern时,对于无法初始化的变量,会把变量名指向一个之前定义过的存储位置。
    • 有多个文件且定义了一个可以在其他文件中使用的全局变量或函数时,可以在其他文件中使用extern来得到已定义的变量或函数的引用。extern是用来在另一个文件中声明一个全局变量或函数。
  • const
    • const要求其所修饰的对象为常量,不可对其修改和二次赋值操作(不能作为左值出现)。
  • volatile 修饰符
    • volatile提醒编译器它后面所定义的变量随时都有可能改变,因此编译后的程序每次需要存储或读取这个变量的时候,告诉编译器对该变量不做优化,都会直接从变量内存地址中读取数据,从而可以提供对特殊地址的稳定访问。

C语言const与static的区别

  • const 就是只读,只在声明中使用;
  • static 一般有两个作用,规定作用域和存储方式。

对于局部变量, static规定其为静态存储方式, 每次调用的初始值为上一次调用的值,调用结束后存储空间不释放;
对于全局变量, 如果以文件划分作用域的话,此变量只在当前文件可见; 对于static函数也是在当前模块内函数可见;
static const 是上面两者的合集。

结构体

结构体的声明方式:

1
2
struct 结构体名
{成员列表};

结构体声明样例:

1
2
3
4
5
6
7
8
9
struct student
{
int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
};

声明的结构体相当于一个模型,但其中并无具体数据,系统对之也不分配实际内存单元,为了能在程序中使用结构类型的数据,应当定义结构体类型的变量,并在其中存放具体的数据。

结构体的嵌套

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct date{
int month;
int day;
int year;
}

struct student{
int num;
char name[20];
char sex;
int age;
struct date birthday;
char addr[30];
}student1, student2;

结构体变量的赋值与引用

例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <string.h>

struct student{
int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
};

int main (){
struct student s1;
s1.num = 1;
strcpy(s1.name,"xiaoming");//不能直接用s1.name="xiaoming"这种方式。
printf("%d: %s", s1.num,s1.name);
}

数组初始化赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

struct student{
int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
};

int main (){
struct student s1 = {1,"xiaoming",'F',10,99.9,"Beijing"};
// 单引号用于字符,双引号用于字符串(字符数组)。
printf("%d: %s", s1.num,s1.name);
}

.->的区别
一般情况下用.只需要声明一个结构体,格式是结构体类型名+结构体名。然后用结构体名加.加域名就可以引用域 了。因为自动分配了结构体的内存。如同int a一样。
而用->则要声明一个结构体的指针,还要手动开辟一个该结构体的内存,然后把返回的指针给声明的结构体指针,才能用->正确引用。

结构体数组

1
2
3
4
5
6
7
8
9
10
struct student{
int mum;
char name[20];
char sex;
int age;
float score;
char addr[30];
} stu[3] = {{10101,"Tom", 'M', 18, 87.5, "Beijing Road"},
{10102,"Bob", 'M', 18, 87.5, "Beijing Road"},
{10103,"Jim", 'M', 18, 87.5, "Beijing Road"} };

结构体变量指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

struct student {
long num;
char name[20];
char sex;
float score;
};

void main(){
struct student stu_1;
struct student *p;
p = &stu_1;
stu_1.num = 89101;
strcpy(stu_1.name, "Li Lin");
stu_1.sex = 'M';
stu_1.score = 89.5;
printf("NO. :%ld\nname: %s\nsex:%c\nscore:%f\n", stu_1.num, stu_1.name, stu_1.sex, stu_1.score);
printf("NO. :%ld\nname: %s\nsex:%c\nscore:%f\n", (*p).num, (*p).name, (*p).sex, (*p).score);
printf("NO. :%ld\nname: %s\nsex:%c\nscore:%f\n",p->num, p->name, p->sex, p->score);
system("pause");
}

结构体数组指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <stdlib.h>

#define FORMAT "%d\t%-3s\t%1c\t%2d\n"

struct student{
int num;
char name[20];
char sex;
int age;
};

struct student stu[3] = {
{1, "Tom", 'M', 18},
{2, "Kim", 'M', 19},
{3, "Jim", 'F', 20}
};

int main(){
struct student *p;
printf("No.\tname\tsex\tage\n");
for(p=stu; p<stu+3;p++)
printf(FORMAT, p->num, p->name, p->sex, p->age);
}

链表

链表是一种常见的数据结构,用于动态地进行存储分配。
以单向链表为例,它有一个头指针变量,存放一个地址,该地址指向一个元素。链表中每一个元素称为结点,每个结点都应包括两个部分,一为用户需要用的实际数据,二为下一个结点的地址。可以看出,头指针head指向第一个元素,第一个元素又指向第二个元素,直到最后一个元素,最后一个元素不再指向其他元素,称之为表尾,它的地址部分放一个NULL(表示空地址),链表到此结束。

单向链表示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <stdlib.h>

struct student{
long num;
float score;
struct student *next;
};

void main(){
struct student s1, s2, s3, *head, *p;
s1.num = 1; s1.score = 89.5;
s2.num = 2; s2.score = 90;
s3.num = 3; s3.score = 85;
head = &s1; //将结点 a 的起始地址赋给头指针 head
s1.next = &s2; //将结点 b 的起始地址赋给 a 结点的 next 成员
s2.next = &s3;
s3.next = NULL; // c 结点的 next 成员不存放其他结点地址
p = head;//使 p 指针指向 a 结点
do{
printf("%ld %5.1f\n", p->num, p->score);// 输出 p 指向的结点的数据
p = p->next; //使 p 指向下一结点
}while(p != NULL);//输出完 c 结点后 p 的值为 NULL
}

链表类型

链表类型有单向链表双向链表循环链表等类型。

双向链表是指在单向链表的基础上,每个链表元素既有指向下一个元素的指针,又有指向前一个元素的指针,其中每个结点都有两种指针,即front和tail,front指针指向左边结点,tail指针指向右边结点。

循环链表指的是在单向链表和双向链表的基础上,将两种链表的最后一个结点指向第一个结点从而实现循环。

Windows堆表中的“快表(快速单向链表)”就是使用了单向链表作为其数据结构,“空表(空闲双向链表)”则是一种双向链表。

参考资料

数据结构之队列、栈和链表(一)
数据结构之队列、栈和链表(二)

今晚复习C语言的指针和数组。

指针

指针:指向一个变量的地址。

声明方式:

1
2
int *p;
char *q;

C语言ptr变量名的含义:pts就是**Pointer Recod(er)**的简写

指针的使用:定义指针变量、把变量地址赋值给指针、访问指针变量指向的地址的值。

空指针:指向0x0,啥也不是。

指针的值:指针的值的类型都是一样的,长度等于一个单位地址的长度的16进制数值(32位、64位等)

指针的类型:指针指向的数据类型必须是一个有效的 C 数据类型。

例如,在32位系统中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int main (){
int *p;
char *t;
printf("Length of p: %d\n", sizeof(p));
printf("Length of t: %d\n", sizeof(t));
printf("Length of *p: %d\n", sizeof(*p));
printf("Length of *t: %d\n", sizeof(*t));
}

/*
执行结果:
Length of p: 4
Length of t: 4
Length of *p: 4
Length of *t: 1
*/

指针的算数运算

指针可以进行++、--、+、-等运算。

例:指针递增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

const int MAX = 3;

int main (){
int var[] = {10, 100, 200};
int i, *ptr;

/* 指针中的数组地址 */
ptr = var;
for ( i = 0; i < MAX; i++) {

printf("存储地址:var[%d] = %x\n", i, ptr );
printf("存储值:var[%d] = %d\n", i, *ptr );

/* 移动到下一个位置 */
ptr++;
}
return 0;
}

指针数组

可以通过指针来声明数组

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int main (){
const char *names[4] = { "Tom", "Bob", "Tony", "Jack" };

int i = 0;
while ( i < 4 ) {
printf("Value of names[%d] = %s\n", i, names[i] );
i++;
}
return 0;
}

指向指针的指针

指向指针的指针是一种多级间接寻址的形式,或者说是一个指针链。通常,一个指针包含一个变量的地址。当我们定义一个指向指针的指针时,第一个指针包含了第二个指针的地址,第二个指针指向包含实际值的位置。

例:

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
#include <stdio.h>

int main (){
int var;
int *ptr;
int **pptr;

var = 3000;

ptr = &var; // 取var的地址作为指针ptr的值

pptr = &ptr; // 取ptr的地址作为pptr的值

printf("&var(%x) => var(%d)\n", &var, var );
printf("&ptr(%x) => ptr(%x) => *ptr(%d)\n", &ptr, ptr,*ptr );
printf("&pptr(%x) => pptr(%x) => **pptr(%d)\n", &pptr, pptr, **pptr);

return 0;
}

/*
执行结果:
&var(ffe3b11c) => var(3000)
&ptr(ffe3b118) => ptr(ffe3b11c) => *ptr(3000)
&pptr(ffe3b114) => pptr(ffe3b118) => **pptr(3000)
*/

指针作为函数参数

当指针(地址)作为函数参数时,函数可以在执行过程中改变指针所指向值:
例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <time.h>

void getSeconds(unsigned long *par);

int main (){
unsigned long sec;
printf("[main] &sec(%x)=>sec(%ld): \n", &sec,sec);
getSeconds( &sec );
printf("[main] sec: %ld\n", sec );
return 0;
}

void getSeconds(unsigned long *par){
printf("[getSeconds] &par(%x)=>par(%x): \n", &par, par);
/* 获取当前的秒数 */
*par = time( NULL );
return;
}

指针作为函数返回值

指针作为函数返回值时,调用方可以直接访问这个地址:
例:

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
#include <stdio.h>

int * getList();

int main (){
int * i;
int j;
printf("[main] &i(%x) => i(%x)\n", &i,i);
i = getList();
printf("[main] &i(%x) => i(%x)\n", &i,i);
//for(j=0;j<5;j++)
// printf("%d\t", i[j]);
return 0;
}

int * getList(){
static int list[5]={1,2,3,4,5};
printf("[getList] &list(%x) => list(%x)\n", &list,list);
return list;
}

/*
执行结果:
[main] &i(ff94f03c) => i(5661b25b)
[getList] &list(5661e01c) => list(5661e01c)
[main] &i(ff94f03c) => i(5661e01c)
*/

数组

一维数组

1
2
int arr[] = {1,2,3,4,5};
char list[] = {"Tom", "Tony"};

多维数组

多维数组可以通过在括号内为每行指定值来进行初始化:

1
2
3
4
5
6
7
8
9
int a[3][4] = {  
{0, 1, 2, 3} , /* 初始化索引号为 0 的行 */
{4, 5, 6, 7} , /* 初始化索引号为 1 的行 */
{8, 9, 10, 11} /* 初始化索引号为 2 的行 */
};

// Or

int a[3][4] = {0,1,2,3,4,5,6,7,8,9,10,11};

多维数组的访问:

1
int val = a[2][3]; //获取数组中第2行第3个元素

数组作为函数参数

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
#include <stdio.h>

/* 函数声明 */
double getAverage(int arr[], int size);

int main (){
/* 带有 5 个元素的整型数组 */
int balance[5] = {1000, 2, 3, 17, 50};
double avg;

/* 传递一个指向数组的指针作为参数 */
avg = getAverage( balance, 5 ) ;

/* 输出返回值 */
printf( "平均值是: %f ", avg );

return 0;
}

double getAverage(int arr[], int size){
int i;
double avg;
double sum=0;

for (i = 0; i < size; ++i) {
sum += arr[i];
}

avg = sum / size;

return avg;
}

数组作为函数返回值

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 要生成和返回随机数的函数 */
int * getRandom(){
static int r[10];
int i;

/* 设置种子 */
srand( (unsigned)time( NULL ) );
for ( i = 0; i < 10; ++i){
r[i] = rand();
printf( "r[%d] = %d\n", i, r[i]);
}

return r;
}

/* 要调用上面定义函数的主函数 */
int main (){
/* 一个指向整数的指针 */
int *p;
int i;

p = getRandom();
for ( i = 0; i < 10; i++ ) {
printf( "*(p + %d) : %d\n", i, *(p + i));
}

return 0;
}

指针和数组的关系

在C语言中,数组名是一个指向数组中第一个元素的常量指针,例如

1
double balance[50];

这个数组中,balance是一个指向&balance[0] 的指针,即数组 balance 的第一个元素的地址。

因此,把 p 赋值为 balance 的第一个元素的地址:

1
2
3
4
double *p;
double balance[10];

p = balance;

使用数组名作为常量指针是合法的,反之亦然。因此,*(balance + 4) 是一种访问 balance[4] 数据的合法方式。

把第一个元素的地址存储在 p 中,就可以使用 *p、*(p+1)、*(p+2) 等来访问数组元素(也等同于*list+1)。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×