棧的基本代碼
棧是限定僅在表尾進行插入和刪除操作的線性表。
先進后出、后進先出
棧頂:允許操作的一端
棧底:不允許操作的一端
入棧，出棧。
順序棧 鏈式棧
30+2\5
1.創建 CreateSeqStack
2.銷毀 DestroySeqStack
3.判斷是否為空棧 IsEmptySeqStack
4.判斷是否為滿棧 IsFullSeqStack
5.壓棧 PushSeqStack
6.出棧 PopSeqStack
seqstack.h
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__typedef struct person
{char name[32];char sex;int age;int score;
} DATATYPE;typedef struct list
{DATATYPE *head;int tlen;int top; // 相當于clen
} SeqStack;// 創建
SeqStack *CreateSeqStack(int size);
// 銷毀
int DestroySeqStack(SeqStack *ss);
// 新增元素 入棧
int PushSeqStack(SeqStack *ss, DATATYPE *data); // add
// 刪除元素 出棧
int PopSeqStack(SeqStack *ss); // del
// 判斷是否為空
int IsEmpySeqStack(SeqStack *ss);
// 判斷是否為滿
int IsFullSeqStack(SeqStack *ss);
// 獲得棧頂元素
DATATYPE *GetTopSeqStack(SeqStack *ss);
int GetSizeSeqStack(SeqStack *ss);
#endifseqstack.c
#include "./seqstack.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// 創建
SeqStack *CreateSeqStack(int size)
{SeqStack *ss = malloc(sizeof(SeqStack));if (NULL == ss){perror("CreateSeqStack malloc error\n");return NULL;}ss->head = malloc(sizeof(DATATYPE) * size);if (NULL == ss->head){perror("CreateSeqStack malloc2 error\n");return NULL;}ss->tlen = size;ss->top = 0;return ss;
}
// 銷毀
int DestroySeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "DestroySeqStack pamter error\n");return 1;}free(ss->head);free(ss);return 0;
}
// 新增元素 入棧
int PushSeqStack(SeqStack *ss, DATATYPE *data)
{if (NULL == ss || NULL == data || IsFullSeqStack(ss)){fprintf(stderr, "PushSeqStack pamter error\n");return 1;}memcpy(&ss->head[ss->top], data, sizeof(DATATYPE));ss->top++;return 0;
}
// 刪除元素 出棧
int PopSeqStack(SeqStack *ss)
{if (NULL == ss || IsEmpySeqStack(ss)){fprintf(stderr, "PopSeqStack pamter error\n");return 1;}ss->top--;return 0;
}
// 判斷是否為空
int IsEmpySeqStack(SeqStack *ss)
{return 0 == ss->top;
}
// 判斷是否為滿
int IsFullSeqStack(SeqStack *ss)
{return ss->tlen == ss->top;
}
// 獲得棧頂元素
DATATYPE *GetTopSeqStack(SeqStack *ss)
{if (NULL == ss || IsEmpySeqStack(ss)){fprintf(stderr, "GetTopSeqStack pamter error\n");return NULL;}return &ss->head[ss->top - 1];
}int GetSizeSeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "GetSizeSeqStack pamter error\n");return -1;}return ss->top;
}main.c
#include "./seqstack.h"
#include <stdio.h>int main(int argc, char **argv)
{SeqStack *ss = CreateSeqStack(5);DATATYPE data[] = {{"zhangsan", 'm', 20, 80},{"lisi", 'f', 22, 86},{"wangmazi", 'f', 22, 67},{"guanerge", 'm', 40, 88},{"liubei", 'm', 42, 90},};int i = 0;for (i = 0; i < 5; i++){PushSeqStack(ss, &data[i]);}int len = GetSizeSeqStack(ss);for (i = 0; i < len; i++){DATATYPE *tmp = GetTopSeqStack(ss);printf("name:%s age:%d\n", tmp->name, tmp->age);PopSeqStack(ss);}DestroySeqStack(ss);// system("pause");return 0;
}
練習
遍歷一個文件，查找文件中字符")" ,"]","}"是否存在正確的配對字符，如果不存在，打印錯誤信息，找出錯誤在文件中的第幾行，以及是上面三種字符中的哪種字符導致的錯誤
seqstack.h
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__typedef struct person
{char sym;int linenum;int colnum;
} DATATYPE;typedef struct list
{DATATYPE *head;int tlen;int top; // 相當于clen
} SeqStack;// 創建
SeqStack *CreateSeqStack(int size);
// 銷毀
int DestroySeqStack(SeqStack *ss);
// 新增元素 入棧
int PushSeqStack(SeqStack *ss, DATATYPE *data); // add
// 刪除元素 出棧
int PopSeqStack(SeqStack *ss); // del
// 判斷是否為空
int IsEmpySeqStack(SeqStack *ss);
// 判斷是否為滿
int IsFullSeqStack(SeqStack *ss);
// 獲得棧頂元素
DATATYPE *GetTopSeqStack(SeqStack *ss);
int GetSizeSeqStack(SeqStack *ss);
#endifseqstack.c
#include "./seqstack.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// 創建
SeqStack *CreateSeqStack(int size)
{SeqStack *ss = malloc(sizeof(SeqStack));if (NULL == ss){perror("CreateSeqStack malloc error\n");return NULL;}ss->head = malloc(sizeof(DATATYPE) * size);if (NULL == ss->head){perror("CreateSeqStack malloc2 error\n");return NULL;}ss->tlen = size;ss->top = 0;return ss;
}
// 銷毀
int DestroySeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "DestroySeqStack pamter error\n");return 1;}free(ss->head);free(ss);return 0;
}
// 新增元素 入棧
int PushSeqStack(SeqStack *ss, DATATYPE *data)
{if (NULL == ss || NULL == data || IsFullSeqStack(ss)){fprintf(stderr, "PushSeqStack pamter error\n");return 1;}memcpy(&ss->head[ss->top], data, sizeof(DATATYPE));ss->top++;return 0;
}
// 刪除元素 出棧
int PopSeqStack(SeqStack *ss)
{if (NULL == ss || IsEmpySeqStack(ss)){fprintf(stderr, "PopSeqStack pamter error\n");return 1;}ss->top--;return 0;
}
// 判斷是否為空
int IsEmpySeqStack(SeqStack *ss)
{return 0 == ss->top;
}
// 判斷是否為滿
int IsFullSeqStack(SeqStack *ss)
{return ss->tlen == ss->top;
}
// 獲得棧頂元素
DATATYPE *GetTopSeqStack(SeqStack *ss)
{if (NULL == ss || IsEmpySeqStack(ss)){fprintf(stderr, "GetTopSeqStack pamter error\n");return NULL;}return &ss->head[ss->top - 1];
}int GetSizeSeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "GetSizeSeqStack pamter error\n");return -1;}return ss->top;
}main.c
#include "./seqstack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int do_chekc(char *buf, SeqStack *ss, int num)
{int col = 1;DATATYPE data;while (*buf){DATATYPE *tmp = NULL;bzero(&data, sizeof(data));int c = *buf;switch (c){case '(':case '[':case '{':data.sym = c;data.linenum = num;data.colnum = col;PushSeqStack(ss, &data);break;case ')':tmp = GetTopSeqStack(ss);if (NULL == tmp){printf("read sym:%c ,line:%d col:%d\n", c, num, col);return 1;}if ('(' == tmp->sym){PopSeqStack(ss);}else{printf("read sym:%c ,line:%d col:%d or top sym:%c ,line:%d col:%d\n", c, num, col, tmp->sym, tmp->linenum, tmp->colnum);return 1;}break;case ']':tmp = GetTopSeqStack(ss);if (NULL == tmp){printf("read sym:%c ,line:%d col:%d\n", c, num, col);return 1;}if ('[' == tmp->sym){PopSeqStack(ss);}else{printf("read sym:%c ,line:%d col:%d or top sym:%c ,line:%d col:%d\n", c, num, col, tmp->sym, tmp->linenum, tmp->colnum);return 1;}break;case '}':tmp = GetTopSeqStack(ss);if (NULL == tmp){printf("read sym:%c ,line:%d col:%d\n", c, num, col);return 1;}if ('{' == tmp->sym){PopSeqStack(ss);}else{printf("read sym:%c ,line:%d col:%d or top sym:%c ,line:%d col:%d\n", c, num, col, tmp->sym, tmp->linenum, tmp->colnum);return 1;}break;}buf++;col++;}return 0;
}
int main(int argc, char **argv)
{SeqStack *ss = CreateSeqStack(100);FILE *fp = fopen("./hello.c", "r");if (NULL == fp){perror("fopen");return 1;}int num = 1;int ret = 0;while (1){char buf[256] = {0};if (NULL == fgets(buf, sizeof(buf), fp)){break;}ret = do_chekc(buf, ss, num);if (1 == ret){DestroySeqStack(ss);exit(1);}num++;}if (IsEmpySeqStack(ss)){printf("file ok\n");}else{DATATYPE *tmp = GetTopSeqStack(ss);printf("top sym:%c ,line:%d col:%d\n", tmp->sym, tmp->linenum, tmp->colnum);}DestroySeqStack(ss);// system("pause");return 0;
}
例如創建一個hello.c文件，其中文件少了一個）；
運行結果：
