精选文章

Android下使用TCPDUMP抓包Wireshark分析数据 如果想分析Android下某个APP的网络数据交互,需要在Android手机上抓包,最常用的抓包工具非tcpdump莫属,用tcpdump生成Wireshark识别的pcap文件,然后将pcap文件下载到电脑上,用电脑上的Wireshark加载pcap文件,通过Wireshark分析tcpdump抓取的数据。...

继续阅读

Mac下部署Android开发环境附加NDK 作为开发者,我们深有体会,不管是进行什么开发,为了部署开发环境,我们往往需要折腾很长时间、查阅很多资料才能完成,而且这次折腾完了,下次到了另一台新电脑上又得重新来过,整个部署过程记得还好,要是不记得又得重新开始,而且遇到Android这种GFW阻隔了开发资源下载链接的环境部署,又尤其浪费时间。所以这也是我写下这篇教程的初衷跟动力源泉,希望大家参考了这篇教程以后可以轻轻松松在Mac系统下将Android环境部署好。...

继续阅读

稍顯嚴肅的台中 坦白說,留在腦海中的台中影像並不多,來台灣之前在Booking上只訂到了台中的一家青旅,第一次住青旅有些不習慣,幹什麼都放不開。 同屋的一個男生是台灣人,不過一年中四分之三的時間在上海跟北京,這麼說來跟我還是比較有共同話題的。得之我準備花15天的時間環島,覺得太倉促了,他們大學時期花一個半月的時間也不見得能將台灣島給逛完。我只能無奈地表示,兩岸允許的簽證時間有限,自己的空閒時間更有限,只能用打卡式的旅行了,我深知正真地旅行應該慢下來,融入當地的環境,感受他們的風土人情,但第一次只能這樣作罷,以後換成民進黨上台,形勢會變成怎樣還不得而知,能否再過來還是個未知數。而我一向信奉的人生格言是秉燭夜遊,活在當下,所以,理解自己吧。...

继续阅读

為之留戀的新竹 來新竹之前本沒有對她有過高的期待,慢慢對她加分要從桃園火車站出發前往新竹開始。 在桃園火車站的候車月台上,有醒目的旅遊資料發放處,這上面的擺放的全是新竹的旅遊宣傳資料,關鍵的是資料做得非常簡潔易懂,而接下來一天的新竹之行就全部是依據這份寶典的指引來完成的。...

继续阅读

從桃園開始台灣之行 初到台灣恰逢華夏銀行系統升級,特意準備的華夏銀聯卡在桃園機場沒能派上用場,只好用建行在機場5000塊,算下來是很不划算的,但是沒辦法,誰叫我出機場就得花錢呢。 從機場打車到桃園的酒店,花了將近六百塊新台幣,到酒店時五點多,天已經漸亮了,洗漱完等到七點吃過早餐就開始補覺囉,一覺醒來已是中午,帶著換下來的衣服外出找自助洗衣店,順便覓食。...

继续阅读

  • Prev
  • Next

栈及其应用实例

文章分类 : C语言, 数据结构

1、是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶,表头端称为栈底。栈的修改是是按照后进先出的原则进行的,因此,栈又成为后进先出(last in first out)的线性表(简称LIFO结构)。

2、当栈顶指针跟栈底指针相同时说明栈空了,因此非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

3、以下是栈的顺序存储表示以及基本操作的算法描述:

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct {
    SElemType *base; //在栈构造之前和销毁之后,base的值为NULL
    SElemType *top; //栈顶指针
    int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack;
status InitStack(SqStack &S)
{
    //构造一个空栈
    S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if (!S.base) exit(OVERFLOW); //存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status GetTop(SqStack S, SElemType &e)
{
    //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
    if (S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;
}
Status Push(SqStack &S, SElemType e)
{
    //插入元素e为新的栈顶元素
    if (S.top -S.base >= S.stackszie) //栈满,追加存储空间
    {
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        if (!S.base) exit(OVERFLOW); //存储分配失败
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
    //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
    if (S.top == S.base) return ERROR;
    e = * --S.top;
    return OK;
}

4、对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数,用C语言伪代码实现如下:

void conversion()
{
    InitStask(S); //构造空栈
    scanf("%d", N);
    while (N)
    {
        Push(S, N%8);
        N = N/8;
    }
    while (!StackEmpty(S))
    {
        Pop(S,e);
        printf("%d", e);
    }
}

5、括号匹配的检查可以用栈来实现,在算法中设置一个栈,每读入一个括号,若是右括号,则或者使置于栈顶的最急迫的期待得以消解,或者是不合法的情况;若是左括号,则作为一个新的更急迫的期待压入栈中,自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。在算法的开始和结束时,栈都应该是空的。

6、行编辑程序可以用栈来实现,设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户缓冲区。允许用户输入出差错,并在发现有误时可以及时更正。例如,当用户发现刚刚键入的一个字符是错的时,可以补进一个退格符”#“,以表示以前一个字符无效;如果发现当前键入的行内差错较多或难以补救,则可键入一个退行符”@”,以表示当前行中的字符无效。例如从终端接受了这样两行字符:

whli##ilr#e(s# *s)
outcha@putchar( *s=# ++ );

则实际有效的是下面两行:

while( *s)
putchar( *s ++ );

为此,可设这个输入缓冲区为一个栈结构,每当从终端接受了一个字符之后作如下判别:如果它既不是退格符也不是退行符,则将该字符压入栈顶;如果是一个退格符,则从栈顶删去一个字符;如果它是一个退行符,则将字符栈清为空栈。上述过程可用C语言伪代码实现如下:

void LineEdit()
{
    //利用字符栈S,从终端接收一行并传送至调用过程的数据区。
    InitStack(S); //构造空栈S
    ch = getchar(); //从终端接收第一个字符
    while (ch != EOF) //EOF为全文结束符
    {
        while (ch != EOF && ch != '\n')
        {
            switch (ch)
            {
                case '#': Pop(S, c); break; //仅当栈非空时退栈
                case '@': ClearStack(S); break; //重置S为空栈
                default: Push(S, ch); break; //有效字符进栈,未考虑栈满情况
            }
            ch = getchar(); //从终端接收下一个字符
        }
        save(S); //将栈底到栈顶的栈内字符传送至调用过程的数据区
        ClearStack(S); //重置S为空栈
        if (ch != EOF) ch = getchar();
    }
    DestroyStack(S);
}


除非注明,文章均为CppLive 编程在线原创,转载请注明出处,谢谢。

本文地址:http://www.cpplive.com/html/1210.html

无觅相关文章插件,快速提升流量