大学计算机:教学课件:-数据结构常见算法.ppt
- 文档编号:15914648
- 上传时间:2023-07-09
- 格式:PPT
- 页数:92
- 大小:657KB
大学计算机:教学课件:-数据结构常见算法.ppt
《大学计算机:教学课件:-数据结构常见算法.ppt》由会员分享,可在线阅读,更多相关《大学计算机:教学课件:-数据结构常见算法.ppt(92页珍藏版)》请在冰点文库上搜索。
数据结构算法,数据结构,数据结构是一门研究非数值计算的程序设计问题中的操作对象(结点)以及它们之间关系和操作等的学科。
1968年克努思教授开创了数据结构的最初体系,他所著的计算机程序设计艺术第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
70年代初,数据结构作为一门独立的课程开始进入大学课堂。
下面介绍数据结构中常见的一些基本算法,关于算法线性表上的常见算法基于队列的常见算法基于栈的常见算法,数据结构常见算法,算法,多项式求的两种方法A(x)=anxn+an-1xn-1+a0A(x)=(anx+an-1)X+an-2)+a0,A(x)=anxn+an-1xn-1+a0,templateTPoly1(Ta,intn,Tx)inti,j;Tresult=0;Txn,xx;for(i=0;in;i+)xn=1;xx=x;for(j=0;ji;j+)xn=xn*xx;result=ai*xn+result;returnresult;,A(x)=(anx+an-1)X+an-2)+a0,templateTPoly2(Ta,intn,Tx)inti,j;Tresult=0;Txn,xx;result=an-1;for(i=n-1;i0;i-)result=result*x+ai-1;returnresult;,线性表,设计一个时间复杂度为O(n)的算法,实现将数组An中所有元素循环右移K个位置已知数组元素为整型,设计算法将其调整为左右两部分,左边元素为奇数,右边元素为偶数设单链表以非递减有序排列,设计算法,实现在单链表中删去系统的多余结点设单链表以非递减有序排列,设计算法,实现在单链表中删去系统的多余结点已知一个单链表中的数据元素含有三类字符:
数字、字母和其他字符。
编写算法,构造三个循环链表,使得每个循环链表中之包含同一类字符,返回,设计一个时间复杂度为O(n)的算法,实现将数组An中所有元素循环右移K个位置,算法分析kn。
k=k%N,A,B(k=1),B(k=2),B(k=3),j=(i+k)%N,inti,j,n;int*a;cinnk;k=k%n;a=newintn;for(i=0;iai;for(i=0;in;i+)j=(i+k)%n;bj=ai;,时间复杂度?
空间复杂度?
空间复杂度更少的方法,假设原数组序列为abcd1234,循环右移了4位数组序列为1234abcd。
右移后,有两段的顺序是不变的:
1234和abcd,可把这两段看成两个整体。
右移K位的过程就是把数组的两部分交换一下。
变换的过程通过以下步骤完成:
1.逆序排列abcd:
abcd1234dcba1234;2.逆序排列1234:
dcba1234dcba4321;3.全部逆序:
dcba43211234abcd。
更一般的情况:
根据K%N的大小,将数据分成两段,第一段长度为N-K个数据,第二段中有K个数据然后分别将两段逆序,最后将整个数组逆序,voidconvert(inta,intstart,intend)intk,temp;for(k=0;k(end-start+1)/2;k+)temp=astart+k;astart+k=aend-k;aend-k=temp;,voidyiwei(inta,intn,intk)convert(a,0,k-1);convert(a,k,n-1);convert(a,0,n-1);,已知数组元素为整型,设计算法将其调整为左右两部分,左边元素为奇数,右边元素为偶数,算法分析设计两个工作指针,分别指向数组的两端(I=0;j=n-1).然后,重复的进行以下工作:
如果ij:
从左向后扫描数组,直到遇到第一个偶数从右向左扫描数组,直到遇到第一个奇数如果ij交换ai、aj的数据,同时修改i,j的值,继续进行2的工作,intn,*a;cinn;a=newintn;inti=0,j=n-1;for(i=0;iai;i=0;while(ij)while(ai%2=1)i+;while(aj%2=0)j-;if(ij)temp=ai;ai=aj;aj=temp;i+;j-,#includestdafx.h#includeclasschangeprivate:
int*a,length;public:
change()coutlength;a=newintlength;coutai;,voidtrans()inti=0,j=length-1;inttemp;while(ij)while(ai%2=1)i+;while(aj%2=0)j-;if(ij)temp=ai;ai=aj;aj=temp;i+;j-;return;,voiddisplay()inti=0;for(i=0;ilength;i+)coutai;coutendl;intmain(intargc,char*argv)changea;coutbeforechange:
;a.display();a.trans();coutafterchange:
;a.display();return0;,返回,设单链表以非递减有序排列,设计算法,实现在单链表中删去系统的多余结点,基本思想:
从头结点出发,进行链表的遍历,在遍历的过程中,设置两个工作指针p和q(q=p-next),比较p、q所指向的节点的值,如果相同,则删除q所指向的节点,,算法描述,设置工作指针p、q,并进行初始化:
p=list.head-next;if(!
p)returnelseq=p-next;在q!
=NULL的情况下,重复进行以下工作:
if(p-data=q-data)temp=q;p-next=q-next;q=p-next;deletetempelsep=q;q=q-next;,templatevoidDeleteSame(LinkLista)Node*p,*q,*temp;p=a.GetHead()-next;if(!
p)coutnext;while(q)if(p-data=q-data)temp=q;p-next=q-next;q=p-next;deletetemp;elsep=q;q=q-next;return;,判断带头节点的双循环链表是否对称,设置两个工作指针p=首元节点,q=尾节点,重复进行以下工作:
比较p和q的值,如果不想等,停止比较,返回false如果相等,观察p、q是否相邻(p-right=q,p-right-right=q),如果相邻,返回true,否则p=p-right,q=q-left,first,1.定义两个工作指针、,并进行初始化:
=list.first-right;q=list.first-left;2.重复进行以下工作(while
(1)if(p-data!
=q-datareturnfalse;elseif(p-right=q|p-right-right=q)returntrue;elsep=p-right;q=q-left;,返回,已知一个单链表中的数据元素含有三类字符:
数字、字母和其他字符。
编写算法,构造三个循环链表,使得每个循环链表中之包含同一类字符,基本思想每个链表都带有头结点。
原始链表为A,分类之后新增B,C,使得A存放字母,B存放数字,C存放其他字符基本过程:
在A中进行遍历,并检查遍历到的符号,如果是字符,不做任何处理(继续后移指针);如果是数字,则将其采用尾插法加入到B中(继续后移指针),如果是第三类符号,则将其采用尾插法插入到C中(继续后移指针),算法分析,已知链表A,构造两个空循环链表B(数字),C(其他字符)设置工作指针p;p=A.first(头结点)定义一个辅助指针q,完成工作:
q=p-next;如果q!
=A.firstIsDigital(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链表遍历结束,templatestructNodeTdata;Node*next;templateclassCycleListNode*head,*rear;intLength;public:
CycleList()head=newNode;head-next=head;rear=head;CycleList(intn);voidDisplay();Node*GetHead()returnhead;voidappend(Node*p);friendvoidSegment(CycleLista);,templatevoidCycleList:
append(Node*p)p-next=rear-next;rear-next=p;rear=p;return;,templateCycleList:
CycleList(intn)Tinput;Node*s;head=newNode;head-next=head;rear=head;Length=n;inti=0;for(i=0;iinput;s=newNode;s-data=input;append(s);,templatevoidCycleList:
Display()Node*p;p=head-next;while(p!
=head)coutdatanext;coutendl;,templatevoidSegment(CycleListA)Node*p,*q,*ahead,*temp;CycleListB,C;coutnext;,templatewhile(q!
=ahead)if(q-data=0,intmain(intargc,char*argv)CycleListA(10);A.Display();Segment(A);return0;,返回,templatewhile(q!
=ahead)if(q-data=0,队列,求解素数环问题列车重排问题杨辉三角形,返回,求解素数环问题,问题描述:
将n个自然数排成环,使得每相邻两数之和为素数,构成一个素数环。
例子:
1,2,3,4,7,10,9,8,5,6,求解思想,先将1放入素数环中。
对2n之间的自然数组成对列,依次将元素出队,测试其是否与素数环中的最后一个数的和为素数,如成立,则将其加入素数环,否则,将其加入到对列中,等待再次处理重复2中操作,直到队列空,代码分析,publicclassPrimeRingpublicPrimeRing(intn)SeqListring=newSeqList(n);ring.add(newInteger
(1);LinkedQueueq=newLinkedQueue();for(inti=2;i=n;i+)q.enqueue(newInteger(i);,inti=0;while(!
q.isEmpty()intk=q.dequeue().intValue();/出队System.out.print(dequeue:
+k+t);if(isPrime(ring.get(i)+k)i+;ring.add(newInteger(k);elseq.enqueue(newInteger(k);System.out.println(素数环:
+ring.toString();,返回,判断一个正整数a是不是素数,只要将所有的小于等于根号a且大于1的素数都除不尽,则a就是素数。
这是判断素数引理6首先0和1不是素数、2是素数、能被2整除的不是素数,(素数肯定是奇数)排除这些数后然后对num进行开平方根,从3开始到这个平方根,每隔2判断一下(奇数肯定不能被偶数整除),看看num能否被其整除,如果能就不是素数,否则,一直检查到最后都没有,那么这个数一定是素数。
publicbooleanisPrime(intk)/判断k是否为素数if(k=2)returntrue;if(k2,返回,队列应用举例-火车厢重排,问题描述:
对任意序列的火车厢,进行重排,使其按照1,2,3,.n的顺序进行排列(起始序列为:
5,8,1,7,4,2,9,6,3),火车站,列车,队列应用举例-火车厢重排,解决方案:
利用缓冲轨进行重排,1.分别对k个队列初始化;2.初始化下一个要输出的车厢编号nowOut=1;3.依次取入轨中的每一个车厢的编号;3.1如果入轨中的车厢编号等于nowOut,则3.1.1输出该车厢;3.1.2nowOut+;,队列应用举例-火车厢重排,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.2nowOut+;,队列应用举例-火车厢重排,3.3如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢,则(如果前两步工作都不成立)3.3.1求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;3.3.2如果j存在,则把入轨中的第一个车厢移至缓冲轨j;3.3.2如果j不存在,但有多于一个空缓冲轨,则把入轨中的第一个车厢移至一个空缓冲轨;否则车厢无法重排,算法结束;,队列应用举例-火车厢重排,返回,杨辉三角形,打印杨辉三角,杨辉三角形元素入队顺序,
(1)第7行的第一个元素1入队。
elementrear=1;rear=(rear+1)%MAXSIZE;
(2)循环做以下操作,产生第7行的中间5个元素并入队。
elementrear=elementfront+element(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;front=(front+1)%MAXSIZE;,(3)第6行的最后一个元素1出队。
front=(front+1)%MAXSIZE;(4)第7行的最后一个元素1入队。
elementrear1;rear=(rear+1)%MAXSIZE;,下面给出打印杨辉三角形的前n行元素的具体算法:
voidYangHuiTriangle()SeqQueueQ;InitQueue(/*打印第n-1行的元素*/,GetHead(Q,/*打印第n-1行的最后一个元素*/EnterQueue(&Q,1)/*第n行的最后一个元素入队*/,返回,栈,迷宫问题骑士巡游问题中缀表达式求值问题中缀表达式转换为后缀表达式的问题后缀表达式求值问题数制转换问题回文的判断括号匹配问题,返回,有一个迷宫,迷宫里面有很多隔断。
给定一个入口和出口,判断从入口到出口是否有通路。
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。
迷宫问题,1111111110100011100010111101001110001111101100011000011111111111,1111111110100011100010111101001110001111101100011000011111111111,迷宫问题算法:
从入口出发,顺着某一个方向进行探索(三个方向),若能走通,则继续前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路,假如所有可能的通路都探索到而未能达到出口,则所设定的迷宫没有通路.,1111111110100011100010111101001110001111101100011000011111111111,迷宫问题算法:
从入口出发,顺着某一个方向进行探索,若能走通,则继续前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路,用栈实现:
从入口出发,顺着某一个方向进行探索,若能走通,则继续前进,此时,将当前在迷宫中的位置和探测的(下一次)方向入栈,如果走不通,则根据这个信息在新的方向上进行探测,1111111110100011100010111101001110001111101100011000011111111111,定义四个方向0表示向东1表示向西2表示向北3表示向南Nx0=0ny0=-1Nx1=0ny1=1Nx2=-1ny2=0Nx3=1ny3=0,定义trace记录是否已经走过位置某个,1111111110100011100010111101001110001111101100011000011111111111,入口:
1,1每次探测都是沿东、西、北、南的方向进行探测首先将(1,1,-1)入栈。
其中:
入口1,1,第三个值表示在这个位置上的下一次探测的方向,1111111110100011100010111101001110001111101100011000011111111111,如果栈不空,并且没有到达出口,则根据栈顶的信息计算新的位置,检查该位置是否可行,如果成立,则将该位置和在该位置的下一个探测方向入栈,否则继续探测如果探测失败,将栈顶出栈,并计算新的位置如果栈空,表示从入口到出口没有通路,否则,栈中的数据即为通路。
返回,#includestdafx.h#include#includeusingnamespacestd;structsiteintx,y;intfrom,direct;,intmain(intargc,char*argv)stacksite_stack;intm,n;int*maze;inti,j;intcurrent_x,current_y,out_x,out_y,direction,from;intnx4,ny4;nx0=0;ny0=-1;nx1=0;ny1=1;nx2=-1;ny2=0;nx3=1;ny3=0;,coutmn;maze=newint*m+2;trace=newint*m+2;for(i=0;imazeij;traceij=0;,cincurrent_xcurrent_y;while(mazecurrent_xcurrent_y=1)coutcurrent_xcurrent_y;coutout_xout_y;sitestart;start.x=current_x;start.y=current_y;start.direct=-1;site_stack.push(start);,while(!
site_stack.empty()/探测方向,while(mazexy=1|tracexy=1),if(mazexy=0,sitepath;while(!
site_stack.empty()path=site_stack.top();cout(path.x,path.y);site_stack.pop();return0;,采用递归方法解决迷宫问题,boolend=false;boolfind=false;boolsearch(intx,inty,intdirection)intnew_x,new_y;if(x=out_x,骑士巡游,编写程序求解骑士巡游问题在n行n列的棋盘上(如n=5),假设一位骑士(按象棋中“马走日”的行走法)从初始坐标位置(x1,y1)出发,要遍访(巡游)棋盘中的每一个位置一次。
请编一个程序,为骑士求解巡游路线图“或告诉骑士,从某位置出发时,无法遍访整个棋盘-问题无解,骑士游历,骑士游历,骑士游历,有八个移动方向1na0=-2ny0=12na1=-1ny1=23na2=1ny2=24na3=2ny3=15na4=2ny4=-16na5=1ny5=-27na6=-1ny6=-28na7=-2ny7=-1,骑士游历,骑士游历,将初始位置、下一个探测方向入栈,设置当前探测方向为已探测,并计算新的位置如果栈不空,并且还有未遍历的位置如果新位置可行,则将新位置、下一个探测入栈,并设置当前位置为已探测否则,栈顶元素出栈,并计算新的位置;如果栈空,则失败;否则,站内记录有效信息,返回,表达式求值是高级语言编译中的一个基本问题,是栈的典型应用实例。
表达式的组成:
操作数(operand):
操作数既可以是常数,也可以是被说明为变量或常量;运算符(operator):
运算符可以分为算术运算符、关系运算符和逻辑运算符三类界限符(delimiter):
基本界限符有左右括号和表达式结束符等。
中缀表达式求值,表达式运算及运算符优先级,1)无括号算术表达式求值,无括号算术表达式的处理过程,2)算术表达式处理规则
(1)规定算符的优先级表。
(2)设置两个栈:
OVS(运算数栈)和OPTR(运算符栈)。
(3)自左向右扫描,遇操作数进OVS,遇操作符则与OPTR栈顶优先数比较:
当前操作符OPTR栈顶,当前操作符进OPTR栈当前操作符OPTR栈顶,OVS栈顶、次顶和OPTR栈顶,退栈形成运算T(i),T(i)进OVS栈。
例:
实现A/BC+D*E的运算过程时栈区变化情况如图3.7所示。
图3.7A/BC+D*E运算过程的栈区变化情况示意图,3)带括号算术表达式假设操作数是整型常数,运算符只含加、减、乘、除等四种运算符,界限符有左右括号和表达式起始、结束符“”,如:
(7+15)*(23-28/4)。
引入表达式起始、结束符是为了方便。
要对一个简单的算术表达式求值,首先要了解算术四则运算的规则,即:
(1)从左算到右;
(2)先乘除,后加减;(3)先括号内,后括号外。
运算符和界限符可统称为算符,它们构成的集合命名为OPS。
根据上述三条运算规则,在运算过程中,任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一:
12,1的优先权高于2。
表3-1算符之间的优先关系,实现算符优先算法时需要使用两个工作栈:
一个称作operator,用以存放运算符;另一个称作operand,用以存放操作数或运算的中间结果。
算法的基本过程如下:
首先初始化操作数栈operand和运算符栈operator,并将表达式起始符“”压入运算符栈;依次读入表达式中的每个字符,若是操作数则直接进入操作数栈operand,若是运算符,则与运算符栈operator的栈顶运算符进行优先权比较,并做如下处理:
(1)若栈顶运算符的优先级低于刚读入的运算符,则让刚读入的运算符进operator栈;
(2)若栈顶运算符的优先级高于刚读入的运算符,则将栈顶运算符退栈,送入,同时将操作数栈operand退栈两次,得到两个操作数a、b,对a、b进行运算后,将运算结果作为中间结果推入operand栈;(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同,说明左右括号相遇,只需将栈顶运算符(左括号)退栈即可。
算法具体描述如下:
intExpEvaluation()/*读入一个简单算术表达式并计算其值。
operator和operand分别为运算符栈和运算数栈,OPS为运算符集合*/InitStack(while(ch!
=|GetTop(operator)!
=)/*GetTop()通过函数值返回栈顶元素*/,if(!
In(ch,OPS)a=GetNumb
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学计算机 教学 课件 数据结构 常见 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)