[少数民族谚语]少数民族谚语大全少数民族谚语大全包括了中国境内最常见的少数民族的谚语，包括：满族、蒙古族、白族、侗族、傣族、彝族、回族、藏族、维吾尔族、哈萨克族、苗族、彝族、壮族等民族的谚语。 本文少数民族谚语大全由纯真网编辑收集整理，希望大家喜欢！
土家族谚语
哈萨克族谚语
维吾尔族谚语
蒙古族的谚语
藏族的谚语
以上这篇少数民族谚语大全就为您介绍到这里，希望它对您有帮助。如果您喜欢这篇文章，不妨分享给您的好友吧。更多经典不同种类的谚语在：谚语 ！上一篇：下一篇：精选图文最新文章08-2808-2808-2808-2808-28您还可以使用以下方式登录
当前位置：&>&&>& > 少数民族谚语：土家族谚语
少数民族谚语：土家族谚语
&少数民族谚语：土家族谚语　　山高石头多，出门就爬坡　　上山雾里钻，下山到潭边　　望见屋，走得哭　　山高一丈，大不一样;阴坡阳坡，差得很多　　立春雨水早，早起晚睡觉　　惊蛰不动风，冷到五月中　　立夏不下，犁耙高挂　　小满不满，干断田坎　　冬前不见冰，冬后冻死人　　天上有云丝，晴天便可知　　早上薄薄云，中午晒死人　　雷公先唱歌，有雨也不多　　有雨山戴帽，无雨山抹腰　　石头出汗，大雨连线　　盐罐回潮，大雨难逃　　蚂蚁搬家雨必淋，蜘蛛结网天必晴&　　狗子吃草干死草，狗子喝水雨滔滔职业生涯规划书大学生职业生涯规划书结束语
欢迎转载：
推荐： 　　　您还可以使用以下方式登录
当前位置：&>&&>& > 天气谚语的深入研究（共2篇）
天气谚语的深入研究（共2篇）
以下是网友分享的关于天气谚语的深入研究的资料2篇，希望对您有所帮助，就爱阅读感谢您的支持。
作者简介 博士主要从事河流海岸动力学方面的研究溃坝洪水的统一二维数学模型防洪减灾研究所 北京摘要 本文通过资料分析 的理论基础 利用作者以往的洪水冲刷试验研究成果模拟溃坝洪水过程的数值模拟 等关键词 溃坝 数值模拟 格尔木温泉水库尤其是对于高坝大库 一旦失事其危害十分巨我国有各类水库大坝亿的大型水库就有问题 正是由于溃坝洪水的巨大危害性 如 丹麦的年由欧盟支持启动的年 专门对目前世界上一些有影响的模型进行了比较分析 在我国 系统研究溃坝数值模型始于世纪以后针对我国一些水库的实际问题开展了一些模型研究 具有一维特征 以往的做法大多是将分别数值处理工作量较大 接另一方面 现有溃坝模型对于土石坝逐渐溃模式采用的一些假定 数学模型水流运动基本方程从水流运动方程的物理意义可知 一维水流运动方程只是平面二维流动的一二维水流连续方程二维水流运动方程为糙率图计算网格方程离散格式 可以看出 如果假定平面二维情况下方这表明 数值模型计算中可以通过采用合适的数值离散方案参照图为计算时段步长分别表示时段始末相应值与流动方向的通道设置为不透水边界 则以通道和节点构成的二维计算格式就完全转化为一维计算问溃坝流量过程计算根据不同的坝型和坝体材料况溃口底部高程土石坝溃坝模式对于混凝土重力坝的溃坝模式一般采用瞬间部参考许多国际溃坝洪水模型的做法 假定所溃坝时出口流量由两部分组成 一部分是溃口流量 另式中为坝前溃口水深为溃口宽度 为流量和对于有效水深程要求可以采用两种方法满足 另一种方法是将水库上游 来水流量过程进行动态计算联立求解得到对于土石坝围堰的溃坝流量计算上述各式中为溃口处的糙率系数为流速 为任意时刻溃为溃口发展任一时刻的平均宽度 为土石物质的干容重参见图横向上由水流强度和 模式利用国外某坝的试验资料计算验证土石坝的溃口冲扩工程算例格尔木温泉水库位于青海省格尔木市南 大坝为复合土 工膜砂砾石坝坝高由于大坝与格尔木市之间的河道格尔木市现有人口万图模型计算范围及网格布置 图 模型计算范围及网格布置平面二维区域淹没水深等值线采用上述模型对温泉水库溃坝洪水及影响范计算范围包括维河道和格尔木市约 面积的城市及周边 区域 全部计算区域采用二维网格离散网格布置及接口如图 一维网格部分的河道地流量一维演进过程和二维淹没区域范围如图左右 对比了国内外一些常用经验和特别是约计算中也发现结论新的溃口发展模式 实际工程算例表明 用一个适当数值离散的二维模型坝洪水波到达的初期存在不稳定现象参 考 文献林秉南 龚振瀛 王连祥魏文礼 等裴爱国 等黄金池 万兆惠谢任之编著黄金池 王兆印 等黄金池篇2
兰州城市学院毕业设计(论文)
学号33 密级
兰州城市学院本科毕业论文
队列的深入研究及应用
学 院 名 称:信息工程学院 专 业 名 称:计算机科学与技术 学 生 姓 名:赵莉来 指 导 教 师:朱正平
二?一二年五月 - I -兰州城市学院毕业设计(论文) BACHELOR'S DEGREE THESIS OF LANZHOU CITY UNIVERSITY
The Deeply Research and Apply of Queue
College :School of Information Engineering Subject :Computer Science and technology Name :Zhao Li lai Directed by:Zhu Zheng ping
May 2012 - II -兰州城市学院毕业设计(论文)
郑 重 声 明
本人呈交的学位论文，是在导师的指导下，独立进行研究工作所取得的成果，所有数据、图片资料真实可靠。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确的方式标明。本学位论文的知识产权归属于培养单位。
本人签名: 日 期:
- III -兰州城市学院毕业设计(论文) 摘 要 队列是一种重要的数据类型。队列在各种类型的系统中应用广泛。在传统的数据结构的研究中，通常只讨论单循环队列等数据类型，并且这些数据类型的存储结构总是事先开辟好定量空间，导致了在具体应用中存储空间不同程度的浪费，以往的文献中并未就此问题做深入探究以求解决。本文就队列的应用中，其存储空间的动态分配和动态回收做了深入研究并得到了实现方法，同时对循环多队列等文献中涉及较少的存储结构给出了具体实现方法。最后用这些结构解决了一些具体问题。
关键词:队列;存储结构;存储空间;动态分配
- IV -兰州城市学院毕业设计(论文) Abstract Queue is an important kinds of data structures,it is widely used in varieties of systems. What we usually discussed in traditional data structures about queue are link-queue and sequential-circulating queue. Just like queue, we discuss the feature of storage structures of circulating-queue, and implement dynamic storage which can avoid the lack of space as well as a waste of it on the basis of traditional queue. On account of practical need, we present multi-circulating queue and discuss the feature of storage structures, implement dynamic storage and use them in practical problem so that it can provide theoretical basis for more reasonable and flexible queue systems of service. The dynamic technology and multi-queue have solved many practical problems. These different kinds of "flexible cup" have overcame lots of puzzles in practical systems. Perhaps this technology can bring revolutionary changes to the development of software.
Key Words: Q Storage S Storage S Dynamic Storage
- V -兰州城市学院毕业设计(论文) 目 录 摘 要 ............................................................................................................................ IV Abstract ................................................................................................................................. V 引 言 ...............................................................................................................................1 1 队列 ...................................................................................................................................2 1.1队列的定义 ..............................................................................................................2 1.2多队列技术 ..............................................................................................................3 1.2.1 循环多队列 .................................................................................................3 1.2.2动态循环多队列 ............................................................................................4 1.3队列的应用 ............................................................................................................ 10 结 论 ............................................................................................................................. 13 致 谢 ............................................................................................................................. 14 参 考 文 献 ........................................................................................................................ 15 附录A 循环多队列的顺序存储和算法实现 ...................................................................... 16- VI -兰州城市学院毕业设计(论文) 引 言 队列是一种重要的抽象数据类型，是一种操作受限的特殊线性表，其特殊性在于限制插入和删除等运算的位置。在队列中，用户只能在一端插入元素而在另一端删除元素，因此呈现先进先出的特性。从数据结构角度看，是线性结构队列在各种类型的软件系统中应用广泛。在操作系统和事务管理中广泛应用了队列技术，讨论队列的结构特征与操作实现特点，有着重要的意义。 循环队列是队列的一种顺序表示和实现方法。与顺序栈类似，在队列的顺序存储结构中，可以用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组Queue[MAXSIZE]。此外，由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front 和rear，分别指示队头元素和队尾元素在数组中的位置。 循环多队列的顺序存储在定义时已经开辟了一定的空间，在存储时，若存储的数据量太小，则会造成存储空间的浪费;但若存储的数据量太大，会发生存储空间不够用的问题，又需要扩大存储空间。相比之下，链式存储的方法更优，其只在插入数据元素时开辟节点的空间，且先确定插入元素然后才开辟，另外，其在出队时立即将要删除元素所占用的空间释放。因此既不会浪费存储空间，也不会发生存储空间不足的问题。但是，若编程语言不提供指针类型，那么链式存储结构就不能实现。所以，对于使用VB等没有指针类型的开发工具的编程人员来说，循环多队列顺序存储结构的研究为其提供了理论依据，同时为应用系统的开发提供了一种新的实现技术。 - 1 -兰州城市学院毕业设计(论文)
1 队列 1.1队列的定义 队列(Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out，FIFO)的特性。这与我们日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人总是加入到队尾。在队列中，允许插入的一端叫做队尾(rear) ，允许删除的一端叫做队头(front)。假如队列为q=(a1，a2，…an )，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…an的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，…an-1都离开队列之后，an才能退出队列。 队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。 下面给出队列的抽象数据类型定义: ADT Queue 数据元素:可以是任意类型的数据，但必须属于同一个数据对象。 关系:队列中数据元素之间是线性关系。 基本操作: InitQueue(&Q):初始化操作。设置一个空队列。 IsEmpty(Q):判空操作。若队列为空，则返回TRUE，否则返回FALSE。 IsFull(Q):判满操作。若队列为满，则返回TRUE，否则返回FALSE。 EnterQueue(&Q，x):进队操作。在队列Q的队尾插入x。操作成功，返回值为TRUE，否则返回值为FALSE。 DeleteQueue(&Q，&x):出队操作。是队列Q的队头元素出队，并用x带回其值。操作成功，返回值为TRUE，否则返回值为FALSE。 GetHead(Q，&x):取队头元素操作。用x取得队头元素的值。操作成功，返回TRUE，否则返回值为FALSE。 ClearQueue(&Q):队列置空操作。将队列置为空队列。 DestroyQueue(&Q):队列销毁操作。释放队列的空间。
- 2 -兰州城市学院毕业设计(论文) 1.2多队列技术 1.2.1 循环多队列 循环多队列的顺序存储结构的定义方式如下: typedef struct { int front, } // 每一个队列需要一个对头和一个队尾指针 typedef struct { ElemType queue[N][M]; /*循环多队列的存储空间, ElemType为数据元素的类型*/ fnode f[N]; /*用来指示N个队列的队头与队尾*/ }MultyQ f[i].front为第i个循环队列的队头指针，f[i].rear为第i个循环队列的队尾指针，queue[N][M]为循环多队列的存储空间。定义的多队列结构如图2.9所示。 f[N] queue[N][M ]
front rear 0 1 2 3 ,, M-1 0 0 0 3 11 12 13 1 1 3 1 24 21 22 23 2 2 1 3 31 32 ,, ,, N-1 N-1 1 2 41
图1.1 多队列示意图 在单队列中，不管是用链式存储结构还是用顺序存储结构其实现都很简单。因为在单队列中只有一个队头和一个队尾，而在多队列中，由于存在多个队列，同时也有多个指针来指示每个队列队头和队尾的位置。故抽象数据类型多队列的基本操作中需要增加一个参数i来指定对哪个队列进行操作。 (1) 初始化 Status InitQueue(MultyQueue *Q) { for(i=0;i<N;i++) Q->f[i-1].front=Q->f[i-1].rear=0;
return OK; - 3 -兰州城市学院毕业设计(论文) } (2) 入队 Status EnQueue(MultyQueue *Q,int i,ElemType e) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ if((Q->f[i-1].rear+1)%M= =Q->f[i-1].front) return OVERFLOW; /*第i个队列已满*/ Q->queue[i-1][Q->f[i-1].rear]=e; Q->f[i-1].rear=(Q->f[i-1].rear+1)%M; return OK; } (3) 出队 Status DeQueue(MultyQueue *Q,int i,ElemType *e) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ if(Q->f[i-1].front= =Q->f[i-1].rear) return OVERFLOW; /*第i个队列已满*/
*e=Q->queue[i-1][Q->f[i-1].front];
Q->f[i-1].front=(Q->f[i-1].front+1)%M;
return OK; } 1.2.2动态循环多队列 此处所定义的循环多队列的动态存储结构，为其中每一行队列都定义了一个初始空间QUEUE_INIT_SIZE，并且为每个单队列设置其存储空间增量QUEUE_INCREMENT，同时将所有单循环队列存放在表f[N]中统一管理，组成动态循环多队列结构。其结构定义如下: # define QUEUE_INIT_SIZE 5 //队列存储空间的初始分配量 # define QUEUE_INCREMENT 3 //队列存储空间的分配增量 # define QUEUE_FREESIZE 10 //队列存储空间的回收预定值 # define PERCENT 0.5 //队列闲置空间的回收预定比例 # define N 4 //循环多队列内单队列的个数 typedef struct { ElemType *Q
int QueueS } typedef struct
- 4 -兰州城市学院毕业设计(论文) { fnode f[N]; /*用来指示N个队列的队头与队尾*/ }MultyQ 其中N表示该循环多队列内单队列的个数，front表示第i个队列的队头指针，rear，表示第i个队列的队尾指针，QueueSize表示第i个队列的容量。若将N赋值为4QUEUE_INIT_SIZE和QUEUE_INCREMENT分别赋值为5和3，则定义的循环多队列结构如图2.10所示。 f[N]
front rear QueueSize Queue 0 1 2 3 4 5 6 7 f[0] 3 1 5 13 11 12 f[1] 0 7 8 21 22 23 24 25 26 27 f[2] 5 2 8 34 35 31 32 33 f[3] 0 5 0 (1) 初始化 图1.2 动态多队列示意图 int InitQueue(MultyQueue *Q) { for(i=0;i<N;i++) { Q->f[i].Queue =(ElemType *)malloc(QUEUE_INIT_SIZE*sizeof(ElemType)); if(!Q->f[i].Queue) //内存分配失败 return ERROR; Q->f[i].QueueSize=QUEUE_INIT_SIZE;
Q->f[i].front=Q->f[i].rear=0; } return OK; } (2) 入队 在传统的循环多队列顺序存储下的入队操作中，若将要被入队的第i号队列已满，则返回错误消息。在循环多队列的动态存储结构下没有这种情况的发生，因为其中的每一行单队列都能够在此队已满时自动扩充其存储空间。若将要被入队的第i号队列已满，只需要通过C语言提供的realloc函数令其容量增加QUEUE_INCREMENT个单元。若扩充空间成功，则需要判断第i号队列的队头指针Q->f[i-1].front与其队尾指针Q->f[i-1].rear的相对位置:若Q->f[i-1].front>Q->f[i-1].rear，则先令Q->f[i-1].front开始到S->f[i-1].QueueSize结束的cnt个数据元素移向Q->f[i-1].QueueSize+QUEUE_INCREMENT-cnt-1到Q->f[i-1].QueueSize+ - 5 -兰州城市学院毕业设计(论文) QUEUE_INCREMENT-1的位置，然后再修改Q->f[i-1].QueueSize为Q->f[i-1].QueueSize+QUEUE_INCREMENT，修改Q->f[i-1].front为Q->f[i-1].QueueSize-cnt，若Q->f[i-1].frontf[i-1].rear，则无需移动元素，只需修改Q->f[i-1].QueueSize为Q->f[i-1].QueueSize+QUEUE_INCREMENT。 int EnterQueue(MultyQueue *Q,int i,ElemType e) { int j,k,
ElemType * if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ ->f[i-1].rear+1)%Q->f[i-1].QueueSize==Q->f[i-1].front) if((Q{ newbase=(ElemType*)realloc(Q->f[i-1].Queue,(Q->f[i-1].QueueSize +QUEUE_INCREMENT) *sizeof(ElemType)); if(!newbase) return ERROR; //内存分配失败，报告错误并退出程序 Q->f[i-1].Queue= if(Q->f[i-1].front>Q->f[i-1].rear) //必要时，需移动部分元素 { for(j=Q->f[i-1].QueueSize-1,k=Q->f[i-1].QueueSize+QUEUE_INCREMENT-1;j>=Q->f[i-1].j--,k--) Q->f[i-1].Queue[k]=Q->f[i-1].Queue[j]; cnt=Q->f[i-1].QueueSize-Q->f[i-1]. Q->f[i-1].QueueSize=Q->f[i-1].QueueSize+QUEUE_INCREMENT; //修改存储空间 Q->f[i-1].front=Q->f[i-1].QueueSize- } else Q->f[i-1].QueueSize+=QUEUE_INCREMENT; //无需移动元素时，直接修改存储空间 } Q->f[i-1].Queue[Q->f[i-1].rear]=e; Q->f[i-1].rear=(Q->f[i-1].rear+1)%Q->f[i-1].QueueS return OK; } (3) 出队
- 6 -兰州城市学院毕业设计(论文) 与队满时的空间动态扩充相应地，当第i号队列内空间过剩时也可以对其进行自动回收。需要在每次有元素出队后判断此号队列内的闲置空间是否达到定值QUEUE_FREESIZE。若达到，则需要按一定比例PERCENT回收部分闲置空间。 例如，容量Q->f[i-1].QueueSize=18的第i号队列中已存储有9个数据元素。若规定闲置空间QUEUE_FREESIZE达到10时按PERCENT=50%的比例回收部分闲置空间，回收个数hsgs=QUEUE_FREESIZE*PERCENT。则，当删除了第9个元素之后，QUEUE_FREESIZE达到了10，这时便需要回收。在回收时队列的头尾指针可能出现以下三种情形: 情形1、队头指针Q->f[i-1].front在前，而队尾指针Q->f[i-1].rear在后，且队头指针指向第i号队列首位置，如图1.3(a)。此时，第i号队列的闲置空间都在队列尾元素之后，可直接回收空间。 回收后的第i号队列如图1.3(b)所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
11 22 33 44 55 66 77 88
front rear (a)
0 1 2 3 4 5 6 7 8 9 10 11 12
11 22 33 44 55 66 77 88
front rear
(b) 图1.3 情形2、队头指针在前，队尾指针在后，且此队列头元素Q->f[i-1].Queue[Q->f[i-1].front]不在队列的首位置上，如图1.4(a)。此时，第i号队列的闲置空间一部分在队列头元素之前，另一部分在队列尾元素之后。需要判断队尾元素后的部分闲置空间Q->f[i-1].QueueSize-(Q->f[i-1].rear+1)是否达到QUEUE_FREESIZE*PERCENT。若达到，直接回收队尾元素后大小为QUEUE_FREESIZE*PERCENT的那部分空间，回收后如图1.4(b);若未达到，则移动第i号队列中所有元素，使队列头元素位于该存储空间的首位置上，且闲置空间都在队列尾元素之后，此时如情形1。然后按情形1进行空间回收，回收后亦如图1.4(b)。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 - 7 -兰州城市学院毕业设计(论文) 11 22 33 44 55 66 77 88
front rear
(a) 0 1 2 3 4 5 6 7 8 9 10 11 12 11 22 33 44 55 66 77 88
front rear
(b) 图1.4 情形3、队头指针在后，而队尾指针在前，如图1.5(a)。此时需要把从Q->f[i-1].front开始到Q->f[i-1].QueueSize结束的cnt个元素移向Q->f[i-1].QueueSize-hsgs-cnt到Q->f[i-1].QueueSize-hsgs，再修改Q->f[i-1].front的值为Q->f[i-1].QueueSize-hsgs-cnt，最后进行空间回收，回收了部分闲置空间后的第i号队列如图1.5(b)所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 11 22 33 44 55 66 77 88
rear front
(a) 0 1 2 3 4 5 6 7 8 9 10 11 12 11 22 33 44 55 66 77 88
rear front
int DeleteQueue(MultyQueue *Q,int i,ElemType *e) { int j,k, int LEN=QueueLength(Q,i); //求队列的长度 int hsgs=int(QUEUE_FREESIZE*PERCENT); //回收个数为限定值的50%
ElemType * if(iN) return ERROR; if(Q->f[i-1].front==Q->f[i-1].rear) return ERROR;
- 8 -兰州城市学院毕业设计(论文) *e=Q->f[i-1].Queue[Q->f[i-1].front]; Q->f[i-1].front=(Q->f[i-1].front+1)%Q->f[i-1].QueueS if(Q->f[i-1].QueueSize-LEN>=QUEUE_FREESIZE)//判断闲置空间是否达到定值 {
if(Q->f[i-1].front>Q->f[i-1].rear) //判断队头指针与队尾指针的相对位置
{ for(j=Q->f[i-1].QueueSize-hsgs-1,k=Q->f[i-1].QueueSize-1; k>=Q->f[i-1].j--,k--)
Q->f[i-1].Queue[j]=Q->f[i-1].Queue[k]; //移动Q->front开始到Q->QueueSize结束的cnt个元素 cnt=Q->f[i-1].QueueSize-Q->f[i-1]. Q->f[i-1].front=Q->f[i-1].QueueSize-hsgs-//修改队头指针 } else if(Q->f[i-1].QueueSize-(Q->f[i-1].rear+1){ for(i=0,j=Q->f[i-1].jf[i-1].i++,j++) Q->f[i-1].Queue[i]=Q->f[i-1].Queue[j]; Q->f[i-1].front=0; Q->f[i-1].rear=Q->f[i-1].front+LEN; } newbase=(ElemType*)realloc(Q->f[i-1].Queue,(Q->f[i-1].QueueSize-hsgs)* sizeof(ElemType)); if(!newbase) //内存分配失败，报告错误并退出程序 return ERROR;
Q->f[i-1].Queue= Q->f[i-1].QueueSize-= } printf("此队列的容量Q->f[i-1].QueueSize=%d\n",Q->f[i-1].QueueSize); return OK; } - 9 -兰州城市学院毕业设计(论文) 1.3队列的应用 例1.1 求迷宫的最短路径:现要求设计一个算法找一条从迷宫入口到出口的最短路径。 )出发，本算法要求找一条迷宫的最短路径，算法的基本思想为:从迷宫入口点(1,1向四周搜索，记下所有一步能到达的坐标点;然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径。 有关迷宫的数据结构、试探方向、如何防止重复到达某点以避免发生死循环的问题与例1.2处理相同，不同的是:如何存储搜索路径。在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点先向下搜索，故引进一个“先进先出”数据结构------队列来保存已到达的坐标点。到达迷宫的出口点(m,n)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此，用一个结构数组sq[num]作为队列的存储空间，因为迷宫中每个点至多被访问一次，所以num至多等于m*n。sq的每一个结构有三个域:x,y和pre，其中x,y分别为所到达的点的坐标，pre为前驱点在sq中的坐标，是一个静态链域。除sq外，还有队头、队尾指针:front和rear用来指向队头和队尾元素。 队的定义如下: typedef struct
{ int x,y;
} sqtype sq[num]; int front, 初始状态，队列中只有一个元素sq[,]记录的是入口点的坐标(,,,)，因为该点是出发点，因此没有前驱点，pre域为,,，队头指针front和队尾指针rear均指向它，此后搜索时都是以front所指点为搜索的出发点，当搜索到一个可到达点时，即将该点的坐标及front所指点的位置入队，不但记下了到达点的坐标，还记下了它的前驱点。front所指点的,个方向搜索完毕后，则出队，继续对下一点搜索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫最短路径，算法结束;或者当前队空即没有搜索点了，表明没有路径算法也结束。 算法如下: void path(maze，move)
- 10 -兰州城市学院毕业设计(论文)
int maze[m][n];/*迷宫数组*/
item move[8];/*坐标增量数组*/ { sqtype sq[NUM];
int front,
int x,y,i,j,v;
front=rear=0; sq[,].x=1; sq[,].y=1; sq[,].pre=-1; /*入口点入队*/ maze[1,1]=-1;
while (front<=rear) /*队列不空*/ { x=sq[front]. y=sq[front ].
for (v=0;v<8;v++)
{ i=x+move[v].x; j=x+move[v].y;
if (maze[i][j]==0)
sq[rear].x=i; sq[rear].y=j; sq[rear].pre=
maze[i][j]=-1;
if (i==m&&j==n)
{ printpath(sq,rear); /*打印迷宫*/
restore(maze); /*恢复迷宫*/
} /*for v*/
front++; /*当前点搜索完，取下一个点搜索 */
} /*while*/ return 0; } /*path*/ void printpath(sqtype sq[],int rear) /*打印迷宫路径*/
do { printf(: (%d,%d),:,sq[i].x , sq[i].y) ;
i=sq[i]. /*回溯*/
} while (i!=-1); } /*printpath*/ 对于图1.6(a)所示的迷宫搜索过程如图和队列中的数据如图1.6(a)、(b)所示。 - 11 -兰州城市学院毕业设计(论文)
入口 1 2 3 4 5 6 7 8 1 0 1 1 1 0 1 1 1 2 1 0 1 0 1 , 1 , 3 0 1 0 0 , , , 1 4 0 1 1 1 0 , 1 1 5 1 0 0 1 1 0 0 0 6 0 1 1 0 0 1 1 0 (a) 用二维数组表示的迷宫 出口
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,, x 1 2 3 3 3 2 4 4 1 5 4 5 2 5 6 5 6 6 5 6 y 1 2 3 1 4 4 1 5 5 2 6 6 6 3 1 7 5 4 8 8 10 11 13 15 15 pr-0 1 1 2 2 3 4 5 6 7 7 8 9 9 e 1 (b)队列中的数据
图1.6 迷宫搜索过程
运行结果: (6,8), (5,7), (4,6),(4,5), (3,4), (3,3), (2,2),(1,1) 在上面的例子中，不能采用循环队列，因为在本问题中，队列中保存了探索到的路径序列，如果用循环队列，则把先前得到的路径序列覆盖掉。而在有些问题中，如持续运行的实时监控系统中，监控系统源源不断的收到监控对象顺序发来的信息如报警，为了保持报警信息的顺序性，就要按顺序一一保存，而这些信息是无穷多个，不可能全部同时驻留内存，可根据实际问题，设计一个适当大的向量空间，用作循环队列，最初收到的报警信息一一入队，当队满之后，又有新的报警到来到时，新的报警则覆盖掉了旧的报警，内存中始终保持当前最新的若干条报警，以便满足快速查询。
- 12 -兰州城市学院毕业设计(论文) 结 论 经过三个月的设计和开发，对队列的深入研究及应用统基本完成。针对在设计过程中遇到的问题，做了及时调整，实现了队列的基本功能，包括队列的初始化、判空、出队、入队等，以及多队列技术中的循环队列和动态循环多队列技术的初始化、入队及出队操作的实现，队列在迷宫最短路径中的应用。这次毕业设计，个人在程序的设计和编码方面的能力有了一个很大的提高，从以往书本上的理论知识运用到了实践当中，又从实践当中回归到了书本中。在这其中学到了很多东西:首先对基本的概念进行掌握，有了初步的理解，并在深入了解的基础上有了大体的知识框架。然后是程序设计的能力，从开始实现队列功能的基本操作，到多队列技术的实现，让我在编码时知道了入队、出队功能具体实现，在反复思考中明白怎么来写代码才能更规范，更能符合数据结构的思想。队列的迷宫最短问题的应用处理让我知道了还存在那些漏洞，在设计和编码时出了那些问题，忽略了那些问题，怎么设计程序更能使程序运行流畅。 通过这次的深入学习，让我深深体会到数据结构C语言的魅力。首先要摆正心态，不要怕困难，静下心来去思考，去攻关。编程的过程就是不断学习的过程，遇到了问题去解决，解决了就学到了东西。百折不挠，必能提高自己。在设计过程中我们相互讨论、相互弥补不足，这样不仅增强了我们的个人能力，而且使我们认识到团队精神的重要性,为我们以后进入公司工作培养这种精神打下良好的基础。
。 - 13 -兰州城市学院毕业设计(论文) 致 谢 毕业设计已接近了尾声，通三个月的努力终于完成了队列的深入研究以应用。在此过程中遇到了很多的困难，是老师和同学们一块探讨学习帮我克服了困难。才使得我毕业设计顺利完成，在这里我向在毕业设计中帮助过我的老师和同学们表示深深的感谢。 本次毕业设计是在老师朱正平的悉心指导和严格要求下业已完成的，从选题到具体系统实现，再到论文修改无不凝聚着老师的心血和汗水，在我的毕业设计期间，朱正平老师为我提供了种种专业知识上的指导和一些富于创造性的建议。朱老师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，严以律己、宽以待人的崇高风范，使我感受到他朴实无华、平易近人的人格魅力。他是我日后学习、工作与生活中的最好的榜样～在此向朱正平老师表示深深的感谢和崇高的敬意～ 感谢所有教过的或没教过我们的全学院的老师，因为你们课堂上的指导和课外的交流，我们才可以学习到很多知识和做人的道理，为今后的人生做准备。 四年时间，不知不觉就要过去了。在此，我衷心感谢四年来辛勤培育我们的老师。在以后的工作岗位上，我也会不断努力，用自己的辛勤工作和不懈奋斗来回报母校和老师们～
- 14 -兰州城市学院毕业设计(论文) 参 考 文 献 [1] 严蔚敏，吴伟民. 数据结构(C语言版).北京:清华大学出版社,1997 [2] Robert L.Kruse,Alexander J.Ryba.Data Structures and Program Design in C++[M].Pearson Education,USA,2001.5 [3] 王晓东.计算机算法设计与分析(第二版)[M]. 北京:电子工业出版社,2005. [4] 李国东等. 通过单向队列自动机对适应性移动计算系统中组合事件的分析(英文)[J].软件学报,): [5]薛华成.管理信息系统.北京:清华大学出版社,1993. [6] 李春葆. 数据结构教程(第二版)[M]. 北京:清华大学出版社,2007 [7] (美)Adam Drozdek.数据结构与算法——C++版[M].北京:清华大学出版社,2006 [8] 王琪玮等.循环队列在实时数据系统处理中的应用[J]华北科技学院学报.):52-53 [9] 龚舒群,任煜等.循环队列中的头尾指针设计[J].现代计算机,):17-20 [10] 梁西陈.关于《数据结构》课程中顺序栈的结构图示的思考.宿州教育学院学报,):100-101- 15 -兰州城市学院毕业设计(论文) 附录A 循环多队列的顺序存储和算法实现
循环多队列的顺序存储和算法实现 任志国～李亚楠～张龙忠～赵莉来 信息工程学院,甘肃 兰州 730070, ,兰州城市学院 摘要:队列是一种重要的数据结构～队列在各种类型的系统中应用广泛～队列技术被广泛应用于编译软件和程序设计中。讨论队列的结构特征与操作实现特点～有着重要的意义。经常讨论的是循环队列或单队列等传统的队列。但在实际应用中经常会遇到循环多队列存储结构～在数据结构与算法中没有研究该内容～在此研究并实现了循环多队列的存储结构。并用这种结构解决了一些实际的问题。 关键词:循环多队列 顺序存储 存储结构 算法实现 中图分类号:TP311.12 1引言: 队列是一种重要的数据结构，队列技术被广泛应用于编译软件和程序设计中。讨论队列的结构特征与操作实现特点，有着重要的意义。经常讨论的是循环单队列这种传统的队列。但在实际应用中经常会遇到循环多队列存储结构，在数据结构与算法中没有研究该内容，本文研究并实现了循环多队列的存储结构。 2 循环单队列的顺序存储 循环队列是队列的一种顺序表示和实现方法。与顺序栈类似，在队列的顺序存储结构中，可以用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组Queue[MAXSIZE]。此外，由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front 和rear，分别指示队头元素和队尾元素在数组中的位置。 循环队列的类型定义: #define MAXSIZE 50 /*队列的最大长度*/ typedef struct { QueueElementType element[MAXSIZE]; /*队列的元素空间*/
int front, /*队头和队尾指针*/ }SeqQ 3 循环多队列的顺序存储
循环多队列的顺序存储结构的定义方式如下: typedef struct { int front,
- 16 -兰州城市学院毕业设计(论文) } // 每一个队列需要一个对头和一个队尾指针 typedef struct { ElemType queue[N][M]; /*循环多队列的存储空间, ElemType为数据元素的类型*/ fnode f[N]; /*用来指示N个队列的队头与队尾*/ }MultyQ f[i].front为第i个循环队列的队头指针，f[i].rear为第i个循环队列的队尾指针，queue[N][M]为循环多队列的存储空间。将N赋值为4，M赋值为5，则定义的循环多队列结构如下: f[N] queue[N][M ] front rear 0 1 2 3 4 0 0 0 3 11 12 13 1 1 22 3 1 23 21 2 2 0 4 31 32 33 34 3 3 1 3 41 42
4 循环多队列顺序存储结构下基本操作的实现
在单队列中，不管是用链式存储结构还是用顺序存储结构其实现都很简单。因为在单队列中只有一个队头和一个队尾，而在多队列中，由于存在多个队列，同时也有多个指针来指示每个队列队头和队尾的位置。故抽象数据类型多队列的基本操作中需要增加一个参数i来指定对哪个队列进行操作。 4.1 循环多队列的初始化和入队算法 对于该循环多队列的初始化就是将循环多队列的队头指针和队尾指针都赋0，即将数组f[i].front和f[i].rear的值都赋为0。则该操作可用算法描述为: Status InitQueue(MultyQueue *Q) { for(i=0;i<N;i++)
Q->f[i-1].front=Q->f[i-1].rear=0;
return OK; } 入队操作Status EnQueue(MultyQueue *Q,int i,ElemType e)，要求在循环多队列Q的第i个队列的队尾放入元素e。其操作过程为:首先将数据元素放在二维数组中，即在queue[i-1][f[i-1].rear]中放入要入队的元素;然后重置f[i-1].rear的位置，即进行操作- 17 -兰州城市学院毕业设计(论文) Q->f[i-1].rear=(Q->f[i-1].rear+1)%M;最后返回入队成功与否的状态。那么该算法可描述为: Status EnQueue(MultyQueue *Q,int i,ElemType e) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ if((Q->f[i-1].rear+1)%M= =Q->f[i-1].front) return OVERFLOW; /*第i个队列已满*/ Q->queue[i-1][Q->f[i-1].rear]=e; Q->f[i-1].rear=(Q->f[i-1].rear+1)%M; return OK; } 4.2循环多队列的出队算法
出队操作Status DeQueue(MultyQueue *Q,int i,ElemType *e),要求将循环多队列Q的第i个队列中队头的元素删除，元素的数值由e带出。其操作过程为:首先将队头位置元素的数值由e带出，即进行*e=Q->queue[i-1][Q->f[i-1].front]操作;然后重置队头的位置，即进行Q->f[i-1].front=(Q->f[i-1].front+1)%M操作;最后返回出队成功与否的状态。那么该算法可描述为: Status DeQueue(MultyQueue *Q,int i,ElemType *e) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ if(Q->f[i-1].front= =Q->f[i-1].rear) return OVERFLOW; /*第i个队列已满*/
*e=Q->queue[i-1][Q->f[i-1].front];
Q->f[i-1].front=(Q->f[i-1].front+1)%M;
return OK; } 4.3循环多队列的判断空和满算法
判空操作int EmptyQueue(MultyQueue *Q,int i)，要求判断循环多队列Q的第i个队列的存储空间是否未被使用。其操作过程为:判断循环多队列Q的第i个队列的是否没有放入元素，并返回队列是否为空的状态。那么该算法可描述为: int EmptyQueue(MultyQueue *Q,int i) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/
if(Q->f[i-1].front= =Q->f[i-1].rear)
return 0; }
- 18 -兰州城市学院毕业设计(论文) 判满操作int FullQueue(MultyQueue *Q,int i)，要求判断循环多队列Q的第i个队列是否已没有存储空间来存放其他元素。其操作过程为:判断循环多队列Q的第i个队列的是否已存满，并返回队列是否为满的状态。那么该算法可描述为: int FullQueue(MultyQueue *Q,int i) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ if((Q->f[i-1].rear+1)%M= =Q->f[i-1].front)
return 1; else
return 0; } 4.6循环多队列的求队长和清空算法
求长度操作int LengthQueue(MultyQueue *Q,int i)，要求求出循环多队列Q的第i个队列中存放的数据元素的数量。其操作过程为:返回队列中存放的数据元素的数量，即返回(Q->f[i-1].rear-Q->f[i-1].front+M)%M的值。那么该算法可描述为: int LengthQueue(MultyQueue *Q,int i) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/
return((Q->f[i-1].rear-Q->f[i-1].front+M)%M); } 清空操作int ClearQueue(MultyQueue *Q,int i)，要求将循环多队列Q中存放的元素全部删除。其操作过程为:将循环多队列的队头指针和队尾指针都赋0，即进行Q->f[i-1].front=Q->f[i-1].rear=0操作。则该操作可用算法描述为: int ClearQueue(MultyQueue *Q) { if(iN) return ERROR; /*参数i不合适，没有编号为i的队列*/ else
Q->f[i-1].front=Q->f[i-1].rear=0; } 5总结 循环多队列的顺序存储在定义时已经开辟了一定的空间，在存储时，若存储的数据量太小，则会造成存储空间的浪费;但若存储的数据量太大，会发生存储空间不够用的问题，又需要扩大存储空间。相比之下，链式存储的方法更优，其只在插入数据元素时开辟节点的空间，且先确定插入元素然后才开辟，另外，其在出队时立即将要删除元素所占用的空间释放。因此既不会浪费存储空间，也不会发生存储空间不足的问题。但是，- 19 -兰州城市学院毕业设计(论文) 若编程语言不提供指针类型，那么链式存储结构就不能实现。所以，对于使用VB等没有指针类型的开发工具的编程人员来说，循环多队列顺序存储结构的研究为其提供了理论依据，同时为应用系统的开发提供了一种新的实现技术。 参考文献: [1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997 [2] 龚舒群,任煜等.循环队列中的头尾指针设计[J].现代计算机,):17-20 [3] (美)Adam Drozdek.数据结构与算法——C++版[M].北京:清华大学出版社,2006 [4] 耿国华. 数据结构—C语言描述[M].北京:高等教育出版社,2005 [5] 王晓东.计算机算法设计与分析(第二版)[M]. 北京:电子工业出版社,2005 [6] 李春葆.数据结构教程(第二版)[M].北京:清华大学出版社,2007 Sequential Storage and Implementation of Circulating Multi-queue Ren Zhiguo, Li Ya’nan, Zhang Longzhong, Zhao Lilai (School of Information Science and Engineering ,Lanzhou City University, Lanzhou 730070,China) Abstract: Queue is an important kind of data structures. Queue is widely used in varieties of systems, especially in compiling softwares and designing programs. Discussing the architectural feature and implementation characteristics of queue is of great significance. What we usually discuss are traditional queues such as single-queue and circulating queue. But in practical application we will encounter circulating multi-queue which haven’t been discussed in data structures and algorithms. Here we discuss and implement storage structure of circulating multi-queue and at the same time solved some practical problems with it. Key Words: Circulating Multi-Sequential SStorage S Realization of Alogrithm
欢迎转载：
相关推荐：