<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                轉載請注明出處 http://blog.csdn.net/pony_maggie/article/details/30802249 作者:小馬 作為一種常用的數據結構, 了解棧對于算法的學習是非常必要的。棧有先進后出的特點,棧底指向數據表中的第一個元素,棧頂指向最后一個元素的下一個位置。如下圖所示: ![](https://box.kancloud.cn/2016-06-13_575e925892318.jpg) 棧和線性表類似,也是有兩種存儲結構,分別為順序結構和鏈式結構。大部分情況下,棧使用前者,這和它的使用場景有關,因為通常情況下我們不會對棧進行頻繁地,隨機地插入,刪除操作。下面是我用順序結構實現的棧,這個棧有個特點就是它的通用性,因為我并沒有限制它所存儲的數據類型,代碼如下: ~~~ //void**其為雙指針,意味入棧和出棧的將只是對應數據的地址,而不需要對數據本身進行拷貝 typedef struct { char *base; char *top; int elementSize; //元素所點字節大小 int stackSize; //當前已分配的空間(注意不是元素的實際個數) }ponyStack; int InitStack(ponyStack *stack, int elementSize) { stack->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char)*elementSize); if (!stack->base) { return RET_ERROR; } stack->top = stack->base; //為空 stack->stackSize = STACK_INIT_SIZE; stack->elementSize = elementSize; return RET_OK; } int ClearStack(ponyStack *stack) { stack->top = stack->base; return RET_OK; } bool IsEmptyStack(ponyStack stack) { if (stack.top == stack.base) { return true; } return false; } ~~~ 這里沒有貼出全部的代碼,更完整的可以從最后的地址那里下載。注意elementSize,這個是棧可以做到通用的核心。不理解的可以再研究一下代碼。 看一個棧的使用示例,數制轉換。十進制轉八進制。例如(1348)十進制= (2504)八進制,它基于如下的原理: N ? ? ? ? ? ? N/8???????????? N%8 1348 ? ? ? ?168 ? ? ? ? ? ? ? 4 168 ? ? ? ? ? 21 ? ? ? ? ? ? ? ?0 ?21 ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? ?5 ?2 ? ? ? ? ? ? ? 0 ? ? ? ? ? ? ? ? ? 2 所以很明顯,N不斷的除8,每次的余數就是結果的其中一個因子,注意先出來的因子是低位的數,可以考慮用棧來保存每次取余的結果,那么出棧的順序就是實際的結果順序。代碼很簡單: ~~~ int decimalToOctonary(int decimalNumber) { double octNumber = 0; int nCount = 0; int nTemp = 0; ponyStack numberStack; InitStack(&numberStack, 4); while (decimalNumber) { nTemp = (int)decimalNumber%8; Push(&numberStack, &nTemp); decimalNumber = decimalNumber/8; } nCount = CountOfStack(numberStack);//元素個數也就是位數 while(!IsEmptyStack(numberStack)) { Pop(&numberStack, &nTemp); octNumber += (nTemp*pow(10.0, --nCount)); } DestroyStack(&numberStack); return (int)octNumber; } ~~~ 再來看一個行編輯程序的示例,用戶在終端輸入字符,完成后保存用戶的數據區, 因為在輸入的過程中可能出錯,需要修改,所以不可能每輸入一個字符就存入數據區。比較好的做法是先在內存里開一個輸入的緩沖區,當用戶輸入完成一行后,再存入數據區。在行內可以修改。例如,當用戶發現剛輸入的一個字符是錯的之后,可以再輸入一個'#',表示前一個字符是錯的,如果發現當前行輸入的錯誤太多,可以輸入一個退行符'@',表示當前行都無效,舉個例子: whli#ilr#e(s#*s) outcha@putchar(*s=#++) 實際有效的字符是這樣的: while(*s) putchar(*s++) 可以把內存里這個輸入緩沖區定為棧,正常情況下每輸入一個字符直接入棧,如果發現字符是'#',就棧頂pop一次,如果是'@'就清空棧.代碼實現如下: ~~~ void lineEdit() { char ch = 0; char chTemp = 0; ponyStack lineStack; InitStack(&lineStack, 1); ch = getchar(); while (ch != EOF) { while (ch != EOF && ch != '\n') { switch (ch) { case '#': Pop(&lineStack, &chTemp); break; case '@': ClearStack(&lineStack); break; default: Push(&lineStack, &ch); break; } ch = getchar(); } writeToFile(lineStack);//存數據 ClearStack(&lineStack);//準備接收下一行 if (ch != EOF) { ch = getchar(); } } DestroyStack(&lineStack); } ~~~ 最后一個例子是表達式求值的算法,這個在計算器應用中比較多用到。比如, 求+4*9-16/4 建兩個棧,一個存操作數,一個存運算符.為簡單起,在運算符棧會預先存一個'#',表示表達式開始,然后以'#'結束。運算規則是這樣的: 輸入字符,如果是'#',則結束,如果是操作數,直接進操作數棧。如果是運算符,則跟棧頂的運算符比較,如果棧頂的優先級低,直接進棧,接收下一字符,如果相等,脫括號,接收下一個字符,如果棧頂的優先級高,pop兩個操作數,pop棧內操作符,運算,然后運算的結果進操作數棧。當前運算符繼續跟棧頂比較。 要實現這個代碼,首先要有一個表格,存儲我們操作符之間的優先級關系,如下所示: ~~~ static char priority[7][7] = { '>','>','<','<','<','>','>', // + '>','>','<','<','<','>','>', // - '>','>','>','>','<','>','>', // * '>','>','>','>','<','>','>', // / '<','<','<','<','<','=',' ', // ( '>','>','>','>',' ','>','>', // ) '<','<','<','<','<',' ','=', // # };// + - * / ( ) # ~~~ 然后實現根據上面的思路,實現起來就比較容易了: ~~~ int evaluateExpression() { char chCurrent = 0; char chOnTop = 0; char chTemp = 0; int nResult = 0; int nTemp = 0; int a,b; int nOperandFlag = 0; ponyStack operatorStack;//運算符棧 ponyStack operandStack; //操作數棧 InitStack(&operatorStack, 1); chTemp = '#'; Push(&operatorStack, &chTemp); InitStack(&operandStack, 4); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); while ((chCurrent != '#')||(chOnTop != '#')) { if (!isOperator(chCurrent))//是操作數,要考慮多位整型數的情況 { nTemp = nTemp * (int)pow(10.0, nOperandFlag); nTemp += (int)(chCurrent - '0'); chCurrent = getchar(); nOperandFlag = 1; } else { if (nOperandFlag == 1) { Push(&operandStack, &nTemp);//操作數輸入結束,入棧 nOperandFlag = 0; nTemp = 0; } GetTop(operatorStack, &chOnTop); switch (precede(chOnTop, chCurrent))//比較優先級 { case '<': //棧頂的優先級小 Push(&operatorStack, &chCurrent); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); break; case '=': //脫括號,接收下個字符 Pop(&operatorStack, &chTemp); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); break; case '>': //棧頂的優先級大,出棧運算,結果入棧 { Pop(&operandStack, &a); Pop(&operandStack, &b); Pop(&operatorStack, &chTemp); nTemp = operate(a, chTemp, b); Push(&operandStack, &nTemp); nTemp = 0;//重置 GetTop(operatorStack, &chOnTop); } break; default: break; } } } GetTop(operandStack, &nResult); DestroyStack(&operatorStack); DestroyStack(&operandStack); return nResult; } ~~~ 代碼下載地址: https://github.com/pony-maggie/StackDemo 或 http://download.csdn.net/detail/pony_maggie/7499167
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看