2022年数据结构栈和队列的基本操作实现及其应用归纳 .pdf

《2022年数据结构栈和队列的基本操作实现及其应用归纳 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构栈和队列的基本操作实现及其应用归纳 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验 二栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。2、会用栈和队列解决简单的实际问题。二、实验内容（可任选或全做）题目一、试写一个算法，判断依次读入的一个以 为结束符的字符序列，是否为 回文。 所谓 “回文 “是 指正向 读和 反向读 都一 样的一 字符 串, 如“321123”或“ableelba ” 。相关常量及结构定义：# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType;

2、 / 栈类型定义typedef struct SqStack SElemType *base; SElemType *top; int stacksize; SqStack; 设计相关函数声明：判断函数： int IsReverse() 栈：int InitStack(SqStack &S ) int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s) 题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。 实现提示 ：参考教材循环

3、队列的有关算法，其中后两个算法参考顺序表的实现。题目三、Rails 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - Description There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds

4、were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the directio

5、n A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N = 1000 coaches numbered in increasing order 1, 2, ., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction

6、 B so that their order will be a1, a2, ., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on

7、 the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return b

8、ack to the station. Input The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation

9、of 1, 2, ., N. The last line of the block contains just 0. The last block consists of just one line containing 0. Output 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - The output contains the lines corresponding to the lines with permutati

10、ons in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the o

11、utput corresponding to the last null block of the input. Sample Input 5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0 Sample Output Yes No Yes 题目四、 Sliding Window Description An array of size n 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the

12、very right. You can only see the knumbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is 1 3 -1 -3 5 3 6 7, and k is 3. Window position Minimum value Maximum value 1 3 -1 -3 5 3 6 7 -13 1 3 -1 -3 5 3 6 7 -33 1 3 -1 -3 5 3 6 7 -35 1

13、 3 -1 -3 5 3 6 7 -35 1 3 -1 -3 5 3 6 7 36名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 1 3 -1 -3 5 3 6 737Your task is to determine the maximum and minimum values in the sliding window at each position. Input The input consists of two lin

14、es. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line. Output There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The

15、 second line gives the maximum values. Sample Input 8 3 1 3 -1 -3 5 3 6 7 Sample Output -1 -3 -3 -3 3 3 3 3 5 5 6 7 题目五 （选作 考查串知识）DNAEvolution 【Description】Evolution is a seemingly random process which works in a way which resembles certain approaches we use to get approximate solutions to hard comb

16、inatorial problems. You are now to do something completely different. Given a DNA string S from the alphabet A,C,G,T, find the minimal number of copy operations needed to create another string T. You may reverse the strings you copy, and copy both from S and the pieces of your partial T. You may put

17、 these pieces 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - together at any time. You may only copy contiguous parts of your partial T, and all copied strings must be used in your final T. Example: From S= “ ACTG ” create T = “GTACTAATAAT

18、”1.Get GT. by copying and reversing TG from S. 2.Get GTAC. by copying AC from S. 3.Get GTACTA. by copying TA from the partial T. 4.Get GTACTA AT by copying and reversing TA from the partial T. 5.Get GTACTAA TAAT by copying AA T from the partial T. 【Input】The first line of input gives a single intege

19、r, 1 k 10, the number of test cases. Then follow, for each test case, a line with the string S , length of S is less then 19, and a line with the string T , length of T is less then 19. 【Output 】Output for each test case the number of copy operations needed to create T from S, or impossible if it ca

20、nnot be done. 【Sample Input 】4 ACGT TGCA A C ACGT TCGATCGA A AAAAAAAAAAAAAAAAAA 【Sample output 】1 impossible 4 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 题目六 （选作 考查数组知识）Magic Squares 描述Following the success of the magic cube, Mr. Rub

21、ik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares: 1 2 3 4 8 7 6 5 In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence o

22、f colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration. Three basic transformations, identified

23、by the letters A, B and C, can be applied to a sheet: A: exchange the top and bottom row, B: single right circular shifting of the rectangle, C: single clockwise rotation of the middle four squares. Below is a demonstration of applying the transformations to the initial squares given above: A:8 7 6

24、5 1 2 3 4 B:4 1 2 3 5 8 7 6 C:1 7 2 4 8 6 3 5 All possible configurations are available using the three basic transformations. You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration. 输入名师

25、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - A single line with eight space-separated integers (a permutation of (1.8) that are the target configuration. 输出Line 1: A single integer that is the length of the shortest transformation sequence

26、. Line 2: The lexically earliest string of transformations expressed as a string of characters, 60 per line except possibly the last line. 样例输入2 6 8 4 5 7 3 1 样例输出7 BCABCCB 三、实验步骤、数据结构与核心算法的设计描述、函数调用及主函数设计（ 可用函数的调用关系图说明） 程序调试及运行结果分析 实验总结四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单（程序过长，可附主要部分）/ int IsReverse()

27、. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - while( (e=getchar()!=) e 依次入栈、入队 /push(S,e);EnQueue(Q,e); . While(!StackEmpty(S) pop(S,a);DeQueue(Q,b); If(a!=b) return 0; return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -