CodeSky 代码之空

随手记录自己的学习过程

C 今天我们来聊聊栈与括号配对

2014-10-31 23:01分类: C评论: 0

很巧的是,之前这两者我都有说过,虽然当时没有深刻的认识,只是很新鲜的看到了之后写了两篇日志罢了,没想到终有一天,我还是和他们俩见面了,而且是合体版。

栈:关于栈的进出 括号匹配:C 一个程序查找基本语法错误

当然,这两篇和数据结构完全没有关系,大致上是科普中的科普了。

我们来看看这次的题目:

表达式中可能出现花括号{}、方括号[]、园括号(),从键盘输入一个表达式,检查左右括号配对情况,并输出结果。 例子:{[(…)(…)]…(…)}配对 而{[(…)(…)]…[(]…)}不配对

那么接下来,开始思考怎么写,其实主函数的想法很简单,只花了一会儿就想到了,通过把左括号压入栈,读取到右括号的时候出栈,合作愉快,相安无事。

果然难点还是在核心的数据结构部分,现在我们要思考的,一是如何实现,二是如何更好的实现。

老师的课件中,这次的资料并不算详细,但有了上一次的经验也就好上手了很多。

(这次有三个版本,两个顺序一个链式)

这次先用顺序栈来写了,虽然我觉得链栈更好,但一是被坑去写了这个,二是确实也需要尝试一下,于是:

1#define STACK_INIT_LENGTH 10
2
3typedef char ElemType;
4
5/* 定义顺序栈 */
6struct stack {
7    ElemType *buf;
8    size_t elem_size;       // 单个元素大小
9    size_t elem_count;      // 有多少个元素
10    size_t buf_count;       // 缓冲区大小
11};
12
13/* 初始化栈 */
14void InitStack(struct stack * s, size_t elem_size)
15{
16    s->elem_count = 0;
17    s->elem_size = elem_size;
18    s->buf_count = STACK_INIT_LENGTH;
19    s->buf = (ElemType *)malloc(s->buf_count * elem_size);
20}
21

可以来看看第一个版本的初始化,大致是把size,buttom的地址记住,然后往里塞就是了,这个数据结构原本可能是更好的,只是被我改怂了。

1/* 存入栈内 */
2void Push(struct stack *s, ElemType elem)
3{
4    CheckStackSize(s);
5    ElemType *p = s->buf;
6    size_t elem_count = s->elem_count;
7    s->elem_count++;
8
9    p[elem_count] = elem;
10}
11
12/* 从栈内弹出 */
13void Pop(struct stack *s, size_t count)
14{
15    if (s->elem_count >= count)
16    {
17        s->elem_count = s->elem_count - count;     // 现在的元素个数
18    }
19    else
20    {
21        s->elem_count = 0;
22    }
23}
24

Push函数大致涉及了指针的使用,把指针写成数组的形式,完全可以嘛,其实就是好看那么一点(比p+i的形式好看多了吧),Pop针对这一点,没想到什么合适的写法,于是就直接从elem_count中-1完成任务,之所以这么处理,是因为这样遍历的时候无法接触到它,虽然内存中还存在,但它已经不属于这个组织了,从某种意义上来说,算是Pop了,但是这样不好:1.无法自由变动大小(减小不能,只会不断增加大小) 2.并没有free掉。

因此当时我就意识到,顺序栈,尤其是这种形式的顺序栈,是相当有局限性的,能力有限,还是用链栈好。

当然,因为还没折腾够(没有尝试过课件上的方法,我尝试了顺序栈2):

1#define STACK_INIT_LENGTH 10
2
3typedef char ElemType;
4
5typedef struct Stack {
6    ElemType *base;         // 栈底
7    ElemType *top;          // 栈顶位置
8    size_t stackSize;      // 开辟内存空间的大小
9} Stack;
10
11void InitStack(struct Stack *s)
12{
13    s->base = (ElemType *)malloc(STACK_INIT_LENGTH * sizeof(ElemType));
14    s->top = s->base;
15    s->stackSize = STACK_INIT_LENGTH;
16}
17

这一套很标准的就是top-base,stackSize表示最大能容纳的元素的个数

之后一些函数,内容层面上而言大同小异,唯一不同的是,我们如何获取现在的元素个数来进行对比:指针的减法。

top-base相减的结果是元素的个数。(嗯还特地去复习了一下指针来着)

这样,我们就能通过指针来进行一系列的操作了,和上一个版本并无什么不同。(其实有些区别,在版本2中把栈改成队列将会让人感觉so easy)

值得注意的是: 这里使用了一个realloc函数,因此催生了:Why not realloc and so on... 总之就偷懒而言,realloc依然相当好,但从某种意义上而言,他也等同于malloc + memcpy + free(效率似乎更高)

三连贯的话:

1void list_set_size(struct list *l, size_t size)
2{
3    void *new_buf;
4
5    if (size == l->buf_count) {
6        return;
7    }
8    new_buf = (void *)malloc(size * l->elem_size);
9    memcpy(new_buf, l->buf, size < l-> buf_count ? size : l->buf_count * l->elem_size);
10    free(l->buf);
11    l->buf = new_buf;
12    l->buf_count = size;
13}
14

其次,我们再次注意这里:

1void CheckStackSize(struct Stack *s)
2{
3    if (s->stackSize == s->top - s->base)
4    {
5        SetStackSize(s, s->stackSize * 2);
6    }
7}
8

我们再次分离了几个功能,这样让其含义变得更清晰,检查,http://www.2zzt.com/,Like that.

剩下的,不再多做介绍,功能什么的,看代码,看函数名,就知道了。

那么接下来的就是链栈了,你会发现,和上一课有什么区别吗!——没有,不仅没有,反而更简单了不少,我不用再考虑排序,删去哪个元素这种问题,而是更加的简单粗暴。

这次主要是尝试着自己再写一次链表,依托函数作用,而不是依靠课件,争取早日随心所欲,当然有些失败。

1/**
2 * 元素出栈
3 * @param LinkStack s
4 * @return ElemType elem 返回出栈节点的data
5 */
6ElemType Pop(LinkStack s)
7{
8    struct Node *node = s, *p;
9    ElemType elem;
10    int i = 0;
11    int position = ElemCount(s);
12
13    if (!position)
14    {
15        return -1;  // 保护机制 如果栈为空
16    }
17
18    while (node->next && i < position - 1)
19    {
20        node = node->next;
21        i++;
22    }
23    p = node->next;
24    node->next = p->next;
25    elem = p->data;
26    free(p);
27    return elem;
28}
29

其他并无惊奇,有的干脆连函数名我都没变,Pop函数无非也就是功能的删减版,让人觉得费了些心思,其实是在玩一个名叫hacked的游戏时,发现他的Push函数会返回出栈的那个元素值,感觉还是个不错的功能,回忆了一下大致都有这个功能的,于是就加了个return ,有了return ,那自然要考虑空栈也得返回,于是就推了个-1进去。


OK这里扯完了,终于我们可以扯扯我们的main函数了。

这次我们多用了两个头文件:

1#include <string.h>
2#include <time.h>
3

之后会有介绍。

inputModecommandMode标记,true or false,我很喜欢玩这套,毕竟好判断嘛。

后来想了想,学着vi这种玩样儿用命令来保存之类的感觉也不错,然后嫌装逼值不够,加了个错误日志。

通过lineNum记录行数,breakLine标记错误的行数方便之后的输出。

主要是输出文件和时间这两点,新玩样儿,翻了书之后果断写之,没想到没啥意外,顿时让我感到很高兴:

1    FILE *program_data, *error_log;
2    program_data = fopen("program_data.log", "a+");
3    error_log = fopen("error_log.log", "a+");
4
5    fprintf(program_data, "=====");
6

定义文件指针,打开文件(读写模式为写入不覆盖而是追加在最后,如果没有文件则创建)

1putc(elem, program_data);
2

基本等同于putchar(),不过这个是输出在文本中的。

1    fclose(program_data);
2    fclose(error_log);
3

一切完毕,关闭文件吧。

然后是时间:

1    time_t t;   // 定义一个时间变量
2    t = time(NULL); // 获取时间
3    char *time, *p;
4    time = ctime(&t);
5    p = time;
6

ctime函数会生成一个带换行的时间戳,导致输出不得不选择:

1    while (p && *p != '\n')
2    {
3        putc(*p, program_data);
4        putc(*p, error_log);
5        p++;
6    }
7

类似于这种方式。

这次清屏还使用了一个system("cls"),早有耳闻,现在一试,就这个Feel倍儿爽。

总之,这次并无惊奇,上一次的缩减罢了。

评论 (0)