• 1. 数据结构算法
  • 2. 数据结构数据结构是一门研究非数值计算的程序设计问题中的操作对象(结点)以及它们之间关系和操作等的学科。 1968 年克努思教授开创了数据结构的最初体系,他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 70 年代初,数据结构作为一门独立的课程开始进入大学课堂。 下面介绍数据结构中常见的一些基本算法
  • 3. 关于算法 线性表上的常见算法 基于队列的常见算法 基于栈的常见算法数据结构常见算法
  • 4. 算法多项式求的两种方法 A(x)=anxn+an-1xn-1+…+a0 A(x)=((anx+an-1)X+an-2)…+a0
  • 5. A(x)=anxn+an-1xn-1+…+a0template T Poly1(T a[],int n,T x) { int i,j; T result=0; T xn,xx; for( i=0;i
  • 6. A(x)=((anx+an-1)X+an-2)…+a0 template T Poly2(T a[],int n,T x) { int i,j; T result=0; T xn,xx; result=a[n-1]; for( i=n-1;i>0;i--) result=result*x+a[i-1]; return result; }
  • 7. 线性表设计一个时间复杂度为O(n)的算法,实现将数组A[n]中所有元素循环右移K个位置 已知数组元素为整型,设计算法将其调整为左右两部分,左边元素为奇数,右边元素为偶数 设单链表以非递减有序排列,设计算法,实现在单链表中删去系统的多余结点 设单链表以非递减有序排列,设计算法,实现在单链表中删去系统的多余结点 已知一个单链表中的数据元素含有三类字符:数字、字母和其他字符。编写算法,构造三个循环链表,使得每个循环链表中之包含同一类字符返回
  • 8. 设计一个时间复杂度为O(n)的算法,实现将数组A[n]中所有元素循环右移K个位置算法分析 kn。 k=k%N01234567891011121314140123456789101112131314012345678910111212131401234567891011AB(k=1)B(k=2)B(k=3)j=(i+k)%N
  • 9. int i,j,n; int *a; cin>>n>>k; k=k%n; a=new int[n]; for (i=0;i>> a[i]; for (i=0;i<
  • 10. 空间复杂度更少的方法假设原数组序列为abcd1234,循环右移了4位 数组序列为1234abcd。 右移后,有两段的顺序是不变的:1234和abcd,可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成: 1.   逆序排列abcd:abcd1234 → dcba1234; 2.   逆序排列1234:dcba1234 → dcba4321; 3.   全部逆序:dcba4321 → 1234abcd。
  • 11. 更一般的情况:01234567891011121314140123456789101112131314012345678910111212131401234567891011根据K%N的大小,将数据分成两段, 第一段长度为N-K个数据,第二段中有K个数据 然后分别将两段逆序,最后将整个数组逆序
  • 12. void convert(int a[], int start, int end) { int k, temp; for (k = 0; k < (end-start+1)/2; k++) { temp = a[start+k]; a[start+k] = a[end-k]; a[end-k] = temp; } }
  • 13. void yiwei(int a[], int n, int k) { convert(a,0,k-1); convert(a,k,n-1); convert(a,0,n-1); }
  • 14. 已知数组元素为整型,设计算法将其调整为左右两部分,左边元素为奇数,右边元素为偶数算法分析 设计两个工作指针,分别指向数组的两端(I=0;j=n-1).然后,重复的进行以下工作: 如果i
  • 15. int n,*a; cin>>n; a=new int [n]; int i=0,j=n-1; for (i=0;i>a[i]; i=0; while (i
  • 16. #include "stdafx.h" #include class change { private: int *a,length; public: change() { cout<<"Please input the length of the array:"; cin>>length; a=new int[length]; cout<<"Please input the data of the array:"; for(int i=0;i>a[i]; }
  • 17. void trans() { int i=0,j=length-1; int temp; while (i
  • 18. void display() { int i=0; for(i=0;i
  • 19. 设单链表以非递减有序排列,设计算法,实现在单链表中删去系统的多余结点基本思想: 从头结点出发,进行链表的遍历,在遍历的过程中,设置两个工作指针p和q(q=p->next), 比较p、q所指向的节点的值,如果相同,则删除q所指向的节点,b带头结点的单链表Ha1a2…an
  • 20. 算法描述设置工作指针p、q,并进行初始化: p=list.head->next; if (!p) return else q=p->next; 在q!=NULL的情况下,重复进行以下工作: if (p->data==q->data) temp=q; p->next=q->next; q=p->next; delete temp else p=q;q=q->next;
  • 21. template void DeleteSame(LinkList a){ Node * p,*q,*temp; p=a.GetHead ()->next; if (!p) {cout<<"This is a empty list!!"; return; } else{ q=p->next; } while (q) { if (p->data==q->data) { temp=q;p->next=q->next;q=p->next;delete temp; } else{ p=q; q=q->next;} } return; }
  • 22. 判断带头节点的双循环链表是否对称设置两个工作指针p=首元节点,q=尾节点, 重复进行以下工作: 比较p和q的值, 如果不想等,停止比较,返回false 如果相等, 观察p、q是否相邻(p->right==q,p->right->right==q),如果相邻,返回true,否则 p=p->right, q=q->left,firsta1a2an
  • 23. 1 .定义两个工作指针p、q,并进行初始化: p=list.first->right; q=list.first->left; 2.重复进行以下工作(while (1)) if(p->data!=q->data return false; else{ if (p->right==q || p->right->right==q) return true; else { p=p->right;q=q->left;} 返 回
  • 24. 已知一个单链表中的数据元素含有三类字符:数字、字母和其他字符。编写算法,构造三个循环链表,使得每个循环链表中之包含同一类字符基本思想 每个链表都带有头结点。原始链表为A,分类之后新增B,C,使得A存放字母,B存放数字,C存放其他字符 基本过程:在A中进行遍历,并检查遍历到的符号, 如果是字符,不做任何处理(继续后移指针); 如果是数字,则将其采用尾插法加入到B中(继续后移指针), 如果是第三类符号,则将其采用尾插法插入到C中(继续后移指针)
  • 25. 算法分析已知链表A,构造两个空循环链表B(数字),C(其他字符) 设置工作指针p;p=A.>first(头结点) 定义一个辅助指针q,完成工作:q=p->next; 如果q!=A.first IsDigital(q->data),则将q从A中删除,并将其链入B中 temp=q; p->next=q->next,q=p->next; temp->next=B.first; B.rear->next=temp; B.rear=p; q->data 是其他字符,则将其从A中删除,并将其链入C中 重复进行上述工作,直到A链表遍历结束
  • 26. template struct Node { T data; Node *next; }; template class CycleList { Node *head, *rear; int Length; public: CycleList(){ head=new Node;head->next=head;rear=head;} CycleList(int n); void Display(); Node * GetHead(){ return head; } void append(Node *p); friend void Segment(CycleList a); };
  • 27. template void CycleList::append(Node *p) { p->next=rear->next; rear->next=p; rear=p; return; }
  • 28. template CycleList::CycleList(int n) { T input; Node *s; head=new Node; head->next=head; rear=head; Length=n; int i=0; for (i=0;i>input; s=new Node; s->data=input; append(s); } }
  • 29. template void CycleList::Display() { Node *p; p=head->next; while(p!=head) { cout <data<<" "; p=p->next; } cout<
  • 30. template void Segment(CycleList A) { Node *p,*q,*ahead,*temp; CycleList B,C; cout <<"the list is :"; A.Display(); p=A.GetHead(); ahead=p; q=p->next;
  • 31. template while(q!=ahead) { if (q->data>='0' && q->data<='9') { temp=q; p->next=q->next; q=p->next; B.append(temp); } else{ if (q->data>='a' && q->data<='z'|| q->data>='A' && q->data<='Z'){ p=q; q=q->next;} else{ temp=q;p->next=q->next; q=p->next; C.append(temp); } } }
  • 32. int main(int argc, char* argv[]) { CycleList A(10); A.Display(); Segment(A); return 0; }返 回
  • 33. template while(q!=ahead) { if (q->data>='0' && q->data<='9') { temp=q;p->next=q->next;q=p->next; B.append(temp);} else{ if (q->data>='a' && q->data<='z'|| q->data>='A' && q->data<='Z'){ p=q; q=q->next; } else{ temp=q; p->next=q->next; q=p->next; C.append(temp); } } } }
  • 34. 队列求解素数环问题 列车重排问题 杨辉三角形 返回
  • 35. 求解素数环问题问题描述: 将n个自然数排成环,使得每相邻两数之和为素数,构成一个素数环。 例子:1,2,3,4,7,10,9,8,5,6
  • 36. 求解思想先将1放入素数环中。 对2~n之间的自然数组成对列,依次将元素出队,测试其是否与素数环中的最后一个数的和为素数,如成立,则将其加入素数环,否则,将其加入到对列中,等待再次处理 重复2中操作,直到队列空
  • 37. 代码分析public class PrimeRing { public PrimeRing(int n) { SeqList ring = new SeqList(n); ring.add(new Integer(1)); LinkedQueue q = new LinkedQueue(); for (int i=2; i<=n; i++) q.enqueue(new Integer(i));
  • 38. int i=0; while (!q.isEmpty()) { int k = q.dequeue().intValue(); //出队 System.out.print("dequeue: "+k+"\t"); if (isPrime(ring.get(i)+k)) { i++; ring.add(new Integer(k)); } else q.enqueue(new Integer(k)); } System.out.println("素数环: "+ring.toString()); }返 回
  • 39. 判断一个正整数a是不是素数,只要将所有的小于等于根号a且大于1的素数都除不尽,则a就是素数。这是判断素数引理6 首先0和1不是素数、2是素数、 能被2整除的不是素数,(素数肯定是奇数) 排除这些数后 然后对num进行开平方根, 从3开始到这个平方根,每隔2判断一下(奇数肯定不能被偶数整除),看看num能否被其整除, 如果能就不是素数,否则, 一直检查到最后都没有,那么这个数一定是素数。
  • 40. public boolean isPrime(int k) //判断k是否为素数 { if (k==2) return true; if (k<2 || k>2 && k%2==0) return false; int j=(int)Math.sqrt(k); //Math.sqrt(k)返回k的平方根值 if (j%2==0) j--; //获得测试范围内的最大奇数 while (j>2 && k%j!=0) j-=2; return j<2; }返 回
  • 41. 队列应用举例-火车厢重排问题描述:n4321n4321对任意序列的火车厢,进行重排,使其按照1,2,3,….n的顺序进行排列(起始序列为:5,8,1,7,4,2,9,6,3)火车站列车
  • 42. 出 轨入 轨581742963987654321H1H3H2转轨站示意图队列应用举例-火车厢重排解决方案:利用缓冲轨进行重排
  • 43. 1. 分别对k个队列初始化; 2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号; 3.1 如果入轨中的车厢编号等于nowOut,则 3.1.1 输出该车厢; 3.1.2 nowOut++;队列应用举例-火车厢重排
  • 44. 3.2 考察每一个缓冲轨队列 for (j=1; j<=k; j++) 3.2.1 取队列 j 的队头元素c; 3.2.2 如果c=nowOut,则 3.2.2.1 将队列 j 的队头元素出队并输出; 3.2.2.2 nowOut++; 队列应用举例-火车厢重排
  • 45. 3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢,则(如果前两步工作都不成立) 3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j; 3.3.2 如果 j 存在,则把入轨中的第一个车厢移至缓冲轨 j; 3.3.2 如果 j 不存在,但有多于一个空缓冲轨,则把入轨中的第一个车厢移至一个空缓冲轨;否则车厢无法重排,算法结束;队列应用举例-火车厢重排返 回
  • 46. 杨辉三角形 打印杨辉三角
  • 47. 杨辉三角形元素入队顺序
  • 48. (1) 第7行的第一个元素1入队。  element[rear]=1; rear=(rear +1 )% MAXSIZE; (2) 循环做以下操作, 产生第7行的中间5个元素并入队。  element[rear]=element[front]+element[(front+1) %MAXSIZE];  rear=(rear +1 )% MAXSIZE; front=(front+1)%MAXSIZE;
  • 49. (3) 第6行的最后一个元素1出队。  front=(front+1)%MAXSIZE; (4) 第7行的最后一个元素1入队。  element[rear]=1; rear=(rear +1 )% MAXSIZE;
  • 50. 下面给出打印杨辉三角形的前n行元素的具体算法: void YangHuiTriangle( ) { SeqQueue Q; InitQueue(&Q); EnterQueue(&Q,1); /* 第一行元素入队*/ for(n=2;n<=N;n++) /* 产生第n行元素并入队, 同时打印第n-1行的元素*/ { EnterQueue(&Q,1); /* 第n行的第一个元素入队*/ for(i=1;i<=n-2;i++)  /* 利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/ { DeleteQueue(&Q,&temp); Printf(″%d″,temp); /* 打印第n-1行的元素*/
  • 51. GetHead(Q,&x); temp=temp+x; /*利用队中第n-1行元素产生第n行元素*/ EnterQueue(&Q,temp);  } DeleteQueue(&Q,&x);  printf(″%d″,x); /* 打印第n-1行的最后一个元素*/ EnterQueue(&Q,1) /* 第n行的最后一个元素入队*/ } } 返 回
  • 52. 栈迷宫问题 骑士巡游问题 中缀表达式求值问题 中缀表达式转换为后缀表达式的问题 后缀表达式求值问题 数制转换问题 回文的判断 括号匹配问题返回
  • 53. 有一个迷宫,迷宫里面有很多隔断。给定一个入口和出口,判断从入口到出口是否有通路。 以一个 m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。迷宫问题1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
  • 54. 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1  迷宫问题算法:   从入口出发,顺着某一个方向进行探索(三个方向),若能走通,则继续 前进; 否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路, 假如所有可能的通路都探索到而未能达到出口,则所设定的迷宫没有通路.
  • 55. 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1  迷宫问题算法:   从入口出发,顺着某一个方向进行探索,若能走通,则继续前进; 否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路, 用栈实现:  从入口出发,顺着某一个方向进行探索,若能走通,则继续前进,此时,将当前在迷宫中的位置和探测的(下一次)方向入栈, 如果走不通,则根据这个信息在新的方向上进行探测
  • 56. 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 定义四个方向 0 表示向东 1 表示向西 2 表示向北 3 表示向南 Nx[0]=0 ny[0]=-1 Nx[1]=0 ny[1]=1 Nx[2]=-1 ny[2]=0 Nx[3]=1 ny[3]=0 定义trace[][] 记录是否已经走过位置某个
  • 57. 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 入口:1,1 每次探测都是沿东、西、北、南的方向进行探测 首先将(1,1,-1)入栈。其中:入口1,1, 第三个值表示在这个位置上的下一次探测的方向
  • 58. 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 如果栈不空,并且没有到达出口, 则根据栈顶的信息计算新的位置, 检查该位置是否可行,如果成立,则将该位置和在该位置的下一个探测方向入栈,否则继续探测 如果探测失败,将栈顶出栈,并计算新的位置 如果栈空,表示从入口到出口没有通路,否则,栈中的数据即为通路。 返 回
  • 59. #include "stdafx.h" #include #include using namespace std; struct site { int x,y; int from, direct; };
  • 60. int main(int argc, char* argv[]){ stack site_stack; int m,n; int **maze; int i,j; int current_x,current_y,out_x,out_y,direction,from; int nx[4],ny[4]; nx[0]=0 ; ny[0]=-1; nx[1]=0 ; ny[1]=1; nx[2]=-1; ny[2]=0; nx[3]=1; ny[3]=0;
  • 61. cout<<"please input the size of a maze(row,column):"; cin>>m>>n; maze=new int * [m+2]; trace=new int *[m+2]; for(i=0;i<=n+1;i++) { maze[i]=new int[n+2]; trace[i]=new int[n+2]; } cout<<"Please input the maze data"<>maze[i][j]; trace[i][j]=0; } }
  • 62. cin>>current_x>>current_y; while(maze[current_x][current_y]==1) { cout<<"This site is not exist, please input again!!!"<>current_x>>current_y; } cout<<"Please input the exit(x,y)"; cin>>out_x>>out_y; site start; start.x=current_x; start.y=current_y; start.direct=-1; site_stack.push(start);
  • 63. while(!site_stack.empty() && !(current_x==out_x &¤t_y==out_y)) { site temp; int x,y; int direction; temp=site_stack.top(); x=temp.x; y=temp.y; direction=temp.direct+1; x=x+nx[direction]; y=y+ny[direction];//探测方向
  • 64. while((maze[x][y]==1 ||trace[x][y]==1)&& direction<=3) { temp=site_stack.top(); x=temp.x+nx[direction]; y=temp.y+ny[direction]; site_stack.top().direct=direction; direction+=1; }
  • 65. if (maze[x][y]==0&&trace[x][y]==0) { trace[x][y]=1; temp.x=x; temp.y=y; temp.direct=0; site_stack.push(temp); current_x=x; current_y=y; } else site_stack.pop(); }
  • 66. site path; while(!site_stack.empty () ) { path=site_stack.top(); cout<<"("<
  • 67. 采用递归方法解决迷宫问题bool end=false;bool find=false; bool search(int x,int y,int direction){ int new_x,new_y; if (x==out_x && y==out_y) { end=true; return true; } else{ find=false; for(int i=direction;i<=3;i++){ if(!find){ new_x=x+nx[i]; new_y=y+ny[i]; if(maze[new_x][new_y]==0 && trace[new_x][new_y]==0) { find=true; trace[new_x][new_y]=1; search(new_x,new_y,0); if (end) cout<<"("<
  • 68. 骑士巡游编写程序求解骑士巡游问题 在n行n列的棋盘上(如n=5),假设一位骑士(按象棋中“马走日”的行走法) 从初始坐标位置(x1,y1)出发,要遍访(巡游)棋盘中的每一个位置一次。 请编一个程序,为骑士求解巡游"路线图“ 或告诉骑士,从某位置出发时,无法遍访整个棋盘 - 问题无解
  • 69. 骑士游历
  • 70. 骑士游历骑士游历 有八个移动方向 1 na[0]=-2 ny[0]=1 2 na[1]=-1 ny[1]=2 3 na[2]=1 ny[2]=2 4 na[3]=2 ny[3]=1 5 na[4]=2 ny[4]=-1 6 na[5]=1 ny[5]=-2 7 na[6]=-1 ny[6]=-2 8 na[7]=-2 ny[7]=-1
  • 71. 骑士游历骑士游历 将初始位置、下一个探测方向入栈,设置当前探测方向为已探测,并计算新的位置 如果栈不空,并且还有未遍历的位置 如果新位置可行,则将新位置、下一个探测入栈,并设置当前位置为已探测 否则, 栈顶元素出栈,并计算新的位置; 如果栈空,则失败;否则,站内记录有效信息返 回
  • 72. 表达式求值是高级语言编译中的一个基本问题, 是栈的典型应用实例。 表达式的组成: 操作数(operand):操作数既可以是常数, 也可以是被说明为变量或常量; 运算符(operator):运算符可以分为算术运算符、 关系运算符和逻辑运算符三类 界限符(delimiter) :基本界限符有左右括号和表达式结束符等。 中缀表达式求值
  • 73. 表达式运算及运算符优先级 1) 无括号算术表达式求值
  • 74. 无括号算术表达式的处理过程
  • 75. 2) 算术表达式处理规则 (1) 规定算符的优先级表。 (2) 设置两个栈: OVS(运算数栈)和OPTR(运算符栈)。 (3) 自左向右扫描,遇操作数进OVS,遇操作符则与OPTR栈顶优先数比较:当前操作符>OPTR栈顶, 当前操作符进OPTR栈当前操作符≤OPTR栈顶,OVS栈顶、次顶和OPTR栈顶,退栈形成运算T(i),T(i)进OVS栈。 例: 实现A/B↑C+D*E#的运算过程时栈区变化情况如图3.7所示。
  • 76. 图3.7 A/B↑C+D*E运算过程的栈区变化情况示意图
  • 77. 3) 带括号算术表达式 假设操作数是整型常数,运算符只含加、减、乘、除等四种运算符, 界限符有左右括号和表达式起始、结束符“#”,如: #(7+15)*(23-28/4)#。 引入表达式起始、 结束符是为了方便。 要对一个简单的算术表达式求值, 首先要了解算术四则运算的规则, 即:  (1) 从左算到右;  (2) 先乘除, 后加减;  (3) 先括号内, 后括号外。
  • 78. 运算符和界限符可统称为算符,它们构成的集合命名为OPS。根据上述三条运算规则,在运算过程中,任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一: θ1<θ2, θ1的优先权低于θ2。  θ1=θ2, θ1的优先权等于θ2。  θ1>θ2, θ1的优先权高于θ2。
  • 79. 表 3-1 算符之间的优先关系
  • 80. 实现算符优先算法时需要使用两个工作栈: 一个称作operator, 用以存放运算符;另一个称作operand,用以存放操作数或运算的中间结果。 算法的基本过程如下: 首先初始化操作数栈operand和运算符栈operator, 并将表达式起始符“#”压入运算符栈; 依次读入表达式中的每个字符,若是操作数则直接进入操作数栈operand, 若是运算符,则与运算符栈operator的栈顶运算符进行优先权比较,并做如下处理: 
  • 81. (1) 若栈顶运算符的优先级低于刚读入的运算符, 则让刚读入的运算符进operator栈;  (2) 若栈顶运算符的优先级高于刚读入的运算符,则将栈顶运算符退栈,送入θ,同时将操作数栈operand退栈两次,得到两个操作数a、b,对a、 b进行θ运算后, 将运算结果作为中间结果推入operand栈; (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同,说明左右括号相遇,只需将栈顶运算符(左括号)退栈即可。
  • 82. 算法具体描述如下: int ExpEvaluation() /*读入一个简单算术表达式并计算其值。 operator和operand分别为运算符栈和运算数栈, OPS为运算符集合*/ { InitStack(&operand); InitStack(&operator); Push(&operator,′#′); printf(″\n\nPlease input an expression(Ending with #) :″); ch=getchar(); while(ch!=′#′||GetTop(operator)! =′#′) /* GetTop()通过函数值返回栈顶元素*/
  • 83. { if(!In(ch,OPS)) {a=GetNumber(&ch); /* 用ch逐个读入操作数的各位数码, 并转化为十进制数a */ Push(&operand,a);}  else switch(Compare(GetTop(operator),ch)) { case ′<′: Push(&operator,ch);  ch=getchar(); break; case ′=′: Pop(&operator,&x);  ch=getchar(); break; case ′>′: Pop(&operator,&op);
  • 84. Pop(&operand,&b); Pop(&operand,&a); v=Execute(a,op,b); /* 对a和b进行op运算 */ Push(&operand,v); break;  } } v=GetTop(operand); return(v); } 返 回
  • 85. 将中缀表达式转换为后缀表达式
  • 86. 中缀表达式转化为后缀表达式设置一个运算符栈。从左到右依次对中缀表达式中的每个符号进行处理 如果遇到“(”,则将其入栈 如果遇到数字,直接输出 如果遇到运算符a,如果a的优先级高于栈顶符号的优先级,则入栈;否则,栈顶符号出栈,直到a的优先级高于栈顶优先级,此时让a入栈 若遇到“)”,则栈顶符号出栈,直到“)” 重复以上工作,直到表达式结束,此时,将栈里符号去不出栈。中缀表达式1+2*(3-4)+5后缀表达式1 2 3 4 - * + 5+返 回
  • 87. 后缀表达式求值
  • 88. 后缀表达式求值算法从左到右对后缀表达式字符串进行处理,每次处理一个符号 若遇到数字,入栈 若遇到运算符,栈顶两个数字出栈,执行运算符所定义的运算,并将运算结果入栈 重复以上的工作,直到表达式结束,此时,栈中的数字代表最终的值。返 回
  • 89. 将十进制数转化为非十进制数转化方法: 除基数,取余数,结果倒排序 转化算法: While(a) { ran=a%radix; push(ran); a=a/radix; } 返 回
  • 90. 判断一个字符串是否是回文回文的特点 abcba,abba, 算法分析 将字符串的前半部分入栈 设置工作指针i,指向第 n/2 个字符 重复进行以下工作 栈顶元素出栈,与第i个字符比较,如果相同,则i++ 否则,报错,算法结束 返 回
  • 91. (……(…( )… )( ( ) )(((左括号:进栈右括号:与栈顶括号匹配 如果成功, 栈顶括号出栈 如果与栈顶括号不匹配,错误 在处理过程中, 如果输入串不空而栈空,错误; 如果输入串空而栈不空,错误 栈空,并且输入串空,成功 括号匹配的检验
  • 92. ((a) 入栈(012top=3(((b) 入栈(0top=1top=23(23010top=1(d) 遇到)时,出栈一个(。当表达式检测完且栈空时,说明括号全部匹配23(c) 遇到)时,出栈一个(,表示一对括号匹配表达式: ((1+2)*(3+4))返 回