目录
栈: 3+5*6
栈的类型:
顺序栈:
功能函数实现:seqstack.c
头文件:seqstack.h
测试功能函数:
练习:
链式栈:
功能函数实现:linkstack.c
头文件:linkstack.h
测试功能函数:
hw:使用栈计算一个加减乘除的整体运算(开两个栈,一个放符号,一个放数字)
队列:
一、顺序,循环队列
功能函数实现:seqqueue.c
头文件:seqqueue.h
测试功能函数:main.c
练习:共有四个任务,当我输入一个任务的时候,线程开始起来工作。
二、链式队列
功能函数实现:linkque.c
头文件:linkque.h
测试功能函数:main.c
栈: 3+5*6
栈是限定仅在表尾进行插入和删除操作的线性表。
先进后出、后进先出
栈顶:允许操作的一端
栈底:不允许操作的一端
入栈,出栈。
顺序栈 链式栈
30+2\5
1.创建 CreateSeqStack
2.销毁 DestroySeqStack
3.判断是否为空栈 IsEmptySeqStack
4.判断是否为满栈 IsFullSeqStack
5.压栈 PushSeqStack
6.出栈 PopSeqStack
栈的类型:
空增栈
空减栈
满赠栈
满减栈
空栈,top指向的位置,是新元素待插入的位置
满栈,top指向的位置,是最后入栈的元素的位置
增栈,随着入栈的操作,新增元素的地址慢慢增大
减栈,随着入栈的操作,新增元素的地址慢慢减小(系统减小)
顺序栈:
功能函数实现:seqstack.c
#include "seqstack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>SeqStack* CreateSeqStack(int len)
{SeqStack* ss = malloc(sizeof(SeqStack)); if(NULL == ss){perror("create seq stack malloc");return NULL;}ss->head= malloc(sizeof(DATATYPE)*len);if(NULL == ss->head){perror("create seq stack malloc2");return NULL;}ss->tlen= len;ss->top = 0;return ss;
}
int DestroySeqStack(SeqStack* ss);
int PushSeqStack(SeqStack* ss, DATATYPE*data)
{if(IsFullSeqStack(ss)){return 1;}memcpy(&ss->head[ss->top++],data,sizeof(DATATYPE));return 0;
}
int PopSeqStack(SeqStack*ss)
{if(IsEmptySeqStack(ss)){return 1;}ss->top--;return 0;
}
int IsEmptySeqStack(SeqStack*ss)
{return ss->top == 0;
}
int IsFullSeqStack(SeqStack*ss)
{return ss->tlen == ss->top;
}
DATATYPE* GetTopSeqStack(SeqStack* ss)
{if(IsEmptySeqStack(ss))return NULL;return &ss->head[ss->top-1];
}int GetSizeSeqStack(SeqStack*ss)
{return ss->top;
}
头文件:seqstack.h
#ifndef __SEQSTACK__H__
#define __SEQSTACK__H__typedef struct person {char name[32];char gender;int age;int score;
}DATATYPE;typedef struct {DATATYPE *head;int tlen;int top;//clen
}SeqStack;SeqStack* CreateSeqStack(int len);
int DestroySeqStack(SeqStack* ss);
int PushSeqStack(SeqStack* ss, DATATYPE*data);//压栈 入栈 插入栈
int PopSeqStack(SeqStack*ss);//出栈 弹栈 删除
int IsEmptySeqStack(SeqStack*ss);
int IsFullSeqStack(SeqStack*ss);
DATATYPE* GetTopSeqStack(SeqStack* ss);
int GetSizeSeqStack(SeqStack*ss);#endif //!__SEQSTACK__H__
测试功能函数:
#include "seqstack.h"
#include <stdio.h>int main(int argc, char **argv)
{SeqStack*ss = CreateSeqStack(10);DATATYPE data[]={{"zhangsan",'m',20,80},{"lisi",'f',21,82},{"wangmazi",'f',22,70},{"lao6",'f',30,70},{"zhaosi",'f',30,50},};int i = 0 ;for(i=0;i<5;i++){PushSeqStack(ss,&data[i]); }DATATYPE* tmp;int len = GetSizeSeqStack(ss);for(i=0;i<len;i++){tmp = GetTopSeqStack(ss);printf("name:%s score:%d\n",tmp->name,tmp->score);PopSeqStack(ss);}printf("hello\n");return 0;
}
练习:
运用栈先进后出的原理扫描一个文件内的括号是否匹配(若配到左括号入栈,若是右括号则判断与栈顶括号是否匹配,若是不匹配则,输出该括号的位置,行号和列号)
示例:
#include "seqstack.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*//该函数使用的DATATYPE结构体定义
typedef struct person {char c;int row;int col;
}DATATYPE;*/int do_check(char *buf,int num,SeqStack*ss)
{int col =1;DATATYPE data;while(*buf){char c = *buf;DATATYPE * tmp= NULL;bzero(&data,sizeof(data));switch(c){case '(':case '[':case '{':data.c = c;data.row = num;data.col = col;PushSeqStack(ss,&data);break;case ')':tmp = GetTopSeqStack(ss);if(NULL == tmp){printf("curren sym:%c row:%d col:%d\n",c,num,col);exit(1);}else {if('('==tmp->c ){PopSeqStack(ss);}else {printf("curren sym:%c row:%d col:%d or top error ,sym:%c row:%d col:%d\n",c,num,col, tmp->c,tmp->row,tmp->col);exit(1);}}break;case ']':tmp = GetTopSeqStack(ss);if(NULL == tmp){printf("curren sym:%c row:%d col:%d\n",c,num,col);exit(1);}else {if('['==tmp->c ){PopSeqStack(ss);}else {printf("curren sym:%c row:%d col:%d or top error ,sym:%c row:%d col:%d\n",c,num,col, tmp->c,tmp->row,tmp->col);exit(1);}}break;case '}':tmp = GetTopSeqStack(ss);if(NULL == tmp){printf("curren sym:%c row:%d col:%d\n",c,num,col);exit(1);}else {if('{'==tmp->c ){PopSeqStack(ss);}else {printf("curren sym:%c row:%d col:%d or top error ,sym:%c row:%d col:%d\n",c,num,col, tmp->c,tmp->row,tmp->col);exit(1);}}break;}buf++;col++;}
}
int main(int argc, char **argv)
{SeqStack*ss = CreateSeqStack(50);FILE* fp = fopen("/home/linux/1.c","r");if(NULL == fp){perror("fopen");return 1;}int num = 1;while(1){char buf[512]={0};char *c = fgets(buf,sizeof(buf),fp);if(NULL == c){break;}int ret = do_check(buf,num,ss);num++;}if(IsEmptySeqStack(ss)){printf("file ok\n");}else {DATATYPE*tmp = GetTopSeqStack(ss);printf("top sym:%c row:%d col:%d\n",tmp->c,tmp->row,tmp->col);}printf("hello\n");return 0;
}
链式栈:
功能函数实现:linkstack.c
#include "linkstack.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
LinkStack* CreateLinkStack()
{LinkStack* ls= (LinkStack*) malloc(sizeof(LinkStack));if(NULL == ls){perror("CreateLinkStack malloc");return NULL;}ls->top = NULL;ls->clen = 0 ;return ls;
}
int DestroyLinkStack(LinkStack*ls)
{int len = GetSizeLinkStack(ls);int i = 0 ;for(i=0;i<len;i++){PopLinkStack(ls);}free(ls);return 0;
}
int PushLinkStack(LinkStack*ls ,DATATYPE*data)
{LinkStackNode*newnode = (LinkStackNode*)malloc(sizeof(LinkStackNode));if(NULL == newnode){perror("push malloc");return 1;}memcpy(&newnode->data,data,sizeof(DATATYPE));newnode->next = NULL;newnode->next= ls->top;ls->top = newnode;ls->clen++;return 0;
}
int PopLinkStack(LinkStack*ls)
{if(IsEmptyLinkStack(ls)){return 1;}LinkStackNode* tmp = ls->top;ls->top=ls->top->next;free(tmp);ls->clen--;return 0;
}
DATATYPE* GetTopLinkStack(LinkStack*ls)
{if(IsEmptyLinkStack(ls)){return NULL;}else {return &ls->top->data ;}}
int IsEmptyLinkStack(LinkStack*ls)
{return 0 == ls->clen ;
}
int GetSizeLinkStack(LinkStack* ls)
{return ls->clen;
}
头文件:linkstack.h
#ifndef _LINK_STACK_
#define _LINK_STACK_ typedef struct person {char name[32];char gender;int age;int score;
}DATATYPE;typedef struct _link_stack_node_
{DATATYPE data;struct _link_stack_node_* next;
}LinkStackNode;typedef struct
{LinkStackNode* top;int clen;}LinkStack;
LinkStack* CreateLinkStack();
int DestroyLinkStack(LinkStack*ls);
int PushLinkStack(LinkStack*ls ,DATATYPE*data);
int PopLinkStack(LinkStack*ls);
DATATYPE* GetTopLinkStack(LinkStack*ls);
int IsEmptyLinkStack(LinkStack*ls);
int GetSizeLinkStack(LinkStack* ls);
#endif
测试功能函数:
#include <stdio.h>
#include "linkstack.h"int main(int argc, char *argv[])
{DATATYPE data[]={{"zhangsan",'m',20,80},{"lisi",'f',21,82},{"wangmazi",'f',22,70},{"lao6",'f',30,70},{"zhaosi",'f',30,50},};LinkStack*ls = CreateLinkStack();int i = 0 ;for(i = 0 ;i<5;i++){PushLinkStack(ls,&data[i]);}DATATYPE* tmp = NULL;for(i = 0;i<6;i++){tmp=GetTopLinkStack(ls);if(NULL == tmp){printf("link stack is empty\n");break;}printf("name:%s score:%d\n",tmp->name,tmp->score);PopLinkStack(ls);}DestroyLinkStack(ls);return 0;
}
hw:使用栈计算一个加减乘除的整体运算(开两个栈,一个放符号,一个放数字)
示例:
#include <stdio.h>
#include "linkstack.h"
#include <string.h>
#if 0
只改了linkstack.h里面的datatype结构体变量
typedef struct person {int num;char c;
}DATATYPE;
#endif
int num = 0;
void get_num(char c)
{num =num*10+ c-'0' ;
}
int get_proity(char c)
{switch(c){case '/':return 4;break;case '*':return 3;break;case '-':return 2;break;case '+':return 1;break;}return 0;
}
int get_result(int num1,int num2,char c)
{switch(c){case '+':return num1+num2;break;case '-':return num1-num2;break;case '*':return num1*num2;break;case '/':return num1/num2;break;}return 0;
}
int main(int argc, char *argv[])
{char buf[]="30*2+6";LinkStack* ls_num = CreateLinkStack();LinkStack* ls_op = CreateLinkStack();char * tmp = buf;DATATYPE data;DATATYPE*top_tmp =NULL;int flag = 0;while(*tmp){bzero(&data,sizeof(data));if(*tmp >='0' && *tmp<='9'){get_num(*tmp); tmp++;continue;}if(0 == flag){data.num = num;PushLinkStack(ls_num,&data);num = 0;}top_tmp = GetTopLinkStack(ls_op);if(IsEmptyLinkStack(ls_op) || get_proity(*tmp) > get_proity(top_tmp->c) ) //empty curr>top {bzero(&data,sizeof(data));data.c = *tmp;PushLinkStack(ls_op,&data);flag =0;}else {top_tmp = GetTopLinkStack(ls_num);int num2 = top_tmp->num ;PopLinkStack(ls_num);top_tmp = GetTopLinkStack(ls_num);int num1 = top_tmp->num ;PopLinkStack(ls_num);top_tmp = GetTopLinkStack(ls_op);char sym = top_tmp->c ;PopLinkStack(ls_op);int result = get_result(num1,num2,sym);bzero(&data,sizeof(data));data.num = result;PushLinkStack(ls_num,&data);flag = 1;continue;}tmp++;}data.num = num;PushLinkStack(ls_num,&data);while(!IsEmptyLinkStack(ls_op)){top_tmp = GetTopLinkStack(ls_num);int num2 = top_tmp->num ;PopLinkStack(ls_num);top_tmp = GetTopLinkStack(ls_num);int num1 = top_tmp->num ;PopLinkStack(ls_num);top_tmp = GetTopLinkStack(ls_op);char sym = top_tmp->c ;PopLinkStack(ls_op);int result = get_result(num1,num2,sym);bzero(&data,sizeof(data));data.num = result;PushLinkStack(ls_num,&data);}top_tmp = GetTopLinkStack(ls_num);int num2 = top_tmp->num ;printf("%s result %d\n",buf,num2);DestroyLinkStack(ls_num);DestroyLinkStack(ls_op);return 0;
}
队列:
队列是只允许在一段进行插入,而在另一端进行删除操作的线性表。
允许插入的称谓队尾,允许删除的一端队头。
顺序队列。
循环队列,
常用操作,入队,出队。
先进先出,FIFO
一、顺序,循环队列
顺序队列,采用循环机制,给一个不用的空间,用来当作判断空满的条件,当空的时候,tail==head,当满的时候tail+1 == head,因为采用的循环,这个不用的空间是动态的,所以要循环注意求余;
#ifndef __HEAD_H__
#define __HEAD_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>
#include <errno.h>
#define error_exit(_errmsg_) error(EXIT_FAILURE, errno, _errmsg_)
typedef int DATATYPE;
typedef struct queue {
DATATYPE *ptr;
int tlen;
int head;
int tail;
}SeqQueue;
int DestroySeqQueue(SeqQueue *queue);
DATATYPE QuitSeqQueue(SeqQueue *queue);
int EnterSeqQueue(SeqQueue *queue, DATATYPE data);
int IsEmptySeqQueue(SeqQueue *queue);
int IsFullSeqQueue(SeqQueue *queue);
SeqQueue *CreateSeqQueue(int len);
#endif
功能函数实现:seqqueue.c
#include "seqqueue.h"
#include <stdio.h>
#include <string.h>
SeqQueue *CreateSeqQueue(int len)
{SeqQueue* sq = malloc(sizeof(SeqQueue));if(NULL ==sq){perror("createseq que malloc");return NULL;}sq->ptr= malloc(sizeof(DATATYPE)*len);if(NULL == sq->ptr){perror("create seqque malloc2");return NULL;}sq->tlen = len;sq->head = 0 ;sq->tail = 0;return sq;}
int DestroySeqQueue(SeqQueue *queue)
{free(queue->ptr);free(queue);return 0;
}
int QuitSeqQueue(SeqQueue *queue)
{if(IsEmptySeqQueue(queue)){return 1;}queue->head = (queue->head+1)%queue->tlen;return 0;
}
int EnterSeqQueue(SeqQueue *queue, DATATYPE *data)
{if(IsFullSeqQueue(queue)){return 1;}memcpy(&queue->ptr[queue->tail],data,sizeof(DATATYPE));queue->tail = (queue->tail+1)%queue->tlen;return 0;
}
int IsEmptySeqQueue(SeqQueue *queue)
{return queue->head == queue->tail;
}
int IsFullSeqQueue(SeqQueue *queue)
{return queue->head == (queue->tail+1)%queue->tlen;
}
DATATYPE* GetHeadSeqQueue(SeqQueue*queue)
{if(IsEmptySeqQueue(queue)){return NULL;}return &queue->ptr[queue->head];
}
头文件:seqqueue.h
#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>
#include <errno.h>typedef int DATATYPE;
typedef struct queue {DATATYPE *ptr;int tlen;int head;int tail;
}SeqQueue;
SeqQueue *CreateSeqQueue(int len);
int DestroySeqQueue(SeqQueue *queue);
int QuitSeqQueue(SeqQueue *queue);
int EnterSeqQueue(SeqQueue *queue, DATATYPE *data);
int IsEmptySeqQueue(SeqQueue *queue);
int IsFullSeqQueue(SeqQueue *queue);
DATATYPE* GetHeadSeqQueue(SeqQueue*queue);#endif
测试功能函数:main.c
#include <stdio.h>
#include "seqqueue.h"//snip
int main(int argc, char **argv)
{SeqQueue*sq = CreateSeqQueue(10);int i=0;for(i=0;i<10;i++){EnterSeqQueue(sq, &i);}DATATYPE* tmp=NULL;while(!IsEmptySeqQueue(sq)){tmp= GetHeadSeqQueue(sq);printf("%d\t",*tmp);QuitSeqQueue(sq);}DestroySeqQueue(sq);//system("pause");return 0;
}
练习:共有四个任务,当我输入一个任务的时候,线程开始起来工作。
示例:
#include <stdio.h>
#include "seqqueue.h"
#include <pthread.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
/*
typedef struct
{char task_name[50];int task_time;
}DATATYPE;//该程序使用的datatype结构体*/sem_t sem_task;DATATYPE data[]={{"cooking",5},{"washing",9},{"do_homework",3},{"over",5},
};
int show_task()
{int i =0 ;for(i=0;i<4;i++){printf("%d %s\n",i,data[i].task_name);}return 0;}
void* th(void* arg)
{SeqQueue* sq = (SeqQueue*)arg;DATATYPE* tmp=NULL;DATATYPE local_data;while(1){sem_wait(&sem_task);bzero(&local_data,sizeof(local_data));tmp= GetHeadSeqQueue(sq);memcpy(&local_data,tmp,sizeof(DATATYPE));QuitSeqQueue(sq);if(0==strcmp(local_data.task_name,"over")){break;}while(local_data.task_time --){printf("i'm %s\n",local_data.task_name);sleep(1);}}return NULL;
}
int main(int argc, char **argv)
{SeqQueue*sq = CreateSeqQueue(10);pthread_t tid;sem_init(&sem_task,0,0);pthread_create(&tid,NULL,th,sq);show_task();DATATYPE tmp_data;while(1){bzero(&tmp_data,sizeof(tmp_data));char buf[10]={0};fgets(buf,sizeof(buf),stdin);int num = atoi(buf);strcpy(tmp_data.task_name,data[num].task_name);tmp_data.task_time = data[num].task_time;EnterSeqQueue(sq,&tmp_data);sem_post(&sem_task) ;// +1 if(3 == num){break;}}pthread_join(tid,NULL);DestroySeqQueue(sq);sem_destroy(&sem_task);//system("pause");return 0;
}
二、链式队列
功能函数实现:linkque.c
#include <stdio.h>
#include "seqqueue.h"
#include <pthread.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
/*
typedef struct
{char task_name[50];int task_time;
}DATATYPE;//该程序使用的datatype结构体*/sem_t sem_task;DATATYPE data[]={{"cooking",5},{"washing",9},{"do_homework",3},{"over",5},
};
int show_task()
{int i =0 ;for(i=0;i<4;i++){printf("%d %s\n",i,data[i].task_name);}return 0;}
void* th(void* arg)
{SeqQueue* sq = (SeqQueue*)arg;DATATYPE* tmp=NULL;DATATYPE local_data;while(1){sem_wait(&sem_task);bzero(&local_data,sizeof(local_data));tmp= GetHeadSeqQueue(sq);memcpy(&local_data,tmp,sizeof(DATATYPE));QuitSeqQueue(sq);if(0==strcmp(local_data.task_name,"over")){break;}while(local_data.task_time --){printf("i'm %s\n",local_data.task_name);sleep(1);}}return NULL;
}
int main(int argc, char **argv)
{SeqQueue*sq = CreateSeqQueue(10);pthread_t tid;sem_init(&sem_task,0,0);pthread_create(&tid,NULL,th,sq);show_task();DATATYPE tmp_data;while(1){bzero(&tmp_data,sizeof(tmp_data));char buf[10]={0};fgets(buf,sizeof(buf),stdin);int num = atoi(buf);strcpy(tmp_data.task_name,data[num].task_name);tmp_data.task_time = data[num].task_time;EnterSeqQueue(sq,&tmp_data);sem_post(&sem_task) ;// +1 if(3 == num){break;}}pthread_join(tid,NULL);DestroySeqQueue(sq);sem_destroy(&sem_task);//system("pause");return 0;
}
头文件:linkque.h
#ifndef __HEAD_H__
#define __HEAD_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>
#include <errno.h>
typedef int DATATYPE;
typedef struct node {DATATYPE data;struct node *next;
}QueueNode;typedef struct queue {QueueNode *head;int clen;QueueNode *tail;
}LinkQueue;
LinkQueue *CreateLinkQueue();
int DestroyLinkQueue(LinkQueue *queue);
int QuitLinkQueue(LinkQueue *queue);
int EnterLinkQueue(LinkQueue *queue, DATATYPE *data);
int IsEmptyLinkQueue(LinkQueue *queue);
DATATYPE* GetHeadLinkQueue(LinkQueue* que);
int GetSizeLinkQueue(LinkQueue*que);
#endif
测试功能函数:main.c
#include <stdio.h>
#include <stdlib.h>
#include "linkque.h"int main(int argc, char **argv)
{LinkQueue* lq = CreateLinkQueue();int i = 0;for(i=0;i<10;i++){EnterLinkQueue(lq, &i);}int len = GetSizeLinkQueue(lq);for(i=0;i<len;i++){DATATYPE* tmp = GetHeadLinkQueue(lq); printf("%d\t",*tmp);QuitLinkQueue(lq);}DestroyLinkQueue(lq);system("pause");return 0;
}