多语言展示
当前在线:1585今日阅读:2今日分享:31

数据结构 第二章 顺序表(下)

三、队列队列的定义:插入端和删除端都是浮动的。通常我们将插入端称为队尾,用一个“队尾指针”指示;而删除端被称为队头,用一个“队头指针”指示。结论:先进先出(First In First Out)表,简称为FIFO线性表。举例1:到医院看病,首先需要到挂号处挂号,然后,按号码顺序救诊。举例2:乘坐公共汽车,应该在车站排队,车来后,按顺序上车。举例3:在Windows这类多任务的操作系统环境中,每个应用程序响应一系列的“消息”,像用户点击鼠标;拖动窗口这些操作都会导致向应用程序发送消息。为此,系统将为每个应用程序创建一个队列,用来存放发送给该应用程序的所有消息,应用程序的处理过程就是不断地从队列中读取消息,并依次给予响应。下面我们给出队列结构的基本操作:(1)初始化队列InitQueue(Q)(2)入队EnQueue(Q,elem)(3)出队DeQueue(Q,elem)(4)获取队头元素内容GetFront(Q,elem)(5)判断队列是否为空QueueEmpty(Q)队列的顺序存储假设为队列开辟的数组单元数目为MAX_QUEUE,在C语言中,它的下标在0~MAX_QUEUE-1之间,若增加队头或队尾指针,可以利用取模运算(一个整数数值整除以另一个整数数值的余数)实现。如下所示:front=(front+1)%MAX_QUEUE;rear=(rear+1)%MAX_QUEUE;当front或rear为MAXQUEUE-1时,上述两个公式计算的结果就为0。这样,就使得指针自动由后面转到前面,形成循环的效果。队空和队满的标志问题:队列变为空,队头和队尾指针相等。解决方法:一是为队列另设一个标志,用来区分队列是'空'还是'满';二是当数组只剩下一个单元时就认为队满,此时,队尾指针只差一步追上队头指针,即:(rear+1)%MAX_QUEUE==front。类型定义:#define MAX_QUEUE 10 //队列的最大数据元素数目typedef struct queue{ //假设当数组只剩下一个单元时认为队满Elemtype elem[MAX_QUEUE]; //存放队列中数据元素的存储单元int front,rear; //队头指针、队尾指针}QUEUE;各项基本操作算法。(1)初始化队列QvoidInitQueue(QUEUE *Q) {Q->front=-1;Q->rear=-1;}(2)入队voidEnQueue(QUEUE *Q,Elemtype elem) {if((Q->rear+1)%MAX_QUEUE==Q->front) exit(OVERFLOW);else {Q->rear=(Q->reasr+1)%MAX_QUEUE;Q->elem[Q->rear]=elem;}}(3)出队voidDeQueue(QUEUE*Q,Elemtype *elem) {if(QueueEmpty(*Q)) exit('Queue is empty.');else {Q->front=(Q->front+1)%MAX_QUEUE;*elem=Q->elem[Q->front];}}(4)获取队头元素内容voidGetFront(QUEUE Q,Elemtype *elem) {if(QueueEmpty(Q)) exit('Queue is empty.');else*elem=Q.elem[(Q.front+1)%MAX_QUEUE];}(5)判断队列Q是否为空intQueueEmpty(Queue Q) {if(Q.front==Q.rear) return TRUE;else returnFALSE;}队列的应用举例【举例1】汽车加油站。随着城市里汽车数量的急速增长,汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是:入口和出口为单行道,加油车道可能有若干条。每辆车加油都要经过三段路程,第一段是在入口处排队等候进入加油车道;第二段是在加油车道排队等候加油;第三段是进入出口处排队等候离开。实际上,这三段都是队列结构。若用算法模拟这个过程,就需要设置加油车道数加2个队列。【举例2】模拟打印机缓冲区。在主机将数据输出到打印机时,会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然,这样会降低主机的使用效率。为此人们设想了一种办法:为打印机设置一个打印数据缓冲区,当主机需要打印数据时,先将数据依次写入这个缓冲区,写满后主机转去做其他的事情,而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印,这样做即保证了打印数据的正确性,又提高了主机的使用效率。由此可见,打印机缓冲区实际上就是一个队列结构。【举例3】CPU分时系统在一个带有多个终端的计算机系统中,同时有多个用户需要使用CPU运行各自的应用程序,它们分别通过各自的终端向操作系统提出使用CPU的请求,操作系统通常按照每个请求在时间上的先后顺序,将它们排成一个队列,每次把CPU分配给当前队首的请求用户,即将该用户的应用程序投入运行,当该程序运行完毕或用完规定的时间片后,操作系统再将CPU分配给新的队首请求用户,这样即可以满足每个用户的请求,又可以使CPU正常工作。本章附录一、约瑟夫(Josephus)问题【问题提出】编号为1,2,···,n的n个人按顺时针方向围坐在一张圆桌旁,每个人手中持有一个密码(正整数)。首先输入一个正整数作为报数上限值m,然后,从第一个人开始按顺时针方向自1开始顺序报数,报到m的人离开桌旁,并将他手中的密码作为新的m值,从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数,如此下去,直至所有人全部离开桌旁为止。假设有7个人,编号从1到7,他们手中的密码分别是3,1,7,2,4,8,4,最初的m=2,通过报数,这7个人离开桌旁的顺序应该是:2,3,5,4,7,6,1。【数据结构的分析】这个问题的主角是n个人,每个人需要描述的信息有:编号、密码和是否在桌旁的状态。假设有7个人,他们的信息可以表示成下面的形式。【算法设计】见书P21【算法实现】顺序存储结构#define LIST_MAX_LENGTH 7#define n LIST_MAX_LENGTHtypedef int Elemtype; //将Elemtype定义为int类型void Joseph(int code[],int n) {//通过一维数组code带入n个人手中的密码,n是开始就坐在桌旁的人数SEQLIST people;int temp,m; //m是报数的上限值scanf('%d',&m); //输入最初的mif (InitList(&people)==ERROR) exitERROR;for (i=1;i<=n;i++)if(ListInsert(&people,i,code[i-1])==ERROR) exit ERROR;position=0; //记录当前报数人的编号for (i=1;i<=n;i++) {count=0; //记录当前所报的数目do{ //报数position=(position+1)%n;GetElem(people,position,&temp);if (temp>0) count++;}while (count!=m);printf('%d',position); //输出当前离开桌旁人的编号GetElem(people,position,&m);people.elem[position-1]=-people.elem[position-1]; //将密码变为负值}}链式存储结构使用一个不带头结点的循环单链表结构。结点结构为:用C语言定义typedef struct { //循环链表中每个结点的数据域部分的类型int No; //编号int code; //密码}INFO;typedef INFO Elemtype;算法void Joseph(int code[],int n) {LINK_LIST people;LINKLIST *position,*pre; //position指向当前报数的结点if (InitList(&people)==ERROR) exit ERROR; //初始化链表peoplefor (i=1;i<=n;i++) //以n个人的信息为数据域内容向链表插入n个结点if(ListInsert(&people,i,code[i-1])==ERROR) exit ERROR;position=people.head; //让position指向最后一个结点,以便报数从第一个开始while (position->next!=people.head)position= NextElem(people,position);scanf('%d',&m); //输入最初的mfor (i=1;ielem.No); //离开桌子处理m=position->elem.code;pre=PriorElem(people,position);pre->next=position->next;free(position);position= pre;}printf('%d',position->elem.No); //处理最后一个人free(position);}二、背包问题一、问题描述:在M件物品取出若干件放在空间为W的背包里,每件物品的重量为W1、W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案(其中所有的重量值均为整数)。二、算法分析:对于背包问题,通常的处理方法是搜索。用递归来完成搜索,算法设计如下:function Make(i {处理到第i件物品},j{剩余的空间为j}:integer):integer;初始时i=m,j=背包总容量beginif i:=0 then Make:=0;if j>=wi then (背包剩余空间可以放下物品i) r1:=Make(i-1,j-wi)+v[i];(第i件物品放入所能得到的价值) r2:=Make(i-1,j) (第i件物品不放所能得到的价值) Make:=max{r1,r2}end;由于本题中所有物品的重量均为整数,经过几次的选择后背包的剩余空间可能会相等,在搜索中会重复计算这些结点,所以,如果把搜索过程中计算过的结点的值记录下来,以保证不重复计算的话,速度就会提高很多。这是简单的'以空间换时间'。由于这些计算过程中会出现重叠的结点,符合动态规划中子问题重叠的性质。同时,可以看出如果通过第N次选择得到的一个最优解的话,那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。考虑用动态规划的方法来解决,这里的:阶段是:在前N件物品中,选取若干件物品放入背包中;状态是:在前N件物品中,选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值;决策是:第N件物品放或者不放;由此可以写出动态转移方程:现用f[i,j]表示在前i件物品中选择若干件放在所剩空间为j的背包里所能获得的最大价值。f[i,j]=max{f[i-1,j-Wi]+Pi(j>=Wi),f[i-1,j]}这样,可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值,也就是f[m,w]。算法设计如下:procedure Make;beginfor i:=0 to w do f[0,i]:=0;for i:=1 to m do for j:=0 to w do begin f[i,j]:=f[i-1,j]; if(j>=w[i])and(f[i-1,j-w[i]]+v[i]>f[i,j] then f[i,j]:=f[i-1,j-w[i]]+v[i]; end;writeln(f[m,wt]);end;由于是用了一个二重循环,这个算法的时间复杂度是O(n*w)。而用搜索的时候,当出现最坏的情况,也就是所有的结点都没有重叠,那么它的时间复杂度是O(2^n)。看上去前者要快很多。但是,可以发现在搜索中计算过的结点在动态规划中也全都要计算,而且这里算得更多,在这一点上有点矛盾。事实上,由于前提是所有的结点都没有重叠。也就是说,任意N件物品的重量相加都不能相等,而所有物品的重量又都是整数,那末这个时候W的最小值是:1+2+2^2+2^3+……+2^n-1=2^n-1此时n*w>2^n,动态规划比搜索还要慢,所以,其实背包的总容量W和重叠的结点的个数是有关的。三、程序代码:#include#includeint knap(int s, int n, int w[]){ if (s==0) return (1); else if(s<0||s>0&& n<1) return(0); else if(knap(s-w[n-1],n-1,w)==1){ printf('result:n=%d,w[%d]=%d \n',n,n-1,w[n-1]); return (1); } else return(knap(s,n-1,w));}int main(){ int * w; ints=0,n=0,result=0,i=0; printf('pleaseinput s= ');/*输入s*/ scanf('%d',&s); printf('pleaseinput n= ');/*输入n*/ scanf('%d',&n); w=(int*)malloc(n*sizeof(int)); printf('pleaseinput the %d numbers(weight):\n',n);/*输入重量*/ for(i=0;i