数据结构-----顺序队列和链式队列的应用

1、顺序队列的应用

1.1 内容：

使用循环队列+两个线程：实现按顺序执行任务。使用sem信号量进行线程之间的同步

1.2 执行代码：

th1 线程函数：

• 用于执行任务队列中的任务，循环从队列中取出任务并执行。
• 使用 sem_wait(&sem_task) 阻塞线程，等待信号量的触发，表示有任务可执行。
• 从队列中取出任务，执行任务的时间长度使用 sleep 函数模拟任务执行的耗时。

main 函数：

• 创建了一个线程 tid1，执行线程函数 th1，传入参数为 sq。使用 sem_init(&sem_task, 0, 0) 初始化信号量 sem_task，初始值为 0，表示无可执行任务。
• 循环从标准输入读取一个数字，表示要执行的任务编号，将对应的任务加入任务队列，并通过 sem_post(&sem_task) 发送信号量，唤醒等待的线程。
• 如果读取到的任务为 "over"，表示任务结束，跳出循环。

sem_t sem_task;

void* th1(void* arg)
{
    SeqQueue* sq =(SeqQueue*) arg;
    DATATYPE data;
    while(1)
    {
        bzero(&data,sizeof(data));
        sem_wait(&sem_task);
        DATATYPE* tmp = GetHeadSeqQueue(sq);
        memcpy(&data,tmp,sizeof(DATATYPE));
        QuitSeqQueue(sq);
        if(0 == strcmp(data.task_name ,"over"))
        {
            break;
        }
        while(data.task_time--)
        {
            printf("I'm %s\n",data.task_name);
            sleep(1);
        }
    }
    return NULL;
}
int main(int argc, char *argv[])
{

    DATATYPE data []=
    {
        {"cooking", 5},
        {"washing", 3},
        {"working", 8},
        {"playing", 5},
        {"over",0},

    };
    SeqQueue* sq = CreateSeqQueue(10);

    pthread_t tid1;
    sem_init(&sem_task,0,0);
    pthread_create(&tid1,NULL,th1,sq);
    DATATYPE dat;
    while(1)
    {
        bzero(&dat,sizeof(dat));
        char buf[5]={0};// 1 2 3 4 5\n
        int num = 0 ;
        fgets(buf,sizeof(buf),stdin);
        num = atoi(buf);
        memcpy(&dat,&data[num-1],sizeof(DATATYPE));
        EnterSeqQueue(sq,&dat);
        sem_post(&sem_task);
        
        if(0 ==strcmp(dat.task_name ,"over"))
        {
            break;
        }

    }
    pthread_join(tid1,NULL);
    sem_destroy(&sem_task);
    DestroySeqQueue(sq);
    return 0;
}

2、链式队列的应用

2.1 内容

使用链式队列实现线程池操作

主线程：进行扫描目录，是目录则入队给工作线程，是.h则扫描检查。

工作线程：接收到入队信息开始扫描，如果是文件则找define，如果是目录则递归目录

然后将所有扫描到的#define写入LOG文件中。

2.2 流程

check_file 函数：

用于检查文件是否包含 #define 关键字，并将符合条件的行写入日志文件。

接受文件路径和一个文件指针作为参数，用于写入日志。

在函数中打开文件、读取文件内容，检查关键字并写入日志。

do_ls 函数：

递归遍历目录下的文件和子目录，并将文件路径加入任务队列中。

使用 opendir 打开目录，使用 readdir 读取目录下的文件和子目录。

对于子目录，如果是 "." 或 ".."，直接跳过；否则，递归调用 do_ls 函数。

对于文件，调用 check_file 函数进行检查。

th 线程函数：

执行任务队列中的任务。

循环从任务队列中取出任务路径，并调用 do_ls 函数进行处理。

当取出的任务为 "over" 时，退出循环。

#define PATH "/home/linux"
pthread_t main_tid;
sem_t sem_task;
int check_file(char *path,FILE* log)
{

    printf("processing %s\n",path);
    FILE* fp = fopen(path,"r");
    if(NULL == fp)
    {
        perror("check_file fopen");
        return 1;
    }

    int num =1;
    while(1)
    {
        char buf[1024]={0};
        if(fgets(buf,sizeof(buf),fp))
        {
            if(strstr(buf,"#define"))
            {
                buf[strlen(buf)-1]='\0';
                fprintf(log,"%s %d %s\n",buf,num,path );
                fflush(log);
            
            }
        }
        else 
        {
            break;
        }
        num++;
    }
    fclose(fp);
    return 0;
}
int do_ls(char* path,FILE* log,LinkQueue*lq)
{

    DIR* dir = opendir(path);
    if(NULL == dir)
    {
        perror("opendir");
        return 1;
    }
    char newpath[512]={0};
    DATATYPE data;
    while(1)
    {
        bzero(newpath,sizeof(newpath));
        bzero(&data,sizeof(DATATYPE));
        struct dirent* info  = readdir(dir);
        if(NULL == info)
        {
            break;
        }
        
        sprintf(newpath,"%s/%s",path,info->d_name);
        if(DT_DIR == info->d_type)
        {
            if(0 == strcmp(info->d_name,".")
               || 0 == strcmp(info->d_name,".."))
            {
                continue;
            }
            if(main_tid == pthread_self())
            {
                strcpy(data.pathname,  newpath);
                EnterLinkQueue(lq,&data);
                sem_post(&sem_task);
            }
            else 
            {
                do_ls(newpath,log,lq);
            }

        }
        else 
        {
            check_file(newpath,log);

        }
    
    }
    closedir(dir);
    return 0;
}
typedef struct
{
    FILE* fp ;
    LinkQueue* lq;
}TH_ARG;
void* th(void* arg)
{
    TH_ARG *tmp = (TH_ARG*)arg;
    FILE* log = tmp->fp ;
    LinkQueue*lq = tmp->lq ;
    char path[512]={0};
    while(1)
    {
        bzero(path,sizeof(path));
        sem_wait(&sem_task);
        DATATYPE* ret = GetHeadLinkQue(lq);
        strcpy(path,ret->pathname);
        QuitLinkQueue(lq);
        if(0 == strcmp(path,"over"))
        {
            break;
        }
        do_ls(path,log,lq);
    }
    return NULL;
}
int main(int argc, char *argv[])
{
    main_tid=pthread_self();
    TH_ARG arg;
    bzero(&arg,sizeof(arg));
    LinkQueue* lq = CreateLinkQueue();
    FILE* log = fopen("log","w");
    if(NULL == log)
    {
        perror("fp");
        return 1;
    }
    arg.fp = log;
    arg.lq = lq;
    sem_init(&sem_task,0,0);
    pthread_t tid1,tid2,tid3;
    pthread_create(&tid1,NULL,th,&arg);
    pthread_create(&tid2,NULL,th,&arg);
    pthread_create(&tid3,NULL,th,&arg);
    do_ls(PATH,log,lq);

    int i = 0 ;
    for(i =0;i<3;i++)
    {
        DATATYPE data;
        strcpy(data.pathname,"over");
        EnterLinkQueue(lq,&data);
        sem_post(&sem_task);
    }
    pthread_join(tid1,NULL);
    pthread_join(tid2,NULL);
    pthread_join(tid3,NULL);
    fclose(log);
    sem_destroy(&sem_task);
    DestroyLinkQueue(lq);
    return 0;
}