自学嵌入式 day22 -数据结构 栈 队列
一、栈
1.定义：栈是限定仅在表尾进行插入和删除的线性表
2.特点：先进后出
3.栈顶：允许操作的一方；栈底：不允许操作的一方
4基础操作：
（1）创建
LinkStack* CreateLinkStack()
{
LinkStack* ls = ( LinkStack* )malloc(sizeof(LinkStack));
if(NULL == ls)
{
fprintf(stderr,"CreateLinkStack malloc\n");
return NULL;
}ls->top =NULL;
ls->clen = 0 ;
return ls;
}
（2）入栈
int PushLinkStack(LinkStack*ls,DATATYPE* data)
{
LinkStackNode* newnode = malloc(sizeof(LinkStackNode));
if(NULL == newnode)
{
fprintf(stderr,"PushLinkStack malloc\n");
return 1;
}
memcpy(&newnode->data,data,sizeof(DATATYPE));
newnode->next = NULL;newnode->next = ls->top;
ls->top = newnode;
ls->clen++;}
（3）出栈
int PopLinkStack(LinkStack*ls)
{
if(IsEmptyLinkStack(ls))
{
return 1;
}
LinkStackNode* tmp = ls->top;
ls->top = ls->top->next;
free(tmp);
ls->clen--;
return 0;
}
int IsEmptyLinkStack(LinkStack*ls)
{
return 0 == ls->clen;
}
（4）取栈顶元素
DATATYPE* GetTopLinkStack(LinkStack*ls)
{
if(IsEmptyLinkStack(ls))
{
return NULL;
}
return &ls->top->data;
}
（5）销毁
int DestroyLinkStack(LinkStack*ls)
{
int len = GetSizeLinkStack(ls);
for(int i = 0 ;i < len ;++i)
{
PopLinkStack(ls);
}free(ls);
return 0;
}
6.判断“（）”“[]”“{}”是否对齐
#include <stdio.h>
#include <string.h>
#include "linkstack.h"
int readfile(char *filename, char *filecontext)//文本读取函数
{
FILE *fp = fopen(filename, "r");
if (NULL == fp)
{
return 1;
}
fread(filecontext, 1024, 1, fp);//从文件读取1024字节到缓冲区，返回实际读取块数
fclose(fp);
return 0;
}
int main(int argc, char **argv)
{
char buf[1024] = {0};//初始化1024字节缓冲区
int ret = readfile("/home/linux/2.c", buf);//读取文件内容到buf
if (1 == ret)//判断读取是否成功
{
return 1;
}
LinkStack *ls = CreateLinkStack();//创建链表来存储符号
char *tmp = buf;//定义一个指针，指向缓冲区起始位置
DATATYPE data = {0};//定义一个结构体存储符号和其行列数
int row = 1;//初始化行号
int col = 1;//初始化列号
DATATYPE *top;//存储栈顶元素
while (*tmp) // 遍历缓冲区
{
memset(&data, 0, sizeof(DATATYPE));//初始化结构体数据
switch (*tmp)//判断是否是“（{ [”符号
{
case '(':
case '[':
case '{':
data.c = *tmp;//存储符号
data.col = col;//存储列号
data.row = row;//存储行号PushLinkStack(ls, &data);//入栈
break;case ')'://判断符号是否是“）”并且与栈顶元素比较，看是否匹配
top = GetTopLinkStack(ls);//获取栈顶元素
if ('(' == top->c && NULL != top)
{
PopLinkStack(ls);
}
else
{
if (NULL == top)
{
printf("sym:%c row:%d col%d\n", ')', row, col);
}
else
{
printf( "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n",top->c, top->row, top->col, *tmp, row, col);
}
return 1;
}break;
case ']'://判断符号是否是“]”并且与栈顶元素比较，看是否匹配
top = GetTopLinkStack(ls);
if ('[' == top->c && NULL != top)
{
PopLinkStack(ls);
}
else
{
if (NULL == top)
{
printf("sym:%c row:%d col%d\n", ')', row, col);
}
else
{
printf(
"top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n",top->c, top->row, top->col, *tmp, row, col);
}
return 1;
}break;
case '}'://判断符号是否是“}”并且与栈顶元素比较，看是否匹配
top = GetTopLinkStack(ls);
if ('{' == top->c && NULL != top)
{
PopLinkStack(ls);
}
else
{
if (NULL == top)
{
printf("sym:%c row:%d col%d\n", ')', row, col);
}
else
{
printf(
"top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n",top->c, top->row, top->col, *tmp, row, col);
}
return 1;
}break;
}
col++;//列数递增
if ('\n' == *tmp)//行数递增
{
col = 1;
row++;
}
tmp++;//移动到下一个字符
}if ('\0' == *tmp && IsEmptyLinkStack(ls))//判断是否成功遍历缓冲区
{
printf("ok");
}
else
{
top = GetTopLinkStack(ls);
printf("top sym:%c row:%d col%d\n", top->c, top->row, top->col);
}DestroyLinkStack(ls);
return 0;
}
return 0;
}
二、队列
1.定义：只允许在一端进行插入，而在另一端进行删除操作的线性表
2.特点：先进先出
3.对尾：只允许插入的一端；对头：允许删除的一端
4.基础操作（顺序链表）：
（1）创建
SeqQueue* CreateSeqQue(int len)
{
SeqQueue *sq = (SeqQueue *)malloc(sizeof(SeqQueue));
if(NULL == sq)
{
fprintf(stderr,"CreateSeqQue malloc\n");
return NULL;
}
sq -> array = (DATATYPE *)malloc(sizeof(DATATYPE) * len);
if(NULL == sq -> array)
{
fprintf(stderr,"DATATYPE malloc");
return NULL;
}
sq -> head = 0;
sq -> tail = 0;
sq -> tlen = len;
return sq;
}
（2）插入
int IsFullSeqQue(SeqQueue*sq)
{
return (sq->tail +1 )%sq->tlen == sq->head;
}
int EnterSeqQue(SeqQueue*sq,DATATYPE*data)
{
if(IsFullSeqQue(sq))
{
fprintf(stderr,"EnterSeqQue,SeqQueue full\n");
return 1;
}
memcpy(&sq->array[sq->tail],data,sizeof(DATATYPE));
sq->tail = (sq->tail+1)%sq->tlen;
return 0;
}
（3）删除
int IsEmptySeqQue(SeqQueue*sq)
{
return sq->head == sq->tail;
}
int QuitSeqQue(SeqQueue*sq)
{
if(IsEmptySeqQue(sq))
{
fprintf(stderr,"QuitSeqQue SeqQueue empty\n");
return 1;
}
sq->head = (sq->head+1)%sq->tlen;
return 0;
}