FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

[旧文整理]C语言打造通用数据结构_ArrayStack

FunctionGHW posted @ 2013年4月20日 16:30 in 数据结构 with tags Stack 数据结构 C , 2366 阅读

记得某本书上好像写过:C语言设计的理念是: 小即是美。不管他美不美吧, 反正他确实是个很小巧的语言。 也许就是因为"小"吧,在使用C的时候很多东西都是需要自己去代码实现,比如一些常用的数据结构, 真是烦透了。但是自己写的往往都是针对特定数据类型的,不够通用。可惜C没有泛型, 如果为每一个类型单独实现一套数据结构的库,估计是要疯掉了。看过一些库函数的声明之后, 得到了一点启发——把所有类型的数据都看作字节块,从而模拟泛型。 不过这样数据的类型在存取的过程中也就"丢失"了,因此我们需要自己去处理类型转换问题。 当然,为了实现通用性,我想"泛型"的性能可能会低一些。

之前学习数据结构的时候,实现过一种用只保存指针的栈, 不过稍微想想就会觉得容易出问题。这次我重新写的是一个"泛型"栈,数组实现,接口定义如下:

#include <stddef.h>

#ifndef BYTE
#define BYTE unsigned char
#endif

typedef struct
{
    size_t size;
    size_t top;
    size_t elemt_size;
    BYTE* data;
} ArrayStack;

//Create a new array stack that has the specified size;
ArrayStack* new_arystk(size_t size, size_t elemt_size);

//Get the number of elements contained in the stack;
size_t arystk_count(const ArrayStack* stack);

//Get the maximum number of elements that the stack could contain currently;
size_t arystk_size(const ArrayStack* stack);

//Get the size of each element in the stack;
size_t arystk_elemt_size(const ArrayStack* stack);

//Check if the stack is full;
int arystk_is_full(const ArrayStack* stack);

//Check if the stack is empty;
int arystk_is_empty(const ArrayStack* stack);

//Insert an element into the top of the stack;
void arystk_push(ArrayStack* stack, const BYTE* elemt);

//Get the top element of the stack;
BYTE* arystk_peek(const ArrayStack* stack);

//Remove the top element, but don't return it;
void arystk_pop(ArrayStack* stack);

//Get the top element and remove it;
BYTE* arystk_peek_and_pop(ArrayStack* stack);

//Delete all elements of the stack;
void arystk_empty(ArrayStack* stack);

//Disopse the stack;
void arystk_dispose(ArrayStack* stack);

//Double the size of the stack;
void arystk_double_size(ArrayStack* stack);


                

我自己试着写了一个实现,代码放在Github上,这里就省略了。 在编码实现的过程中,暴露出一些问题,觉得以后都很有必要注意下。

首先,一个可谓是老生常谈的问题——算术溢出(Arithmetic Overflow)。刚开始学习编程的时候不就写过加减乘除吗? 然而,尽管知道算术溢出的后果,但是自己在写代码的时候很少去考虑这个问题,一直认为没必要想那么复杂, 可惜因此形成了惯性思维,等到写一些"正式的代码"的时候,根本想不到这方面的东西,即使代码因此而出错, 估计也要查半天吧。或许我们根本就忘了有这回事,不过这也看出来,坏毛病都是自己惯出来的<T_T>。

在用malloc(size_t size);的时候, 因为size是根据输入计算来的,偶然想到一个问题,如果运算结果是0会怎样?malloc(0)返回什么?NULL? Not NULL?很自然地想,分配0字节的空间"不太正确"吧,所以函数应该会返回NULL。 但是C标准的说法却是:由编译器自己决定,即行为未定义!我的第一反应就是,这真是坑爹啊, 要0字节大小的空间有什么用啊?不能理解。在加上这个检查之后,才意识到,我以前有注意过malloc(0)吗? 似乎一次都没有。但是输入是无符号整数,应该很容易想到输入可能是0的情况吧。为什么没有想过呢? 我想这估计是态度问题吧,自己不够严谨,考虑不够全面,写代码也太随意。

最后,在着手写代码实现的时候,基本是写到哪才想到哪,当发现自己错的时候, 又急急忙忙的修改,最后,思路彻底凌乱了。这个问题其实我已经遇到很多次了,有时候需要完全重写一次, 没有重视过,总是喜欢一开始就不停地写啊写,而不是在写代码之前先详细的设计和思考。 也许很像"胸有成竹"这个词的意思吧,程序员的境界应该是:在写代码之前,头脑中就已经有了完整程序。先思考再编码, 思路混乱,必然代码也混乱,我也算是有点体会到了。

旧文链接

原来写过两次栈,一次是使用int类型的实现,一次是使用指针类型的失败"泛型"。
My ADT Stack...简单数组实现
My New ADT Stack 数组实现[修改]

Liwovosa 说:
2021年4月21日 18:22 Excellent blog! I found it while surfing around on Google. Content of this page is unique as well as well researched. Appreciate it. click here
jackjohnny 说:
2021年6月17日 22:58

I havent any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. 먹튀사이트

jackjohnny 说:
2021年6月24日 17:43

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks... https://www.towelsforthebeach.com/

jackjohnny 说:
2021年6月26日 22:02

It was wondering if I could use this write-up on my other website, I will link it back to your website though.Great Thanks. 토토사이트

jackjohnny 说:
2021年6月29日 18:43

I was reading some of your content on this website and I conceive this internet site is really informative ! Keep on putting up. インド緊急ビザ

arkseo 说:
2021年7月05日 13:09

Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post. become a payment service provider

jackjohnny 说:
2021年7月05日 19:19

That is really nice to hear. thank you for the update and good luck. สล็อต

arkseo 说:
2021年7月06日 13:02

i read a lot of stuff and i found that the way of writing to clearifing that exactly want to say was very good so i am impressed and ilike to come again in future.. best free Plagiarism Checker Tool

jackjohnny 说:
2021年7月11日 20:14

Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. 토토사이트


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter