标签 c 下的文章

linux编程学习 05-01 网络编程

计算机联网的目的

  • 使用远程资源
  • 共享信息,程序和数据
  • 分布处理

协议

  • 计算机网络中实现通信必须有一些约定,如对速率,传输代码,代码结构,传输控制步骤和出错控制步骤等约定,这些约定即被称为通信协议
  • 在两个节点之间要成功进行通信,两个节点之间必须使用相同的“语言”,这些被通信各方共同遵守的约定,语言,规则被称为协议
  • 在internet中,最为通用的网络协议是TCP/IP协议

TCP/IP协议族

  • TCP/IP实际上是一个一起工作的通信家族,为网际数据通信通路
  • TCP/IP协议族大体上分为三个部分

    • internet协议,如IP协议,对应网络层
    • 传输控制协议(TCP)和用户数据报文协议(UDP),对应传输层
    • 处于TCP和UDP之上的一组协议专门开发的应用程序。他们包括:远程登陆协议(TELNET),文件传送协议(FTP),域名服务(DNS)和简单的邮件传送程序(SMTP),超文本传输协议(HTTP)等,对应应用层

网络层协议

  • internet协议(IP)

    • 该协议被设计成互联网分组交换通信网,以形成一个网际通信环境。他负责在源主机和目的主机之间传输来自其较高层软件的称为数据报文的数据块,他在源和目的地之间提供非连接型传递服务
  • 网际控制报文协议(ICMP)

    • ICMP实际上不是IP层部分,但直接同IP层一起工作,报告网络上的某些出错情况。允许网际路由器传输出错信息或测试报文。
  • 地址识别协议(ARP)
    -ARP实际上不是网络层部分,他处于IP和数据链路层之间,他是在32位IP地址和48位局域网物理地址之间执行翻译的协议。mac地址与IP地址的转换

传输层协议

  • 传输控制协议(TCP)

    • 可靠的面向连接的传输层服务
    • 主要功能

      • 监听输入对话建立请求
      • 请求另一网络站点对话
      • 可靠的发送和接收数据
      • 适度的关闭对话
  • 用户数据报文协议(UDP)

    • UDP提供不可靠的非连接型传输层服务

      • 他允许在源和目的站点之间传送数据,而不必在传送数据之前建立对话
      • 不使用TCP使用端对端差错校验
      • 传输层功能全部发挥,而开销却比较低
      • 主要用于那些不要求TCP协议的非连接型应用程序。例如,名字服务,网络管理,视频点播和网络会议等

应用层协议

Internet协议(IP)

  • IP的主要目的是为数据输入/输出网络提供基本算法,为高层协议提供无连接的传送服务。这意味着在IP将数据递交给接收站点以前不在传输站点和接收站点之间建立对话(虚拟链路)。它只是封装和传递数据,但不向发送者和接收者报告包的状态,不处理所原道的故障。
  • IP协议主要有以下四个主要功能

    • 数据传送
    • 寻址
    • 路由选择
    • 数据报文的分段
  • IP协议不注意包内的数据类型,他所知道的一切是必须将称为IP帧头的控制协议加到高层协议(TCP或者UDP)所接收的数据上

IP地址

  • 在TCP/IP网络中,每个主机都有唯一的地址,他是通过IP协议来实现的。
  • IP协议要求在每次与TCP/IP网络建立连接时,每台主机都必须为这个连接分配一个唯一的32位地址,因为在这个32位IP地址,不但可以用来识别某一台主机,而且还隐含着网际间的路径信息
  • 主机是指网络上的一个节点,不能简单的理解为一台计算机,实际上IP地址是分配给计算机的网络适配器(网卡)的,一台计算机可以有多个网络适配器,就可以有多个IP地址,一个网络适配器就是一个节点
  • IP地址为32位地址,一般以4个字节表示。每个字节的数字又用十进制表示,即每个字节的数的范围是0~255,且每个数字之间用“.”隔开,例如:192.168.1.8,这种记录方法称为“点-分”十进制号发。IP地址结构如下
    |网络类型|网络ID|主机ID|

IP地址分类

  • Internet地址可分为5类
地址类型第一个字节的十进制数
A000-127
B128-191
C192-233
D224-239
E240-255
  • A,B,C三类有InterNIC(Internet网络信息中心)在全球范围内同一分配,D,E类为特殊地址

端口号

  • TCP/UDP协议使用16位整数存储端口号,所以每个主机拥有65535个端口
  • 一些端口被IANA分配给指定应用

    • 21:FTP
    • 23:Telnet
    • 80:HTTP
    • RFC 1700(大约有2000个保留端口)

传输控制协议(TCP)

  • TCP(传输控制协议Transmission Control Protocol)是重要的传输层协议,TCP提供一种面向连接的,可靠的字节流服务
  • TCP协议的目的是允许数据同网络上的另外站点进行可靠的交换。他能提供端口编号的译码,以识别主机的应用程序,而且完成数据的可靠传输
  • TCP协议具有严格的内装差错校验算法确保数据的完整性
  • TCP协议是面向字节的顺序协议,这意味着包内的每个字节被分配一个顺序编号,并分配给每包一个顺序编号

用户数据报文协议(UDP)

  • UDP(用户数据报协议User Datagram Protocol)也是TCP/IP的传输层协议,他是无连接的,不可靠的传输服务。当接收数据时他不向发送方提供确认信息,他不提供输入包的顺序,如果出现丢失包或重份包的情况,也不会向发送方发出差错报文

    • 他允许在源和目的地站点间传送数据,而不必在传送数据之间建立对话
    • 不使用TCP使用的端对端差错校验
    • 传输层功能全部发挥,而开销却比较低
  • 由于他执行功能时具有较低的开销,因此执行速度比TCP快。他多半用于不需要可靠传输的应用程序,例如网络视频点播和视频会议等

TCP和UDP协议区别

  • TCP以连接为基础,即两台电脑必须先建立连接,然后才能传输数据,事实上,发送和接收的电脑必须一直互相通讯和联系。
  • UDP是一个无连接服务,数据可以直接发送而不必在两台电脑之间建立一个网络连接。他和有连接的TCP相比,占用带宽少,但是无法确认数据是否真正到达了客户端,而客户端收到的数据也不知道是否还是原来的发送数据

网络层其他数据路由协议

  • 路由协议分析数据包的地址并且决定传输数据到目的电脑最佳路线。他们也可以把大的数据分成几个部分,并且在目的地再把他们组合起来。IP处理实际上传输数据

    • ICMP(网络控制信息协议Internet Control Message Protocol)处理IP状态信息,比如能影响路由决策的数据错误或改变
    • RIP(路由信息协议Routing Information Protocol)他是几个决定信息传输的最佳路由路线协议中的一个
    • OSPF(Open Shortest Path First)一个用来决定路由的协议
    • ARP(地址解析协议Address Resolution Protocol)确定网络上一台电脑的数字地址
    • DNS(域名系统Domain Name System)从机器的名字确定机器的数字地址
    • RARP(反向地址解析协议Reverse Address Resolution Protocol)确定网络上一台计算机的地址,和ARP正好相反

其他用户服务协议

  • BOOTP(启动协议Boot Protocol)由网络服务器上取得启动信息,然后将本地的网络计算机启动
  • FTP(文件传输协议File Transfer Protocol)通过国际互联网从一台计算机上传输一个或多个文件到另一台计算机
  • TELNET(远程登陆)允许一个远程登陆,使用者可以从网络上的一台计算机通过TELNET连线到另一台机器,就向使用者直接在本地操作一样
  • EGP(外部网关协议Exterior Gateway Protocol)为外部网络传输路由信息
  • GGP(网关到网关协议Gateway-to-Gateway Protocol)在网关和网关之间传输路由协议
  • IGP(内部网关协议Interior Gateway Protocol)在内部网络传输路由协议

socket(套接字)

  • socket(套接字)是一种通讯机制,他包含一整套的调用接口和数据结构定义,他给应用程序提供了使用如TCP/UDP等网络协议进行通讯的手段
  • linux中的网络编程通过socket接口实现,socket既是一种特殊的I/O,提供对应的文件描述符。一个完整的socket都有一个相关描述(协议,本地地址,本地端口,远程地址,远程端口),每一个socket有一个本地的唯一socket,由操作系统分配
  • 内核提供的实现网络通信的接口

创建socket

int socket(int domain,int type,int protocol);

  • 返回:成功返回描述符,出错返回-1
  • 头文件
#include <sys/socket.h>
  • socket创建在内核中,若创建成功返回内核文件描述表的socket描述符
  • 参数

    • domain

      • AF_INET IPV4因特网域
      • AF_INET6 IPV6因特网域
      • AF_UNIX unix域
      • AF_UNSPEC 未指定
    • protocol

      • 通常为0,表示按给定的域和套接字类型选择默认协议
    • type

      • SOCK_STREAM

        • 流式的套接字可以提供可靠的,面向连接的通讯流。他使用了TCP协议。TCP保证了数据传输的正确性和顺序性
      • SOCK_DGRAM

        • 数据报套接字定义了一种无连接的服务,数据通过相互独立的报文进行传输,是无序的,并且不保证可靠,无差错。使用数据报协议UDP协议
      • SOCK_RAW

        • 原始套接字允许对低层协议如IP或ICMP直接访问,主要用于新的网络协议实现的测试等
      • SOCK_SEQPACKET

        • 长度固定,有序,可靠的面向链接报文传递

字节序

  • 不同体系结构的主机使用不同字节序存储器中保存多字节整数。字节存储顺序不同,有的系统是高位在前,低位在后,有的系统是低位在前,高位在后
  • 字节序分为大端和小端字节序
  • 网络协议使用网络字节序即大端字节序

字节序转换函数

  • 网络传输的数据大家是一定要同一顺序的,所以对于内部字节表示顺序和网络字节顺序不同的机器,就一定要对数据进行转换

    • uint32_t htonl(uint32_t hostlong);

      • 将一个32位整数由主机字节序转换成网络字节序
    • uint12_t htons(uint16_t hostshort);

      • 将一个16位整数由主机字节序转换成网络字节序
    • uint32_t ntohl(uint32_t netlong);

      • 将一个32位整数由网络字节序转换成主机字节序
    • uint16_t ntohs(uint16_t netshort);

      • 将一个16位整数由网络字节序转换成主机字节序

通用地址结构

#include <sys/socket.h>
struct sockaddr
{
        unsigned short sa_family;// Internet 地址族 AF_XXX
        char sa_data[14];// 14bytes的协议地址
};
  • sa_data包含了一些远程电脑的地址,端口和套接字的数目,他里面的数据是杂溶在一起的
  • sa_family一般来说,IPV4使用AF_INET
  • 在传递给需要地址结构的函数时,把指向该结构体的指针转换成(struct sockaddr*)传递进去

因特网地址结构

#include <netinet/in.h>
struct in_addr
{
        in_addr_t s_addr;// ipv4地址
};
struct sockaddr_in
{
        short int sin_family;// internet地址族如AF_INET(主机字节序)
        unsigned short int sin_port;// 端口号,16位值(网络字节序)
        struct in_addr sin_addr;// Internet地址,32位ipv4地址(网络字节序)
        unsigned char sin_zero[8];// 添0(为了格式对齐的填充位)
};
  • 这两个(sockaddr和sockaddr_in)数据类型是等效的,可以相互转换,通常使用sockaddr_in更为方便

IPV4地址族和字符地址间的转换

const char* inet_ntop(int domain,const void*restrict addr,char*restrict str,socklen_t size);

  • 返回:成功返回地址字符串指针,出错返回NULL
  • 功能:网络字节序转换成点分十进制
    int inet_pton(int domain,const char*restrict str,void*restrict addr);
  • 返回:成功返回1,无效格式返回0,出错返回-1
  • 功能:点分十进制转换成网络字节序
  • 头文件
#include <arpa/inet.h>
  • 参数

    • domain:internet地址族地址,如AF_INET
    • addr:internet地址,32位IPV4地址(网络字节序)
    • str:地址字符串(点分十进制)指针
    • size:地址字符串大小

填写IPV4地址族结构案例

struct sockaddr_in sin;// 定义一个sockaddr_in结构体
char buf[16];
memset(&sin,0,sizeof(sin));// 内存清0
sin.sin_family = AF_INET;// 填写internet地址族
sin.sin_port = hton((short)3001);// 填写端口号,转换成网络字节序
// 填充sin_addr,需要吧字符串型的ip地址转换成网络字节序
if(inet_pton(AF_INET,"192.168.2.1",&sin.sin_addr.s_addr) <= 0)
{
        // 错误处理
}
// 网络字节序不能直接输出,需要从网络字节序转换回字符串型才能输出
printf("%s\n",inet_ntop(AF_INET,&sin.sin_addr.s_addr,buf,sizeof(buf)));

TCP客户端服务器编程模型

  • 客户端调用序列

    • 调用socket函数创建套接字
    • 调用connect连接服务器端
    • 调用I/O函数(read/write)与服务器端通讯
    • 调用close关闭套接字
  • 服务器端调用序列

    • 调用socket函数创建套接字
    • 调用bind绑定本地地址和端口
    • 调用listen启动监听
    • 调用accept从已连接队列中提取客户连接,没有客户连接会阻塞
    • 调用I/O函数(read/write)与客户端通讯
    • 调用close关闭套接字

套接字与地址绑定

绑定地址

int bind(int sockfd,const struct sockaddr* addr,socklen_t len);

  • 返回:成功返回0,出错返回-1
  • 头文件
#include <sys/socket.h>
查找绑定到套接字的地址

int getsockname(inf sockfd,struct sockaddr*restrict addr,socklen_t*restrict alenp);

  • 返回:成功返回0,出错返回-1
  • 头文件
#include <sys/socket.h>
获取对方地址

int getpeername(int sockfd,struct sockaddr*restrict addr,socklen_t*restrict alenp);

  • 返回:成功返回0,出错返回-1
  • 头文件
#include <sys/socket.h>

建立连接

服务器端

int listen(int sockfd,int backlog);

  • 返回:成功返回0,出错返回-1。backlog指定进行客户端连接排队的队列长度
  • 头文件
#include <sys/socket.h>

int accept(int sockfd,struct sockaddr*restrict addr,socklen_t*restrict len);

客户端

int connect(int sockfd,const struct sockaddr* addr,socklen_t len);

  • 返回:成功返回0,出错返回-1
  • 头文件
#include <sys/socket.h>

特殊bind地址

  • 一台主机可以有多个网络接口和多个IP地址,如果我们只关心某个地址的连接请求,我们可以指定一个具体的IP地址,如果要响应所有接口上的连接请求就要使用一个特殊的地址INADDR_ANY
  • #define INADDR_ANY (uint32_t)0x00000000
// 监听所有服务器上ip所得到的连接请求
struct sockaddr_in servaddr;
memset(&servaddr,0,sizeof(servaddr));
servaddr.sin_addr.s_addr = INADDR_ANY;

tcp示例

服务器端代码
#include <stdio.h>
// atoi函数
#include <stdlib.h>
// I/O函数
#include <unistd.h>
#include <time.h>
// socket 系列函数
#include <sys/socket.h>
// sockaddr_in 结构体
#include <netinet/in.h>
// hton 函数
#include <arpa/inet.h>
#include <signal.h>
// memset函数
#include <string.h>
// 服务器socket描述符
int server_fd = 0;
// 服务器连接属性
struct sockaddr_in server_attr;
// 客户端socket描述符
int client_fd = 0;
// 客户端连接属性
struct sockaddr_in client_attr;
// ctrl + c 关闭服务器监听
void sigint_handle(int);
// 响应客户端连接
void response(int);
// 服务器连接日志
void server_log(struct sockaddr_in*);
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        if(SIG_ERR == signal(SIGINT,sigint_handle))
        {
                perror("signal error");
                return 1;
        }
        memset(&server_attr,0,sizeof(server_attr));
        memset(&client_attr,0,sizeof(server_attr));
        /*
         * 1. 创建socket
         * socket创建在内核中,是一个结构体
         * AF_INET : IPV4
         * SOCK_STREAM : TCP协议
         */
        server_fd = socket(AF_INET,SOCK_STREAM,0);
        if(server_fd == -1)
        {
                perror("sock error");
                return 1;
        }
        /*
         * 2. 调用bind函数将socket与地址(ip,port)进行绑定
         */
        server_attr.sin_family = AF_INET;
        // 转换位网络字节序
        server_attr.sin_port = htons((short)atoi(argv[1]));
        // 表示所有ip,也可以指定第一个ip,指定ip时要把主机字节序转换成网络字节序
        server_attr.sin_addr.s_addr = INADDR_ANY;
        // 绑定ip端口
        if(-1 == bind(server_fd,(struct sockaddr*)&server_attr,sizeof(server_attr)))
        {
                perror("bind error");
                return 1;
        }
        /*
         * 3. 调用listen函数启动监听,通知系统接收来自客户端的请求
         * 第二个参数代表客户端队列的长度
         * 执行成功后能用netstat查看
         */
        if(-1 == listen(server_fd,8))
        {
                perror("listen error");
                return 1;
        }
        socklen_t addrlen = sizeof(client_attr);
        /*
         * 4. 调用accept获得客户端连接,并返回一个新的socket文件描述符
         * 若没有客户端连接,此函数会阻塞,直到获得一个客户端连接
         */
        while(1)
        {
                client_fd = accept(server_fd,(struct sockaddr*)&client_attr,&addrlen);
                server_log(&client_attr);
                /*
                 * 5. 调用I/O函数(read/write)和连接的客户端进行双向的通信
                 */
                response(client_fd);
                close(client_fd);
        }
        close(server_fd);
}
void sigint_handle(int sig)
{
        close(server_fd);
        exit(0);
}
void response(int fp)
{
        time_t rawtime;
        struct tm* timeinfo;
        time(&rawtime);
        timeinfo = localtime(&rawtime);
        char str[39] = "I am server. ";
        strcat(str,asctime(timeinfo));
        write(fp,str,sizeof(str));
}
void server_log(struct sockaddr_in* client_attr)
{
        char ip[16] = {'\0'};
        // 结构体的的数据不能直接显示,需要先转换成本机字节序
        inet_ntop(AF_INET,&client_attr->sin_addr.s_addr,ip,sizeof(ip));
        printf("connected by %s:%d\n",ip,ntohs(client_attr->sin_port));
}
服务器端代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <sys/socket.h>
int main(int argc,char* argv[])
{
        if(argc < 3)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        int client_fd = socket(AF_INET,SOCK_STREAM,0);
        struct sockaddr_in client_attr;
        memset(&client_attr,0,sizeof(client_attr));
        client_attr.sin_family = AF_INET;
        // 主机字节序转换成网络字节序
        client_attr.sin_port = htons((short)atoi(argv[2]));
        inet_pton(AF_INET,argv[1],&client_attr.sin_addr.s_addr);
        // client_attr.sin_addr.s_addr = 
        if(-1 == connect(client_fd,(struct sockaddr*)&client_attr,sizeof(client_attr)))
        {
                perror("connect ");
                return 1;
        }
        char res[39] = {'\0'};
        read(client_fd,res,sizeof(res));
        printf("buf = %s\n",res);
        close(client_fd);
        return 0;
}
自定义协议服务器端,多进程处理并发
#include <stdio.h>
// atoi函数
#include <stdlib.h>
// wait函数
#include <sys/wait.h>
// I/O函数
#include <unistd.h>
#include <time.h>
// socket 系列函数
#include <sys/socket.h>
// sockaddr_in 结构体
#include <netinet/in.h>
// hton 函数
#include <arpa/inet.h>
#include <signal.h>
// memset函数
#include <string.h>
// 服务器socket描述符
int server_fd = 0;
// 服务器连接属性
struct sockaddr_in server_attr;
// 客户端socket描述符
int client_fd = 0;
// 客户端连接属性
struct sockaddr_in client_attr;
// ctrl + c 关闭服务器监听
void sigint_handle(int);
//  回收子进程方法
void sigchld_handle(int);
// 响应客户端连接
void response(int);
// 服务器连接日志
void server_log(struct sockaddr_in*);
// 自定义写
int my_write(int fd,char* str);
// 自定义读
int my_read(int fd,char* str);
/* 自定义协议结构体 */
typedef struct{
        int bytes;
        char data[512];
}my_protocol;
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        if(SIG_ERR == signal(SIGINT,sigint_handle))
        {
                perror("signal error");
                return 1;
        }
        memset(&server_attr,0,sizeof(server_attr));
        memset(&client_attr,0,sizeof(server_attr));
        /*
         * 1. 创建socket
         * socket创建在内核中,是一个结构体
         * AF_INET : IPV4
         * SOCK_STREAM : TCP协议
         */
        server_fd = socket(AF_INET,SOCK_STREAM,0);
        if(server_fd == -1)
        {
                perror("sock error");
                return 1;
        }
        /*
         * 2. 调用bind函数将socket与地址(ip,port)进行绑定
         */
        server_attr.sin_family = AF_INET;
        // 转换位网络字节序
        server_attr.sin_port = htons((short)atoi(argv[1]));
        // 表示所有ip,也可以指定第一个ip,指定ip时要把主机字节序转换成网络字节序
        server_attr.sin_addr.s_addr = INADDR_ANY;
        // 绑定ip端口
        if(-1 == bind(server_fd,(struct sockaddr*)&server_attr,sizeof(server_attr)))
        {
                perror("bind error");
                return 1;
        }
        /*
         * 3. 调用listen函数启动监听,通知系统接收来自客户端的请求
         * 第二个参数代表客户端队列的长度
         * 执行成功后能用netstat查看
         */
        if(-1 == listen(server_fd,8))
        {
                perror("listen error");
                return 1;
        }
        socklen_t addrlen = sizeof(client_attr);
        /*
         * 4. 调用accept获得客户端连接,并返回一个新的socket文件描述符
         * 若没有客户端连接,此函数会阻塞,直到获得一个客户端连接
         */
        int pid = 0;
        // 注册SIGCHLD信号处理函数,回收子进程,避免僵尸进程的产生
        signal(SIGCHLD,sigchld_handle);
        while(1)
        {
                client_fd = accept(server_fd,(struct sockaddr*)&client_attr,&addrlen);
                if(client_fd <= 0)
                {
                        continue;
                }
                server_log(&client_attr);
                // 子线程处理I/O,达到并发的效果
                pid = fork();
                if(pid == 0)
                {
                        /*
                        * 5. 调用I/O函数(read/write)和连接的客户端进行双向的通信
                        */
                        response(client_fd);
                        close(client_fd);
                        break;
                }
                close(client_fd);
        }
        close(server_fd);
        return 0;
}
void sigint_handle(int sig)
{
        close(server_fd);
        exit(0);
}
void response(int fp)
{
        time_t rawtime;
        struct tm* timeinfo;
        char client_data[512];
        int read_len = 0;
        while(1)
        {
                memset(client_data,'\0',sizeof(client_data));
                time(&rawtime);
                timeinfo = localtime(&rawtime);
                if((read_len = my_read(fp,client_data)) == -1)
                {
                        break;
                }
                else if(read_len == 0)
                {
                        strcat(client_data,"incorrect data\n");
                }
                else
                {
                        strcat(client_data,"\n");
                        strcat(client_data,asctime(timeinfo));
                }
                if(my_write(fp,client_data) == -1)
                {
                        break;
                }
        }
}
void server_log(struct sockaddr_in* client_attr)
{
        char ip[16] = {'\0'};
        // 结构体的的数据不能直接显示,需要先转换成本机字节序
        inet_ntop(AF_INET,&client_attr->sin_addr.s_addr,ip,sizeof(ip));
        printf("connected by %s:%d\n",ip,ntohs(client_attr->sin_port));
}
int my_write(int fd,char* str)
{
        my_protocol p = {0};
        memset(&p.data,'\0',sizeof(p.data));
        strcpy(p.data,str);
        p.bytes = strlen(p.data);
        if(write(fd,&p,sizeof(p)) < 0)
        {
                return -1;
        }
        return 0;
}
int my_read(int fd,char* str)
{
        my_protocol p = {0};
        memset(&p.data,'\0',sizeof(p.data));
        int read_len = 0;
        read_len = read(fd,&p,sizeof(p));
        if(p.bytes != strlen(p.data) && read_len != 0)
        {
                return -1;
        }
        strcpy(str,p.data);
        return read_len;
}
//  回收子进程方法
void sigchld_handle(int sig)
{
        // signal(SIGCHLD,sigchld_handle);
        wait(NULL);
        printf("free\n");
}
自定义协议客户端
#include <stdlib.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <sys/socket.h>
// 自定义写
int my_write(int fd,char* str);
// 自定义读
int my_read(int fd,char* str);
/* 自定义协议结构体 */
typedef struct{
        int bytes;
        char data[512];
}my_protocol;
int main(int argc,char* argv[])
{
        if(argc < 3)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        int client_fd = socket(AF_INET,SOCK_STREAM,0);
        struct sockaddr_in client_attr;
        memset(&client_attr,0,sizeof(client_attr));
        client_attr.sin_family = AF_INET;
        // 主机字节序转换成网络字节序
        client_attr.sin_port = htons((short)atoi(argv[2]));
        inet_pton(AF_INET,argv[1],&client_attr.sin_addr.s_addr);
        // client_attr.sin_addr.s_addr = 
        if(-1 == connect(client_fd,(struct sockaddr*)&client_attr,sizeof(client_attr)))
        {
                perror("connect ");
                return 1;
        }
        char res[512];
        while(1)
        {
                memset(res,'\0',sizeof(res));
                scanf("%s",res);
                if(-1 == my_write(client_fd,res))
                {
                        perror("write");
                        break;
                }
                if(my_read(client_fd,res) <= 0)
                {
                        perror("read");
                        break;
                }
                printf("res = %s",res);
        }
        close(client_fd);
        return 0;
}
int my_write(int fd,char* str)
{
        my_protocol p = {0};
        memset(&p.data,'\0',sizeof(p.data));
        strcpy(p.data,str);
        p.bytes = strlen(p.data);
        if(write(fd,&p,sizeof(p)) < 0)
        {
                return -1;
        }
        return 0;
}
int my_read(int fd,char* str)
{
        my_protocol p = {0};
        memset(&p.data,'\0',sizeof(p.data));
        int read_len = 0;
        read_len = read(fd,&p,sizeof(p));
        if(p.bytes != strlen(p.data) && read_len != 0)
        {
                return -1;
        }
        strcpy(str,p.data);
        return read_len;
}
tcp自定义协议服务器端,多线程处理并发
#include <stdio.h>
// atoi函数
#include <stdlib.h>
// wait函数
#include <sys/wait.h>
// I/O函数
#include <unistd.h>
#include <time.h>
// socket 系列函数
#include <sys/socket.h>
// sockaddr_in 结构体
#include <netinet/in.h>
// hton 函数
#include <arpa/inet.h>
#include <signal.h>
// memset函数
#include <string.h>
// pthread库
#include <pthread.h>
// 服务器socket描述符
int server_fd = 0;
// 服务器连接属性
struct sockaddr_in server_attr;
// 客户端socket描述符
int client_fd = 0;
// 客户端连接属性
struct sockaddr_in client_attr;
// ctrl + c 关闭服务器监听
void sigint_handle(int);
//  回收子进程方法
void sigchld_handle(int);
// 响应客户端连接
void response(int);
// 服务器连接日志
void server_log(struct sockaddr_in*);
// 自定义写
int my_write(int fd,char* str);
// 自定义读
int my_read(int fd,char* str);
// 多线程处理并发函数
void* thread_handle(void* data);
/* 自定义协议结构体 */
typedef struct{
        int bytes;
        char data[512];
}my_protocol;
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        if(SIG_ERR == signal(SIGINT,sigint_handle))
        {
                perror("signal error");
                return 1;
        }
        memset(&server_attr,0,sizeof(server_attr));
        memset(&client_attr,0,sizeof(server_attr));
        /*
         * 1. 创建socket
         * socket创建在内核中,是一个结构体
         * AF_INET : IPV4
         * SOCK_STREAM : TCP协议
         */
        server_fd = socket(AF_INET,SOCK_STREAM,0);
        if(server_fd == -1)
        {
                perror("sock error");
                return 1;
        }
        /*
         * 2. 调用bind函数将socket与地址(ip,port)进行绑定
         */
        server_attr.sin_family = AF_INET;
        // 转换位网络字节序
        server_attr.sin_port = htons((short)atoi(argv[1]));
        // 表示所有ip,也可以指定第一个ip,指定ip时要把主机字节序转换成网络字节序
        server_attr.sin_addr.s_addr = INADDR_ANY;
        // 绑定ip端口
        if(-1 == bind(server_fd,(struct sockaddr*)&server_attr,sizeof(server_attr)))
        {
                perror("bind error");
                return 1;
        }
        /*
         * 3. 调用listen函数启动监听,通知系统接收来自客户端的请求
         * 第二个参数代表客户端队列的长度
         * 执行成功后能用netstat查看
         */
        if(-1 == listen(server_fd,8))
        {
                perror("listen error");
                return 1;
        }
        socklen_t addrlen = sizeof(client_attr);
        /*
         * 4. 调用accept获得客户端连接,并返回一个新的socket文件描述符
         * 若没有客户端连接,此函数会阻塞,直到获得一个客户端连接
         */
        pthread_t tid = 0;
        // 初始化线程属性,用来创建分离的线程,使子线程结束后自动回收
        pthread_attr_t thread_attr;
        pthread_attr_init(&thread_attr);
        pthread_attr_setdetachstate(&thread_attr,PTHREAD_CREATE_DETACHED);
        // 注册SIGCHLD信号处理函数,回收子进程,避免僵尸进程的产生
        signal(SIGCHLD,sigchld_handle);
        // 忽略SIGPIPE信号处理函数,避免由于客户端断开连接,并由于read发送SIGPIPE信号导致进程结>束
        signal(SIGPIPE,SIG_IGN);
        while(1)
        {
                client_fd = accept(server_fd,(struct sockaddr*)&client_attr,&addrlen);
                if(client_fd <= 0)
                {
                        continue;
                }
                server_log(&client_attr);
                // 子线程处理I/O,达到并发的效果
                pthread_create(&tid,&thread_attr,thread_handle,(void*)client_fd);
                        printf("child thread\n");
                        // break;
                // 线程是共享的进程资源,这里不要关闭,不然线程里面的也没了
                // close(client_fd);
        }
        // close(server_fd);
        sleep(3);
        return 0;
}
void sigint_handle(int sig)
{
        close(server_fd);
        close(client_fd);
        exit(0);
}
void response(int fp)
{
        time_t rawtime;
        struct tm* timeinfo;
        char client_data[512];
        int read_len = 0;
        while(1)
        {
                memset(client_data,'\0',sizeof(client_data));
                time(&rawtime);
                timeinfo = localtime(&rawtime);
                if((read_len = my_read(fp,client_data)) == -1)
                {
                        break;
                }
                else if(read_len == 0)
                {
                        strcat(client_data,"incorrect data\n");
                }
                else
                {
                        strcat(client_data,"\n");
                        strcat(client_data,asctime(timeinfo));
                }
                if(my_write(fp,client_data) == -1)
                {
                        break;
                }
        }
}
void server_log(struct sockaddr_in* client_attr)
{
        char ip[16] = {'\0'};
        // 结构体的的数据不能直接显示,需要先转换成本机字节序
        inet_ntop(AF_INET,&client_attr->sin_addr.s_addr,ip,sizeof(ip));
        printf("connected by %s:%d\n",ip,ntohs(client_attr->sin_port));
}
int my_write(int fd,char* str)
{
        my_protocol p = {0};
        memset(&p.data,'\0',sizeof(p.data));
        strcpy(p.data,str);
        p.bytes = strlen(p.data);
        if(write(fd,&p,sizeof(p)) < 0)
        {
                return -1;
        }
        return 0;
}
int my_read(int fd,char* str)
{
        my_protocol p = {0};
        memset(&p.data,'\0',sizeof(p.data));
        int read_len = 0;
        read_len = read(fd,&p,sizeof(p));
        if(p.bytes != strlen(p.data) && read_len != 0)
        {
                return -1;
        }
        strcpy(str,p.data);
        return read_len;
}
//  回收子进程方法
void sigchld_handle(int sig)
{
        // signal(SIGCHLD,sigchld_handle);
        wait(NULL);
        printf("free\n");
}
void* thread_handle(void* data)
{
        int fd = (int)data;
        /*
        * 5. 调用I/O函数(read/write)和连接的客户端进行双向的通信
        */
        response(fd);
        close(fd);
        return (void*)NULL;
}

udp编程

udp编程模型

  • 客户端调用序列

    • 调用socket函数创建套接字
    • 调用bind连接服务器端(这一步可以不要)
    • 调用sendto/readfrom与服务器端通讯
    • 调用close关闭套接字
  • 服务器端调用序列

    • 调用socket函数创建套接字
    • 调用bind绑定本地地址和端口
    • 调用sendto/readfrom与客户端通讯
    • 调用close关闭套接字

数据传输

发送数据

ssize_t send(int sockfd,const void* buf,size_t nbytes,int flag);

  • 返回:成功返回发送字节数,出错返回-1
  • 功能:发送数据,需要在发送数据前已经建立的连接,多用于TCP,用于UDP时要使用connect函数先建立连接
    `ssize_t sendto(int sockfd,const void buf,size_t nbytes,int flag,const struct sockaddr

desaddr,socklen_t destlen);`

  • 返回:成功返回发送的字节数,出错返回-1
  • 功能:发送数据,需要指定发送方(desaddr参数)
  • sockaddr:目的地的相关信息
    ssize_t sendmsg(int sockfd,const struct msghdr* msg,int flag);
  • 返回:成功返回发送的字节数,出错返回-1
  • 头文件
#include <sys/socket.h>
  • msghdr结构体
struct msghdr
{
        void* msg_name;// optional address
        socklen_t msg_namelen;// address size in bytes
        struct iovec* msg_iov;// array of I/O buffers
        int msg_iovlen;// number of elements in array
        void* msg_control;// ancillary data
        socklen_t msg_controllen;// number of ancillary bytes
        int msg_flags;// flag for received message
};
接收数据

ssize_t recv(int sockfd,void* buf,size_t nbytes,int flag);

  • 功能:接收数据,不能获得发送方的信息,
    ssize_t recvfrom(int sockfd,void*restrict buf,size_t len,int flag,struct sockaddr*restrict addr,socklen_t*restrict addrlen);
  • 功能:除了能获取数据外,还可以获得发送方的信息,用于在之后对指定的发送方发送数据
    ssize_t recvmsg(int sockfd,struct msghdr* msg,int flag);
  • 头文件
#include <sys/socket.h>

示例

服务器端
#include <stdio.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <pthread.h>
typedef struct
{
        struct sockaddr_in attr;
        char data[512];
}thread_data;
int server_fd = 0;
void* thread_handle(void* client);
void server_log(struct sockaddr_in* attr);
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incorrect parametr\n");
                return 1;
        }
        /*
         * 1. 创建socket
         * SOCK_DGRAM : 使用UDP传输
         */
        server_fd = socket(AF_INET,SOCK_DGRAM,0);

        /*
         * 2. 设置服务器选项,SO_REUSEADDR,会先解除之前的绑定,在绑定一次,避免重启时因为连接还
没有断开导致的bind报错
         */
        setsockopt(server_fd,SOL_SOCKET,SO_REUSEADDR,(void*)NULL,0);

        /*
         * 3. 设置服务器选项,SO_SNDTIMEO,发送客户端消息的超时时间,避免子线程阻塞
         */
        struct timeval time_out = {3,0};
        // setsockopt(server_fd,SOL_SOCKET,SO_RCVTIMEO,(char*)&time_out,sizeof(time_out));
        setsockopt(server_fd,SOL_SOCKET,SO_SNDTIMEO,(char*)&time_out,sizeof(time_out));

        /*
         * 4. 设置绑定的ip及端口信息
         */
        struct sockaddr_in server_attr;
        server_attr.sin_family = AF_INET;
        server_attr.sin_port = htons((short)atoi(argv[1]));
        server_attr.sin_addr.s_addr = INADDR_ANY;

        /*
         * 5. 绑定本地ip,port
         */
        bind(server_fd,(struct sockaddr*)&server_attr,sizeof(server_attr));
        // 存放客户端信息
        thread_data* client;
        // 存放子线程id
        pthread_t tid = 0;
        // 存放子线程属性,用以设置以分离模式启动子线程
        pthread_attr_t thread_attr;
        memset(&thread_attr,0,sizeof(thread_attr));
        pthread_attr_setdetachstate(&thread_attr,PTHREAD_CREATE_DETACHED);
        // 上次是否读取成功的标识,用以判断是否需要重新申请内存
        int recv_flag = 0;
        // 连接信息结构体的大小
        socklen_t addrlen = sizeof(struct sockaddr_in);
        while(1)
        {
                /*
                * 6. 获得客户端发送的数据与客户端信息,用于与客户端通信
                */
                if(recv_flag == 0)
                {
                        client = malloc(sizeof(thread_data));
                }
                memset(client,0,sizeof(struct sockaddr_in));
                if(0 >= recvfrom(server_fd,client->data,sizeof(client->data),0,(struct sockaddr*)&client->attr,&addrlen))
                {
                        // 超时或者读取失败则继续下一次等待,设置标识,避免下次重新申请内存
                        printf("time out\n");
                        recv_flag = 1;
                        continue;
                }
                server_log(&client->attr);
                /*
                * 7. 使用子线程处理并发
                */
                pthread_create(&tid,&thread_attr,thread_handle,(void*)client);
                recv_flag = 0;
        }
        return 0;
}
void* thread_handle(void* client)
{
        thread_data* t = (thread_data*)client;
        char thread_id[20] = {'\0'};
        sprintf(thread_id,"%lu",pthread_self());
        // 连接信息结构体的大小
        strcat(t->data,"\n;thread_id = ");
        strcat(t->data,thread_id);
        sendto(server_fd,t->data,sizeof(t->data),0,(struct sockaddr*)&t->attr,sizeof(t->attr));
        // 释放动态申请的内存
        free(client);
        return NULL;
}
void server_log(struct sockaddr_in* attr)
{
        char ip[16] = {'\0'};
        inet_ntop(AF_INET,&attr->sin_addr.s_addr,ip,sizeof(ip));
        printf("connect from %s handle by %lu\n",ip,pthread_self());
}
udp客户端
#include <stdio.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <pthread.h>
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incorrect parametr\n");
                return 1;
        }
        /*
         * 1. 创建socket
         * SOCK_DGRAM : 使用UDP传输
         */
        int client_fd = socket(AF_INET,SOCK_DGRAM,0);


        /*
         * 3. 设置服务器的ip及端口信息
         */
        struct sockaddr_in server_attr;
        server_attr.sin_family = AF_INET;
        server_attr.sin_port = htons((short)atoi(argv[2]));
        inet_pton(AF_INET,argv[1],&server_attr.sin_addr.s_addr);
        char res[512] = {'\0'};
        while(1)
        {
                scanf("%s",res);
                if(sendto(client_fd,res,sizeof(res),0,(struct sockaddr*)&server_attr,sizeof(server_attr)) <= 0)
                {
                        perror("sendto");
                        break;
                }
                if(recv(client_fd,res,sizeof(res),0) <= 0)
                {
                        perror("recv");
                        break;
                }
                printf("%s\n",res);
        }
        return 0;
}

域名解析函数

hostent结构体

struct hostent
{
        char* h_name;// 主机名
        char** h_aliases;// 别名,字符串数组
        int h_addrtype;// 协议类型
        int h_length;// 网络地址大小
        char** h_addr_list;// 指向网络地址的指针
};

函数

struct hostent* gethostent(void);
struct hostent* gethostbyname(const char* hostname);
void sethostent(int stayopen);
void endhostent(void); // 与hostent一起使用

  • 头文件
#include <netdb.h>

示例

if((hptr = gethostbyname("www.jinblog.com")) == NULL)
{
        fprintf(stderr,"gethostbyname call faile. %s\n",hsterror(h_errno));
        return 1;
}
printf("official name:%s\n",hptr->h_name);
for(pptr = hptr->h_aliases;*pptr != NULL;pptr++)
{
        printf("\talias:%s\n",*pptr);
}
if(hptr->h_addrtype != AF_INET)
{
        fprintf(stderr,"invalid address type %d\n",hptr->h_addrtype);
}
pptr = hptr->h_addr_list;
for(;*pptr != NULL;pptr++)
{
        printf("\taddress:%s\n",inet_ntop(hptr->h_addrtype,*pptr,str,sizeof(str)));
}
打印
#include <stdio.h>
#include <string.h>
#include <netdb.h>
#include <arpa/inet.h>
void print_host(struct hostent* host);
int main(void)
{
        printf("----------gethostent start--------\n");
        struct hostent* host;
        while((host = gethostent()) != NULL)
        {
                print_host(host);
        }
        endhostent();
        printf("----------gethostent  stop--------\n");
        
        printf("\n\n----------gethostentbyname start--------\n");

        if((host = gethostbyname("jinblog.com")) != NULL)
        {
                print_host(host);
        }

        printf("----------gethostentbyname  stop--------\n");
        return 0;
}
void print_host(struct hostent* host)
{
        printf("host : %s\n",host->h_name);
        int i = 0;
        while(host->h_aliases[i] != NULL)
        {
                printf("\talias : %s\n",host->h_aliases[i]);
                i++;
        }
        switch(host->h_addrtype)
        {
                case AF_INET:
                        printf("address type : AF_INET\n");
                        break;
                case AF_INET6:
                        printf("address type : AF_INET6\n");
                        break;
                case AF_UNIX:
                        printf("address type : AF_UNIX\n");
                        break;
                default:
                        printf("address type : unknown\n");
                        break;
        }
        printf("length : %d\n",host->h_length);
        i = 0;
        char ip[32] = {'\0'};
        while(host->h_addr_list[i] != NULL)
        {
                inet_ntop(host->h_addrtype,host->h_addr_list[i],ip,sizeof(ip));
                printf("\tip : %s",ip);
                i++;
                memset(ip,'\0',sizeof(ip));
        }
        printf("\n\n\n");
}

广播

  • 实现一对多的通讯
  • 通过向广播地址发送数据报文实现

套接字选项

  • 套接字选项用于修饰套接字以及其底层通讯协议的各种行为。函数setsockopt和getsockopt可以查看和设置套接字的各种选项
    int getsockopt(int sockfd,int optname,void* optval,socklen_t* optlen);

int setsockopt(int sockfd,int optname,void* optval,socklen_t* optlen);

SO_BROADCAST选项

  • SO_BROADCAST选项控制着UDP套接字是否能够发送广播数据报,选项的类型位int,非零意味着是,注意,只有UDP套接字可以使用这个选项,TCP是不能使用广播的
int opt = 1;
if((sockfd = sock(AF_INET,SOCK_DGRAM,0)) < 0)
{
        // 错误处理
}
if(setsockopt(sockfd,SOL_SOCKET,SO_BROADCAST,&opt,sizeof(int)) < 0)
{
        // 错误处理
}

SO_SNDBUF和SO_RCVBUF选项

  • 每个套接字有一个发送缓冲区和接收缓冲区,这两个缓冲区由底层协议使用,接收缓冲区存放由协议接收的数据直到被应用程序读走,发送缓冲区存放应用写出的数据直到被协议发送出去。SO_SNDBUF和SO_RCVBUF选项分别控制发送和接收缓冲区的大小,他们类型为int,以字节为单位
if((sockfd = sock(AF_INET,SOCK_DGRAM,0)) < 0)
{
        // 错误处理
}
int opt = 0;
if(getsockopt(sockfd,SOL_SOCKET,SO_SNDBUF,&opt,sizeof(opt)) < 0)
{
        // 错误处理
}
opt += 888;
if(setsockopt(sockfd,SOL_SOCKET,SO_SNDBUF,&opt,sizeof(opt)) < 0)
{
        // 错误处理
}

广播地址

  • 如果用{netID,subnetID,hostID}({网络id,子网id,主机id})标识IPV4地址,那么有四类的广播地址,我们用-1表示所有比特都为1的字段
  • 子网广播地址:{netID,subnetID,-1},这类地址编排指定子网上的所有接口,例如,如果我们对B类地址192.168采用8为子网id,那么192.168.2.255将是192.168.2子网上的所有接口的子网广播地址。路由器不转发这类广播
  • 全部子网地址:{netID,-1,-1}。这类广播地址编排指定网络上的所有子网。如果说这类地址被使用过的话,那么现在已很少见了
  • 受限广播地址{-1,-1,-1}或255.255.255.255。路由器从不转发目的地址为255.255.255.255的IP报数据。

示例

广播服务器端
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>
int main(int argc,char* argv[])
{
        if(argc < 3)
        {
                printf("incrrect parameter\n");
                return 1;
        }
        /*
         * 1. 创建socket,要创建UDP类型的socket,广播包是用UDP发送的
         */
        int server_fd = socket(AF_INET,SOCK_DGRAM,0);

        /*
         * 2. 设置要发送到的广播域和port
         */
        struct sockaddr_in des_sock_attr;
        des_sock_attr.sin_family = AF_INET;
        // 注意argv[1]是广播地址
        inet_pton(AF_INET,argv[1],&des_sock_attr.sin_addr.s_addr);
        des_sock_attr.sin_port = htons((short)atoi(argv[2]));

        /*
         * 2. 设置socket选项,使socket可以发送广播报
         */
        int opt = 1;
        setsockopt(server_fd,SOL_SOCKET,SO_BROADCAST,&opt,sizeof(int));
        char buf[512] = {'\0'};
        int i = 0;
        while(1)
        {
                sprintf(buf,"message %d\n",i);
                if(0 >= sendto(server_fd,buf,sizeof(buf),0,(struct sockaddr*)&des_sock_attr,sizeof(des_sock_attr)))
                {
                        perror("sendto");
                        continue;
                }
                printf("broadcast : %d\n",i);
                sleep(3);
                i++;
                memset(buf,'\0',sizeof(buf));
        }
        return 1;
}
广播客户端
#include <stdio.h>
#include <stdlib.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incrrect parameter\n");
                return 1;
        }
        /*
         * 1. 创建socket,要创建UDP类型的socket,广播包是用UDP发送的
         */
        int client_fd = socket(AF_INET,SOCK_DGRAM,0);
        /*
         * 2. 设置socket,ip,port等属性
         */
        struct sockaddr_in client_attr;
        client_attr.sin_port = htons((short)atoi(argv[1]));
        client_attr.sin_addr.s_addr = INADDR_ANY;
        client_attr.sin_family = AF_INET;

        /*
         * 3. 设置 SO_REUSEADDR,避免bind报错
         */
        setsockopt(client_fd,SOL_SOCKET,SO_REUSEADDR,(void*)NULL,0);
        /*
         * 4. bind绑定ip端口
         */
        bind(client_fd,(struct sockaddr*)&client_attr,sizeof(client_attr));

        /*
         * 5. 接收广播报数据
         */
        struct sockaddr_in server_attr;
        char buf[512] = {'\0'},ip[16] = {'\0'};
        socklen_t addrlen = sizeof(server_attr);
        while(1)
        {
                if(recvfrom(client_fd,buf,sizeof(buf),0,(struct sockaddr*)&server_attr,&addrlen) <= 0)
                {
                        perror("recvfrom");
                        return 1;
                }
                inet_ntop(AF_INET,&server_attr.sin_addr.s_addr,ip,sizeof(ip));
                printf("server ip : %s;\nbroadcast data : %s\n\n",ip,buf);
        }
        return 0;
}

下一篇:http://jinblog.com/archives/868.html

linux编程学习 03 线程

线程

  • 进程是资源管理的最小单位,线程是程序执行的最小单位
  • 每个进程都有自己的数据段,代码段和堆栈段。线程通常叫做轻型的进程,他包含独立的栈和cpu寄存器状态,线程是进程的一条执行路径,每个线程共享其所属进程的所有资源,包括打开的文件,内存页面,信号标识及动态分配的内存
  • 因为线程和进程比起来很小,所以相对来说,线程花费更少的cpu资源
  • 在操作系统设计上,从进程演化出线程,最主要的目的就是更好的支持多处理器,并且减少进程上下文切换的开销。

进程与线程的关系

  • 线程和进程的关系是:线程是属于进程的,线程运行在进程空间内,同已进程所产生的线程共享同一用户内存空间,当进程退出时该进程所产生的线程都会被强制退出并清除。一个进程至少需要一个线程作为他的指令执行体。进程管理着资源(比如cpu,内存,文件等)。而将线程分配到某个cpu上执行。
  • 进程默认会有一个线程,称为主控线程
  • 进程进入running状态时再对进程下的线程分配运行时间,同一时间只有一个线程在运行

线程分类

  • 线程按照其调度者可分为用户级线程和内核级线程两种

    • 用户级线程:主要解决上下文切换问题,其调度过程由用户决定
    • 内核级线程:有内核调度机制实现
  • 现在大多数操作系统都采用用户级线程和内核级线程并存的方法
  • 用户线程要绑定内核级线程运行,一个进程中的内核级线程会分配到固定的时间片,用户级线程分配的时间片以内核线程为准
  • 默认情况下用户级线程和内核级线程是一对一,也可以多对一,但是这样实时性会较差。
  • 当cpu分配给线程的时间片用完后但线程没有执行完毕,此时线程会从运行状态切换到就绪状态,将cpu让给其他进程使用

linux线程实现

  • 以下线程均为用户级线程,在linux中,一般采用pthread线程库实现线程的访问与控制,由POSIX提出,具有良好的移植性
  • linux线程程序编译需要在gcc上链接库pthread

线程标识

  • 每个进程内部的不同线程都有自己的唯一标识
  • 线程标识只在它所属的进程环境中有效
  • 显示标识是pthread_t数据类型
    int pthread_equal(pthread_t,pthread_t)
  • 返回:相等返回0,否则返回非0
    pthread_t pthread_self(void);
  • 返回:调用线程的线程id
  • 头文件
    #include <pthread.h>

线程创建

int pthread_create(pthread_t *retrict tidp,const pthread_attr_t *restrict attr,void *(*start_rtn)(void*),void* restrict arg);

  • 返回:成功返回0,失败返回错误编号
  • 头文件
    #include <pthread.h>
  • 参数

    • tidp:线程标识符指针
    • attr:线程属性指针
    • start_rtn:线程运行函数的起始地址
    • arg:传递给线程运行函数的参数
  • 新线程从start_rtn函数的地址开始执行
  • 不能保证新线程和调用线程的执行顺序
  • 示例
typedef struct
{
        int start;
        int end;
}for_length;
int main(void)
{
        pthread_t thread1_id,thread2_id;
        int res = 0;
        // 传递单个参数
        if((res = pthread_create(&thread1_id,NULL,thread_func,(void*)8)) != 0)
        {   
                perror("create thread1 error");
                return 1;
        }   
        if((res = pthread_create(&thread2_id,NULL,thread_func,(void*)6)) != 0)
        {   
                perror("create thread2 error");
                return 1;
        }
        // 这里要把进程阻塞,不然进程结束,线程也会结束
        // sleep(30);
        // 主控线程调用pthread_join,自己会阻塞,直到thread1和thread2结束才会运行
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        // 传递多个参数时,可以使用结构体
        for_length f1 = {1,10},f2 = {1,8};
        if((res = pthread_create(&thread1_id,NULL,thread_func2,(void*)(&f1))) != 0)
        {
                perror("create thread1 error");
                return 1;
        }
        if((res = pthread_create(&thread2_id,NULL,thread_func2,(void*)(&f2))) != 0)
        {
                perror("create thread2 error");
                return 1;
        }
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        return 0;
}
/**
 * 接收单个参数
 * */
void* thread_func(void* par)
{
        // 注意因为传递时,是直接把常量的值转换成地址,一般情况下 par = 0x7fffa76962f0 指针变量>是存放的地址,但是这里的情况是 par = 0x000000000006,所以直接转换就可以了
        int times = (int)par;
        for(int i = 0;i < times;i++)
        {
                sleep(1);
                printf("I am thread %li;i = %d\n",pthread_self(),i);
        }
        return (void*)NULL;
}
/**
 * 接收多个参数
 * */
void* thread_func2(void* par)
{
        // 转换成结构体指针
        for_length* times = (for_length*)par;
        for(int i = times->start;i < times->end;i++)
        {
                sleep(1);
                printf("I am thread %li;i = %d\n",pthread_self(),i);
        }
        return (void*)NULL;
}

终止方式

  • 主动终止

    • 线程的执行函数中调用return语句
    • 调用pthread_exit
  • 被动终止

    • 线程可以被同一进程的其他进程取消,其他线程调用pthread_cancel(pthid)

int pthread_cancel(pthread_t tid);
void pthread_exit(void *retval);
int pthread_join(pthread_t th,void** thread_return);

  • 返回值:成功返回0,否则返回错误编号
  • 头文件:
#include <pthread.h>
  • pthread_cancel

    • 线程可以被同一进程的其他线程取消,tid为终止的线程标识符
  • pthread_exit

    • retval:pthread_exit调用者线程的返回值,可由其他函数和pthread_join来检测获取
    • 线程退出时使用函数pthread_exit,是线程的主动行为
    • 由于一个线程中的多个线程共享数据段,因此通常在线程退出后,退出线程所占用的资源并不会随线程结束而释放。所以需要pthread_join函数来等待线程结束,类似于wait系统调用
  • pthread_join

    • th:被等待线程的标识符
    • thread_return:用户定义指针,用来存储被等待进程的返回值
  • 示例
typedef struct
{
        int id;
        char name[10];
}user;
void* thread_func(void* data);
int main(void)
{
        pthread_t thread_id;
        int res = 0;
        user u = {1,"jin"};
        if((res = pthread_create(&thread_id,NULL,thread_func,(void*)&u)) != 0)
        {
                perror("create thread error");
        }
        // 指针变量接收要回传的数据
        void* join_res;
        // 要传递的是指针变量的地址
        pthread_join(thread_id,&join_res);
        printf("id = %d;name = %s\n",((user*)join_res)->id,((user*)join_res)->name);
        return 0;
}
void* thread_func(void* data)
{
        // 先转换指针
        user* u = (user*)data;
        printf("id = %d;name = %s\n",u->id,u->name);
        u->id = 6;
        return (void*)u;
}

线程清理和控制函数

void pthread_cleanup_push(void (*rtn)(void*),void* arg);
void pthread_cleanup_pop(int execute);

  • 返回:成功返回0,否则返回错误编号
  • 头文件
#include <pthread.h>
  • 参数

    • rtn:清理函数指针
    • arg:调用清理函数传递的参数
    • execute:值1时执行线程清理函数,值0时不执行线程清理函数
  • 触发线程调用清理函数动作

    • 调用pthread_exit
    • 响应取消请求
    • 用非零execute参数调用thread_cleanup_pop时
  • 示例
int main(void)
{
        pthread_cleanup_push(cleanup_func,(void*)6);
        // 传入非0才会执行
        pthread_cleanup_pop(-1);
        return 0;
}
void cleanup_func(void* v)
{
        printf("I am cleanup_func;i = %d;\n",(int)v);
}

进程,线程启动和终止方式的比较

进程线程
fork()pthread_create()
return/exit()/_exit()return/pthread_exit()
wait()pthread_join()
atexit()pthread_cleanup_push()/pthread_cleanup_pop()

线程属性初始化和销毁

int pthread_attr_init(pthread_attr_t* attr);
int pthread_attr_destroy(pthread_attr_t* attr);

  • 返回:成功返回0,否则返回错误编号
  • 头文件
#include <pthread.h>
  • 线程属性结构体
typedef struct
{
      int etachstate; // 线程的分离状态
      int schedpolicy; // 线程调度策略
      structsched_param schedparam; // 线程的调度参数
      int inheritsched; // 线程的继承性
      int scope; // 线程的作用域
      size_t guardsize; // 线程栈末尾的警戒缓冲区大小
      int stackaddr_set; // 线程的栈设置
      void* stackaddr; // 线程栈的位置
      size_t stacksize; // 线程栈的大小
}pthread_attr_t;

设置和获得分离属性

int pthread_attr_getdetachstat(const pthread_attr_t*restrict attr,int* detachstate);
int pthread_attr_setdetachstat(const pthread_attr_t* attr,int detachstate);

  • 返回:成功返回0,出错返回错误编号
  • detachstate取值

    • PTHREAD_CREATE_JOINABLE(默认值) 正常启动线程
    • PTHREAD_CREATE_DETACHED 以分离状态启动线程
  • 以默认方式启动的线程,在线程结束后不会自动释放占有的系统资源,要在主控线程中调用pthread_join后才会释放
  • 以分离状态启动的线程,在线程结束后会自动释放所占有的系统资源
  • 分离属性在网络通讯中使用的较多
  • 示例
int main(void)
{
        pthread_attr_t attr;
        pthread_attr_init(&attr);
        pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_DETACHED);
        pthread_t thread_id;
        int res = 0;
        if((res = pthread_create(&thread_id,&attr,pthread_func,(void*)6)) != 0)
        {
                perror("create thread error");
                return 1;
        }
        // 使用分离状态启动进程时,pthread_join无效,看不到输出结果,需要sleep才能看到输出结果
        pthread_join(thread_id,NULL);
        sleep(1);
        return 0;
}
void* pthread_func(void* data)
{
        printf("child thread;data = %d\n",(int)data);
        return (void*)NULL;
}

线程的同步和互斥

  • 线程同步

    • 是一个宏观的概念,在微观上线程的相互排斥和线程的先后执行的约束问题
    • 解决同步方式

      • 条件变量
      • 进程信号量
  • 线程互斥

    • 线程执行的相互排斥
    • 解决互斥方式

      • 互斥锁
      • 读写锁
      • 线程信号量

线程互斥-互斥锁

  • 互斥锁(mutex)是一种简单的加锁的方法来控制对共享资源的访问。在同一时刻只能有一个线程掌握某个互斥锁,拥有上锁状态的进程能够对共享资源进行访问。若其他线程希望上锁一个已经被上了互斥锁的资源。则该线程挂起,直到上锁的线程释放互斥锁为止
  • 互斥锁数据类型

    • pthread_mutex_t

互斥锁创建与销毁

int pthread_mutex_init(pthread_mutex_t*restrict mutex,const pthread_mutexattr_t* mutexattr);
int pthread_mutex_destroy(pthread_mutex_t* mutex);

  • 返回:成功返回0,否则返回错误编号
  • 头文件
#include <pthread.h>
  • 参数

    • mutex:互斥锁
    • mutexattr:互斥锁创建方式

      • PTHREAD_MUTEX_INITIALIZER

        • 快速创建互斥锁
      • PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP

        • 创建递归互斥锁
      • PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP

        • 创建检错互斥锁

互斥锁上锁和解锁

int pthread_mutex_lock(pthread_mutex_t* mutex);

  • 功能:上锁,拿不到锁阻塞
    int pthread_mutex_trylock(pthread_mutex_t* mutex);
  • 功能:上锁,拿不到锁阻塞
    int pthread_mutex_unlock(pthread_mutex_t* mutex);
  • 功能:释放锁
  • 返回:成功返回0,出错返回出错码
  • 参数

    • mutex:互斥锁
  • 示例
typedef struct
{
        int deposit;
        pthread_mutex_t lock;// 把锁与变量联系在一起
}Account;
typedef struct
{
        char name[8];
        int amount;
        Account* account;
}User;
void* withdraw(void*);
void* withdraw(void*);
int main(void)
{
        Account account = {88888};
        pthread_mutex_init(&account.lock,NULL);
        User user1 = {"jin1",88888,&account};
        User user2 = {"jin2",88888,&account};
        pthread_t thread1_id,thread2_id;
        int res = 0;
        if((res = pthread_create(&thread1_id,NULL,withdraw,(void*)&user1)) != 0)
        {
                perror("create thread error");
        }
        if((res = pthread_create(&thread2_id,NULL,withdraw,(void*)&user2)) != 0)
        {
                perror("create thread error");
        }
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        printf("account's deposit %d\n",account.deposit);
        return 0;
}
void* withdraw(void* user)
{
        User* u = (User*)user;
        // 加锁,其他线程到这里加锁时会阻塞住,等解锁后才会继续运行
        pthread_mutex_lock(&u->account->lock);
        sleep(1);
        if(u->amount > u->account->deposit)
        {
                printf("sorry %s;your balance is not enough\n",u->name);
                return (void*)NULL;
        }
        printf("%s => %d\n",u->name,u->amount);
        u->account->deposit -= u->amount;
        // 解锁,解锁后其他线程才会继续运行
        pthread_mutex_unlock(&u->account->lock);
        return (void*)NULL;
}

互斥锁进程共属性操作

int pthread_mutexattr_getpshared(const pthread_mutextattr_t*restrict attr,int*restrict pshared);
int pthread_mutexattr_setpshared(pthread_mutexattr_t* attr,int pshared);

  • 返回:成功返回0,出错返回错误编号
  • 参数

    • attr:互斥锁熟悉
    • pshared

      • PTHREAD_PROCESS_PRIVATE(默认情况)

        • 锁只能用于一个进程内部的两个线程进行互斥
      • PTHREAD_PROCESS_SHARED

        • 锁能用于两个不同进程中的线程进行互斥

互斥锁类型操作

int pthread_mutexattr_gettype(const pthread_mutexattr_t*restrict attr,int*restrict type);
int pthread_mutexattr_settype(const pthread_mutexattr_t*restrict attr,int type);

  • 返回:成功返回0,出错返回错误编号
  • 参数

    • attr:互斥锁属性
    • type:互斥锁类型

      • 标准互斥锁:PTHREAD_MUTEX_NORMAL

        • 第一次上锁成功,第二次上锁会阻塞
      • 递归互斥锁:PTHREAD_MUTEX_RECURSIVE

        • 第一次上锁成功,第二次以后上锁还是成功,内部计数
      • 检查互斥锁:PTHREAD_MUTEX_ERRORCHECK

        • 第一次上锁成功,第二次上锁会出错
      • 默认互斥锁:PTHREAD_MUTEX_DEFAULT(同标准互斥锁)
  • 示例
int main(int argc,char* argv[])
{
        if(argc < 2)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        // 初始化属性变量
        pthread_mutexattr_t attr;
        // 设置属性
        if(strcmp(argv[1],"normal") == 0)
        {
                pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_NORMAL);
        }
        else if(strcmp(argv[1],"recursive") == 0)
        {
                pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_RECURSIVE);
        }
        else if(strcmp(argv[1],"errorcheck") == 0)
        {
                pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_ERRORCHECK);
        }
        else
        {
                pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_DEFAULT);
        }
        pthread_mutex_t lock;
        // 使用设置的属性初始化锁
        pthread_mutex_init(&lock,&attr);
        if(pthread_mutex_lock(&lock) != 0)
        {
                printf("first lock error\n");
        }
        else
        {
                printf("first lock\n");
        }
        if(pthread_mutex_lock(&lock) != 0)
        {
                printf("secound lock error\n");
        }
        else
        {
                printf("second lock\n");
        }
        // 销毁锁
        pthread_mutex_destroy(&lock);
        pthread_mutexattr_destroy(&attr);
        return 0;
}

线程互斥-读写锁

  • 线程使用互斥锁缺乏都并发性
  • 当读操作较多,写操作较少时,可使用读写锁提高线程读并发性
  • 读写数据锁类型

    • pthread_rwlock_t

读写锁创建和销毁

int pthread_rwlock_init(pthread_rwlock_t*restrict rwlock,const pthread_rwlockattr_t*restrict attr);
int pthread_rwlock_destroy(pthread_rwlock_t* rwlock);

  • 头文件
#include <pthread.h>
  • 参数

    • rwlock:读写锁
    • attr:读写锁属性

读写锁加锁和解锁

int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock);

  • 功能:加读锁
    int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock);
  • 功能:加写锁
    int pthread_rwlock_unlock(pthread_rwlock_t* rwlock);
  • 功能:释放锁
  • 返回:成功返回0,出错返回错误编号
  • 参数

    • rwlock:读写锁
  • 读写锁特性

    • 读和读:不互斥,两个都会成功
    • 读和写:互斥,第二个会阻塞
    • 写和写:不排斥,第二会失败
    • 写和读:不互斥,第二个会失败
  • 示例
int main(int argc,char *argv[])
{
        if(argc < 3)
        {
                printf("incorrect parameter\n");
                return 1;
        }
        pthread_rwlock_t rwlock;
        pthread_rwlock_init(&rwlock,NULL);
        if(strcmp(argv[1],"r") == 0)
        {
                if(pthread_rwlock_rdlock(&rwlock) != 0)
                {
                        printf("first read lock fail\n");
                }
                else
                {
                        printf("first read lock success\n");
                }
        }
        else
        {
                if(pthread_rwlock_wrlock(&rwlock) != 0)
                {
                        printf("first write lock fail\n");
                }
                else
                {
                        printf("first write lock success\n");
                }
        }
        if(strcmp(argv[2],"r") == 0)
        {
                if(pthread_rwlock_rdlock(&rwlock) != 0)
                {
                        printf("second read lock fail\n");
                }
                else
                {
                        printf("second read lock success\n");
                }
        }
        else
        {
                if(pthread_rwlock_wrlock(&rwlock) != 0)
                {
                        printf("second write lock fail\n");
                }
                else
                {
                        printf("second write lock success\n");
                }
        }
        // 注意上面锁了两次,所以这里要解锁两次
        pthread_rwlock_unlock(&rwlock);
        pthread_rwlock_unlock(&rwlock);
        pthread_rwlock_destroy(&rwlock);
        return 0;
}

线程同步-条件变量

  • 互斥锁的缺点是它只有两种状态:锁定和非锁定
  • 条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足
  • 条件变量内部是一个等待队列,放置等待的线程,线程在条件变量上等待和通知,互斥锁来保护等待队列(对等待队列上锁),条件变量通常和互斥锁一起使用。
  • 条件变量运行线程等待特定条件发生,当条件不满足时,线程通常先进入阻塞状态,等待条件发生变化。一旦它的某个线程改变了条件,可唤醒一个或多个阻塞的线程
  • 具体判断条件还需用户给出
  • 条件变量数据类型

    • pthread_cond_t

条件变量的创建和销毁

int pthread_cond_wait(pthread_cond_t*restrict cond,pthread_mutex_t*restrict mutex);
int pthread_cond_timewait(pthread_cond_t*restrict cond,pthread_mutex_t*restrict mutex,const struct timespec*restrict timeout);

  • 返回:成功返回0,出错返回错误变化
  • 头文件
#include <pthread.h>
  • timespec结构体
struct timespec
{
        time_t tv_sec; // seconds
        long tv_nsec;  // nanoseconds
}
  • 参数

    • cond:条件变量
    • mutex:互斥锁
  • 互斥锁mutex是对条件变量cond的保护
  • 线程由于调用wait函数阻塞,否则释放互斥锁

条件变量通知操作

int pthread_cond_signal(pthread_cond_t* cond);
int pthread_cond_broadcast(pthread_cond_t* cond);

  • 返回:成功返回0,出错返回错误编号
  • 参数

    • cond:条件变量
  • 当条件满足,线程需要通知等待的线程
  • pthread_cond_signal函数通知单个线程
  • pthread_cond_broadcast函数通知所有线程
  • pthread_cond_wait函数内部流程

    1. unlock(&mutex); // 释放锁
    2. lock(&mutex);
    3. 将线程自己插入到条件变量的等待队列中
    4. unlock(&mutex);
    5. 当前等待的线程阻塞(等待阻塞) <== 等其他线程通知唤醒
    6. 在唤醒后,lock(&mutex)
    7. 在等待队列中删除自己
  • 示例
typedef struct
{
        pthread_mutex_t mutex;
        pthread_cond_t cond;
        int res;
        int is_wait;
}Data;
void* get_v(void*);
void* compare_v(void*);
int main(void)
{
        pthread_cond_t cond;
        pthread_mutex_t mutex;
        pthread_cond_init(&cond,NULL);
        pthread_mutex_init(&mutex,NULL);
        Data data = {mutex,cond,0,0};
        pthread_t thread1_id,thread2_id;
        if(pthread_create(&thread1_id,NULL,compare_v,(void*)&data) != 0)
        {
                printf("create thread1 error\n");
                return 1;
        }
        if(pthread_create(&thread2_id,NULL,get_v,(void*)&data) != 0)
        {
                printf("create thread2 error\n");
                return 1;
        }
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        pthread_cond_destroy(&cond);
        pthread_mutex_destroy(&mutex);
        return 0;
}
// 获得输入和输出结果的线程函数
void* get_v(void* data)
{
        Data* d = (Data*)data;
        // 锁定数据,避免多个线程同时操作
        pthread_mutex_lock(&d->mutex);
        // 读取输入
        scanf("%d",&d->res);
        // 设置判断条件变量,使计算线程知道已经读取数据完毕
        d->is_wait = 1;
        // 等待计算线程计算完成
        pthread_cond_wait(&d->cond,&d->mutex);
        // pthread_cond_wait函数最后会将mutex再次锁住,所以这里要解锁
        pthread_mutex_unlock(&d->mutex);
        printf("res = %d",d->res);
        return (void*)NULL;
}
// 负责计算的线程函数
void* compare_v(void*data)
{
        Data* d = (Data*)data;
        // 先锁住,避免数据同时有多个线程操作
        pthread_mutex_lock(&d->mutex);
        // 判断输入线程是否已经正确读取输入
        while(d->is_wait == 0)
        {
                // 先解除锁定,给读取输入的线程机会去读取输入
                pthread_mutex_unlock(&d->mutex);
                usleep(0.1);
                // 再次锁定
                pthread_mutex_lock(&d->mutex);
        }
        // 读取数据线程成功读取,等待计算结果,下面进行计算
        int res = 0;
        for(int i = 0;i <= d->res;i++)
        {
                res += i;
        }
        d->res = res;
        // 先解除上面的锁定
        pthread_mutex_unlock(&d->mutex);
        // 通知输出线程输出数据
        pthread_cond_broadcast(&d->cond);
        return (void*)NULL;
}
  • 读者和写者
typedef struct
{
        int data;
        int write;/* 0表示不能写数据,1表示可以写数据 */
        int read;/* 0表示不能读数据,1表示可以读数据 */
        int length;
        pthread_cond_t write_cond;
        pthread_cond_t read_cond;
        pthread_mutex_t write_mutex;
        pthread_mutex_t read_mutex;
}Data;
int main(void)
{
        Data data = {0,0,1,3};
        pthread_cond_init(&data.write_cond,NULL);
        pthread_cond_init(&data.read_cond,NULL);
        pthread_mutex_init(&data.write_mutex,NULL);
        pthread_mutex_init(&data.read_mutex,NULL);
        pthread_t thread1_id,thread2_id;
        pthread_create(&thread1_id,NULL,writer,(void*)&data);
        pthread_create(&thread2_id,NULL,reader,(void*)&data);
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        return 0;
}
/* 得到reader方法通知写数据,再通知writer方法写数据,并阻塞等待reader方法读数据  */
void* writer(void* data)
{
        Data* d = (Data*)data;
        for(int i = 0;i < d->length;i++)
        {
                pthread_mutex_lock(&d->write_mutex);
                while(d->write == 0)
                {
                        pthread_mutex_unlock(&d->write_mutex);
                        usleep(0.1);
                        pthread_mutex_lock(&d->write_mutex);
                }
                printf("write %d\n",d->data);
                d->write = 0;
                d->read = 1;
                pthread_mutex_unlock(&d->write_mutex);
                pthread_cond_broadcast(&d->read_cond);
                if(i < ( d->length - 1) )
                {
                        pthread_cond_wait(&d->write_cond,&d->write_mutex);
                        pthread_mutex_unlock(&d->write_mutex);
                }
        }
        return (void*)NULL;
}
/* 读数据方法,先读数据,再通知writer方法写一个数据,并阻塞等write方法通知 */
void* reader(void* data)
{
        Data* d = (Data*)data;
        for(int i = 0;i < d->length;i++)
        {
                pthread_mutex_lock(&d->write_mutex);
                d->data = i;
                d->write = 1;
                printf("read %d\n",d->data);
                pthread_cond_broadcast(&d->write_cond);
                while(d->read == 0)
                {
                        pthread_mutex_unlock(&d->write_mutex);
                        usleep(0.1);
                        pthread_mutex_lock(&d->write_mutex);
                }
                d->read = 0;
                pthread_mutex_unlock(&d->write_mutex);
                if(i < ( d->length - 1) )
                {
                        pthread_cond_wait(&d->read_cond,&d->read_mutex);
                        pthread_mutex_unlock(&d->read_mutex);
                }
        }
        return (void*)NULL;
}

线程的同步和互斥-线程信号量

  • 信号量从本质上是一个非负整数计数器,是共享资源的数目,通常被用来控制对共享资源的访问。
  • 信号量可以实现线程的同步和互斥
  • 通过sem_post()和sem_wait()函数对信号量进行加减操作从而解决线程的同步与互斥
  • 信号量数据类型

    • sem_t

信号量的创建和销毁

int sem_init(sem_t* sem,int pshared,unsigned value);
int sem_destroy(sem_t* sem);

  • 返回:成功返回0,失败返回错误编号
  • 头文件
#include <semaphore.h>
  • 参数

    • sem

      • 信号量指针
    • pshared

      • 是否在进程间共享的标志,0为不共享,1为共享
    • value

      • 信号量的初始值

信号量的加和减操作

int sem_post(sem_t* sem);

  • 功能:增加信号量的值
    int sem_wait(sem_t* sem);
  • 功能:减少信号量的值
    int sem_trywait(sem_t* sem);
  • 功能:sem_wait的非阻塞版本
  • 返回:成功返回0,出错返回错误编号
  • 调用sem_post一次信号作加1操作
  • 调用sem_wait一次信号量作减一操作
  • 当线程调用sem_wait后,若信号量的值小于0则线程阻塞。只有在其他线程在调用sem_post对信号量作加操作之后并且其值大于或等于0时,阻塞的线程才能继续运行
  • 示例
int main(void)
{
        // 按照 c->b->a 的顺序执行
        sem_init(&sem1,0,0);
        sem_init(&sem2,0,0);
        pthread_t thread_a,thread_b,thread_c;
        pthread_create(&thread_a,NULL,a,(void*)NULL);
        pthread_create(&thread_b,NULL,b,(void*)NULL);
        pthread_create(&thread_c,NULL,c,(void*)NULL);
        pthread_join(thread_a,NULL);
        pthread_join(thread_b,NULL);
        pthread_join(thread_c,NULL);
        return 0;
}
void* a(void* data)
{
        sem_wait(&sem1);
        printf("func a\n");
        return (void*)NULL;
}
void* b(void* data)
{
        sem_wait(&sem2);
        sem_post(&sem1);
        printf("func b\n");
        return (void*)NULL;
}
void* c(void* data)
{
        sem_post(&sem2);
        printf("func c\n");
        return (void*)NULL;
}
  • PV操作-银行账户
ypedef struct
{
        int deposit;
        sem_t sem;
}Account;
int main(void)
{
        pthread_t thread1_id,thread2_id;
        Account account = {888};
        sem_init(&account.sem,0,1);
        pthread_create(&thread1_id,NULL,func1,(void*)&account);
        pthread_create(&thread2_id,NULL,func2,(void*)&account);
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        return 0;
}
void* func1(void* data)
{
        Account* a = (Account*)data;
        // P(1)
        sem_wait(&a->sem);
        if(a->deposit >= 888)
        {
                a->deposit -= 888;
        }
        // V(1)
        sleep(2);
        printf("func1; deposit = %d\n",a->deposit);
        sem_post(&a->sem);
        return (void*)NULL;
}
void* func2(void* data)
{
        Account* a = (Account*)data;
        // P(1)
        sem_wait(&a->sem);
        if(a->deposit >= 888)
        {
                a->deposit -= 888;
        }
        // V(1)
        sleep(1);
        printf("func2; deposit = %d\n",a->deposit);
        sem_post(&a->sem);
        return (void*)NULL;
}
  • 计算
typedef struct
{
        int data;
        sem_t get_sem,c_sem;
}Data;
int main(void)
{
        Data data = {1};
        sem_init(&data.get_sem,0,0);
        sem_init(&data.c_sem,0,0);
        pthread_t thread1_id,thread2_id;
        // get_v线程先读取输入,calculate_v线程计算,再由get_v线程输出
        pthread_create(&thread1_id,NULL,calculate_v,(void*)&data);
        pthread_create(&thread2_id,NULL,get_v,(void*)&data);
        pthread_join(thread1_id,NULL);
        pthread_join(thread2_id,NULL);
        return 0;
}
void* get_v(void* data)
{       
        Data* d = (Data*)data;
        scanf("%d",&d->data);
        sem_post(&d->c_sem);
        sem_wait(&d->get_sem);
        printf("data = %d\n",d->data);
        return (void*)NULL;
}
void* calculate_v(void* data)
{
        Data* d = (Data*)data;
        sem_wait(&d->c_sem);
        d->data += 8;
        sem_post(&d->get_sem);
        return (void*)NULL;
}

死锁

  • 两个线程试图同时占用两个资源,并按不同次序锁定相应的共享资源
  • 解决方式

    • 按相同的次序锁定相应的共享资源
    • 使用函数pthread_mutex_trylock,它是函数pthread_mutex_lock的非阻塞函数

线程和信号

  • 进程中每个线程都有自己的信号屏蔽字和信号未决字
  • 信号的处理方式是进程中所有线程共享的
  • 进程中的信号是传递到单个线程的
  • 定时器是进程资源,进程中所有线程共享相同的定时器

    • 子线程调用alarm函数产生的alarm信号发送给主控线程
      int pthread_sigmask(int how,const sigset_t*restrict set,sigset_t*restrict oset);
  • 功能:线程的信号屏蔽
  • 返回:成功返回0,失败返回错误编号
  • 示例
#include <stdio.h>
#include <pthread.h>
#include <signal.h>
void* func1(void*);
void* func2(void*);
void alarm_handle(int);
int main(void)
{
        pthread_t t1_id,t2_id;
        pthread_create(&t1_id,NULL,func1,(void*)NULL);
        pthread_create(&t2_id,NULL,func2,(void*)&t1_id);
        // 虽然是睡眠10s,但是子线程会发送alarm信号(SIGALRM默认给主线程处理),这时主线程会醒来继
续运行,可以在主线程中屏蔽,如下
        // 编译时加上 std=gnu99,不然会显示sigset_t类型没有定义
        sigset_t sig_set;
        sigemptyset(&sig_set);
        sigaddset(&sig_set,SIGALRM);
        // 屏蔽,当前线程不会处理
        pthread_sigmask(SIG_SETMASK,&sig_set,NULL);
        for(int i = 0;i < 10;i++)
        {
                printf("master thread i = %d;thread_id = %d\n",i,pthread_self());
                sleep(10);
        }
        pthread_join(t1_id,NULL);
        pthread_join(t2_id,NULL);
        return 0;
}
void alarm_handle(int sig)
{
        printf("I am alarm handle;threadid = %d\n",pthread_self());
        signal(SIGALRM,alarm_handle);
        alarm(2);
}
void* func1(void* data)
{
        // 在子线程中设置信号处理函数
        signal(SIGALRM,alarm_handle);
        alarm(2);
        for(int i = 0;i < 100;i++)
        {
                printf("thread1 i = %d;thread_id = %d\n",i,pthread_self());
                sleep(1);
        }
        return (void*)NULL;
}
void* func2(void* data)
{
        for(int i = 0;i < 100;i++)
        {
                if(i == 8)
                {
                        // 终止func1进程
                        pthread_cancel(*((pthread_t*)data));
                }
                printf("thread2 i = %d;thread_id = %d\n",i,pthread_self());
                sleep(1);
        }
        return (void*)NULL;
}

linux编程学习 02 进程与信号

进程

  • 程序:是存放在磁盘文件中的可执行文件
  • 进程

    • 程序的执行示例被称为进程(process)
    • 进程独立的权限和职责,如果系统中某个进程崩溃,它不会影响其余的进程。
    • 每个进程允许在气各自的虚拟地址空间中,进程之间可以通过由内核控制的机制互相通讯
  • 进程ID

    • 每个linux进程都一定有一个唯一的数字标识符,称为进程ID(process ID),进程ID总是一个非负整数
  • 每一个启动的进程都对应一个task_struct结构体
  • task_struct可以在/usr/src/kernels/2.6.32-642.13.1.el6.x86_64/include/linux/sched.h文件中查看,注意只有安装了kernel-devel包才有这个文件

c程序启动过程

  • 内核启动特殊例程
  • 启动例程

    • 在进程的main函数执行之前内核会启动
    • 该历程放置在/lib/libc.so.*
    • 编译器在编译时会将启动例程编译进可执行文件中
  • 启动例程作用

    • 搜集命令行的参数传递给main函数中的argc和argv
    • 搜集环境信息构建环境表并传递给main函数
    • 登记进程的终止函数

进程终止

  • 正常终止

    • 从main函数返回
    • 调用exit(标准c库函数)
    • 调用_exit_Exit(系统调用)
    • 最后一个线程从其启动例程返回
    • 最后一个线程调用pthread_exit
  • 异常终止

    • 调用abort
    • 接受到一个信号并终止
    • 最后一个线程对取消请求做处理响应
  • 进程返回

    • 通常程序运行成功返回0,否则返回非0
    • 在shell中可以查看进程返回值(echo $?)

atexit函数

int atexit(void (*function)(void));

  • 返回:若成功则为0,若出错则为-1
  • 功能:像内核登记终止函数
  • 头文件:
#include <stdlib.h>
  • 每个启动的进程都默认登记了一个标准的终止函数
  • 终止函数在进程终止时释放进程所占用的一些资源
  • 登记的多个终止函数执行顺序是以栈的方式执行,先登记的后执行
  • 使用_exit或_Exit退出时,不会执行终止函数

进程终止方式的区别

对比项returnexit()_exit()/_Exit()
是否刷新标准I/O缓存
是否自动调用终止函数

在centos 6.6 中,使用 _exit和_Exit会调用终止函数

ps命令

  • 可以查看到:进程的id,进程的用户id,进程状态和进程的command
  • ps aux可以查看到更多的信息
  • ps输出信息
    |列名|解释|
USER进程的属主
PID进程的ID
PPID父进程ID
%CPU进程占用的CPU时间
%MEM占用内存的百分比
NI进程的NICE值,数值大,表示较少占用CPU时间
VSZ进程的虚拟大小
RSS驻留集的大小,可以理解为内存中页的数量
TTY终端ID
WCHAN正在等待的进程资源
START启动进程的时间
TIME进程消耗CPU的时间
COMMAND命令的名称和参数

进程状态

进程常见状态

  • 运行状态

    • 系统当前进程
    • 就绪状态进程
    • ps命令的STAT列为R
  • 等待状态

    • 等待事件发生
    • 等待系统资源
    • 等待状态可分为可中断等待和不可中断等待
    • 可中断等待时ps命令的STAT列为S
    • 不可中断等待时ps命令的STAT列为D
  • 停止状态

    • ps命令的STAT列为T
  • 僵尸状态

    • 进程终止或结束
    • 在进程表项中仍有记录
    • ps命令的STAT列为Z

进程调度

  • 第一步:处理内核中的工作
  • 第二步:处理当前进程
  • 第三步:选择进程

    • 实时进程
    • 普通进程
  • 第四步:进程交换
  • task_struct中的调度信息

    • 策略

      • 轮流策略
      • 先进先出策略
    • 优先权

      • Jiffies变量
    • 实时优先权

      • 实时进程之间
    • 计数器

进程标识

pid_t getpid(void); 获得当前进程ID
pid_t getuid(void); 获得当前进程的实际用户ID
pid_t geteuid(void); 获得当前进程的有效用户ID,启动程序时使用的用户id,参照nginx
pid_t getgid(void); 获得当前进程的用户组ID
pid_t getppid(void); 获得当前进程的父进程ID
pid_t getpgrp(void); 获得当前进程所在进程组ID
pid_t getpgid(pid_t pid); 获得进程ID为pid的进程所在的进程组ID

  • 头文件
#include <unistd.h>
#include <sys/types.h>

进程创建

pid_t fork(void);
pid_t vfork(void);

  • 返回:子进程中为0,父进程中为子进程ID,出错为-1
  • fork创建的新进程被称为子进程,该函数被调用一次,但返回两次。两次返回的区别是:在子进程中的返回值是0,而在父进程中的返回值则是进进程的进程ID
  • 创建子进程,父子进程哪个先运行根据系统调度且复制父进程的内存空间
  • vfork创建子进程,但子进程先运行且不复制父进程的内存空间

子进程的继承

  • 子进程的继承属性

    • 用户的信息和权限,目录信息,信号信息,环境,共享存储段,资源限制,堆,栈和数据段,就是把父进程的信息复制一遍。但是共享代码段(复制虚拟地址,但是虚拟地址映射到同一个物理地址)。
  • 子进程特有属性

    • 进程ID,锁信息,运行时间,未决信号
  • 操作文件时的内核结构变化

    • 子进程只继承父进程的文件描述表,不继承但共享文件表项和i-node。
    • 父进程创建一个子进程后,文件表项的引用计数器加1变2,当父进程作close操作后,计数器减1,子进程还是可以使用文件表项,只有当计数器为0时才会释放文件表项
  • 实例
/**
 * 如何创建子进程
 * */
void fork_example1(void)
{
        int pid = fork();
        if(pid == -1) 
        {   
                printf("fork error\n");
        }   
        // 根据fork的返回值判断是父进程还是子进程
        if(pid > 0)
        {   
                // 父进程睡眠下,如果父进程在子进程结束之前结束,子进程ppid就为1
                sleep(1);
                printf("I am parent process,my pid is %d,my ppid is %d\n",getpid(),getppid());
        }
        else
        {   
                printf("I am child process,my pid is %d,my ppid is %d\n",getpid(),getppid());
        }           
}
/**
 * 父子进程哪个先运行由系统调度
 **/
void fork_example2(void)
{
        int pid = fork(),l = 10;
        if(pid == 0)
        {
                for(int i = 0;i < l;i++)
                {
                        sleep(1);
                        printf("parent pid => %d,ppid => %d;count => %d\n",getpid(),getppid(),i);
                }
        }
        else
        {
                for(int i = 0;i < l;i++)
                {
                        sleep(1);
                        printf("child pid => %d,ppid => %d;count => %d\n",getpid(),getppid(),i);
                }
        }
}
int a = 1;
/**
 * 子进程和父进程的虚拟地址是一样的,下面的打印可以看出,但是物理地址是不一样的
 * */
void fork_example3(void)
{
        int b = 2;
        int pid = fork();
        if(pid > 0)
        {
                printf("&a = %p;&b = %p",&a,&b);
        }
        else if(pid == 0)
        {
                printf("&a = %p;&b = %p",&a,&b);
        }
}
/**
 * io
 * */
void fork_example4(void)
{
        FILE* f1 = fopen("f1.txt","w+");
        int f2 = open("f2.txt",O_CREAT | O_WRONLY);
        // c标准函数写,这里的start在文件里面会写入两次,因为子进程会把标准的id的缓存也复制一边>,最后结束时,就会写入两次
        fprintf(f1,"start\n");
        // 系统函数写
        write(f2,"start\n",6);
        int pid = fork();
        if(pid > 0)
        {
                // c标准函数写
                fprintf(f1,"parent end\n");
                // 系统函数写
                write(f2,"parent end\n",11);
        }
        else if(pid == 0)
        {
                // c标准函数写
                fprintf(f1,"child end\n");
                // 系统函数写
                write(f2,"child end\n",10);
        }
        fclose(f1);
        close(f2);
}
void fork_example5(void)
{
        int f = open("a.txt",O_WRONLY | O_CREAT);
        int pid = fork();
        if(pid > 0)
        {
                // 主进程调整位置,子进程写入
                lseek(f,0,SEEK_END);
        }
        else
        {
                sleep(3);
                // f是主进程f的复制,所以主进程使用lseek对子进程也是有效的
                write(f,"write",5);
        }
        close(f);
}

进程链

int main(void)
{
        int pid = 0;
        for(int i = 10;i > 0;i--)
        {
                if(pid > 0)
                {
                        sleep(i);
                        printf("pid = %d;ppid = %d\n",getpid(),getppid());
                        break;
                }
                else if(pid == 0)
                {
                        pid = fork();
                }
        }
        return 0;
}

进程扇

int main(void)
{
        int pid = 0;
        for(int i = 10;i > 0;i--)
        {       
                pid = fork();
                if(pid == 0)
                {       
                        printf("pid = %d;ppid = %d\n",getpid(),getppid());
                        return 0;
                }
        }
        sleep(3);
        printf("pid = %d;ppid = %d\n",getpid(),getppid());
        return 0;
}

守护进程

  • 守护进程(deamon)是生存期长的一种进程。他们常常在系统引导装入时启动,在系统关闭时终止。
  • 所有守护进程都以超级用户(用户id为0)的优先权运行
  • 守护进程没有控制终端
  • 守护进程的父进程都是init进程

孤儿进程

  • 父进程结束,子进程就成为孤儿进程,会由1号进程(init进程)领养。

僵尸进程

  • 子进程结束但是没有完全释放内存(在内核中的task_struct没有释放),该进程就成为僵尸进程。
  • 当僵尸进程的父进程结束后就会被init进程领养。最终被回收
  • 避免僵尸进程

    • 让僵尸进程的父进程来回收,父进程每隔一段时间来查询子进程是否结束并回收,调用wait()或waitpid(),通知内存释放僵尸进程
    • 采用信号SIGCHLD通知处理,并在信号处理程序中调用wait函数
    • 让僵尸进程成为孤儿进程,有init回收
  • 实例
int main(void)
{
        int pid = fork();
        if(pid == 0)
        {
                printf("child finish\n");
                // 这里return之后子进程就成为僵尸进程了
                return 0;
        }
        while(1)
        {
                sleep(1);
        }
        return 0;
}

wait和waitpid

pid_t wait(int* status);

  • 返回:成功返回子进程id,出错返回-1
  • 功能:等待子进程推出并回收,防止僵尸进程的产生
    pid_t waitpid(pid_t pid,int* status,int options);
  • 返回:成功返回子进程id,出错返回-1
  • 功能:wait函数的非阻塞版本
  • 头文件
#include <sys/types.h>
#include <sys/wait.h>
  • wait与waitpid函数区别

    • 在一个子进程终止前,wait使其调用者阻塞
    • waitpid有一选择项,可使调用者不阻塞
    • waitpid等待一个指定的子进程,而wait则等待所有的子进程,返回任一终止子进程的状态
  • status参数

    • 为空时,代表任意状态结束的子进程,若不为空,则代表指定状态结束的子进程
  • 检查wait和waitpi函数返回终止状态的宏

    • WIFEXITED/WEXITSTATUS(status)

      • 若为正常终止子进程返回的状态,则为真
    • WIFSIGNALED/WTERMSIG(status)

      • 若为异常终止子进程返回的状态则为真(接到一个不能捕捉的信号)
    • WIFSTOPPED/WSTOPSIG(status)

      • 若为当前暂停子进程的返回的状态,则为真
  • options参数

    • WNOHANG

      • 若由pid指定的进程没有退出则立即返回,则waaitpid不阻塞,此时其返回值为0
    • WUNTRACED

      • 若某实现支持作业控制,则由pid指定的任一子进程状态已暂停,且其状态自暂停以来还未报告过,则返回其状态
  • waitpid函数的pid参数

    • pid == -1

      • 等待任一子进程,功能与wait等效
    • pid > 0

      • 等待进程id与pid相等的子进程
    • pid == 0

      • 等待其组id等于调用进程的组id的任一子进程
    • pid < -1

      • 等待其组id等于pid的绝对值得任一进程
  • 示例
void out_put(int status)
{       
        int i = 0;
        if(WIFEXITED(status))
        {       
                printf("normal exit;");
                i = WEXITSTATUS(status);
        }
        else if(WIFSIGNALED(status))
        {       
                printf("abnormal exit;");
                i = WTERMSIG(status);
        }
        else if(WIFSTOPPED(status))
        {       
                printf("stopped sig;");
                i = WSTOPSIG(status);
        }
        printf("status = %d\n",i);
}
int main(void)
{
        int pid = fork();
        int status;
        if(pid == 0)
        {
                printf("pid = %d;ppid = %d\n",getpid(),getppid());
                sleep(3);
                // 暂停
                pause();
                exit(1);
                return 11;
        }
        // 会阻塞
        // wait(&status);
        // sleep(3);
        // waitpid(pid,&status,WNOHANG);
        // 不会阻塞,
        while(0 == waitpid(pid,&status,WUNTRACED | WNOHANG))
        {

        }
        out_put(status);
        return 0;
}

exec函数

  • 在用fork函数创建子进程后,子进程往往要调用一种exec函数以执行另一个程序
  • 当进程调用一冲exec函数时,该程序完全由新程序代换,替换原有进程的正文,而新程序则从其main函数开始执行。因为调用exec并不创建新进程,所以前后的进程id并不改变。exec只是用另一个新程序替换了当前进程的正文,数据,堆和栈。
int execl(const char* pathname,const char* arg0,.../* (char*)0 */);
int execv(const char* pathname,char* const argv[]);
int execle(const char* pathname,const char* arg0,.../* (char*)0,char* const envp[] */);
int execve(const char* pathname,char* const argv[],char* const envp[]);
int execlp(const char* pathname,const char* arg0,.../* (char*)0 */);
int execvp(const char* pathname,char* const argv[]);
  • 返回:出错返回-1,成功则不返回
  • exec系列函数注意点

    • execve函数为系统调用,其余为库函数。执行execve函数后面的代码不执行
    • execlp和execvp函数中的pathname,相对路径和绝对路径均可使用,其他四个函数中的pathname只能使用绝对路径。相对路径一定要在进程环境表对应的PATH中
    • argv参数为新程序执行main函数中传递argv参数,最后一个元素为NULL
    • envp为进程的环境表
  • 六个函数都是以“exec”四个字母开头,后面的字幕代表了其用法上的区别:

    • 带有字母的“l”函数,表明后面的参数列表是要传递给程序的参数列表,参数列表的第一个参数必须是执行程序,最后一个参数必须是NULL
    • 带有字母“p”的函数,第一参数可以是相对路径或程序名,如果无法立即找到要执行的程序,那么就在环境变量PATH指定的路径中搜索。其他函数的第一个参数则必须是绝对路径名。
    • 带有字母“v”的函数,表明程序的参数列表通过一个字符串数组来传递。这个数组和最后传递给程序的main函数的字符串数组argv完全一样。第一个参数必须是程序名。最后一个参数也必须是NULL
    • 带有字母“e”的函数,用户可以自己设置程序接收一个设置环境变量的数组
  • 示例
int main(void)
{
        char command1[] = "cat",command2[] = "/bin/cat";
        char *parameters[20] = {command1,"/etc/passwd",NULL};
        int pid = fork();
        if(pid == 0)
        {       
                // 注意传递参数时,命令也要传递进去
                if(execl(command2,parameters[0],parameters[1],parameters[2]))
                // if(execvp(command1,parameters))
                {
                        perror("error\n");
                        return 1;
                }
                else
                {       
                        // 下面这个不会输出,因为子进程成功不会返回
                        printf("success\n");
                        return 0;
                }
        }
        wait(NULL);
        return 0;
}

system函数

int systemp(const char* command);

  • 返回:成功返回命令执行的状态,出错返回-1
  • 功能:简化exec函数的使用
  • 头文件
    #include <stdlib.h>
  • system函数内部构建一个子进程,由子进程调用exec函数
  • 等同于/bin/bash -c "command"或者exec("bash","-c","cmd")
  • 示例
int main(void)
{
        char* command = "date";
        // system(command);
        my_system(command);
        return 0;
}
void my_system(char* command)
{
        int pid = fork();
        if(pid == 0)
        {
                execl("/bin/bash","bash","-c",command,NULL);
                perror("error:");
        }
        wait(NULL);
}

进程状态的切换

new ---fork---> runnable <-os scheduler/timeout-> running -return/exit/_exit-> dead
         ↑                        |
         |                   read/write/sleep/pause
         |                        ↓
         ---------------------block suspend

信号

  • 信号signal机制是linux系统中最古老的进程之间的通信机制,解决进程在正常运行中被中断的问题,导致进程的处理流程会发生变化
  • 信号是软件中断
  • 信号是异步事件

    • 不可预见
    • 信号有自己的名称和编号
    • 信号和异常处理机制
  • 信号发生的来源

    • 硬件来源:比如我们按下了键盘或其他硬件故障,信号是由硬件驱动程序产生
    • 软件来源:最常用发送信号的系统函数是kill(),raise(),alarm()和setitimer()等函数,软件来源还包括一些非法运算登操作,软件设置条件(如:gdb调试),信号是由内核产生。

信号无优先级

1~31:非实时信号,发送的信号可能会丢失,不支持信号排队
31~64:实时信号,支持信号排队发送的多个实时信号都会被接收
可在/usr/include/bits/signum.h

信号的处理

进程可以通过三种方式来响应和处理一个信号

  • 忽略信号

    • SIGKILL和SIGSTOP永远不能忽略
    • 忽略硬件异常
    • 进程启动时SIGUSR1和SIGUSR2两个信号被忽略
  • 执行默认操作

    • 每个信号有默认动作大部分信号默认动作是终止进程
  • 捕获信号

    • 告诉内核出现信号时调用自己的处理函数
    • SIGKILL和SIGSTOP不能被捕获

信号变革

  • 信号出现在最早的unix系统中
  • 早期信号模型是不可靠
  • BSD和System V分别对早期信号进行扩展,但是相互不兼容
  • POSIX统一了上述两种模型,提供了可靠信号模型

SIGNAL函数

void (*signal(int signo,void (*func)(int)))(int);

  • 返回:若成功则返回先前的信号处理函数指针,出错则返回SIG_ERR
  • 功能:向内核登记信号处理函数
  • 参数

    • signo

      • 要登记的信号值,一般使用参数的宏,方便辨识
    • func

      • 信号处理函数指针
      • SIG_IGN:忽略信号
      • SIG_DFL:采用系统默认方式处理信号,执行默认操作
  • 示例
int main(void)
{
        // kill -20 pid即可看到函数被执行了
        // signal(SIGTSTP,my_signal_handle);
        // 忽略
        if(signal(SIGTSTP,SIG_IGN) == SIG_ERR)
        {
                perror("error");
        }
        for(int i = 0;i < 6;i++)
        {
                sleep(6);
                printf("for => i = %d\n",i);
        }
        return 0;
}
void my_signal_handle(int sig)
{
        printf("I am my signal handle\n;my pid is %d\nsignal number is %d\n",getpid(),sig);
}

SIGCHLD信号

  • 子进程状态发生变化(子进程结束)产生该信号,父进程需要使用wait调用来等待子进程结束并回收它
  • 避免僵尸进程
  • 示例
void my_sigchld_handle(int sig)
{
        // 当接受到信号时要调用wait函数,否则子进程会是僵尸进程
        wait(NULL);
        printf("excute wait;pid = %d\n",getpid());
}
int main(void)
{
        // 子进程结束时会执行
        signal(SIGCHLD,my_sigchld_handle);
        int pid = fork();
        if(pid > 0)
        {
                for(int i = 0;i < 66;i++)
                {
                        sleep(1);
                        printf("I am parent;pid = %d;count = %d\n",getpid(),i);
                }

        }
        else if( pid == 0 )
        {
                
                for(int i = 0;i < 6;i++)
                {
                        sleep(1);
                        printf("I am child;pid = %d;count = %d\n",getpid(),i);
                }
        }
        else
        {
                perror("fork error");
        }
        return 0;
}

信号发送

  • 除了内核和超级用户,并不是每个进程都可以向其他的进程发送信号。
  • 一般的进程只能向具有相同uid和gid的进程发送信号,或向相同进程组中的其他进程发送信号
  • 常用的发送信号的函数有kill(向其他进程发送),raise(向自己发送),alarm(定时器),settimer(定时器),abort(异常终止信号)

kill和raise函数

`int kill(pid_t pid,int signo);

  • 返回:成功返回0,出错返回-1
  • 功能:向指定的进程发送某一个信号
    `int raise(int signo);
  • 返回:成功返回0,出错返回-1
  • 功能:向进程本身发送某一个信号
  • 头文件
#include <signal.c>
  • 参数:

    • pid:接受信号进程的pid

      • pid>0:将信号发送给进程id为pid的进程
      • pid==0:将信号发送给与发送进程同一进程组的所有进程
      • pid<0:将信号发送给进程组id为pid的绝对值的所有进程
      • pid==-1:将该信号发送给发送进程有权限像他们发送信号的系统上的所有进程
    • signo:要发送的信号值
  • kill函数将信号发送给函数或进程组

    • 0为空信号,常用来检测特定进程是否存在
  • 示例
int main(void)
{
        signal(SIGUSR1,my_signal_handle);
        for(int i = 0;i < 66;i++)
        {
                // 程序直接结束
                // raise(SIGUSR1);
                kill(getpid(),SIGSTOP);
        }
        return 0;
}
void my_signal_handle(int signo)
{
        printf("I am signal handle\n");
}

定时器

unsigned int alarm(unsigned int seconds);

  • 返回:0或以前设置的定时器时间余留秒数
  • 头文件
#include <unistd.h>
  • alarm函数可设置定时器,当定时器超时,产生SIGALRM
  • 信号由内核产生,在指定的seconds秒之后,给进程本身发送一个SIGALRM信号
  • 参数为0,取消以前设置的定时器。
  • 一次性的
  • ualarm函数精确性更高
  • 示例
int main(void)
{
        signal(SIGALRM,my_sigalarm_handle);
        // 六秒后发送SIGALRM信号到本进程
        alarm(6);
        for(int i = 0;i < 66;i++)
        {
                printf("i = %d\n",i);
                sleep(1);
        }
}
void my_sigalarm_handle(int signo)
{
        printf("sigalrm signo = %d\n",signo);
        // 每隔五秒发送一次信号
        alarm(6);
        // 信号注册函数也需要重新执行下
        signal(SIGALRM,my_sigalarm_handle);
}

c多模块

多模块软件编译和链接

编译和运行过程

  • 编译和运行过程图示
    源文件(.c) === c编译器 ===> 目标文件(.o) === 连接器(linker) ===> 可执行文件

/usr/lib:              +
所有标准函数库文件        函数库
/usr/include             +
所有标准头文件。        其他目标文件
                   +
              针对不同系统的启动代码

  • 编译环境

    • 将c源程序转换为特定平台的可执行程序
    • 预处理阶段 -> 编译阶段 -> 汇编阶段 -> 链接阶段
  • 运行环境

    • 运行可执行程序的环境
  • 编译流程

    • 预处理阶段

      • gcc -E -o example.i example.c
      • 预处理指令的处理,如,将声明的头文件中的内容加到生成的.i文件中
    • 编译阶段

      • gcc -S -o example.s example.i
      • .i文件内容编译称汇编语言后生成.s文件
    • 汇编阶段

      • gcc -o example.o -c example.s
      • .s文件内容汇编成机器语言后生成.o文件
    • 链接阶段

      • gcc -o example example.o
      • .o文件链接生成可执行文件
        直接编译生成可执行程序时,中间过程产生的文件缓存在内存中

多模块编译

  • 多模块软件

    • 多数软件被分割为多个源文件,每个文件称为一个模块
  • 多模块软件的建立

    • 首先将一个大型程序根据其功能合理地划分为若干个小的源程序,每个小的源程序均以程序文件(扩展名为.c)的形式保存在磁盘上。

      • 如:一个较大的程序分解成file1.c,file2.c,file3.c...等多个源程序,各自独立地保存在磁盘上
    • 这些若干个源程序可以进行单独编译,分别形成.o目标文件
    • 最后将这个.o目标文件链接生成一个大的可执行程序
  • 多模块软件的设计思路

    • 将整个大问题化成各个小模块,再利用模块之间的联系来完成整个流程
  • 优点

    • 较小的程序文件更易于管理和维护,也就是说编辑,编译,测试和调试较小的程序文件所花的的时间更少
    • 只需编译经过修改的源文件,而不是编译整个软件系统
  • 缺点

    • 必须知道构成整个系统的所有文件,这些文件的相互依赖性(即哪些文件需要重新编译),以及生成最终可执行系统后哪些文件被修改过
    • 跟踪所有文件修改的时间戳
    • 必须键入很长的命令行来编译

静态库和共享库

  • 函数库

    • 函数库时由系统建立的具有一定功能的函数的集合。库中存放函数的名称和对应的目标代码,以及链接过程中所需的重定位信息
    • linux中标准的c函数库放置在/usr/lib下,以文件形式存放
    • 用户可以根据自己的需要建立自己的用户函数库
    • 函数库分为静态库(.a)和共享库(或称动态链接库或动态库.so)
  • 库函数

    • 存放在库函数种的函数。库函数具有明确的宫恩,入口调用参数和返回值
    • 库函数的源代码一般是不可见的,但在对应的头文件中你可以看到它对外的接口(函数原型)。
  • 静态库的概念

    • 静态库就是一些.o目标文件的集合,以.a结尾
    • 静态库在程序链接时使用,连接器会将程序中使用到的函数的代码从库文件中拷贝到可执行文件中。一旦链接完成,在执行程序的时候就不需要静态库了。
    • 由于每个使用静态库的应用程序都需要拷贝所用函数的代码,所以生成的可执行文件会比较大。
  • 静态库的创建

    • ar rcs lib库文件名.a 目标文件1 目标文件2 目标文件3 ...

      • r表示将.o的目标文件加入到静态库中
      • c表示创建静态库
      • s表示生成索引
      • 创建的库文件名字前面建议加上前缀lib,即lib库文件名.a
  • 静态库的使用

    • gcc -o 可执行文件 调用者的目标文件 -Ldir -l库文件名
    • gcc -o 可执行文件 -ldir 调用者的c源文件 -Ldir -l库文件名

      • -Ldir选项表示将制定的库文件所在目录加入到库搜索路径中,默认的库搜索路径在/usr/lib目录下
      • -lname选项(前缀lib不要加上),表示库搜索路径下的libname.alib name.so文件,这也是为什么库文件都以lib开头的原因之一,如果你的库文件不是以lib开头(如hello.a),那就不能用-l选项,而是直接写上hello.a,将原来的-lhello换成hello.a即可。
      • -l时链接器选项,必须要放到被编译和链接的文件后面
      • 删除静态库文件后不会影响到可执行文件的运行
    • 示例
-bash-4.1$ gcc -c -o obj/01_lib.o src/01_lib.c -I include
-bash-4.1$ ar rcs lib/lib01.a obj/01_lib.o 
-bash-4.1$ gcc -o bin/01 src/01.c -I include -L lib -l 01
共享库
  • 共享库的概念

    • 共享库即动态链接库,在linux中以.so(share object)为后缀,windows中以.dll为后缀
    • 共享库在程序链接时并不像静态库那样会拷贝使用函数的代码,而只是做些标记。在程序开始启动(实际上在加载程序时)运行的时候,加载所需函数
    • 可执行程序在运行时仍需要共享库的支持
    • 共享库链接出来的文件比静态库小得多
    • c语言中的所有标准的共享库放置在/usr/lib目录中
  • 共享库的创建

    • gcc -shared -fPCI -o lib库文件名.so 目标文件1 目标文件2 ...

      • -shared表示是使用共享库
      • -fpci-fPCI表明创建产生独立目标代码,具体取决于平台
  • 共享库的使用

    • gcc -o 可执行文件 调用者的目标文件 -Ldir -l库文件名
    • gcc -o 可执行文件 调用者的c源文件 -Ldir -l库文件名
    • 运行可执行文件的出错解决方案(库文件找不到)

      • cp lib hello.so /usr/lib (需root用户操作)
      • export LD_LIBRARY_PATH=库文件目录
      • 删除库文件会导致程序失效

make和makefile

  • make引入的原因

    • 一个软件工程中的源文件不计其数,其按类型,功能,模块分别放在若干个目录中,哪些文件需要首先编译,哪些文件需要后编译,哪些文件需要重新编译,甚至于更复杂的功能操作,这就需要一个工具来全面地,系统地处理
  • make和Makefile

    • linux/unix系统有一个非常强大的使用程序,称为make,可以用它来管理多模块程序的编译和链接,直至生成可执行程序
    • make使用程序读取一个说明文件,称为Makefile。Makefile文件中描述了整个软件工程的编译规则及各文件之间的依赖关系
  • Makefile就像一个shell脚本,其中也可以执行操作系统的命令。它带来的好处就是自动化编译,一旦写好,只需要一个make命令,整个软件工程完全自动编译,极大的提高了软件开发的效率
  • make时一个命令行工具,时一个解释Makefile中指令的命令工具,一般来说,大多数的IDE都有这个命令,比如:Delphi的make,Visual C++的nmake,linux下GNU的make
  • make使冲洗编译的次数最小化
  • Makefile实质上是一种脚本语言

make使用语法

make [选项] [目标] [宏定义]

常用选项特性
-d显示调试信息
-f <文件>指定从哪个文件中读取依赖关系信息。默认文件是Makefilemakefile,-表示从标准输入读取
-h显示所有选项的简要说明
-n不运行任何Makefile命令,只显示它们
-s安静的方式运行,不显示任何信息
Makefile的编写原则
  • 当make命令不带选项运行时,它从Makefile中读取制定规则
  • 当制定规则在不同于Makefile(或makefile)的其他文件中,就要运行带有-f的make命令,比如make.fray.Makefile
Makefile的编写规则一
目标列表:关联性列表
<TAB>命令列表
  • 目标列表:是用一个或多个空格分开的目标文件的清单
  • 关联性列表(也称先决条件):同样是一个或多个空格分开的目标文件,是目标列表依赖的多个目标文件的清单
  • 命令列表:用于创建目标文件的将要执行的命令清单,这些命令被换行符分开。命令列表中的每个命令必须以<tab>字符开始
Makefile的编写规则二
目标列表:关联性列表:命令列表
  • 命令列表是一系列被分号隔开的命令。一个很长的命令行要续行时可以用反斜线符号。
  • 示例
cd /home/sarwar/courses/bin;rm file1 file2\
lab2 lab3\
prog1.c prog2.c prog3.c

等同于

cd /home/sarwar/courses/bin;rm file1 file2 lab2 lab3 prog1.c prog2.c prog3.c
  • Makefile中可以使用shell中的一些通配符

    • 注释(#),连接符()
    • 关联列表和命令列表中可使用shell通配符?,*等
  • Makefile示例1
# xxxxxxxxx
#xxxxx
power:power.c
    gcc -o power power.c
    • 依赖树

      • power 依赖于 power.c
    • Makefile示例2
    power:power.o compute.o
        gcc -o power power.o compute.o
    power.o:power.c
        gcc -o power.o power.c
    compute.o:compute.c
        gcc -o compute.o compute.c
    • 依赖树

      • power依赖于power.o和compute.o
      • power.o依赖于power.c
      • compute.o依赖于compute.c
    • 示例
    # 编写makefile文件
    vim 01_makefile
    bin/01:obj/01.o obj/01_lib.o
            gcc -o bin/01 obj/01.o obj/01_lib.o -I include
    obj/01.o:src/01.c
            gcc -c -o obj/01.o src/01.c -I include
    obj/01_lib.o:src/01_lib.c
            gcc -c -o obj/01_lib.o src/01_lib.c -I include
    # 使用make编译
    -bash-4.1$ make -f 01_makefile -B
    gcc -c -o obj/01.o src/01.c -I include
    gcc -c -o obj/01_lib.o src/01_lib.c -I include
    gcc -o bin/01 obj/01.o obj/01_lib.o -I include

    make命令不加-B的话,不会重现生成在上次编译之后没有修改的文件,加上则强制重新生成

    makefile的变量的使用

    • 简单变量

      • 定义

        • 变量名:=[文本]

          • 这类变量的实质就是一组字符串
      • 添加

        • 变量名+=[文本]等价于变量名:=[文本] [文本]
    • 引用变量

      • $(变量名)
      • $单字符变量

        • 如:G:=gcc

          • $G -o power power.c
      • 示例
    builder:=gcc
    H:=-I 
    H+= include
    TARGET:=bin/01
    $(TARGET):obj/01.o obj/01_lib.o
            $(builder) -o $(TARGET) obj/01.o obj/01_lib.o
    obj/01.o:src/01.c
            $(builder) -c -o obj/01.o src/01.c $H
    obj/01_lib.o:src/01_lib.c
            $(builder) -c -o obj/01_lib.o src/01_lib.c $H
    • 内置变量

      • make中有几个内置变量,使用这些变量工作会变的更简单,常用的内建(内部)变量和它们的意义
    变量名意义
    $@当前目标的名称
    $?比当前目标更新的以修改依赖性列表
    $<依赖性列表中的第一个文件
    $^用空格分开的所有依赖性列表
    builder:=gcc
    H:=-I
    H+= include
    TARGET:=bin/01
    $(TARGET):obj/01.o obj/01_lib.o
            $(builder) -o $(TARGET) $^
    obj/01.o:src/01.c
            $(builder) -c -o $@ $< $H
    obj/01_lib.o:src/01_lib.c
            $(builder) -c -o $@ $^ $H

    虚目标

    • 不存在的文件,而且也无需创建它们
    • 允许你强制执行某些事件,而这些事件在正常规则中时不会发生的
    • 虚目标不是真正的文件,make命令可以使用针对它们的任意规则

      • 虚目标总是使与之有关的命令被执行
    常见的虚目标列表
    目标意义
    all生成工程中所有可以执行者,通常是makefile的第一个生成目标
    test允许程序的自动测试套件
    clean删除make all生成的所有文件
    install在系统目录中安装工程项目生成的可执行文件和文档
    uninstall删除make install安装的文件

    示例

    # makefile文件内容
    vim 04_makefile
    
    builder:=gcc
    H:=-I
    H+= include
    TARGET:=bin/01
    DEPEND:=obj/01.o obj/01_lib.o
    $(TARGET):$(DEPEND)
            $(builder) -o $(TARGET) $^
    obj/01.o:src/01.c
            $(builder) -c -o $@ $< $H
    obj/01_lib.o:src/01_lib.c
            $(builder) -c -o $@ $^ $H
    clean:
            rm -rf $(TARGET) $(DEPEND)
    # 执行make命令
    make -f 04_makefile clean
    • 当存在一个与虚目标相同的文件时,命令会执行不正常(如下),碰到这种情况,可以用特殊目标处理
    -bash-4.1$ make -f 04_makefile clean
    make: “clean”是最新的。
    特殊目标
    • make中有一些预定义的目标,这些预定义目标被make以一种特殊的方式进行处理,这些目标称为特殊目标
    特殊目标目的
    .DEFAULTS如果make找不到生成目标的任何makefile入口或后缀规则,它就执行与目标相关的命令
    .IGNORE如果某一行makefile包含该目标,make忽略错误代码并继续建立,如果一个命令不正常存在,make自然会停止。带有-i选项的make命令可以执行相同的任务
    .PHONY允许您制定一个不是文件的目标,所以您能指示make调用一系列makefile中的命令,即使在您的当前目录中有一个具有目标名称的文件
    .SILENTmake执行这些命令但不显示这些命令,带有-s选项的make可以执行相同的任务。如前面讨论的,该命令前防治一个@符号就可以执行一个特别命令
    .SUFFIXES为目标制定的前提(后缀)可以与后缀规则相关联。如果与目标没有相关联的前提,已存在的后缀列表就会被删除

    示例

    # 编辑makefile文件
    vim 05_makefile
    builder:=gcc
    H:=-I
    H+= include
    TARGET:=bin/01
    DEPEND:=obj/01.o obj/01_lib.o
    $(TARGET):$(DEPEND)
            $(builder) -o $(TARGET) $^
    obj/01.o:src/01.c
            $(builder) -c -o $@ $< $H
    obj/01_lib.o:src/01_lib.c
            $(builder) -c -o $@ $^ $H
    .PHONY:clean
    clean:
            rm -rf $(TARGET) $(DEPEND)
    # 执行,存在相同名字的文件也可以正常执行了
    -bash-4.1$ make -f 05_makefile clean
    rm -rf bin/01 obj/01.o obj/01_lib.o
    默认模式规则
    • make中有许多预定义的制定规则(也称为后缀规则),它可以让make自动执行许多任务。
    • make中已经内建许多其他语言的规则和unix实用程序(包括SCCS,PCS,ar,lex和yacc)的规划。
    • 为了建立一个目标,make会遍历一遍依赖关系,这是为了决定从何处开始建立(或重建)。如果没有找到目标文件,make就按照优先顺序查找源文件。
    • 为了生成目标文件,它首先查找带.c,.f.s后缀的文件,如果一个都没找到,他会继续寻找带.c后缀的文件并继续搜索,直到找到一个源文件。如果没有找到一个源文件,make就会报告一个异常。
    • 默认的规则(GNU make)
    %.o:%.c:
        $(CC) $(CFLAGS) -c $<
    %.o:%.s
        $(AS) $(ASFLAGS) -o $@ $<
    • 默认的后缀规则
    SUFFIXES:.o.c.s
    .c.o:
        $(CC) $(CFLAGS) -c $<
    .s.o:
        $(AS) $(ASFLAGS) -o $@ $<
    • 示例
    builder:=gcc
    H:=-I
    H+= include
    TARGET:=bin/01
    DEPEND:=obj/01.o obj/01_lib.o
    $(TARGET):$(DEPEND)
            $(builder) -o $(TARGET) $^
    # 这两条条就相当于下面的四条
    obj/%.o:src/%.c
            $(builder) -c -o $@ $< $H
    #obj/01.o:src/01.c
    #       $(builder) -c -o $@ $< $H
    #obj/01_lib.o:src/01_lib.c
    #       $(builder) -c -o $@ $^ $H
    .PHONY:clean
    clean:
            rm -rf $(TARGET) $(DEPEND)

    c数据结构学习

    数据的逻辑结构

    根据数据元素间的基本特性,有四种基本数据结构

    类型特性
    集合数据元素间除“同属于同一集合”外,无其他关系
    线性结构一个对一个,如线性表,栈,队列
    树形结构一个对多个
    图状结构多个对多个

    线性结构的特点

    • 一对一的关系
    • 除了第一个和最后一个元素外,数据中的每一个元素都有且只有一个直接前驱和一个直接后继

    树形结构的特点

    • 一对多的关系
    • 有且只有一个特定的称为根(root)的数据元素(节点)
    • 在树形结构中,树根节点没有前驱元素,其余的每个节点有且只有一个前驱元素。末端元素没有后续的元素,其余的每个元素的后续元素个数可以是一个也可以是多个

    图状结构的特点

    • 多对多的关系
    • 任意的两个元素都可能相关,即图中的任一元素可以有若干个直接前驱和直接后继,属于网状结构类型

    逻辑结构

    表示数据元素之间的抽象关系(如邻接关系,从属关系等),按每个元素可能具有的直接前驱数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。它是从具体问题中抽象出来的数学模型,是独立于计算机存储器(与机器无关)。


    数据的存储结构思想

    无论数据的逻辑结构是怎样的,它都需要参与各种运算,那就需要将这些数据元素他原本的逻辑关系进行保存,存储于计算机的存储器中(内存)。存储结构是通过计算机语言所编制的程序来实现的故而是依赖于具体的计算机语言的。

    顺序存储

    将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中(如c语言的数据)
    如表L = (a1,a2,a3...)顺序结构

    链式存储

    将数据结构中各元素分布到存储器的不同点,用地址(或链指针)方式建立他们之间的联系,由此得到的存储结构为链式存储结构
    如表L = (a1,a2,a3...)顺序结构
    链式存储结构是数据结构的一个重点,因为数据结构元素的关系在计算机内部很大程序上是通过地址或指针建立的

    索引存储

    在存储数据的同时,建立一个附加的索引表,即索引存储结构=数据文件+索引表
    电话号码查询问题:为便于提高查询速度,在存储用户数据文件的同时,建立一张姓氏索引表

    散列存储

    散列技术是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
    散列法存储的基本思想是:由节点的关键码决定节点的存储位置。散列技术除了可以用于查找外,还可以用于存储
    散列是数组存储方式的一种发展,相比数组,散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数据在数组中的存储位置,进而能够快速实现数据的访问,理想的散列访问速度是非常迅速的。


    算法

    算法是一个有穷规则(或语句,指令)的有序集合
    它确定了解决某一问题的一个运算序列。对于问题的初始输入,通过算法有限步的运行,产生一个或多个输出

    算法的特点

    • 有穷性:算法的执行步骤是有限的
    • 确定性:每个计算步骤无二义性
    • 可行性:每个计算步骤能够在有限的时间内完成
    • 输入:算法有一个或多个外部输出
      要说明的是,算法与程序既有联系又有区别。二者都是为了完成某个任务,或解决某个问题而编制的规则(或语句)的有序集合,这是他们的共同点。区别在于:其一,算法与计算机无关,但程序依赖于具体的计算机语言。其二,算法必须是有穷尽的,但程序可能是无穷尽的。其三,算法可能忽略一些语法细节问题,重点放在解决问题的思路上,但程序必须严格遵循相应语言工具的语法。算法转换成程序后才能在计算机上运行。

    数据结构是研究从具体问题中抽象出来的数学模型如何在计算机存储器中表示出来;而算法研究的是对数据处理的步骤。如果对问题的数据表示和数据处理都作出了具体的设计,就相当于完成了相应的程序。

    算法分析

    词句的频度

    词句频度定义为可执行语句在算法(或程序)中重复执行的次数,若某语句执行一次时间为t,执行次数为f则该语句所耗时间估计为t*f
    示例

    float A[n][n],B[n][n],C[n][n];
    int j,j,k;
    for(i = 0;i < n;i++) // n + 1
    {
            for(j = 0;j < n;j++) // n * (n + 1)
            {
                    C[n][n] = 0; // n * n
                    for(k = 0;k < n;k++) // n * n * (n + 1)
                    {
                            C[i][j] = C[i][j] + A[i][j] * C[i][j]; // n * n * n
                    }
            }
    }

    时间复杂度

    算法的时间复杂度定义为可执行语句的频度之和,记为T(n)T(n)是算法所需时间的一种估计,其中n为问题的规模(或大小,体积)。

    空间复杂度

    设算法对应问题的体积(或规模)为n,执行算法所占存储空间的量为D(n),则D(n)为算法的空间复杂度

    算法效能度量

    • 算法效率:用依据该算法编制的程序在计算机上执行所消耗的时间来度量。用字母“O”表示其数量级的概念
    • 算法中基本操作重复执行的次数是问题规模n的某个函数f(n)

    线性表

    • 定义:线性表是信息表的一种形式,表中数据元素之间满足线性逻辑关系(或线性结构),是一种最基本,最简单的数据结构类型
    • 线性表(Linear List)是包含若干数据元素的一个线性序列,记为:L=(a0,...ai-1,ai,ai+1,...an-1)

      • 其中:L为表面,ai(0 <= i <= n-1)为数据元素,n为表长,n大于0时,线性表L为非空表,否则为空表。线性表L可用二元组形式描述:L=(D,R)
      • 即线性表L包含数据元素集合D和关系集合R。
    • 线性表的特征:对非空表,a0是表头,无前驱;an-1是表尾,无后继;其他元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)
    • 运算:设线性表L=(a0,a1,...an-1)

      • 建立一个空表:CreateList(L);
      • 置空表:ClearList(L);
      • 判断表是否为空:EmptyList(L);,如表为空,返回true,否则返回false
      • 求表长:LengthList(L);
      • 取表中某个元素:GetList(L,i);,即ai。要求0 <= i <= length(L) - 1
      • 定位运算:LocateList(L,x);,确定元素x在表L中的位置(或序号)
      • 插入:InsertList(L,x,i);,将元素x插入表L中的第i个元素ai之前,切表长加1
      • 删除:DeleteList(L,i);删除表L中第i个元素ai,且表长减1,要求0 <= i <= n-1
      • 其他:合并,拆分,复制,排序,遍历等

    线性表的存储

    线性表作为一种基本数据类型结构,在计算机存储器中的映像(或表示)一般有两种形式,一种是顺序映像,一个是链式映像
    线性表的存储结构

    • 若将线性表中的各元素依次存储于计算机一片连续的空间。这种为线性表的顺序存储结构。

      • 逻辑上相邻的元素,存储位置上也是相邻的
      • 对数据元素ai的存取为随机存取或按地址存取
      • 存储密度高。存储密度D=(数据结构中元素所占的存储空间)/(整个数据结构所占空间)
    • 顺序存储结构的不足

      • 对表的插入和删除等运算的时间复杂度较差
        子c语言中,一维数组的元素也是存放在一片连续的存储空间中,故可借助c语言中一维数组类型来描述线性表的顺序存储结构,即
    #define MAX               // 线性表的最大长度
    typedef struct{           // 表的类型
        datatype data[MAX];   // 表的存储空间
        int last;             // 当前表尾指针
    }sqlist;*sqlink;          // 表说明符

    如说明sqlink L;L = (sqlink)malloc(sizeof(sqlist))
    关于线性表的运算,有些实现起来是相当简单的

    • 置空表

      • ClearList(L),令L->last=-1
    • 取表元素

      • GetList(L,i),取L->data[i]的值
    • 求表长

      • Length(L),取L->last之值加1即可
        示例
    #include <stdio.h>
    #include <malloc.h>
    #include <string.h>
    #include "01_lib.h"
    #define MAX 20
    typedef struct{
            int data[MAX];
            int last;
    }sqlist;
    typedef sqlist* sqlink;
    sqlink CreateList(void)
    {       
            sqlink l = (sqlink)realloc(NULL,sizeof(sqlist));
            l->last = -1;
            memset(l->data,0,MAX);
            return l;
    }
    int Length(sqlink L)
    {       
            return L->last + 1;
    }
    void ClearList(sqlink L)
    {       
            free(L);
    }
    int EmptyList(sqlink L)
    {       
            return L->last == -1;
    }
    int FullList(sqlink L)
    {       
            return L->last == (MAX - 1);
    }
    int GetList(sqlink L,int index)
    {       
            if(index >= 1 || index <= (L->last + 1))
            {       
                    return L->data[index - 1];
            }
            return -1;
    }
    int LocateList(sqlink L,int value)
    {       
            if(EmptyList(L))
            {       
                    return -1;
            }
            for(int i = 0;i <= L->last;i++)
            {       
                    if(L->data[i] == value)
                    {       
                            return i + 1;
                    }
            }
            return -1;
    }
    void InsertList(sqlink L,int value,int index)
    {       
            if(EmptyList(L) || FullList(L) || index - 1 > L->last)
            {       
                    return;
            }
            for(int i = index - 1;i <= L->last;i++)
            {       
                    L->data[i + 1] = L->data[i];
            }
            L->data[index - 1] = value;
            L->last++;
    }
    void DeleteList(sqlink L,int index)
    {
            if(EmptyList(L) || FullList(L) || index - 1 > L->last)
            {   
                    return;
            }   
            for(int i = index - 1;i < L->last;i++)
            {   
                    L->data[i] = L->data[i + 1]; 
            }   
            L->last--;
    }
    void PushList(sqlink L,int value)
    {
            if(FullList(L))
            {   
                    return;
            }   
            L->data[++L->last] = value;
    
    }
    void PrintList(sqlink L)
    {
            for(int i = 0;i <= L->last;i++)
            {   
                    printf("data[%d] = %d\n",i,L->data[i]);
            }   
    }

    单向链表

    将线性链表L=(a<sub>0</sub>,a<sub>1</sub>,...,a<sub>n-1</sub>)中各元素分布在存储器的不同存储块,称为节点,通过地址或指针建立他们之间的联系,所得到的存储结构为链表结构

    • 其中元素ai的节点有由datanext两部分组成
    • 其中,节点的data域存放元素ai,而next域是一个指针,指向ai的直接后继ai + 1所在的节点。于是,线性表L=(a0,a1,...,an-1)的结构
    • 示例
    #include "03_lib.h"
    #include <malloc.h>
    int empty(sqlink* L)
    {       
            if(*L == NULL)
            {       
                    return 0;
            }
            return 1;
    }
    sqlink* CreateList(void)
    {       
            sqlink* L = (sqlink*)malloc(sizeof(sqlink));
            *L = NULL;
            return L;
    }
    int Length(sqlink* L)
    {       
            if(empty(L) == 0)
            {       
                    return 0;
            }
            int length = 0;
            sqlink l = *L;
            while(l->next != NULL)
            {       
                    length++;
            }
            return length;
    }
    void freeList(sqlink L)
    {
            if(L->next != NULL)
            {
                    freeList(L->next);
            }
            free(L);
    }
    void ClearList(sqlink* L)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            freeList(*L);
    }
    int GetList(sqlink* L,int index)
    {
            if(empty(L) == 0)
            {
                    return -1;
            }
            index--;
            int i = 0;
            sqlink l = *L;
            while(l->next != NULL)
            {
                    if(i == index)
                    {
                            return l->data;
                    }
                    l = l->next;
                    i++;
            }
            return -1;
    }
    int LocateList(sqlink* L,int value)
    {
            if(empty(L) == 0)
            {
                    return -1;
            }
            int i = 1;
            sqlink l = *L;
            while(l->next != NULL);
            {
                    if(l->data == value)
                    {
                            return i;
                    }
                    i++;
            }
            return -1;
    }
    void PushList(sqlink* L,int value)
    {
            if(empty(L) == 0)
            {
                    *L = (sqlink)malloc(sizeof(sqlist));
                    (*L)->data = value;
                    (*L)->next = NULL;
                    return;
            }
            sqlink l = *L;
            while(1)
            {
                    if(l->next == NULL)
                    {
                            l->next = (sqlink)malloc(sizeof(sqlist));
                            l->next->data = value;
                            l->next->next = NULL;
                            return;
                    }
                    l = l->next;
            }
    }
    void InsertList(sqlink* L,int value,int index)
    {
            sqlink l = NULL;
            if(index == 1)
            {
                    l = (sqlink)malloc(sizeof(sqlist));
                    l->data = value;
                    l->next = *L;
                    *L = l;
                    return;
            }
            int i = 1;
            sqlink l1 = *L;
            do{
                    if(index == (i + 1))
                    {
                            l = (sqlink)malloc(sizeof(sqlist));
                            l->data = value;
                            l->next = l1->next;
                            l1->next = l;
                            return;
                    }
                    i++;
                    l1 = l1->next;
            }
            while(l1->next != NULL);
    }
    void DeleteList(sqlink* L,int index)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            sqlink l = NULL;
            if(index == 1)
            {
                    l = (*L)->next;
                    free(*L);
                    *L = l;
                    return;
            }
            l = *L;
            int i = 1;
            while(l->next != NULL)
            {
                    if(i == (index - 1))
                    {
                            sqlink temp = l->next->next;
                            free(l->next);
                            l->next = temp;
                    }
                    i++;
            }
    }
    void PrintList(sqlink* L)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            sqlink l = *L;
            int i = 1;
            do
            {
                    printf("data[%d] = %d\n",i,l->data);
                    l = l->next;
                    i++;
            }
            while(l != NULL);
    }
    void reverse(sqlink* L)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            sqlink l = *L,reverse = NULL,last = *L,temp;
            do{
                    temp = l;
                    l = l->next;
                    if(reverse == NULL)
                    {
                            reverse = temp;
                    }
                    else
                    {
                            temp->next = reverse;
                            reverse = temp;
                    }
            }
            while(l != NULL);
            *L = reverse;
            last->next = NULL;
    }
    void merge(sqlink * L_left,sqlink * L_right)
    {
            if(empty(L_left) == 0 || empty(L_right) == 0)
            {
                    return;
            }
            sqlink l = *L_left;
            while(l != NULL)
            {
                    if(l->next == NULL)
                    {
                            l->next = *L_right;
                    }
                    l = l->next;
            }
            *L_right = *L_left;
    }
    • 约瑟夫环
    #include <stdio.h>
    #include <malloc.h>
    struct node
    {       
            int data;
            struct node* pre;
            struct node* next;
    };
    void Joseph_problem(int i,int j,int k);
    int main(void)
    {       
            Joseph_problem(7,2,3);
            return 0;
    }
    void Joseph_problem(int i,int j,int k)
    {
            struct node* L = NULL,* l = NULL;
            int a = 1;
            for(;a <= i;a++)
            {
                    if(L == NULL)
                    {
                            L = (struct node*)malloc(sizeof(struct node));
                            L->data = a;
                            l = L;
                    }
                    else
                    {
                            l->next = (struct node*)malloc(sizeof(struct node));
                            l->next->data = a;
                            l->next->pre = l;
                            l = l->next;
                    }
            }
            L->pre = l;
            l->next = L;
            l = L;
            for(a = 1;a <= j;a++)
            {
                    l = l->next;
            }
            a = 1;
            struct node* temp;
            while(L->next != L)
            {
                    if(k == a)
                    {
                            temp = L->next;
                            L->next = L->next->next;
                            L->next->pre = L;
                            printf("%d\n",temp->data);
                            free(temp);
                            a = 1;
                    }
                    else
                    {
                            a++;
                    }
                    L = L->next;
            }
            printf("%d\n",L->data);
            free(L);
    }

    • 定义:栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许操作的一端称为栈顶,另一端固定称为栈底,当栈中没有元素时称为空栈。
    • 特点:后进先出
    • 由于栈也是线性逻辑结构,因此线性表的存储结构对栈也适用,通常栈有顺序链和链栈两种存储结构,这两种存储结构的不同,则实现栈的基本运算的算法也不同。
    • 运算:设S=(a0,a1,...,an-1)

      • 构造空栈:InitStack(S);
      • 设置空栈:SetEmpty(S);
      • 判断是否是空栈:IsEmpty(S);
      • 元素进栈:StackPush(S,x);,可形象的理解为压入,这时栈中会多一个元素
      • 元素出栈:StackPop(S);,可形象的理解为弹出,弹出后栈中就无此元素了
      • 读取栈顶元素:ShowTop(S);,不同与弹出,只是使用栈顶元素的值,该元素仍在栈顶不会改变
    • 顺序存储
    typedef struct node{
            int* data;
            int top;
    } node,* nodep;
    nodep InitStack(void)
    {
            nodep p = malloc(sizeof(node));
            p->top = -1;
            p->data = NULL;
            return p;
    }
    void SetEmpty(nodep p)
    {
            free(p->data);
            p->top = -1;
            p->data = NULL;
    }
    int IsEmpty(nodep p)
    {
            if(p->top == -1)
            {
                    return 1;
            }
            else
            {
                    return 0;
            }
    }
    void StackPush(nodep p,int data)
    {
            p->data = realloc(p->data,sizeof(int) * (++p->top + 1));
            p->data[p->top] = data;
    }
    int StackPop(nodep p)
    {
            if(1 == IsEmpty(p))
            {
                    return 0;
            }
            int data = ShowTop(p);
            p->data = realloc(p->data,sizeof(int) * p->top--);
            if(p->top == -1)
            {
                    p->data = NULL;
            }
            return data;
    }
    int ShowTop(nodep p)
    {
            if(1 == IsEmpty(p))
            {
                    return 0;
            }
            return p->data[p->top];
    }
    • 链表存储
    typedef struct node{
            int data;
            struct node* next;
    } node,* nodep;
    nodep* InitStack(void)
    {
            nodep* p = (nodep*)malloc(sizeof(nodep));
            *p = NULL;
            return p;
    }
    void freeNode(nodep p)
    {
            if(p->next != NULL)
            {
                    freeNode(p->next);
            }
            free(p);
    }
    void SetEmpty(nodep* p)
    {
            if(IsEmpty(p) == 1)
            {
                    return;
            }
            freeNode(*p);
    }
    int IsEmpty(nodep* p)
    {
            if(*p == NULL)
            {
                    return 1;
            }
            return 0;
    }
    void StackPush(nodep* p,int data)
    {
            nodep temp = (nodep)malloc(sizeof(node));
            temp->data = data;
            temp->next = *p;
            *p = temp;
    }
    int StackPop(nodep* p)
    {
            if(IsEmpty(p) == 1)
            {
                    return 0;
            }
            int data = (*p)->data;
            nodep temp = *p;
            *p = (*p)->next;
            free(temp);
            return data;
    }
    int ShowTop(nodep* p)
    {
            if(IsEmpty(p) == 1)
            {
                    return 0;
            }
            return (*p)->data;
    

    队列

    • 定义:队列也是一种运算受限的线性表,它的运算限制与栈不同,是两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进),允许删除的一端成为队头(Front),允许插入的一端称为队尾(rear),当线性表中没有队尾时,称为空队。
    • 特点:先进先出
    • 常用基本运算

      • 置空队:SetEmpty(Q);
      • 判断空队:IsEmpty(Q);
      • 判断满队:IsFull(Q);
      • 入队:PushQueue(Q,x)
      • 出队:OutQueue(Q);
      • 取队头:ShowFront(Q);

    队列顺序存储结构

    顺序队列是线性逻辑结构顺序存储的一种,具有和顺序表一样的存储结构,由数组定义,配合用数组下标表示的对头指针和队尾指针(相对指针)完成各种操作

    • 规定:头指针front总是指向队头元素的第一个位置,尾指针rear总是指向队尾元素所在位置的下一个位置
    • 在队列操作过程中,为了提高效率,以调整指针代替队列元素的移动,并将数组作为循环队列的操作空间
    • 为区别空队和满队,尾指针rear指向的位置必须为空,满队元素个数比数组元素个数少一个。
    • 实例
    typedef struct queue
    {
            int data[MAX_SIZE];
            int front;
            int rear;
    }queue,* queuep;
    queuep InitQueue(void)
    {
            queuep q = (queuep)malloc(sizeof(queue));
            SetEmpty(q);
            return q;
    }
    int IsEmpty(queuep q)
    {
            return (q->front == q->rear) ? 1 : 0;
    }
    void SetEmpty(queuep q)
    {
            q->front = 0;
            q->rear = 0;
    }
    int IsFull(queuep q)
    {
            return (((q->rear + 1) % MAX_SIZE) == q->front) ? 1 : 0;
    }
    void PushQueue(queuep q,int v)
    {
            if(IsFull(q) == 1)
            {
                    return;
            }
            q->data[q->rear] = v;
            q->rear = (q->rear + 1) % MAX_SIZE;
    }
    int OutQueue(queuep q)
    {
            if(IsEmpty(q) == 1)
            {
                    return -1;
            }
            int temp = q->data[q->front];
            q->front = (q->front + 1) % MAX_SIZE;
            return temp;
    }
    int ShowFront(queuep q)
    {
            if(IsEmpty(q) == 1)
            {
                    return -1;
            }
            return q->data[q->front];
    }

    链式存储

    • 在c语言中,不能用静态分配的一维数组来实现循环队列,若使用循环队列,必须设置最大队列长度,若无法估计最大长度,就使用链式队列。
    • 插入操作在队尾进行,删除操作在队头进行,由队头指针和队尾指针控制队列的操作
    typedef struct node
    {
            int data;
            struct node* next;
    }node,* nodep;
    typedef struct queue
    {
            nodep front;
            nodep rear;
    }queue,* queuep;
    queuep InitQueue(void)
    {
            queuep q = (queuep)malloc(sizeof(queue));
            q->front = NULL;
            q->rear = NULL;
            return q;
    }
    int IsEmpty(queuep q)
    {
            return (q->front == NULL) ? 1 : 0;
    }
    void SetEmpty(queuep q)
    {
            nodep n = q->front,temp = NULL;
            while(n != NULL)
            {
                    temp = n;
                    n = n->next;
                    free(temp);
            }
            q->front = NULL;
            q->rear = NULL;
    }
    int IsFull(queuep q)
    {
            return 0;
    }
    void PushQueue(queuep q,int v)
    {
            if(q->rear == NULL)
            {
                    q->rear = (nodep)malloc(sizeof(node));
                    q->front = q->rear;
                    q->rear->next = NULL;
            }
            else
            {
                    q->rear->next = (nodep)malloc(sizeof(node));
                    q->rear->next->next = NULL;
                    q->rear = q->rear->next;
            }
            q->rear->data = v;
    }
    int OutQueue(queuep q)
    {
            if(IsEmpty(q) == 1)
            {
                    return -1;
            }
            int n = q->front->data;
            nodep temp = q->front;
            q->front = q->front->next;
            if(q->front == NULL)
            {
                    q->rear = NULL;
            }
            free(temp);
            return n;
    }
    int ShowFront(queuep q)
    {
            if(IsEmpty(q) == 1)
            {
                    return -1;
            }
            return q->front->data;
    }

    • 树(Tree)是n(n>=0)个节点的有限集合,可记为T,满足两个条件

      • 有且只有一个特定的称为根(Root)的节点
      • 其余的节点可以分为m(m>=0)个互不相交的有限集合T1,T2...Tm,其中每一个集合又是一个树并称为其根的子树
    • 表示方法:树形表示法,目录表示法
    • 特点:仅有一个根节点,节点间有明显的层次关系

    树的基本术语

    • 一个节点的子树的个数称为该节点的度数,一棵树的度数是指该树中节点的最大度数
    • 度数为0的节点称为树叶或终端节点,度数不为0的节点称为分支节点,除根节点之外的节点称为内部节点
    • 一个节点的子树的节点称为该节点的子节点,该节点称为他们的父节点,同一节点的各个子节点之间称为兄弟节点。一个数的根节点没有父节点,叶节点没有子节点
    • 节点的层数等于父节点的层数加1,根节点的层数定义为1。树中节点层数的最大值称为该树的高度或深度
    • 一个节点k1,k2,...ki,ki+1,...,kj并满足ki是ki+1的父节点,就称为一条从k1到kj的路径,路径的长度为j-1,即路径的边数。路径总前面的节点是后面的节点的祖先,后面节点是前面节点的子孙
    • 若树中每个节点的各个子树的排列为从左到右,不能交换,即兄弟之间是有序的,则称该树为有序树,一般的树是有序树
    • m(m>=0)颗互不相交的树的集合,称为森林。树去掉根节点就成为森林,森林加上一个新的根节点就称为树

    树的逻辑结构

    树中任何节点都可以有零个或多个直接后继节点(子节点),但至多只有一个直接前驱节点(父节点),根节点没有前驱结点,叶节点没有后继节点。

    树的存储结构

    树的存储结构可以采用具有多个指针域的多重链表,节点中指针域的个数应由树的度来决定。在实际应用中,这种存储结构很不方便,一般将树转化为二叉树表示法进行处理

    二叉树

    • 二叉树是一种重要的树形结构。是由n(n>=0)个节点组成的有限集合,他或者是空集(n=0),或者是由一个根节点以及两颗互不相交的,分别称为左子树和右子树的二叉树组成
    • 二叉树与普通有序树不同,二叉树严格区分左孩子和右孩子,即使只有一个子节点也要区分左右,左右次序不能颠倒。
    • 基本形态:

      • 要点:二叉树结点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确的指出该子树是左子树还是右子树
    • 二叉树的性质

      • 二叉树第i(i>=1)层上的节点最多2i-1
      • 深度为k(k>=1)的二叉树最多有2k-1个节点
      • 在任意一颗二叉树中,叶子数(度数为0)=度数为2的节点数 + 1
    • 二叉树的形式

      • 满二叉树:深度为k(k>=1)且有2k-1个节点的二叉树
      • 完全二叉树:只有最下面两层有度数小于2的节点,且最下面一层的叶节点集中在最左边的若干位置上。

        • 具有n个节点的完全二叉树的深度为(log2n)+1或log2(n+1)

    二叉树存储结构

    • 顺序存储结构

      • 完全二叉树节点的编号方法是从上到下,从左到右,根节点为一号节点
      • 有n个节点的完全二叉树可以用有n+1个元素的数组进行顺序存储,节点号和数组下标一一对应,下表为0的元素不用
      • 利用以上特性,可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚结点构成完全二叉树,然后用数组存储,还要浪费一些存储空间
      • 一般二叉树必须转换成完全二叉树的形式存储,将造成存储的浪费
      • 若父节点在数组中i下标处,其左孩子在2i处,右孩子在2i-1处
    • 链式存储结构

      • 每个节点由数据域,左指针域和右指针域组成
    typedef struct BiTNode
    {
        int data;
        struct BiTNode *lchilde,*rchild;
    }BiTNode,* BiTree;

    二叉树遍历

    • 沿着某条搜索路径周游二叉树,对树中的每一个节点访问一次且仅访问一次
    • 是任何类型均有的操作,对线性结构而言,只有一条搜索路径(因为每个节点均只有一个后继),故不需要另加讨论。而二叉树是非线性结构,每个节点有两个后继,则存在如何遍历即按什么样的搜索路径进行遍历的问题。
    • 查找某个节点,或对二叉树中全部节点进行某种处理,就需要遍历
    • 由于二叉树的递归性质,遍历算法将采用递归方式
    • 三种基本的遍历方法如下

      • 先上(根)后下(子树)的按层次遍历
      • 先左(子树)后(子树)的遍历
      • 先右(子树)后左(子树)的遍历
    • 遍历的算法

      • 前序遍历(D L R)

        • 访问跟节点,按先序遍历左子树,按先序访问右子树
      • 中序遍历(L D R)

        • 按中序遍历左子树,访问根节点,按中序遍历右子树
      • 后序遍历(L R D)

        • 按后序遍历左子树,按后序遍历右子树,访问根节点
        • 二叉树为空时,执行空操作,即空二叉树已遍历完
    • 实例
    typedef struct BiTNode{
            int data;
            struct BiTNode *l,*r;
    }BiTNode,* BiTree;
    BiTree create(void)
    {
            BiTree tree = NULL;
            char c;
            if((c = fgetc(stdin)) != '#' && c != '\n')
            {
                    tree = (BiTree)malloc(sizeof(BiTNode));
                    tree->data = c;
                    tree->l = create();
                    tree->r = create();
            }
            return tree;
    }
    // 前序
    void PerOrder(BiTree tree)
    {
            printf("%c",tree->data);
            if(tree->l != NULL)
            {
                    PerOrder(tree->l);
            }
            if(tree->r != NULL)
            {
                    PerOrder(tree->r);
            }
    }
    // 中序
    void InOrder(BiTree tree)
    {
            if(tree->l != NULL)
            {
                    InOrder(tree->l);
            }
            printf("%c",tree->data);
            if(tree->r != NULL)
            {
                    InOrder(tree->r);
            }
    }
    // 后序
    void PostOrder(BiTree tree)
    {
            if(tree->l != NULL)
            {
                    PostOrder(tree->l);
            }
            if(tree->r != NULL)
            {
                    PostOrder(tree->r);
            }
            printf("%c",tree->data);
    }

    排序

    • 将无序的记录序列调整成有序的序列
    • 对记录进行排序有着重要的意义。如果记录按key有序,可对其折半查找,使查找效率提高;在数据库(Data Base)和文件库(File Base)等系统中,一般要建立若干索引文件(记录),就涉及到排序问题;在一些计算机的应用系统中,要按不同的数据做出若干统计,也涉及到排序。排序效率的高低,直接影响到计算机的工作效率。
    • 设有n个记录文件f=(R1,R2,...,Rn),相应记录关键字(key)集合k={k1,k2,...,kn},若对1,2,3,...,n的一种排列
      P(1) P2 P3 (1 <= P(i) <= n,i!=j时,Pi!=Pj)

    有:KP(1) <= KP(2) <= ... <= KP(n) 递增
    有:KP(1) >= KP(2) >= ... >= KP(n) 递减
    则使f按key线性有序:(Rp(1) Rp(2) ... Rp(n)),称这种运算为排序(或分类),关系符"<="和">="并不一定是数学意义上的"小于等于"或者"大于等于",而是一种次序关系。但为了讨论问题方便,取整型数作为key,故"<="和">="可以看作通常意义上的符号

    • 稳定排序和非稳定排序
      设文件f=(R1,R2,...,Ri,...,Rj,...,Rn)中记录Ri Rj(i!=j,i=1...n)的key相等,即Ri=Rj,若在排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称这种排序是稳定的,其含义是没有破坏原本已有序的次序。反之,若排序后Ri和Rj的次序有可能颠倒,则这种排序是非稳定的,即他有可能破坏了原本以有序记录的次序
    • 内排序和外排序
      若待排文件f在计算机的内部存储器中,且排序过程也在内存中进行,称这种排序为内排序,内排序速度快,但由于内存容量一般很小,文件的长度(记录个数)n受到一定限制。若排序中的文件存入外存储器,排序过程借助于内外数据交换(或归并)来完成,则称这种排序为外排序
    • 内排序的分类

      • 交换法排序

        • 冒泡排序
        • 快速排序
      • 插入法排序

        • 直插排序
      • 选择法排序
      • 归并法排序
    • 排序的对象

      • 顺序结构:类似线性表的顺序存储,将文件f=(R1,R2,...,Rn)存于一片连续的存储空间,逻辑上相连的存储记录在存储器中的物理位置也是相邻的,在这种结构上对文件进行排序,一般要作记录的移动。当发生成片记录移动时,是一个非常耗时的工作
      • 链表结构:类似于线性表的链式存储,文件中记录用节点来表示,其物理位置随意,节点之间用指针相连,链表的优点在于排序时无需移动记录,只需修改相应记录的指针即可
    • 交换法-冒泡排序
      外层循环决
    void sort1(sqlink* L)
    {
            int length = Length(L);
            sqlink i_temp = NULL;
            for(int i = 0;i < length - 1;i++)
            {
                    i_temp = *L;
                    // while(l->next != NULL)
                    for(int j = 0;j < length - i - 1;j++)
                    {       
                            //printf("%d\n",j);
                            if(i_temp->data < i_temp->next->data)
                            {       
                                    if(i_temp->pre != NULL)
                                    {
                                            i_temp->pre->next = i_temp->next;
                                    }
                                    if(i_temp->next->next != NULL)
                                    {
                                            i_temp->next->next->pre = i_temp;
                                    }
                                    i_temp->pre = i_temp->next;
                                    i_temp->next = i_temp->next->next;
                                    if(i_temp->pre != NULL)
                                    {
                                            i_temp->pre->next = i_temp;
                                    }
                                    if(j == 0)
                                    {
                                            *L = i_temp->pre;
                                    }       
                            }       
                            else    
                            {
                                    i_temp = i_temp->next;
                            }       
                    }       
            }       
    }
    • 交换法-快速排序
      对冒泡排序的一种改进,目的是提高排序的效率

    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    • 示例
    void sort2(sqlink* L,sqlink left,sqlink right)
    {
            sqlink key,left_copy = left,right_copy = right;
            int flag_left = 1,flag_right = 1;
            while(left != right)
            {
                    while(left != right)
                    {
                            if(left->data > right->data)
                            {
                                    swapSqlink(L,left,right);
                                    key = left;
                                    left = right;
                                    right = key;
                                    if(flag_left == 1)
                                    {
                                            left_copy = left;
                                            if(flag_right == 1)
                                            {
                                                    right_copy = right;
                                            }
                                    }
                                    break;
                            }
                            else
                            {
                                    flag_right++;
                                    right = right->pre;
                            }
                    }
                    while(left != right)
                    {
                            if(left->data > right->data)
                            {
                                    swapSqlink(L,left,right);
                                    key = left;
                                    left = right;
                                    right = key;
                                    if(flag_right == 1)
                                    {
                                            right_copy = right;
                                    }
                                    break;
                            }
                            else
                            {
                                    flag_left++;
                                    left = left->next;
                            }
                    }
            }
            // printf("\nleft_copy %d; address = %p\n",left_copy->data,left_copy);
            // printf("right_copy %d; address = %p\n",right_copy->data,right_copy);
            // printf("right %d; address = %p\n",right->data,right);
            // printf("left %d; address = %p\n",left->data,left);
            //printf("left->pre %d; address = %p\n",left->pre->data,left->pre);
            if(left_copy != left->pre && left->pre != NULL && left != left_copy)
            {
                    sort2(L,left_copy,left->pre);
            }
    // printf("start %d; address = %p\n",left->data,left);
            if(right_copy != right->next && right->next != NULL && right != right_copy)
            {
                    sort2(L,right->next,right_copy);
            }
            // printf("end\n");
            // return left;
    }
    void swapSqlink(sqlink* L,sqlink left,sqlink right)
    {
            // PrintList(L);
            // printf("\tstart %d %d\n",left->data,right->data);
            if(left->pre == NULL)
            {
                    *L = right;
            }
            if(left->next == right)
            {
                    if(left->pre != NULL)
                    {
                            left->pre->next = right;
                    }
                    if(right->next != NULL)
                    {
                            right->next->pre = left;
                    }
                    left->next = right->next;
                    right->pre = left->pre;
                    left->pre = right;
                    right->next = left;
            }
            else
            {
                    sqlink ll = left->pre,lr = left->next,rl = right->pre,rr = right->next;
                    if(ll != NULL)
                    {
                            ll->next = right;
                    }
                    // printf("\tyyy %d %d\n",left->data,right->data);
                    lr->pre = right;
                    right->pre = ll;
                    right->next = lr;
                    if(rr != NULL)
                    {
                            rr->pre = left;
                    }
                    rl->next = left;
                    left->pre = rl;
                    left->next = rr;
            }
            // printf("\tend %d %d\n",left->data,right->data);
    }
    • 插入法-直插排序
    Last login: Sat Feb  4 08:55:01 2017 from 192.168.1.62
    -bash-4.1$ pwd
    /home/jin
    -bash-4.1$ cd c_test/
    -bash-4.1$ cd 19_algorithm/
    -bash-4.1$ 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    -bash-4.1$ ls
    bin  include  obj  src
    -bash-4.1$ vim src/
    01.c      02.c      03_lib.c  05.c      06.c      07.c      08_lib.c  09_lib.c  10_lib.c  11_lib.c  12_lib.c  
    01_lib.c  03.c      04.c      05_lib.c  06_lib.c  08.c      09.c      10.c      11.c      12.c      
    -bash-4.1$ vim src/.
    ./  ../ 
    -bash-4.1$ vim src/12
    12.c      12_lib.c  
    -bash-4.1$ vim src/12.c 
    -bash-4.1$ vim src/12.c 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
                                    {
                                            new_l_copy->pre->next = old_l;
                                    }       
                                    else    
                                    {
                                            new_l = old_l;
                                            old_l->pre = NULL;
                                    }       
                                    new_l_copy->pre = old_l;
                                    old_l->next = new_l_copy;
                                    new_l_copy = new_l;
                                    break;
                            }       
                            else if(new_l_copy->next == NULL)
                            {
                                    new_l_copy->next = old_l;
                                    old_l->next = NULL;
                                    old_l->pre = new_l_copy;
                                    new_l_copy = new_l;
                                    break;
                            }       
                            new_l_copy = new_l_copy->next;
                    }       
                    old_l = *l;
            }       
            *l = new_l;
    }
    • 以上案例是基于如下链表的
    typedef struct node{
            int data;
            struct node* next;
            struct node* pre;
    }sqlist,*sqlink;
    int empty(sqlink* L)
    {       
            if(*L == NULL)
            {       
                    return 0;
            }
            return 1;
    }
    sqlink* CreateList(void)
    {
            sqlink* L = (sqlink*)malloc(sizeof(sqlink));
            *L = NULL;
            return L;
    }
    int Length(sqlink* L)
    {
            if(empty(L) == 0)
            {
                    return 0;
            }
            int length = 0;
            sqlink l = *L;
            while(l != NULL)
            {
                    l = l->next;
                    length++;
            }
            return length;
    }
    void freeList(sqlink L)
    {
            if(L->next != NULL)
            {
                    freeList(L->next);
            }
            free(L);
    }
    void ClearList(sqlink* L)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            freeList(*L);
    }
    sqlink GetList(sqlink* L,int index)
    {
            if(empty(L) == 0)
            {
                    return NULL;
            }
            index--;
            int i = 0;
            sqlink l = *L;
            while(l->next != NULL)
            {
                    if(i == index)
                    {
                            return l;
                    }
                    l = l->next;
                    i++;
            }
            return NULL;
    }
    int LocateList(sqlink* L,int value)
    {
            if(empty(L) == 0)
            {
                    return -1;
            }
            int i = 1;
            sqlink l = *L;
            while(l->next != NULL);
            {
                    if(l->data == value)
                    {
                            return i;
                    }
                    i++;
            }
            return -1;
    }
    void PushList(sqlink* L,int value)
    {
            if(empty(L) == 0)
            {
                    *L = (sqlink)malloc(sizeof(sqlist));
                    (*L)->data = value;
                    (*L)->next = NULL;
                    (*L)->pre = NULL;
                    return;
            }
            sqlink l = *L;
            while(1)
            {
                    if(l->next == NULL)
                    {
                            l->next = (sqlink)malloc(sizeof(sqlist));
                            l->next->data = value;
                            l->next->next = NULL;
                            l->next->pre = l;
                            return;
                    }
                    l = l->next;
            }
    }
    void InsertList(sqlink* L,int value,int index)
    {
            if(empty(L) == 0 || index > Length(L))
            {
                    return;
            }
            sqlink l = NULL;
            if(index == 1)
            {
                    l = (sqlink)malloc(sizeof(sqlist));
                    l->data = value;
                    l->next = *L;
                    (*L)->pre = l;
                    *L = l;
                    return;
            }
            int i = 1;
            sqlink l1 = *L;
            do{
                    if(index == i)
                    {
                            l = (sqlink)malloc(sizeof(sqlist));
                            l->data = value;
                            l->pre = l1->pre;
                            l->next = l1;
                            l->next->pre = l;
                            l->pre->next = l;
                            return;
                    }
                    i++;
                    l1 = l1->next;
    }
            while(l1 != NULL);
    }
    void DeleteList(sqlink* L,int index)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            sqlink l = NULL;
            if(index == 1)
            {
                    l = (*L)->next;
                    free(*L);
                    *L = l;
                    return;
            }
            l = *L;
            int i = 1;
            while(l->next != NULL)
            {
                    if(i == (index - 1))
                    {
                            sqlink temp = l->next->next;
                            free(l->next);
                            l->next = temp;
                    }
                    i++;
            }
    }
    void PrintList(sqlink* L)
    {
            if(empty(L) == 0)
            {
                    return;
            }
            sqlink l = *L;
            int i = 1;
            do
            {
                    printf("data[%d] = %d\n",i,l->data);
                    l = l->next;
                    i++;
            }
            while(l != NULL);
    }

    查找

    • 顺序查找,就是遍历链表,就不写了
    • 二分查找
    int BinSearch(sqlink l,int value,int length)
    {
            int left = 0,right = length,mid = (left + right) / 2,i;
            sqlink l_copy = l;
            while(left <= right)
            {
                    mid = (left + right) / 2;
                    l_copy = l;
                    for(i = 0;i < mid;i++)
                    {
                            l_copy = l_copy->next;
                    }
                    // printf("%d\n",l_copy->data);
                    if(l_copy->data > value)
                    {
                            left = mid + 1;
                    }
                    else if(l_copy->data < value)
                    {
                            right = mid - 1;
                    }
                    else
                    {
                            return 1;
                    }
            }
            return -1;
    }
    • 哈希表

      • 又称散列表,杂凑表。在前面讨论的顺序,拆半,分块查找和树表的查找中,其ASL的量级都在O(n)~O(log2n)之间。不论ASL是哪个量级,都与记录长度n有关,随着n的扩大,算法的效率会越来越低。ASL与n有关是因为存储在存储器中的存放是随机的,或者说记录的key与记录的存放地址无关,因而查找只能建立在key的比较基础上。
      • 理想的查找是:对给定的k,不经任何比较便能获取所需记录,其查找时间复杂度为常数级O(C)。这叫要求在建立记录表的时候,确定记录的key与其存储地址之间的关系f,即使key与记录的存放地址H相对应
      • 或者说记录按key存放
      • 之后,当要查找key=k的记录时,通过关系f就可得到响应记录的地址儿获取记录了,从而免去了key的比较过程。这个关系f就是所谓的哈希函数(或称散列函数,杂凑函数),记为H(key)。它实际上是一个地址映像函数,其自变量为记录的key,函数值为记录的存储地址(或称Hash地址)
      • 另外,不同的key可能得到同一个Hash地址,即当key1 != key2时,可能会有H(key1)=H(key2),此时称key1和key2为同义词。这种现象称为冲突或碰撞,因为一个数据单位只可存放一条记录。
      • 一般,选取Hash函数只能做到使冲突尽可能少,却不能完全避免。这就要求在出现冲突后,寻求适当的方法来解决冲突记录的存放问题
      • 例 设记录的key的集合为c语言的一些保留字,则k={case,char,float,for,int,while,struct,typedef,union,goto,void,return,switch,if,break,continue,else},构造关于k的Hash表时,可按不同的方法选取H(key)

        • 令H1(key)=key[0]-'a',其中key[0]为key的第一个字符。显然这样选取的Hash函数冲突现象频繁。如:H1(float)=H1(for)='f'-'a'=5。解决冲突的方法之一时为for寻求另一个有效位置。
        • 令H2(key)=(key[0]+key[i-1]-2'a')/2。其中key[i-1]为key的最后一个字符。如:H2(float)=('f'+'t'-2'a')/2=12,H2(for)=('f'+'r'-2*'a')/2=11,从而消除了一些冲突的发生,但仍无法完全避免,如:H2(case)=H2(continue)
    • 综上所述,对Hash表的含义描述如下

      • 根据选取的hash函数H(key)和处理冲突的方法,将一组记录(R1 R2 R3 ...)映射到记录的存储空间,所得到的记录表称为Hash表
      • 关于Hash表的讨论关键时两个问题,一是选取Hash函数的方法;二是确定解决冲突的方法
    • 选取(或构造)Hash函数的方法很多,原则是尽可能将记录均匀分布,以减少冲突现象发生。以下是几种常用的构造方法

      • 直接地址法

        • 直接取key的某个线性函数为hash函数,即令:H(key)=a*key+b,其中a,b为常数,此时称H(key)为直接hash函数或自身函数
      • 数字分析法

        • 分析数据的规律,取数据中的部分进行hash
      • 平方取中法
      • 保留除数法
    • 根据实际情况,数据的规律,选取(或构造)Hash函数的方法