目录
Data structure advanced training course notes and algorithm exercises
Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining
题目1
假设算术表达式只包含“+”、“-”、“*”、“/”，正整数和括号的合法数学表达式。根据算符优先关系，
- 将算术表达式的中缀表示法转换为后缀表示法。
- 对得到的后缀表达式进行求值
1.1 算法设计思想
1.1.1 转后缀表达式：
- 从左到右扫描每一个字符。如果扫描到的字符是操作数（如a、b等），就直接输出这些操作数。
- 如果扫描到的字符是一个操作符，分三种情况：
（1）如果堆栈是空的，直接将操作符存储到堆栈中（pushCStack it）
（2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（pushCStack it）
（3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（popCStack it）,直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（pushCStack）- 如果遇到的操作符是左括号"（”，就直接将该操作符输出到堆栈当中。
该操作符只有在遇到右括号“ )”的时候移除。这是一个特殊符号该特殊处理。- 如果扫描到的操作符是右括号“ ”，将堆栈中的操作符导出（popCStack）到output中输出，直到遇见左括号“（”。将堆栈中的左括号移出堆栈（popCStack ）。继续扫描下一个字符。
- 如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。
1.1.3 求值
后缀表达式求值的算法是:
遍历后缀表达式，如果遇到运算数，那么运算数入栈
如果遇到运算符，那么弹出栈里面两个元素，先弹出的是右运算数，后弹出的是左运算数，计算运算结果，然后将结果入栈
最后遍历到后缀表达式末尾，当结果只有一个元素时，就是答案
1.2 源代码
#define StackSize 50
#define INFINITY 32768
// 定义运算符栈
typedef struct{
char elem[StackSize];
int top;
}SeqCStack;
void InitCStack(SeqCStack *S){
S->top=-1;
}
void pushCStack(SeqCStack *S, char operator){
if(S->top == StackSize - 1){ // 栈满
return ;
}
else{
S->top++;
S->elem[S->top] = operator;
return ;
}
}
void popCStack(SeqCStack *S, char *e){
if(S->top == -1){ // 栈空
return ;
}
else{
*e = S->elem[S->top];
S->top--;
return ;
}
}
char getCStackTop(SeqCStack S){
if(S.top == -1){ // 栈空
return '#';
}
else{
return S.elem[S.top];
}
}
void traverse(SeqCStack S){
int i=0;
while(i <= S.top){
printf("%c ", S.elem[i++]);
}
printf("\n");
}
// 定义运算数栈
typedef struct{
int data[StackSize];
int top;
}SeqNStack;
void InitNStack(SeqNStack *S){
S->top=-1;
}
void pushNStack(SeqNStack *S, int num){
if(S->top == StackSize - 1){ // 栈满
return ;
}
else{
S->top++;
S->data[S->top] = num;
return ;
}
}
void popNStack(SeqNStack *S, int *e){
if(S->top == -1){ // 栈空
return ;
}
else{
*e = S->data[S->top];
S->top--;
return ;
}
}
int getNStackTop(SeqNStack S){
if(S.top == -1){ // 栈空
return INFINITY;
}
else{
return S.data[S.top];
}
}
char compare(char operator, char top){
if(top == '#') // 空栈，操作符直接进栈
return '>';
else if(operator==')' && top=='(')
return '=';
else if(top=='(')
return '>';
else if(operator=='+') // 如果操作符是'+', 无论栈顶元素是什么, '+'优先级都小
return '<';
else if(operator=='-')
return '<';
else if(operator=='*' && top=='+')
return '>';
else if(operator=='*' && top=='-')
return '>';
else if(operator=='*' && top=='*')
return '<';
else if(operator=='*' && top=='/')
return '<';
else if(operator=='*' && top=='(')
return '<';
else if(operator=='/' && top=='+')
return '>';
else if(operator=='/' && top=='-')
return '>';
else if(operator=='/' && top=='*')
return '<';
else if(operator=='/' && top=='(')
return '<';
else if(operator=='(')
return '>';
else if(operator==')')
return '<';
}
int caculate(int left, int right, char c){
int re = 0;
switch (c){
case '+':
re = left + right;
break;
case '-':
re = left - right;
break;
case '*':
re = left * right;
break;
case '/':
re = left / right;
break;
default:
break;
}
return re;
}
void main(){
SeqCStack OS, SuffixExp;
SeqNStack NS;
/* 初始化运算符栈 */
InitCStack(&OS);
/* 初始化运算数栈 */
InitNStack(&NS);
/* 初始后缀表达式栈 */
InitCStack(&SuffixExp);
char exp[] = {'5', '+', '2', '*', '(', '1', '+', '6', ')', '-', '8', '/', '2', '\0'};
printf("Infix expression is: %s\n", exp);
char suffixstr[50], temp;
int i = 0, tempNum;
while (exp[i]!='\0'){
if(isdigit(exp[i])){ // 如果是数字直接进后缀表达式栈
pushCStack(&SuffixExp, exp[i]);
// printf("num------%c\n", exp[i]);
i++;
}
else{
// printf("char------\n");
// printf("compare----%c\n", compare(exp[i], getCStackTop(OS)));
switch(compare(exp[i], getCStackTop(OS))){
case '>':
pushCStack(&OS, exp[i]);
// printf("case1 >---%c\n", exp[i]);
i++;
break;
case '=':
popCStack(&OS, &temp); // 脱括号
// printf("case2 =---%c\n", temp);
i++;
break;
case '<':
while(compare(exp[i], getCStackTop(OS))=='<'){
// printf("case3 <---%c\n", exp[i]);
// printf("case3 getCStackTop %c\n", getCStackTop(OS));
popCStack(&OS, &temp);
// printf("case3 after getCStackTop %c\n", getCStackTop(OS));
pushCStack(&SuffixExp, temp);
}
// if(exp[i]!=')'){i++;}
break;
}
}
}
/* 最后把栈中剩余的运算符依次弹栈打印 */
while(getCStackTop(OS)!='#'){
popCStack(&OS, &temp);
pushCStack(&SuffixExp, temp);
}
traverse(SuffixExp);
for(i=SuffixExp.top; i>=0; i--){
popCStack(&SuffixExp, &temp);
suffixstr[i] = temp;
}
printf("Infix expression to suffix expression is: %s\n", suffixstr);
/* 后缀表达式求值的算法是: 遍历后缀表达式， 如果遇到运算数，那么运算数入栈 如果遇到运算符，那么弹出栈里面两个元素，先弹出的是右运算数，后弹出的是左运算数， 计算运算结果，然后将结果入栈。 最后遍历到后缀表达式末尾，当结果只有一个元素时，就是答案 */
char *p=suffixstr;
while (*p != '\0'){
if (isdigit(*p)){
pushNStack(&NS, *p-'0');
}
else{
popNStack(&NS, &tempNum);
int rightNum = tempNum;
// printf("rightNum:::%d\n", rightNum);
// free(temp);
popNStack(&NS, &tempNum);
int leftNum = tempNum;
// free(temp);
int result = caculate(leftNum, rightNum, *p);
// printf("caculate result----%d\n", result);
pushNStack(&NS, result);
}
p++;
}
printf("result: %d\n", getNStackTop(NS));
system("pause");
}
1.3 运行情况截图
题目2
设L为带头结点的单链表，实现从尾到头反向输出链表中每个结点的值。（递归思想）
2.1 算法设计思想
递归语句在打印之前就可以了
2.2 源代码
void printReversely(LinkList L){
if(L->next!=NULL){
printReversely(L->next);
printf("%c ", L->next->data);
}
}
2.3 运行情况截图
题目3
一只青蛙一次可以跳上1级台阶，也可以跳上2级。
编写代码求青蛙跳上一个n级的台阶，总共有多少种跳法？
- 若条件改为：
一只青蛙一次可以跳上1级台阶，也可以跳上2级，也可以跳上3级，...，也可以跳上n级。
编写代码求青蛙跳上一个n级的台阶，总共有多少种跳法？
3.1 算法设计思想
Q：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法。A：
f(n) = f(n-1)+f(n-2)+…+f(1)
f(n-1) = f(n-2)+ f(n-3)…+f(1)
两式相减，得到f(n) = 2*f(n-1)
3.2 源代码
int Jump(int i, int n) {
//表示当前台阶数大于总台阶数，很显然这种情况不符合，走不通，记为 0
if (i > n) {
return 0;
}
//表示当前台阶数正好等于总的台阶数，那么这种情况符合，记为 1
if (i == n) {
return 1;
}
return Jump(i + 1, n) + Jump(i + 2, n);
}
int JumpN(int num){
if (num == 1){
return 1;
}
else{
return 2*JumpN(num-1);
}
}
3.3 运行情况截图
题目4
用一个2X1的小矩形横着或竖着去覆盖更大的矩形。如下图
- 具体：用8个2X1小矩形横着或竖着去覆盖2X8的大矩形，覆盖方法有多少种？
- 编写代码求用2X1小矩形横着或竖着去覆盖2Xn的大矩形。输出总共有多少种覆盖方法
4.1 算法设计思想
当n=1时，覆盖方法有1种；
当n=2时，覆盖方法有2种；
当n=3时，覆盖方法有2+1=3种；
当n=4时，覆盖方法有3+2=5种；
按照规律就转化成了斐波那契数列问题
4.2 源代码
int Cover(int n){
if(n<=0){
return 0;
}
else if(n==1||n==2){
return n;
}
else{
return Cover(n-1) + Cover(n-2);
}
}
4.3 运行情况截图
题目5
借助自定义栈以非递归形式求解汉诺塔问题（n,a,b,c）；
即将n个盘子从起始塔座a通过辅助塔座b移动到目标塔座c,
并保证每个移动符合汉诺塔问题的要求
5.1 算法设计思想
利用递归的思想，用栈来处理；
比如n=3时，转化的问题是：
先要移动A塔座上面2个盘子到B塔座，这个操作进栈后续处理；
然后移动A塔座上面最后一个大盘子到C塔座，这个操作进栈后续处理；
最后再移动B塔座上最后两个盘子到C塔座；
一直访问栈，如果栈顶处理的盘子数不是1，就在把操作细分，进栈；
直到盘子数为1，移动盘子；
直到栈为空
5.2 源代码
// 定义汉诺塔数据
typedef struct{
char A;
char B;
char C;
int n;
}HanoiData;
// 定义栈
typedef struct{
HanoiData elem[StackSize];
int top;
}SeqStack;
void InitStack(SeqStack *S){
S->top=-1;
}
void push(SeqStack *S, HanoiData hd){
if(S->top == StackSize - 1){ // 栈满
return ;
}
else{
S->top++;
S->elem[S->top] = hd;
return ;
}
}
void pop(SeqStack *S, HanoiData *e){
if(S->top == -1){ // 栈空
return ;
}
else{
*e = S->elem[S->top];
S->top--;
return ;
}
}
// HanoiData getTop(SeqStack S){
// if(S.top == -1){ // 栈空
// return ;
// }
// else{
// return S.elem[S.top];
// }
// }
void move1(int n,char A,char B,char C){
if(n==1){
printf("%c-->%c\n",A,C);
}
else{
move1(n-1,A,C,B);
move1(1,A,B,C);
move1(n-1,B,A,C);
}
}
void hanoi(int n){
SeqStack S;
InitStack(&S);
HanoiData h = {'A', 'B', 'C', n};
push(&S,h);//初始栈
// hanoi_data x;//用来保存出栈的n,A,B,C
while(S.top!=-1){
pop(&S, &h);//出栈并用x带回
if(h.n==1){
printf("%c-->%c\n",h.A,h.C);//打印出移动方案
}
else{
HanoiData h1 = {h.B, h.A, h.C, h.n-1};
push(&S,h1);
HanoiData h2 = {h.A, h.B, h.C, 1};
push(&S,h2);
HanoiData h3 = {h.A, h.C, h.B, h.n-1};
push(&S,h3);
}
}
}
5.3 运行情况截图
京公网安备 11010502036488号