国庆期间，自己搞了C/C++编译环境（cygwin其实比mingw好安装一些），跟着敲了一些代码，记录一下：
/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /* * File: main.cpp * Author: dingcc * * Created on 2020年10月6日, 下午10:10 */ #include <cstdlib> #include <iostream> #include <math.h> using namespace std; /** * 寻找两个单词的相同字母的节点 */ typedef struct LNode { char data; struct LNode *next; }LNode; LNode *findFirstCommon(LNode *str1, LNode *str2) { int len1 = 0, len2 = 0; LNode *p = str1->next, *q = str2->next; while (p != NULL) { len1++; p = p->next; } while (q != NULL) { len2++; q = q->next; } for (p=str1->next; len1>len2; len1--) p=p->next; for (q=str2->next; len1<len2; len2--) q=q->next; while (p !=NULL && p->data != q->data) { p = p->next; q = q->next; } cout<<p->data<<endl; return p; } /** * 尾插法 * @param head * @param n * @param length */ void createLinkListR(LNode *&head, char n[], int length) { head = (LNode*) malloc(sizeof(LNode)); head ->next = NULL; LNode *p = NULL, *r=head; for (int i=0; i < length; ++i) { p = (LNode*) malloc(sizeof(LNode)); p ->next = NULL; p ->data = n[i]; p ->next = r->next; r ->next = p; r = p; } cout<<head ->next ->data<<endl; } /** * 头插法 * @param head * @param n * @param length */ void createLinkListL(LNode *&head, char n[], int length) { head = (LNode*) malloc(sizeof(LNode)); head ->next = NULL; LNode *p = NULL; for (int i=0; i < length; ++i) { p = (LNode*) malloc(sizeof(LNode)); p ->next = NULL; p ->data = n[i]; p ->next = head->next; head ->next = p; } cout<<head ->next ->data<<endl; } /** * 合并数组 * @param a 数组a * @param m 数组a的长度 * @param b 数组b * @param n 数组b的长度 * @param c 合并后的数组c */ void mergearray (int a[], int m, int b[], int n, int c[]) { int i = 0, j = 0; int k = 0; while (i < m && j < n) { if (a[i] < b[j]) c[k++] = a[i++]; // c[k] = a[i]; k++; i++; else c[k++] = b[j++]; } while (i < m) c[k++] = a[i++]; while (j < n) c[k++] = b[j++]; } /** * 合并链表 * @param A 链表A * @param B 链表B * @param C 结果链表C */ void merge(LNode *A, LNode *B, LNode *&C) { LNode *p = A->next; LNode *q = B->next; LNode *r; C = A; C->next = NULL; free(B); r = C; while(p != NULL && q != NULL) { if (p ->data <= q ->data) { r->next = p; p = p->next; r = r->next; } else { r ->next = q; q = q->next; r = r->next; } } if(p!=NULL) r->next = p; if(q!=NULL) r->next = q; } int getPriority(char op) { if (op == '+' || op == '-') return 0; else return 1; } /** * 中缀式转后缀式 * @param infix * @param s2 * @param top2 */ void infixToPostFix(char infix[], char s2[], int &top2) { char s1[11]; int top1 = -1; int i = 0; while(infix[i] != '\0') { if ('0' <= infix[i] && infix[i] <= '9') { s2[++top2] = infix[i]; ++i; } else if (infix[i] == '(') { s1[++top1] = '('; ++i; } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') { if (top1 == -1 || s1[top1] == '(' || getPriority(infix[i]) > getPriority(s1[top1])) { s1[++top1] = infix[i]; ++i; } else s2[++top2] = s1[top1--]; } else if (infix[i] == ')') { while (s1[top1] != '(') s2[++top2] = s1[top1--]; --top1; ++i; } } while (top1 != -1) s2[++top2] = s1[top1--]; for (int j = 0; j < 12; j++) { cout<<s2[j]<<endl; } } int calSub(float opand1, char op, float opand2, float &result) { if (op == '+') result = opand1 + opand2; if (op == '-') result = opand1 - opand2; if (op == '*') result = opand1 * opand2; if (op == '/') { if (fabs(opand2) < 0.01) { return 0; } else { result = opand1 / opand2; } } return 1; } int calStackTopTwo(float s1[], int &top1, char s2[], int &top2) { float opnd1, opnd2, result; char op; int flag; opnd2 = s1[top1--]; opnd1 = s1[top1--]; op = s2[top2--]; flag = calSub(opnd1, op, opnd2, result); if (flag == 0) cout<<"ERROE"<<endl; // puts("ERROR"); s1[++top1] = result; return flag; } /** * 中缀表达式计算 * @param exp * @return */ float callInfix(char exp[]) { int maxSize = 10; float s1[maxSize]; int top1 = -1; char s2[maxSize]; int top2 = -1; int i = 0; while (exp[i] != '\0') { if ('0' <= exp[i] && exp[i] <= '9') { s1[++top1] = exp[i] - '0'; ++i; } else if (exp[i] == '(') { s2[++top2] = '('; ++i; } else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') { if (top2 == -1 || s2[top2] == '(' || getPriority(exp[i]) > getPriority(s2[top2])) { s2[++top2] = exp[i]; ++i; } else { int flag = calStackTopTwo(s1, top1, s2, top2); if (flag == 0) return 0; } } else if (exp[i] == ')') { while (s2[top2] != '(') { int flag = calStackTopTwo(s1, top1, s2, top2); if (flag == 0) return 0; } --top2; ++i; } } while (top2 != -1) { int flag = calStackTopTwo(s1, top1, s2, top2); if (flag == 0) return 0; } return s1[top1]; } /** * 后缀表达式计算 * @param exp * @return */ float calPostFix(char exp[]) { int maxSize = 10; float s[maxSize]; int top = -1; for (int i = 0; exp[i] != '\0'; ++i) { if ('0' <= exp[i] && exp[i] <= '9') s[++top] = exp[i] - '0'; else { float opnd1, opnd2, result; char op; int flag; opnd2 = s[top--]; opnd1 = s[top--]; op = exp[i]; flag = calSub(opnd1, op, opnd2, result); if (flag == 0) { cout<<"ERROR"<<endl; //puts("ERROR"); break; } s[++top] = result; } } return s[top]; } /** * 前缀表达式计算 * @param exp * @param len * @return */ float calPreFix(char exp[], int len) { int maxSize = 10; float s[maxSize]; int top = -1; for (int i = len -1; i >= 0; --i) { if ('0' <= exp[i] && exp[i] <= '9') s[++top] = exp[i] - '0'; else { float opnd1, opnd2, result; char op; int flag; opnd1 = s[top--]; opnd2 = s[top--]; op = exp[i]; flag = calSub(opnd1, op, opnd2, result); if (flag == 0) { cout<<"ERROR"<<endl; //puts("ERROR"); return 0; } s[++top] = result; } } return s[top]; } /** * 迭代输出链表元素 * @param c */ void foo (LNode *c) { if (c->next->data != '\0') { cout<<c->next->data<<endl; foo(c->next); } } /* * */ int main(int argc, char** argv) { //cout<<"hello world!"<<endl; //合并数组 // int a[4] = {1,3,5,7}; // int b[3] = {2,4,6}; // int m = 4, n = 3; // int c[7]; // mergearray(a, m, b, n, c); // for (int i=0; i<7; ++i) { // cout<<c[i]<<endl; // } // 合并链表 // LNode *A; // char a[3] = {'a', 'b', 'c'}; // createLinkListR(A, a, 3); // LNode *B; // char b[5] = {'d', 'e', 'f', 'g', 'h'}; // createLinkListR(B, b, 5); // LNode *C; // merge(A, B, C); // foo(C); // 头插法生成单链表 // LNode *p; // char n[] ="abc"; // createLinkListL(p, n, 3); // 尾插法生成单链表，找两个单词相同的第一个字母 // LNode *str1; // char n[7] = {'l', 'o', 'a', 'd', 'i', 'n', 'g'}; // createLinkListR(str1, n, 7); // cout<<"str1;"<<str1 ->next->data<<endl; // LNode *str2; // char m[5] = {'d', 'o', 'i', 'n', 'g'}; // createLinkListR(str2, m, 5); // cout<<"str2;"<<str2 ->next->data<<endl; // LNode *x = findFirstCommon(str1, str2); // cout<<"x:"<<x->data<<endl; // 中缀转后缀表达式 // char infix[] = "(6+(3+5)*2-1)/3"; // char s2[11]; // int top2 = 0; // infixToPostFix(infix, s2, top2); // cout<<"top2"<<top2<<endl; // 中缀、后缀、前缀表达式计算 char exp[] = "(6+(3+5)*2-1)/3"; float s1 = callInfix(exp); cout<<"s1:"<<s1<<endl; char exp2[] = "635+2*+1-3/"; float s2 = calPostFix(exp2); cout<<"s2:"<<s2<<endl; char exp3[] = "/-+6*+35213"; float s3 = calPreFix(exp3, 11); cout<<"s3:"<<s3<<endl; return 0; }代码参考：天勤率辉考研
