搜索到
40
篇与
的结果
-
栈的应用三——后缀表达式求值 // 将字符转换成数字 double readNumber(char c[],int *i) { double x = 0.0; int k = 0; while (c[*i] >= '0' && c[*i] <= '9') x = x*10 + (c[(*i)++] - '0'); if(c[*i] == '.') { (*i)++; while (c[*i] >= '0' && c[*i] <= '9') { x = x*10 + (c[(*i)++] - '0'); k++; } } while (k != 0) { x = x/10.0; k--; } return x; } // 后缀表达式求值 double cal(char c[]) { double op[MAX_SIZE] = {}; // 操作数栈 int top = 0; // 栈顶指针 double left,right; // 左、右操作数 int i = 0; while (c[i]) { if(c[i] >= '0' && c[i] <= '9') op[top++] = readNumber(c,&i); else if(c[i] == ' ') i++; else { right = op[--top]; left = op[--top]; if(c[i] == '+') op[top++] = left + right; else if(c[i] == '-') op[top++] = left - right; else if(c[i] == '*') op[top++] = left * right; else op[top++] = left / right; i++; } } return op[--top]; } int main() { char c[] = "6/3+(5*6-2*7)/4"; char r[MAX_SIZE]={}; convert(c,r); int i=0; while (r[i]) printf("%c",r[i++]); printf("\n"); printf("%f",cal(r)); return 0; } -
栈的应用二——中缀转后缀表达式 使用以上栈的声明和基本操作，只需把typedef int dataType;中的int改为char即可。// 将字符分类 int classify(char c) { switch (c) { case '(': case ')': return 2; // 表示界限符 case '+': case '-': case '*': case '/': return 3; // 表示运算符 default: return 1; // 表示操作数0-9 } } // 将运算符划分优先级 int priority(char c) { switch (c) { case '+': case '-': return 1; case '*': case '/': return 2; } } // 中缀表达式转后缀表达式的机器计算 /** 初始化一个栈，用于保存暂时无法确定运算顺序的运算符，依次扫描元素直到结束， * 1.遇到操作数直接加入后缀表达式； * 2.遇到左界限符则入栈，遇到右界限符则依次弹出栈中的运算符加入表达式， * 直到弹出左界限符，但左界限符不加入表达式； * 3.遇到运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式， * 直到弹出左界限符或栈空。然后再把当前运算符入栈。 * 4.当扫描的中缀表达式结束时，栈中的运算符依次出栈加入后缀表达式。 **/ void convert(char m[], char r[]) { int i=0,j=0,type; seqStack stack; init(&stack); while (m[i]) { type = classify(m[i]); if(type == 1) // 扫描到数字时 { r[j++] = m[i]; } else if(type == 2) // 扫描到界限符 { if(m[i] == '(') push(&stack,m[i]); else { while (!empty(stack)) { if(read(stack) != '(') { r[j++] = read(stack); pop(&stack); } else { pop(&stack); break; } } } } else // 扫描到运算符 { while(!empty(stack)&&read(stack)!='('&&classify(read(stack))==3) { if(priority(read(stack)) >= priority(m[i])) { r[j++] = read(stack); pop(&stack); } else break; // 如果栈中运算符优先级较低则退出循环 } push(&stack,m[i]); r[j++] = ' '; // 每两个数之间加一个分隔符 } i++; } while (!empty(stack)) { r[j++] = read(stack); pop(&stack); } } int main() { char c[] = "6/3+(5*6-2*7)/4"; char r[MAX_SIZE]={}; convert(c,r); int i=0; while (r[i]) { printf("%c",r[i++]); } return 0; }
-
栈的应用一——括号匹配 // 括号匹配 int matchBracket(char c[]) { seqStack stack; init(&stack); int i = 0; while (c[i]) { switch (c[i]) { case '{': case '[': case '(': push(&stack,c[i]);break; case '}': if(!empty(stack) && read(stack) == '{') { pop(&stack); break; } else return 0; case ']': if(!empty(stack) && read(stack) == '[') { pop(&stack); break; } else return 0; case ')': if(!empty(stack) && read(stack) == '(') { pop(&stack); break; } else return 0; } i++; } return empty(stack); // 匹配结束后栈空则匹配成功，否则失败。 } int main() { char c[] = "{[()]}"; if(matchBracket(c)) printf("匹配成功！\n"); else printf("匹配失败！\n"); return 0; }
-
顺序栈及其实现 #include <stdio.h> #include <stdlib.h> typedef int dataType; #define MAX_SIZE 100 // 2.3 顺序栈(设定top=0为空栈) typedef struct { dataType a[MAX_SIZE]; int top; }seqStack; // 1.初始化(置空)栈 void init(seqStack *st) { st->top = 0; } // 2.判断栈是否为空 int empty(seqStack st) { return st.top ? 0:1; } // 3.读栈顶元素 dataType read(seqStack st) { if(empty(st)) { printf("栈是空的!\n"); exit(1); } return st.a[st.top-1]; } // 4.元素x进栈 void push(seqStack *st, dataType x) { if(st->top == MAX_SIZE) { printf("栈已满，无法进栈！\n"); exit(1); } st->a[st->top] = x; st->top+=1; // 或st->top++; } // 5.出栈 void pop(seqStack *st) { if(!st->top) { printf("栈已空，无法出栈！"); exit(1); } st->top-=1; // 或st->top--; } int main() { seqStack st; // 定义栈 init(&st); // 初始化栈 dataType x = 1; push(&st,x); // 数据元素x进栈 printf("%d\n", read(st)); // 读栈顶元素 pop(&st); // 出栈 pop(&st); // 出栈 return 0; }
-
顺序表及其实现 #include <stdio.h> #include <stdlib.h> typedef int dataType; #define MAX_SIZE 100 // 2.2.2 顺序表(顺序存储的线性表) typedef struct { dataType a[MAX_SIZE]; int size; }seqList; // 1.顺序表的初始化/置空表 void init(seqList *slt) { slt->size = 0; } // 2.在顺序表尾部追加值为x的元素 void append(seqList *slt,dataType x) { if(slt->size == MAX_SIZE) { printf("顺序表是满的，无法追加！\n"); exit(1); } slt->a[slt->size++] = x; } // 3.判断顺序表是否为空 int empty(seqList slt) { return !slt.size; } // 4.打印顺序表各结点的值 void display(seqList slt) { if(empty(slt)) printf("顺序表是空的！\n"); else { for (int i = 0; i < slt.size; i++) printf("%d ",slt.a[i]); printf("\n"); } } // 5.查找顺序表中值为x的结点位置 int find(seqList slt, dataType x) { int i = 0; while (i < slt.size && slt.a[i] != x) i++; return i < slt.size ? i : -1; } // 6.获取顺序表第i个结点的值 dataType get(seqList slt,int i) { if(i < 1 || slt.size < i) { printf("访问越界！\n"); exit(1); } return slt.a[i-1]; } // 7.在顺序表的position位置插入值为x的结点 void insert(seqList *slt, int position,dataType x) { if(slt->size == MAX_SIZE) { printf("顺序表是满的，无法插入！"); exit(1); } if(position < 0 || position > slt->size) { printf("插入的位置非法，无法插入！"); exit(1); } for (int i = slt->size; i > position; i--) slt->a[i] = slt->a[i-1]; slt->a[position] = x; slt->size+=1; // 或slt->size++; } // 8.删除顺序表第position位置的结点 void del(seqList *slt, int position) { if(empty(*slt)) { printf("顺序表是空的，无法删除！"); exit(1); } if(position < 0 || position >= slt->size) { printf("删除的位置非法，无法删除！\n"); exit(1); } for (int i = position; i < slt->size-1; i++) slt->a[i] = slt->a[i+1]; slt->size-=1; // 或slt->size--; } // 9.中点优先递归遍历顺序表 void listOrder(seqList list, int low, int high) { if(low <= high) { int mid = (low+high)/2; printf("%d ",list.a[mid]); listOrder(list,low,mid-1); listOrder(list,mid+1,high); } } // 10.从键盘输入创建顺序表 void scanCreateList(seqList *list) { printf("请输入整数序列，以9999作为结尾：\n"); dataType x; scanf("%d",&x); while (x != 9999 && list->size < MAX_SIZE) { list->a[list->size++] = x; scanf("%d",&x); } } // 11.把顺序表前后两部分位置对调(0-m,m+1-n变为m+1-n,0-m) void divList(seqList *L, int m) { int i, j, x, last = L->size-1; for (i = 1; i <= m; i++) { x = L->a[0]; for (j = 1; j <= last ; j++) L->a[j-1] = L->a[j]; L->a[last] = x; } } int main() { seqList slt; // 定义顺序表 init(&slt); // 初始化顺序表 display(slt); // 打印顺序表 append(&slt,1); append(&slt,2); // 追加元素 display(slt); printf("%d\n",find(slt,2)); // 按值查找 printf("%d\n",get(slt,2)); // 按位查找 insert(&slt,0,3); // 插入元素 display(slt); listOrder(slt,0,slt.size-1); printf("\n"); seqList L; init(&L); scanCreateList(&L); display(L); divList(&L,4); display(L); return 0; }
