【0】表ADT 1）intro：我們把 形如 A1, A2, A3, ..., An 的結構稱為表； 2）表的實現： 數組（循環數組） 或 鏈表 或 雙鏈表 或 循環鏈表實現； 3）表的插入，刪除操作可以在任意位置上進行；
【1】棧（基于表） 1）intro：棧是限制插入和刪除只能在一個位置上進行的的表； 2）棧的實現： 數組實現 或 鏈表實現； 3）棧的應用 應用荔枝1）檢驗代碼的平衡符號：每一個 括號（圓括號，中括號，花括號） 都要一一對應； Attention）stack.h如下： #include <stdio.h> #include <malloc.h>#define ElementType char #define ERROR(str) printf(str)struct Stack; typedef struct Stack *Stack;struct Stack {int size;ElementType* head;int top; };int isFull(Stack s); int isEmpty(Stack s); Stack initStack(int size); void push(Stack s, ElementType c); void pop(Stack s, ElementType *e);int isFull(Stack s) {return s->size == s->top ? 1 : 0; }int isEmpty(Stack s) {return 0 == s->top ? 1 : 0; }Stack initStack(int size) {Stack s = (Stack)malloc(sizeof(struct Stack));if(s==NULL){ERROR("error: failed initStack() for there is no spare space.\n");}else {s->size = size;s->top = 0;s->head = (ElementType*)malloc(sizeof(ElementType) * size);if(s->head==NULL){ERROR("error: failed initStack() for there is no spare space.\n");return NULL;}}return s; }void push(Stack s, ElementType c) {if(!isFull(s)){s->head[s->top++] = c;} else{printf("%s", "failed pushing for stack is full.");} }void pop(Stack s, ElementType *e) {if(!isEmpty(s)){*e = s->head[--s->top];}else{*e = ' ';printf("%s", "failed poping for stack is empty.");} } </pre><pre code_snippet_id="1797122" snippet_file_name="blog_20160731_3_2765700" name="code" class="cpp">#include "stack.h"// check whether the grammar defined in given file is correct or not. int checkFile(Stack s) {FILE *fp;ElementType c;ElementType popc;fp = fopen("D:\\classical_books\\datastructure_alg\\source_code\\chapter3\\review_for_job\\p52_check_balanced_char\\temp.txt", "r");// only test for round bracket '()', bracket '[]', brace'{}'.// do you know the meanings of open brace '{' and close brace '}'.while((c=getc(fp)) != EOF){if(c == '(' || c == '[' || c == '{'){push(s, c);}else if(c == ')' || c == ']' || c == '}'){pop(s, &popc);if(c==')' && popc!= '('){return 0;}else if(c==']' && popc!= '['){return 0;}else if(c=='}' && popc!= '{'){return 0;}}}return 1; }int main() {Stack s;int result; s = initStack(1000);if(s==NULL){return -1;}result = checkFile(s);printf("%d \n", result);return 0; } 應用荔枝2）計算后綴表達式的值：step1）將中綴表達式轉為 后綴表達式；step2）然后求 后綴表達式的值；
Attention）infix2postfix.h 見應用荔枝3； #include "infix2postfix.h" void computeExpr(Stack s, ElementType *postfix, int length) {int i = 0;char c;ElementType num1, num2, result;for(;i<length;i++){c = postfix[i];if(isOperator(c) == -1)// c is an operand.{push(s, c-48);}else if(isOperator(c) != -1) // c is an operator.{pop(s, &num1);pop(s, &num2); switch(c){case '+': result = num1+num2;break;case '-': result = num1-num2;break;case '*': result = num1*num2;break;case '/': result = num1/num2;break;}push(s, result);}}pop(s, &result); printf("final computing result is %d \n", result); }int main() {Stack s; ElementType output[255];int length;s = initStack(1000);if(s==NULL){return -1;}length = infix2postfix(s, output); //switch infix into postfix.printChatArray(output, length);// compute postfix expr.free(s);s=initStack(1000);computeExpr(s, output, length);return 0; }

應用荔枝3）中綴表達式：?中綴轉后綴表達式；
stack.h 同上 && infix2postfix.h 如下： #include "stack.h" #include "math.h"void printChatArray(ElementType* array, int size); int isOperator(ElementType c); int checkPriority(int p1, int p2); int infix2postfix(Stack s, ElementType *output);// just print array. void printChatArray(ElementType* array, int size) {int i=0;for(;i<size; i++){putchar(array[i]);}printf("\n\n"); }// check whether the char is operator or not. // if true returns priority with array index ,otherwise return -1. int isOperator(ElementType c) { int i = 0;char priorities[] = {'(', ' ', '+','-',' ','*','/'};int size = 7;for(; i<size; i++){if(c==priorities[i]){return i;}}return -1; } // 0 means p1.priority == p2.priority // 1 > // -1 < int checkPriority(int p1, int p2) {if(p1-p2==1 || p1-p2==-1 || p1-p2==0){return 0;}else if(p1-p2>1){return 1;}else if(p1-p2 < -1){return -1;} }// transmit infix into postfix. // attention for operands not being pushed into stack. int infix2postfix(Stack s, ElementType *output) { ElementType c, popc, topc; int i = 0;int p1, p2; printf("%s", "input the expr: ");while((c=getchar()) != '\n'){if(c=='(') // when the char is ( or ){push(s, c);}else if(c==')'){while(!isEmpty(s) && (topc=getTop(s))!='('){pop(s, &popc);output[i++] = popc; }if(topc=='('){pop(s,&popc);}} // when the char is ( or ) over.else if(isOperator(c) == -1) // c is an operand.{output[i++] = c;}else if((p1=isOperator(c)) != -1) // c is an operator.{if(isEmpty(s)) // if the stack is empty.{push(s, c);}else // if the stack is not empty.{ while(!isEmpty(s)){topc = getTop(s);// after that, check priority between c and topc.p2 = isOperator(topc);if(checkPriority(p1,p2) != 1) // p1.priority <= p2.priority, then pop operand under p2 into output array.{pop(s, &popc);output[i++] = popc;}else{ break;}} push(s, c);} }}while(!isEmpty(s)) // pop surplus elements into output array.{pop(s, &popc);output[i++] = popc; } return i; }#include "infix2postfix.h" int main() {Stack s; ElementType output[255];int length;s = initStack(1000);if(s==NULL){return -1;}length = infix2postfix(s, output); //switch infix into postfix.printChatArray(output, length);return 0; }

【2】隊列（基于表） 1）intro：隊列是插入在一端，而刪除在另一端的表； 2）隊列的實現：數組實現 或 ?循環數組（隊列）實現； 3）（循環隊列）代碼如下： #include <stdio.h> #include <malloc.h>#define ElementType int #define Error(str) printf("\nerror: %s", str)struct Queue; typedef struct Queue* Queue;// 循環隊列的數據結構. struct Queue {int capacity;int front;int rear;int size;ElementType* array; };Queue initQueue(int capacity); int isFull(Queue queue); void enQueue(Queue queue, ElementType e); int isEmpty(Queue queue); ElementType deQueue(Queue queue); void printQueue(Queue queue);// init queue wit capacity. Queue initQueue(int capacity) {// allocate memory for queue.Queue queue = (Queue)malloc(sizeof(struct Queue)); if(queue==NULL){Error("failed initQueue() for out of space.");return NULL; } queue->capacity = capacity;queue->front = 0;queue->rear = 0;queue->size = 0;// allocate memory for queue->array.queue->array = (ElementType*)malloc(capacity * sizeof(ElementType));if(queue->array == NULL){Error("failed initQueue() for out of space.");return NULL;} return queue; }// judge whether the queue is full or not. int isFull(Queue queue) {return queue->size == queue->capacity ? 1 : 0; }// 進隊列，滿時不進. void enQueue(Queue queue, ElementType e) { if(isFull(queue)){Error("failed enQueue() for the queue is full.");return ;} queue->array[queue->rear++ % queue->capacity] = e;queue->size++; }// judge whether the queue is empty or not. int isEmpty(Queue queue) {return queue->size == 0 ? 1 : 0; }// 出隊列，空時不出. ElementType deQueue(Queue queue) {int temp;if(isEmpty(queue)){Error("failed deQueue() for the queue is empty.");return -1;}temp = queue->array[queue->front++ % queue->capacity];queue->size--;return temp; }// 打印隊列 void printQueue(Queue queue) {int i, index;ElementType* array = queue->array;printf("\n");for(i=0; i<queue->size; i++){index = (queue->front + i) % queue->capacity;printf("%d ", array[index]);}printf("\n"); }// 打印隊列所在數組 void printArray(Queue queue) {int i;printf("\nelements in queue->array from index 0 are as follows: ");for(i=0; i<queue->size; i++){printf("%d ", queue->array[i]);}printf("\n"); }#include "queue.h"void main() {ElementType array[] = {3, 4, 6, 1, 2, 0, 10, 8, 9};Queue queue;int capacity=6;int i;queue=initQueue(capacity); // 初始化隊列if(queue == NULL){return ;}printf("\nlet {3, 4, 6, 1, 2, 0, 10, 8, 9} enter queue.\n");for(i=0; i<9; i++){enQueue(queue, array[i]); // 讓元素進隊列}printf("\n\nthe elements in queue are as follows: ");printQueue(queue);// 讓元素出隊列deQueue(queue);deQueue(queue);deQueue(queue);enQueue(queue, array[6]);enQueue(queue, array[7]);enQueue(queue, array[8]);printf("\n\nafter 3 dequeue operations and enQueue({10,8,9}) ,the elements in queue are as follows: ");printQueue(queue);printArray(queue); }

總結

以上是生活随笔為你收集整理的ReviewForJob(3)表、栈和队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。